主题:[原创]解金山公司面试题
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个回复)
81 楼
seasoftware [专家分:0] 发布于 2007-03-31 23:25:00
楼主 关于170个苹果 10 个箱子 的答案有误 我的答案337,012,699 我的程序
#include<iostream>
#define ma 100
using namespace std;
int n;
int m;
int w[ma];
long int count;
void f(int num,int max ,int k);
int main()
{
count=0;
cin>>n>>m;
for(int j=1;j<=m;j++)
w[j]=0;
f(n,n,1);
cout<<count;
return 0;
}
void f(int num,int max,int k)
{
if(num==0)
{
if(w[m])
{
//for(int j=1;j<=m;j++)
// cout<<w[j]<<" ";
//cout<<endl;
count++;
}
}
else
{
int q=num>max?max:num;
int p;
if(num%(m-k+1)==0)
p=num/(m-k+1);
else
p=num/(m-k+1)+1;
for(int i=q;i>=p;i--)
{
w[k]=i;
f(num-i,i,k+1);
}
}
}
将注释号 // 删除可输出 每一种分法 我认为我的没有错
如果我的真错了 请赐教 楼主
83 楼
seasoftware [专家分:0] 发布于 2007-03-31 23:33:00
sorry 是我的错了
84 楼
seasoftware [专家分:0] 发布于 2007-04-01 00:09:00
#include<iostream>
#define ma 100
using namespace std;
int n;
int m;
int w[ma];
long int count;
void f(int num,int max ,int k);
int main()
{
count=0;
cin>>n>>m;
for(int j=1;j<=m;j++)
w[j]=0;
f(n,n,1);
cout<<count;
return 0;
}
void f(int num,int max,int k)
{
int q=num>max?max:num;
q=q>num-m+k?num-m+k:q;
int p;
if(num%(m-k+1)==0)
p=num/(m-k+1);
else
p=num/(m-k+1)+1;
for(int i=q;i>=p;i--)
{
w[k]=i;
if(k==m)
{
//for(int j=1;j<=m;j++)
//cout<<w[j]<<" ";
//cout<<endl;
count++;
}
else
f(num-i,i,k+1);
}
}这个是对的 不过用的时间挺多的
85 楼
绿吗甲都不能用 [专家分:0] 发布于 2007-04-01 13:39:00
#include "stdio.h"
main()
{
long double num=1,i;
int n;
scanf("%d",&n);
for(i=1;i<=9;i++)
num=(n-10+i)/i*num;
printf("%.100g",num);
}
86 楼
lidemin [专家分:0] 发布于 2007-04-04 06:43:00
没学过组合数学,不过frojan 的算法确实不错啊。学习中。。。。。。
受益良多啊!
87 楼
LostHellX [专家分:0] 发布于 2007-04-04 22:29:00
其实这是一道很基础的高中题目来的 排列的~~
无需什么算法 直接就是可以写出答案
C(10,999)
88 楼
雨中飞燕 [专家分:18980] 发布于 2007-04-04 22:31:00
[quote]其实这是一道很基础的高中题目来的 排列的~~
无需什么算法 直接就是可以写出答案
C(10,999)[/quote]
楼上的。。。。。哎。。。。。。
不知道怎么说你了
89 楼
xpckk [专家分:40] 发布于 2007-04-05 00:16:00
如果箱子不同,就是求10的990次方~~
如果箱子相同,就是求10的989次方~~
90 楼
forjane [专家分:5670] 发布于 2007-04-05 00:51:00
满无奈的,很多人回帖不看贴的吗,前面已经讨论的很清楚了,为何还自以为高明的随便甩个答案上来[color=FF0000]甚至连简单的2个苹果2个桶也不去验证一下[/color]呢?
为了显示自己有多高明吗?真愚蠢
我来回复