可用分押宝游戏火热进行中...	专题改版：Java Web 专题

救命！某大公司程序员笔试题！答中有重奖！超难算法

楼主poyi_820921（）2006-03-30 09:51:15 在 Web 开发 / PHP 提问

是的这样的：

有十种水果： a 有550个,b 有600个,c 有700个,d 有700个,e 有650个,f 有500个,g 500个,h 有600个,i 有600个,j 有500个

现在有个1000人小学校，要求把这些水果平均分到孩子手里

一年级 200人每人要求分到：9个

二年级 100人每人要求分到：8个

三年级 200人每人要求分到：5个

四年级 100人每人要求分到：3个

五年级 200人每人要求分到：6个

六年级 200人每人要求分到：4个

要求：要每个人手里实际分到的水果和要求分到的水果恰好相等，没人多拿没人少拿，

并且所有水果全部分完，一个不剩

还有一点要求，就是每个人手里的水果不能有重复品种的水果的，也就是说，比如：某人手里不能同时拿到两个A水果，这样是错误的做法

请各位老大救命，小弟谢了，最好发个源程序，任何语言做的都可以，发到xyz_133676984281@yahoo.com.cn里

我看行了，再和你联系，买你的源代码，谢谢
问题点数：20、回复次数：41Top

1 楼Gdj（陈水.智商只有129.非卖品）回复于 2006-03-30 10:18:18 得分 0

我怎么觉得是初中生的考试题。不是你把作业拿出来蒙人吧……Top

2 楼ashchen（老陳）回复于 2006-03-30 10:33:26 得分 0

招枪手的公司？Top

3 楼poyi_820921（）回复于 2006-03-30 10:38:49 得分 0

晕!说得简单,先把你的源程序发来,运行通过,买你代码Top

4 楼Gdj（陈水.智商只有129.非卖品）回复于 2006-03-30 10:43:46 得分 0

什么说得简单。实际也简单啊。

只要每个学生循环按要求拿水果。水果种类不够就向前搜索看拿过的人里有谁的水果可以换一下。Top

5 楼poyi_820921（）回复于 2006-03-30 10:43:50 得分 0

最好下午1 点前把程序发我邮箱里,能运行,我就买你代码Top

6 楼Gdj（陈水.智商只有129.非卖品）回复于 2006-03-30 10:45:48 得分 0

反正也没要求执行时间。就按简单的思路写就行了。Top

7 楼poyi_820921（）回复于 2006-03-30 10:47:08 得分 0

不是呀,每人手里的水果种类可以不一样,但是不能有重复的,但是每个人手里的水果数量和规定的数量必须一样Top

8 楼zairwolfb（君子兰）回复于 2006-03-30 10:49:03 得分 0

买...........Top

9 楼poyi_820921（）回复于 2006-03-30 10:52:51 得分 0

如果各位认为是小问题,就求哪位能人把大概的思路写出来吧,小弟谢了大哥先Top

10 楼Gdj（陈水.智商只有129.非卖品）回复于 2006-03-30 10:58:12 得分 0

思路我写拉。就是说不够数量时就向前搜索。跟发过的人换一下以保证没有拿重复的。你先别着急。我说的这是笨方法。一会说不定会有好方法出来。Top

11 楼poyi_820921（）回复于 2006-03-30 11:00:57 得分 0

不是的,这位老哥,你的办法我也用过,最后不是有人多拿了.就是有人不够Top

12 楼zeroleonhart（Strong Point:Algorithm）回复于 2006-03-30 11:10:51 得分 0

这个怎么看也不像是有多难的啊
将水果的种类按照数量排序，从多到少
一年级：取出前9种水果，每种水果数量扣掉200，然后仍然按照数量由多到少将剩下的水果排序
二年级：在剩下的水果中取出前8种，每种扣掉200，如果有某种水果数量不够，就从剩下的2种水果里取。
三年级以此类推。。。Top

13 楼zeroleonhart（Strong Point:Algorithm）回复于 2006-03-30 11:13:59 得分 0

就是发完一个年级就对剩下的水果排序然后再发下一个年级Top

14 楼poyi_820921（）回复于 2006-03-30 11:14:36 得分 0

