主题:[原创]解金山公司面试题
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个回复)
71 楼
moz [专家分:37620] 发布于 2007-03-17 15:26:00
哦,是我把问题复杂化了, 我以为1000个苹果不用放完 呢,那好办,改一下就可以了
if i=1 then
sum3=1
这样子一改,答案就跟你们的一样了.
72 楼
7zeal [专家分:370] 发布于 2007-03-17 21:42:00
[quote]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[/quote]
呵呵,请问用的函数多项试相乘吗??
73 楼
goal00001111 [专家分:4030] 发布于 2007-03-20 15:45:00
转化成分解整数问题
#include<iostream>
using namespace std;
int Fun(int max, int n, int num);
int main()
{
int max = 200;//苹果数量
int n = 10;//箱子数量
int sum = Fun(max, n, 1);
cout << "sum = " << sum << endl;
system("pause");
return 0;
}
int Fun(int max, int n, int num)
{
if (n == 2)
return max/2 - num + 1;//保证不小于前面的数
int sum = 0;
for (int i=num; i<=max/n; i++)
sum += Fun(max-i, n-1, i);
return sum;
}
74 楼
xuxiangtian [专家分:0] 发布于 2007-03-21 20:55:00
的确有重复的,但是容易知道每个重复的次数应该是10的阶乘次,因为每十个数可以做一个排列,除全是100外.所以可以对上面的sum如下运算:
(sum-1)/10!+1则为所有的种数.不知道对否.自己感觉没有问题,请指教!
75 楼
xuxiangtian [专家分:0] 发布于 2007-03-21 20:56:00
[quote]穷举可以, 但问题在于你怎么使穷举情况没有重复. :)[/quote]
的确有重复的,但是容易知道每个重复的次数应该是10的阶乘次,因为每十个数可以做一个排列,除全是100外.所以可以对上面的sum如下运算:
(sum-1)/10!+1则为所有的种数.不知道对否.自己感觉没有问题,请指教!
76 楼
hoan [专家分:0] 发布于 2007-03-22 14:17:00
此题不是要你算出990!的值多少,而是看你的算法设计,算法的时间度!
77 楼
henanlsl [专家分:10] 发布于 2007-03-23 02:03:00
这更是一道数学题
是组合,999!/9!/(999-9)!
78 楼
hadewood [专家分:60] 发布于 2007-03-25 16:12:00
9楼的方法好像不对,要注意10个箱子是一样的。
79 楼
568892558 [专家分:0] 发布于 2007-03-29 16:19:00
新手上路,每太看懂,可以讲解以下算法吗?多谢!!!!
80 楼
zbhddt6 [专家分:490] 发布于 2007-03-30 09:17:00
9楼兄弟 排阶层做什么 这不是排队或者做位子的问题
假如有13个苹果 那么有三个方法
1: 9个1和1个4(m个n代表有m个箱子放n个苹果)
2: 8个1和1个2和1个3
3: 7个1和3个2
注意箱子和苹果是一样的!
教你一招叫插花法:1000个苹果横排起来有999个空当,在这个999个空当里边选出9个空当把苹果分为10份,每份放入一个箱子里边。c(999,9)这个数等于把箱子编上号码计算出来的数目。所以要比这个数要小,但是又会比c(999,9)/10!大
所以范围可以确定在比c(999,9)/10!--比c(999,9)
所以9楼的兄弟错了
我来回复