主题:[原创]解金山公司面试题
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个回复)
51 楼
rickone [专家分:15390] 发布于 2007-03-16 16:25:00
[quote]这个纯粹是个组合问题。我的解法如下,不知道有没有错
注:(题意有点不清楚,我的理解是每个苹果一样,每个箱子一样)
因为要求每个箱子至少要放一个苹果,所以先放10个苹果(每个箱子各放一个).剩下990个苹果。这990个苹果要分成10份,想象有9块隔板,将隔板插到苹果里面,就可以将苹果分成10份。
故苹果和隔板加起来作个全排列,有(990+9)!,不过苹果是没有区别的,隔板也是没有区别的,故将苹果分成10份的方法数有,999!/(9!*990!).
另外箱子也是一样的,故最后的结果为999!/(9!*990!*10!).
这个结果算出来会是725886134430032。
还有,如果我的思路是正确的,150个苹果放到10个箱子,会有149!/(9!*140!*10!),这个结果算出来是21486520。
我的前提是基于苹果都一样,箱子都一样。如果箱子不一样,或者苹果不一样。答案会有不同,思路应该一样。
[/quote]
这位朋友的解答有点接近学数学的思路,嘻~
何必要先选10个呢?直接插空就行了。
1000个苹果先编号1,2,...1000,哦,不考虑它们的编号,那就不用排列,排一种出来:1,2,...1000,先放在那里,摆好,从教一楼门口摆到教二楼门口。
现要把它分到10个筐里,那就是取9个插空,1000个苹果中间有多少个插空?999个,C(999,9)
编程的时候就只要一个计算组合数的算法了,用递推,估计这个结果会很大。
另外,这不是整数拆分。如果10个筐也去掉对称相同的情况,比如9个苹果分到2个筐里,分成的1,8和8,1;2,7和7,2都分别算一种情况,这才是整数拆分。
52 楼
if007 [专家分:650] 发布于 2007-03-16 17:11:00
这样组合的计算算多了...
举个例子 10个苹果编号后中间数与数之间有9个空,这9个空我也编号为1到9吧. 现在我只在这些空里插两个挡板.
现实意义就是用两个挡板插空把这些苹果分成三部份.
那么插1和5两个空的情况, 和插5和9的情况, 把苹果的分法是一样的. 但是计算插空的组合的时侯却把这两种分法结果一样插法看成是两种不同的组合了, 所以算多了.
53 楼
向人民学习 [专家分:0] 发布于 2007-03-16 17:43:00
[em10]
54 楼
ccpp [专家分:9360] 发布于 2007-03-16 18:16:00
[quote]
另外,这不是整数拆分。如果10个筐也去掉对称相同的情况,比如9个苹果分到2个筐里,分成的1,8和8,1;2,7和7,2都分别算一种情况,这才是整数拆分。[/quote]
是整数拆分,只不过效率很低。
在1000减去10后,剩990个无区别的苹果 放入 10个无区别的框中,
就变成了整数拆分。可参见《组合数学》卢开澄 卢华明
55 楼
向人民学习 [专家分:0] 发布于 2007-03-16 18:36:00
按数学的方法:
先举:5个苹果放俩个相同的箱子:分别给箱子编一号和二号
可先确定:一号放一 则二号有四种放法
一号放2个 则二号有3种放法
一号放3个 则二号有2种放法
一号放四个 则二号有一种放法
按这样 则总共有4+3+2+1=10种
下面接着分析 1000个苹果放到10个箱子种并且要求箱子都放有苹果
按这5个苹果放俩箱子的思路分析
10个箱子 给编写好号:
从第一到第十:
先假设前九个箱子只放一个苹果 则第十个为991种放法
为了更好的说明 我给列出 数组:
第一个箱子 二 三 四 五 六 七 八 九 十
1 1 1 1 1 1 1 1 1 991放法
1 1 1 1 1 1 1 1 2 990放法
1 1 1 1 1 1 1 1 3 989。。
1 1 1 1 1 1 1 1 4 988。。
1 1 1 1 1 1 1 1 5 987。。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
1 1 1 1 1 1 1 1 991 1。。
从上面的看 当然第十箱子可编给十个箱子的任何一个
第九个箱子可编写给十个种的任何一个
那么 总共方法 可推出:(991+990+。。。。1)这一组可安排在十个箱子的任何一个
按这样的话:
总共有(991+990+。。。。。。。1)*10种方法 不知道是否正确 不足地方 希望大家指导!
56 楼
rickone [专家分:15390] 发布于 2007-03-16 19:50:00
如果是整数拆分那计数就会少很多,设
整数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)
57 楼
rickone [专家分:15390] 发布于 2007-03-16 20:08:00
// 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
58 楼
xuxiangtian [专家分:0] 发布于 2007-03-16 20:40:00
刚看了c程序的三种基本结构,在此献丑一下:
认为改题用10个for循环,i=1到1000,因为题目的实质1----1000之间的任何10个数相加之和等于1000,在循环体里判断如果 a1+a2+.........+a10=1000则是一种分法,if(a1+a2+.........+a10=1000),sum=0,sum=sum+1;最后的sum值就是有多少中分法.
初学者请高手指教
59 楼
if007 [专家分:650] 发布于 2007-03-16 20:44:00
穷举可以, 但问题在于你怎么使穷举情况没有重复. :)
60 楼
7zeal [专家分:370] 发布于 2007-03-16 20:51:00
[quote]
是整数拆分,只不过效率很低。
在1000减去10后,剩990个无区别的苹果 放入 10个无区别的框中,
就变成了整数拆分。可参见《组合数学》卢开澄 卢华明
[/quote]
同意!!!用函数法比较快的
我来回复