主题:[原创]解金山公司面试题
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个回复)
沙发
if007 [专家分:650] 发布于 2007-03-10 03:36:00
实际上, 我这题并没解出来, 算法是有了, 但实现有问题...
把这题贴出来, 有兴趣的朋友可以试试, 如有更好的思路请赐教. :)
板凳
if007 [专家分:650] 发布于 2007-03-10 04:10:00
不甘心, 又试了下170个苹果放在10个箱子, 10几秒后出结果: 210,440,370
即是说2亿多种放法... 按这种数据规模增长趋势,那么1000个苹果?... ^-^!
金山的面试题啊...呵...
3 楼
forjane [专家分:5670] 发布于 2007-03-10 06:45:00
呵呵,假设c(x,n)为x个apple放入n个箱子的所有放法(没有至少一个的限制)
有这样的递推公式
c(x,1)=1;
c(x,n)=c(x,n-1)+c(x-n,n-1)+c(x-2*n,n-1)+...c(x-i*n,n-1)+...+c(x%n,n-1);
写成程序就是
#include <iostream>
using namespace std;
typedef int Type;
Type fun(int apple, int box)
{
Type *p,*q,*tmp;
int i,j,k;
Type result;
//本来我的fun(apple,box)是计算没有"至少放1个apple"限制的所有方法的
apple-=box; //加上这句fun函数的功能就等价于每个box至少放一个apple了
p=new Type[apple+1];
q=new Type[apple+1];
for(i=0;i<=apple;i++)
p[i]=1; //p[i]此时表示i个apple放1个box时的可能种类(没限制)
for(j=2;j<=box;j++) //box数j从2递增到box
{
for(i=0;i<=apple;i++) //计算i个apple放j个box时的可能种类,结果存放到q[i]
for(q[i]=0,k=i;k>=0;k-=j)
q[i]+=p[k];
tmp=p; //交换数组p,q
p=q;
q=tmp;
}
result=p[apple];
delete []p;
delete []q;
return result;
}
int main()
{
int sum,m;
cout<<"请输入苹果数目: ";
cin>>sum;
cout<<"请输入箱子数: ";
cin>>m;
cout<<"放法总数目为:"<<fun(sum,m)<<endl;
system("pause");
return 0;
}
4 楼
forjane [专家分:5670] 发布于 2007-03-10 06:49:00
上面的程序计算150个苹果只有毫秒级,因为运算都是加法所以算1000或者更大也很简单.
只要自己写一个长整数的类并且重载+和=以及<<运算符,然后替换我的typedef就可以了.
5 楼
renew [专家分:200] 发布于 2007-03-10 10:16:00
貌似还可以继续优化。。。
6 楼
believefym [专家分:1550] 发布于 2007-03-10 10:23:00
[em10]
7 楼
sarrow [专家分:35660] 发布于 2007-03-10 10:54:00
forjane,解得很棒!
(俺也想过,推导了一下公式,但没有去做——看来行动力太差了.........)
8 楼
intotherain112 [专家分:0] 发布于 2007-03-10 18:19:00
每个箱子至少放一个萍果。
共10个箱子 需 10个苹果
剩下990个苹果 进行全排列
共有990!种排法
990的阶乘是多少? 有必要算出来吗?
9 楼
ccpp [专家分:9360] 发布于 2007-03-10 19:37:00
[quote]每个箱子至少放一个萍果。
共10个箱子 需 10个苹果
剩下990个苹果 进行全排列
共有990!种排法
990的阶乘是多少? 有必要算出来吗?[/quote]
不是全排列!
不允许存在空盒,则先在每个盒子里放1个苹果。
问题就变成了 剩下990个向10个盒子里放。
这个过程 相当于把990用 {1,2,3...10}进行拆分(可参见 组合数学 的书籍)。
所以问题变成了整数拆分的个数 ,你可以参看整数拆分的程序。
10 楼
if007 [专家分:650] 发布于 2007-03-10 20:10:00
虽然我十分不喜欢张靓影, 但我对你的算法表示极度的喜欢和赞赏.
你的算法比我的快多了. :)
如果我没记错, 整数的划分好像也是用过这样的解题思路...
我来回复