主题:[原创]解金山公司面试题
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个回复)
31 楼
7zeal [专家分:370] 发布于 2007-03-14 22:48:00
师傅帮忙看看~~偶的程序快不?
[color=FF0000]不好意思~~~这个是INT型的只算100以下的,
偶又改了个可以算1000的,超级快的~~~欢迎到65楼参观[/color]
#include <stdio.h>
#include <string.h>
#include <iostream.h>
const int max = 101;//苹果最大数~~
int xinum[max],jimun[max],applen,boxn;
int main()
{
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 < applen+1)
{
for(ii = 0 ; ii + zhishu < applen+1 ; ii++) jimun[ii+zhishu] += xinum[ii];
zhishu += k;
}
memcpy(xinum,jimun,max * sizeof(int));
memset(jimun,0,sizeof(jimun));
k++;
}
printf("%d\n",xinum[applen]);
return 0;
}
32 楼
雨中飞燕 [专家分:18980] 发布于 2007-03-14 23:32:00
偶这个数学白痴实在不应该做这个。。。
33 楼
loveling [专家分:0] 发布于 2007-03-15 12:02:00
应该是10的990次方
34 楼
雨中飞燕 [专家分:18980] 发布于 2007-03-15 12:19:00
楼上的看清楚题目
35 楼
CanBone [专家分:0] 发布于 2007-03-15 13:28:00
[quote][quote]每个箱子至少放一个萍果。
共10个箱子 需 10个苹果
剩下990个苹果 进行全排列
共有990!种排法
990的阶乘是多少? 有必要算出来吗?[/quote]
不是全排列!
不允许存在空盒,则先在每个盒子里放1个苹果。
问题就变成了 剩下990个向10个盒子里放。
这个过程 相当于把990用 {1,2,3...10}进行拆分(可参见 组合数学 的书籍)。
所以问题变成了整数拆分的个数 ,你可以参看整数拆分的程序。
[/quote]
也并非是整数拆分的个数,
而是把1000拆分成10个数的方法.
其实这样的方法并不多
36 楼
CanBone [专家分:0] 发布于 2007-03-15 13:31:00
答案绝对不会超过1W的
楼主再好好思考一下
下午有课,我写了一个程序,但是还有一点小小的问题
晚上调写好再发上来
暂时数值是4500左右的
注意,题目所给的箱子是一样的,意思就是苹果放哪个箱子都一样,
最重要是把1000分解为10个自然数,其组成的数组ApplesInBoxes[10]是不同的.
37 楼
雨中飞燕 [专家分:18980] 发布于 2007-03-15 16:38:00
那楼上的程序一定有问题。。。。。。
38 楼
dump1984 [专家分:0] 发布于 2007-03-15 17:11:00
C(9,n-1)
39 楼
CanBone [专家分:0] 发布于 2007-03-15 19:45:00
[quote]那楼上的程序一定有问题。。。。。。[/quote]
上课时候想了一下...错了一步..[em17][em17][em17]
40 楼
if007 [专家分:650] 发布于 2007-03-15 19:54:00
有谁能说说这个公式的由来吗? :)
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);
我来回复