zeroleonhart(莱昂哈特) 老兄,你说的方法我也用过了,最后不是有人多拿了.就是有人不够.这个问题决不是那么简单的,不然别人不会拿这个来问我的Top

15 楼poyi_820921（）回复于 2006-03-30 11:18:55 得分 0

拜托各位,当初我也认为很简单,是小学生的问题,可是用了N种方法,就是做不到每个人实际拿到的,和他应该拿的一样,而且还有剩的水果,求各位仔细想想Top

16 楼poyi_820921（）回复于 2006-03-30 11:22:39 得分 0

求各位仔细想想,既然认为简单,就救救我,明天就该...............Top

17 楼Gdj（陈水.智商只有129.非卖品）回复于 2006-03-30 12:28:37 得分 0

吃饭ing。。。。
吃完再说Top

18 楼Cain（一苇渡江）回复于 2006-03-30 12:36:23 得分 0

题目很简单，对方可能要求的是算法吧Top

19 楼mingxuan3000（铭轩）回复于 2006-03-30 12:53:19 得分 0

up，学习Top

20 楼zeroleonhart（Strong Point:Algorithm）回复于 2006-03-30 12:55:25 得分 0

大哥，我演算了一遍，我的算法完全没有问题的。你按照我的方法一步一步来就知道了。另外你可以将年级也按照每人分得的水果数量由多到少排列，也就是1，2，5，3，6，4的顺序排序进行分配。
不可能会出现有人多拿有人不够的情况。因为每一种水果分配给一个年级的数量没有超过年级的总人数。也就是最多一人一个，怎么可能出现有人多拿的情况啊？
严重怀疑问你的人是如何看你的。。。Top

21 楼zeroleonhart（Strong Point:Algorithm）回复于 2006-03-30 13:09:21 得分 5

我的算法的结果：
一年级：c,d,e,h,i,b,a,f,g每人一个，每种水果200个
二年级：c,d,j,e,h,i,b,a每人一个，每种水果100个
五年级：c,d,j,e,h,i每人一个，每种水果200个
三年级：b,f,g,a,c每人一个,每种水果200个
六年级：d200,j200,e150+a50,b100+f100，d,j每人一个，另外两种水果在e和a，b和f之间选择
四年级：g,h,i每人一个，每种水果100个，至此全部发完Top

22 楼LongLongAgoImBoy（ThereIsAMe）回复于 2006-03-30 13:49:48 得分 10

zeroleonhart(莱昂哈特) 的方法已经符合要求了，不知道楼主还有什么要求？
a b c d e f g h i j
550 600 700 700 650 500 500 600 600 500

1 200 9
2 100 8
3 200 5
4 100 3
5 200 6
6 200 4

c d e h i b a f g j 年级
700 700 650 600 600 600 550 500 500 500
500 500 450 400 400 400 350 300 300 500 1
j c d e h i b a f g
500 500 500 450 400 400 400 350 300 300
400 400 400 350 300 300 300 250 300 300 2
j c d e h i b f g a
400 400 400 350 300 300 300 300 300 250
200 200 200 150 100 300 300 300 300 250 3
i b f g a j c d e h
300 300 300 300 250 200 200 200 150 100
200 200 200 300 250 200 200 200 150 100 4
g a i b f j c d e h
300 250 200 200 200 200 200 200 150 100
100 50 0 0 0 0 200 200 150 100 5
c d e h g + a i + b + f j
200 200 200 200 100 100 100 50 50 0
0 0 0 0 0 0 0 0 0 0 6

Top

23 楼paky（游猫娱乐）回复于 2006-03-30 13:56:31 得分 0

最后一行：

200 200 150 100 100 50 0 0 0 0
0 0 0 0 0 0 0 0 0 0 6Top

24 楼Gdj（陈水.智商只有129.非卖品）回复于 2006-03-30 14:40:55 得分 5

