主题：[原创]解金山公司面试题
if007
[专家分：650] 发布于 2007-03-10 03:31:00
/*************************************
文件名: 解金山公司面试题
创建人: 陈泽丹
创建时间: 2007年3月10日
版本号: 0.5
*************************************/
/*-------------------------------------------
问题描述:
1000个苹果放在10个箱子里, 10个箱子一模一样且要
求每个箱子都放有苹果, 问共有多少种放法?
-------------------------------------------*/
/*========================================
很遗憾:
我试了150个苹果放10个箱子, 在我的机子上运行10几秒
后得出结果:75611815 也就是说7千万多种放法...
那1000个苹果呢?...不敢想象其数据...就算我的机
子能运行出来并且我想到更快速的算法解答, 但
我很担心一个问题:其结果会不会是一个天文数字? 会不会溢
出双精度的范围了...即是说能算出来,但还需使用技巧来表
示出这个数字这就加大了编程的麻烦性,而我现在没有太多的
时间可用.
所以对这题的解答先写到这吧, 很有遗憾!有时间我一定
会再来写这道题的!
===========================================*/
#include <iostream>
using namespace std;
int m;
int sum;
long y=0;
int* a;
int fun1(int x, int num, int left)
{
int i;
if (num >= m-1)
{
a[num]=left;
for (i=0; i<m; i++)
cout<<a[i]+1<<" ";
cout<<endl;
y++;
return 0;
}
int count=x;
while(1)
{
int nn=m-1-num;
if ((left-count)/nn >= count)
{
a[num]=count;
fun1(count, num+1, left-count);
count++;
}
else break;
}
return 0;
}
int main()
{
cout<<"请输入苹果数目: ";
cin>>sum;
cout<<"请输入箱子数: ";
cin>>m;
a=new int[m];
y=0;
fun1(0, 0, sum-m);
cout<<"放法总数目为:"<<y<<endl;
int bb;
cin>>bb;
}
最后更新于：2007-03-10 03:37:00
回复列表 （共102个回复）
61 楼
rickone [专家分：15390] 发布于 2007-03-16 20:58:00
给个链接
[url=http://www.programfan.com/club/showbbs.asp?id=220775]http://www.programfan.com/club/showbbs.asp?id=220775[/url]
我觉得那个公式也是正确的，但用那个公式不能递归（打表的递归也不行，栈不够深），我的那个公式是直接计算的，整数拆分效率是非常高的。
62 楼
ccpp [专家分：9360] 发布于 2007-03-16 21:01:00
[quote]// Apple.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
double f(int n,int m)
{
static double sf[1001][11]={0.0};
double result=0.0;
if(n<m)
return 0.0;
if(sf[n][m]>0.0)
return sf[n][m];
if(n==m)
{
result=1.0;
}
else
{
for(int i=1;i<=m;++i)
result+=f(n-m,i);
}
//printf("n=%d,m=%d,r=%d\n",n,m,result);
sf[n][m]=result;
return result;
}
int main(int argc, char* argv[])
{
int n,m;
scanf("%d%d",&n,&m);
printf("%lf\n",f(n,m));
return 0;
}
1000 10
886745696653253.000000
Press any key to continue[/quote]
那么结果是正确的啊，强啊！
63 楼
rickone [专家分：15390] 发布于 2007-03-16 21:09:00
我用另外一个公式也做了一下，结果相同：
// Apple.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
double f1(int n,int m)
{
static double sf[1001][1001]={0.0};
double result=0.0;
if(n<m)
return 0.0;
if(sf[n][m]>0.0)
return sf[n][m];
if(n==m)
{
result=1.0;
}
else
{
for(int i=1;i<=m;++i)
result+=f1(n-m,i);
}
//printf("n=%d,m=%d,r=%d\n",n,m,result);
sf[n][m]=result;
return result;
}
double f2(int n,int m)
{
static double sf[1001][1001]={0.0};
static bool init=true;
if(init)
{
init=false;
for(int i=0;i<=1000;++i)
{
sf[i][1]=1.0;
sf[1][i]=1.0;
sf[0][i]=1.0;
}
}
for(int j=2;j<=n;++j)
{
for(int k=2;k<=m;++k)
{
if(j<=k)
sf[j][k]=1.0+sf[j][j-1];
else
sf[j][k]=sf[j-k][k]+sf[j][k-1];
}
}
return sf[n][m];
}
int main(int argc, char* argv[])
{
int n,m;
scanf("%d%d",&n,&m);
printf("%lf\n",f1(n,m));
printf("%lf\n",f2(n-m,m));
return 0;
}
1000 10
886745696653253.000000
886745696653253.000000
Press any key to continue
64 楼
ccpp [专家分：9360] 发布于 2007-03-16 21:12:00
[quote]如果是整数拆分那计数就会少很多，设
整数n拆分成m份的全部拆分数为f(n,m)，有
f(n,m)=0 if(n<m)
f(n,n)=1
f(n,m)=f(n-m,m)+f(n-m,m-1)+...+f(n-m,1)[/quote]
把forjane 的代码中的 int 改成double,
那么和你的计算结果是一样的！
这是很有效整数拆分的解法。学到了！！
65 楼
7zeal [专家分：370] 发布于 2007-03-16 21:22:00
#include <stdio.h>
#include <windows.h>
#include <iostream.h>
const int max = 1010;//最大苹果数
double xinum[max],jimun[max];
int applen,boxn;
int main()
{
long startTime, endTime;
startTime = GetTickCount();
cout<<"start time: "<<startTime<<endl;
printf("请输入苹果的个数\n");
scanf("%d",&applen);
printf("请输入合子的个数\n");
scanf("%d",&boxn);
int ii,zhishu,k;
for(ii = 0 ; ii < applen+1 ; ii++) xinum[ii] = 1;
k = 2;
while(k <= boxn)
{
zhishu = 0;
if(k==boxn) {zhishu=boxn;}
while(zhishu < max)
{
for(ii = 0 ; ii + zhishu < max ; ii++) jimun[ii+zhishu] += xinum[ii];
zhishu += k;
}
memcpy(xinum,jimun,max * sizeof(double));
memset(jimun,0,sizeof(jimun));
k++;
}
printf("%lf\n",xinum[applen]);
endTime = GetTickCount();
cout<<"end time is:"<<endTime<<endl;
cout<<"your time is:"<<endTime-startTime<<endl;
return 0;
}
start time: 3194828
请输入苹果的个数
1000
请输入合子的个数
10
886745696653253.000000
end time is:3199265
your time is:3031
Press any key to continue...
hehe当你计算5000个苹果1000个盒子时,这个算法应该能体现它的优越性.
而且只开辟了2个苹果数的内存单元~~[em1]
66 楼
ttuurr [专家分：70] 发布于 2007-03-17 08:54:00
const int MAXN=1000;
const int MAXK=10;
typedef __int64 Type;
Type f[MAXN+1][MAXK+1];
int main() {
int n, k;
cin>>n>>k;
f[0][0]=1;
int j;
for(int i=1; i<=n; i++)
for(j=1; j<=k; j++)
if(i>=j)
f[i][j]=f[i-j][j]+f[i-1][j-1];
printf("总数为:%I64d\n",f[n][k]);
}
1000 10
886745696653253
67 楼
moz [专家分：37620] 发布于 2007-03-17 11:23:00
90645232075739600我算出来的东西跟所有上层做的结果完全不一样,
但我换成小一点的数得到的 结果是正确的,各位也可以换成小数看看,
呵呵,我还没搞清楚错误在 哪里:
Dim sum2(10, 1000)
Function sum1(i, j)
If sum2(i, j) > 0 Then
sum1 = sum2(i, j)
Else
If i = 1 Then
sum3 = j
Else
For k = j To 1 Step -i
sum3 = sum3 + sum1(i-1, (k))
Next
End If
sum2(i, j) = sum3
sum1 = sum3
End If
End Function
运算结果:debug.print sum1(10,991) = 90645232075739600 (10个纸箱,1000个苹果)
debug.print sum1(10,141) = 1291514647 (10个纸箱,150个苹果)
debug.print sum1(3,10-3+1) = 31 (3个纸箱, 10个苹果)
debug.print sum1(2,15-2+1) = 56 (2个纸箱, 15个苹果)
验证: 3个纸箱,10个苹果
(1-8),1,1 8种放法
(2-7),2,1 6种放法
(3-6),3,1 4种放法
(4-5),4,1 2种放法
(2-6),2,2 5种放法
(3-5),3,2 3种放法
(4-4),4,2 1种放法
(3-4),3,3 2种放法 总共31种不同的放法
2个纸箱15个苹果
(1-14),1 14种放法
(2-13),2 12种放法
(3-12),3 10种放法
..........................
(7-8),7 2种放法 至此为止是一个递减数列 (14+2)*7/2 = 56 种放法
68 楼
moz [专家分：37620] 发布于 2007-03-17 11:53:00
我剽窃了一下,改成C,不知道对没对.
#include "stdafx.h"
double f(int n,int m)
{
static double sf[1001][11]={0.0};
double result=0.0;
if(sf[n][m]>0.0)
return sf[n][m];
else
{
if(n==1)
return m;
else
{
for(int i=m;i>=1;i=-n)
result+=f(n-1,i);
}
}
sf[n][m]=result;
return result;
}
int main(int argc, char* argv[])
{
int n,m;
scanf("%d%d",&n,&m);
printf("%lf\n",f(n,m-n+1));
return 0;
}
69 楼
rickone [专家分：15390] 发布于 2007-03-17 12:03:00
debug.print sum1(2,15-5+1) = 56 (2个纸箱, 15个苹果)
这个结果显然是错的，15的拆分为2个数只有
1 14
2 13
3 12
...
7 8
7种
70 楼
lizi [专家分：60] 发布于 2007-03-17 13:25:00
先每个箱子放一个苹果
剩下990个,任意放如10个箱子,每个放之前有10种选择,理论上有 10^990 种放法
我来回复
您所在位置：