主题:[原创]解金山公司面试题
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个回复)
91 楼
雨中飞燕 [专家分:18980] 发布于 2007-04-05 12:20:00
[quote]满无奈的,很多人回帖不看贴的吗,前面已经讨论的很清楚了,为何还自以为高明的随便甩个答案上来[color=FF0000]甚至连简单的2个苹果2个桶也不去验证一下[/color]呢?
为了显示自己有多高明吗?真愚蠢[/quote]
顶啊
92 楼
xinxinjob [专家分:0] 发布于 2007-04-05 15:33:00
都是高手!!!!!!!
93 楼
vcacm [专家分:1500] 发布于 2007-04-06 21:24:00
高精度运算,我可以在10妙之内求得结果(这是指一般地PC )
在我们学校的服务器上运行只需0.9999妙!!!!!!!!!!!!!!
要答案的;
E-mail to : v_acm @hotmail.com
94 楼
雨中飞燕 [专家分:18980] 发布于 2007-04-06 21:33:00
楼上的真无聊
95 楼
vcacm [专家分:1500] 发布于 2007-04-06 21:40:00
[quote]楼上的真无聊[/quote]
crazy !
96 楼
快乐祥子 [专家分:0] 发布于 2007-04-09 15:16:00
是啊,这其实就是一个排列问题
97 楼
niuyuelei [专家分:90] 发布于 2007-04-14 00:41:00
见过张靓影哦![em1]
98 楼
leon916 [专家分:60] 发布于 2007-04-21 13:08:00
intotherain112
每个箱子至少放一个萍果。
共10个箱子 需 10个苹果
剩下990个苹果 进行全排列
共有990!种排法
990的阶乘是多少? 有必要算出来吗?
修改intotherain112的方法:剩下990个苹果 进行全排列不是进行全排。而是用10的990次方。
是公式我想应该是:C(1000,10)*(10的990次方)
99 楼
eubel [专家分:0] 发布于 2007-04-22 08:43:00
晕,这个也不知道.
大家怎么学习的?
解题思路:从1000个苹果中任拿10个出来放入10个箱中,共有c(1000,10)中方法,剩下的990个随便放都满足条件了,共有10^990种.
所以总的方法数为:c(1000,10)*10^990.
100 楼
rickone [专家分:15390] 发布于 2007-04-23 13:07:00
100楼,打止吧,楼主可以称得上热帖之王了,我觉得你应该去做网站,你可以把它做得很火,呵,开玩笑。
可能金山公司出题的人不是这么想的,不同的人理解也不同,可能对和错都不是面视时最重要的,思路啊,理解的基础上理好思路,建好数学模型,寻找解决方案,如果真是组合数不要说写个C(xxx)就说解出来了,数值的解或者精确的解,输入到输出花的时间,可以忍受的时间很多都要考虑。好了好了,这帖可以结了,打住。
我来回复