估计他要的是程序不是算法...
这段程序是最最最土的。但一样能得出结果
$food=array(
'a'=>550,
'b'=>600,
'c'=>700,
'd'=>700,
'e'=>650,
'f'=>500,
'g'=>500,
'h'=>600,
'i'=>600,
'j'=>500
);
$student=array();
function get_food($index)
{
global $student,$food;
//该拿几个
if($index<200) $num=9;
elseif($index<300) $num=8;
elseif($index<500) $num=5;
elseif($index<600) $num=3;
elseif($index<800) $num=6;
else $num=4;

foreach($food as $k=>$v){
if($v>0){
$food[$k]--;
$student[$index].=$k;
$num--;
if($num==0) break;
}
}
while($num>0){
for($i=0;$i<$index;$i++){
foreach($food as $k=>$v){
if($v>0 && false===strpos($student[$i],$k)){
for($j=0;$j<strlen($student[$i]);$j++){
if(false===strpos($student[$index],$student[$i][$j])){
$student[$index].=$student[$i][$j];
$student[$i]=substr($student[$i],0,$j).substr($student[$i],$j+1).$k;
$food[$k]--;
$num--;
break 3;
}
}
}
}
}
}
}

for($i=0;$i<1000;$i++){
get_food($i);
}
foreach($student as $k=>$v){
echo sprintf("%04d",$k+1).":{$v}<br>";
}
exit;
Top

25 楼Hylas（羽心）回复于 2006-03-30 16:56:46 得分 0

问题最大的难点在于：到最后出现这样的情况，其中某水果没了，某水果还很多。
导致某人拿同一水果。

解决办法：相信每个小朋友都是聪明的，他们会按照以下方法去取水果。
原则一：从最多的水果开始挑选。
原则二：每人要求个数少的优先挑选。

具体实现：
排列水果从多到少： sortapple()
悠闲挑选水果顺序： 3 4 5 6 8 9
算法时间： (1000)*(200*9+100*8+200*5+100*3+200*6+200*4) = 100万次
算法优化： sortapple()函数

个人认为还有更好的办法。
poyi_820921() 是不是去笔面试：）

Top

26 楼cquazhi（阿志）回复于 2006-03-30 17:20:03 得分 0

到底是先让分到水果多学生先拿呢，还是让分到水果少的学生先拿呢？Top

27 楼ycy589（ycy589）回复于 2006-03-30 18:11:13 得分 0

顶吧Top

28 楼dyl8910（188）回复于 2006-03-30 18:50:16 得分 0

我觉得要是没要求运行时间 Gdj的那段最土的代码就行`````````Top

29 楼deepass（渴望突破）回复于 2006-03-30 20:48:51 得分 0

是不是就只要写算法就可以啦,楼上不是有人做出来了?Top

30 楼macongbin88（小马）回复于 2006-03-30 21:40:56 得分 0

同意Hylas(羽心)的观点
原则一：优先拿剩下的水果数多的
原则二：让要求分到水果种类多的学生先拿。

个人感觉算法时间不会有百万级那么大，应该是1000*（10个数排序的算法时间）
Top

31 楼fl99（笨笨(QQ:250009333)）回复于 2006-03-30 21:55:36 得分 0

我关心能有多少钱？
我可以做成你输入任一水果数，只要能分配就马上能出来结果！
我关心能有多少钱？Top

32 楼fl99（笨笨(QQ:250009333)）回复于 2006-03-31 00:31:29 得分 0

搞定了，你第任一指定班级人数，任一指定班每人应该分得水果数，任一指定每种水果数目，
用时0.000125秒分配出正确答案，如果需要，联系QQ250009333，
Top

33 楼fl99（笨笨(QQ:250009333)）回复于 2006-03-31 01:29:58 得分 0

DEMO地址，http://www.mit9.com/fp.rar
任一指定班级人数，任一指定班每人应该分得水果数，任一指定每种水果数目
欢迎各位同僚指点一二Top

34 楼Unending（看分答题）回复于 2006-03-31 06:12:26 得分 0

小CaseTop

35 楼poyi_820921（）回复于 2006-03-31 10:16:14 得分 0

谢谢各位的关注,其实这是我在做排考系统中遇到的一个小问题,我拿来了,改了一下外皮,愚人节快到了,也让大家开心一下,哈哈Top

36 楼atwdsgood（东流水）回复于 2006-03-31 10:41:49 得分 0

无聊的人，无聊的题Top

37 楼poyi_820921（）回复于 2006-03-31 11:13:15 得分 0

atwdsgood(东流水) ,你做做就知道有意思了Top

38 楼carry_on（Never lose my passion）回复于 2006-03-31 13:36:12 得分 0

TO:Hylas(羽心)
同意你嘀观点，，但有一点跟你有点差别
解决办法：相信每个小朋友都是聪明的，他们会按照以下方法去取水果。
原则一：从最多的水果开始挑选。
原则二：个数要求多嘀年级优先挑选。

具体实现：
排列水果从多到少： sortapple()
个数要求多嘀年级挑选，挑一次sorapple()一次，保证不出现剩下嘀水果品种不能满足年级要求嘀个数
悠闲挑选水果顺序： 9，8，6，5，4，3
算法时间：约为 M（学生人数）*N（水果种类数）Top

39 楼AvalonFX（若不是痛彻心扉，谁又记得谁）回复于 2006-03-31 15:44:15 得分 0

http://www.edacn.net/bbs/get.php?id=23516Top

40 楼lovemaggie20（花满池塘得自由）回复于 2006-04-01 07:33:01 得分 0

用不着原则2也可以啊，每个人挑前给水果排下序，按顺序挑他要求的个数就可以了啊。Top

41 楼wallace_lee（诸葛猫的老公）回复于 2006-04-02 21:16:03 得分 0

C++的代码：

#include <iostream.h>

#define FRUIT_KINDS 10
#define GRADES 6

void fruit_order(int);

int grade_students[GRADES]={200,100,200,100,200,200};
int grade_fruits[GRADES]={9,8,5,3,6,4};

char fruit_name[FRUIT_KINDS]={'a','b','c','d','e',
'f','g','h','i','j'};
int fruits[FRUIT_KINDS]={550,600,700,700,650,
500,500,600,600,500};

int main()
{

int temp;

//水果的数量先排序
int k=FRUIT_KINDS-1;
for (int i=0;i<k;i++) {
for(int j=i+1;j<FRUIT_KINDS;j++) {
if (fruits[i]<fruits[j]) {
temp=fruits[i];
fruits[i]=fruits[j];
fruits[j]=temp;
temp=fruit_name[i];
fruit_name[i]=fruit_name[j];
fruit_name[j]=temp;
}
}
}

//output
for (k=0;k<FRUIT_KINDS;k++) {
cout<< fruit_name[k] <<":" << fruits[k] << ",";
}
cout << endl;

//外循环是年级，内循环是人数，里面第三层循环是每年级可拿的水果数
for(int i=0;i<GRADES;i++) {

k=grade_fruits[i]-1;

for (int j=0;j<grade_students[i];j++) {
for (int x=0;x<=k;x++) {
fruits[x]--;
}
fruit_order(grade_fruits[i]);
}

//output
for (k=0;k<FRUIT_KINDS;k++) {
cout<< fruit_name[k] <<":" << fruits[k] << ",";
}
cout << endl;
}
}

void fruit_order(int bs)
{
int i,j,temp;

for (i=bs-1;(i>=0) && (fruits[i]<fruits[i+1]);i--) {
for(j=FRUIT_KINDS-1;j>=i+1;j--)
{
if (fruits[i]<fruits[j])
{
temp=fruits[i];
fruits[i]=fruits[j];
fruits[j]=temp;
temp=fruit_name[i];
fruit_name[i]=fruit_name[j];
fruit_name[j]=temp;
}
}
}
}

执行结果：
c:700,d:700,e:650,b:600,h:600,i:600,a:550,f:500,g:500,j:500, //未拿时
c:500,d:500,e:450,b:400,h:400,i:400,j:363,g:363,a:362,f:362, //一年级拿后
c:400,d:400,e:350,h:308,j:307,g:307,a:307,f:307,i:307,b:307, //二年级拿后
c:230,d:230,a:230,g:230,h:230,e:230,b:230,i:230,j:230,f:230, //三年级拿后
j:200,f:200,d:200,c:200,g:200,a:200,b:200,i:200,h:200,e:200, //四年级拿后
d:80,c:80,g:80,a:80,j:80,f:80,b:80,i:80,h:80,e:80, //五年级拿后
d:0,c:0,g:0,a:0,j:0,f:0,b:0,i:0,h:0,e:0, // 六年级都给拿光了
Top