救命！某大公司程序员笔试题！答中有重奖！超难算法
是的这样的：
有十种水果： 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、回复次数：24Top
1 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-30 10:50:09 得分 0
这个题目有错！
1、水果有 5900 个，而学生按要求仅需 5500 个水果，如何“所有水果全部分完，一个不剩”？
2、每个年级学生数均为整百，若不能切分水果，那么有 550 个的水果 a 能分完吗？Top
2 楼poyi_820921（）回复于 2006-03-30 11:10:41 得分 0
这位老哥,题目没错,你把各年级的要求分到的水果总数一加,就是5900个,一个不多,一个不少,题目我确定过了,没错的,Top
3 楼wotobo（晓敢）回复于 2006-03-30 11:14:47 得分 0
每一次分发都要坚持一个原则:
一定要保持水果品种的数量最多为前提!
所以分发时应该保护某种水果不要被分发完!Top
4 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-30 11:15:50 得分 0
是我看错了一个数字:(
但 “a 有550个，...，e 有650个,”，在现有的条件下是无论如何也无法完成分配的，原因见我第一次回复的第 2 条。（∵550 mod 100 = 50，小心被忽悠了，哈哈）Top
5 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-30 11:18:03 得分 0
除非要求同一年级学生有不同的分配方案！
（但不知是降低了难度，还是增加了难度，自己揣摩吧。。。)Top
6 楼poyi_820921（）回复于 2006-03-30 11:20:39 得分 0
拜托各位,当初我也认为很简单,是小学生的问题,可是用了N种方法,就是做不到每个人实际拿到的,和他应该拿的一样,而且还有剩的水果,求各位仔细想想Top
7 楼poyi_820921（）回复于 2006-03-30 11:22:22 得分 0
求各位仔细想想,既然认为简单,就救救我,明天就该...............Top
8 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-30 12:25:00 得分 5
一 二 三 四 五 六
200 100 200 100 200 200
===========================================
a 550 1 1 1 0.5 0 0
b 600 1 0 1 0 1 0
c 700 1 1 0 0 1 1
d 700 1 1 1 0 1 0
e 650 1 0 0 0.5 1 1
f 500 1 1 1 0 0 0
g 500 1 1 0 0 0 1
h 600 1 1 0 1 0 1
i 600 1 1 0 1 1 0
j 500 0 1 1 0 1 0
===========================================
（其中表中两个“0.5”表示四年级等分成两组，a或e仅取其一）
以上结果是随便排出来的，如果不允许出现“0.5”，则无解（原因已阐明）！Top
9 楼coldcool（寒冰）回复于 2006-03-30 12:28:17 得分 5
还是比较简单的，思路如下
10种水果
6个年纪
先吧最多数量的分到最少年纪
如4年纪100人，每人3个
CDE各减100
变成
550,600,600,600,550,500,500,600,600,500
四年机完成分配
分6年纪每人四各200人，四种水果
350，400，400，400，550，500，500，600，600，500
三年纪200各，五种
350,400,400,400,350,300,300,400,400,500
以此类推，每次匹配最多的，
用for加if语句就可以完成。。
写程序好烦。。。
Top
10 楼zzwu（未名）回复于 2006-03-30 12:47:25 得分 0
同一年级的学生是否要求拿到相同品种的水果?Top
11 楼zzwu（未名）回复于 2006-03-30 13:15:57 得分 5
如果同一年级的学生不要求拿到相同品种的水果,则问题可以
用下面的一系列的数学式子来表示:
设i年级分到的第j种水果为nij,（i=1..6,j=0..9,共60个系数）则
1年级要求的各种水果为：
n10*a+n11*b+n12*c+n13*d+n14*e+n15*f+n16*g+n17*h+n18*i+n19*j=200*9;
2年级要求的各种水果为：
n20*a+n21*b+n22*c+n23*d+n14*e+n15*f+n16*g+n17*h+n18*i+n19*j=100*8;
...
6年级要求的各种水果为：
n60*a+n61*b+n62*c+n63*d+n64*e+n65*f+n66*g+n67*h+n68*i+n69*j=200*4;
（以上共6个方程）
要求满足下列约束：
1。所有系数（即每个年级每种水果的数目）都是非负整数：
nij>=0, i=0...6, j=0..9
（共60个约束）
2。分给i年级的第j种水果数目nij应<=该年级人数mi，否则就有人会有相同水果
nij<=mi, i=0...6, j=0..9
（共60个约束）
3。各种水果总数是已知的，即要求：
水果a总数=550:
n10+n20+n30+n40+n50+n60=550
水果b总数=600:
n11+n21+n31+n41+n51+n61=600
...
水果j总数=500:
n19+n29+n39+n49+n59+n69=500
（共10个约束）
这个规划问题共有6+60+60+10=136个等式或不等式方程！
如不找窍门，要用人工直接求解可不容易！
Top
12 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-30 14:10:41 得分 0
前面给的结果排版不是很好，重新排版一下：
年级|人数 | a b c d e f g h i j | ∑
===========|======================================================|=====
一 200 | 1 1 1 1 1 1 1 1 1 0 | 9
二 100 | 1 0 1 1 0 1 1 1 1 1 | 8
三 200 | 1 1 0 1 0 1 0 0 0 1 | 5
四 100 | / 0 0 0 / 0 0 1 1 0 | 3
五 200 | 0 1 1 1 1 0 0 0 1 1 | 6
六 200 | 0 0 1 0 1 0 1 1 0 0 | 4
===========|============================================================
总 计 | 550 600 700 700 650 500 500 600 600 500 | 5900
其中：
“1”——表示该年级取用该水果；
“0”——表示该年级不取用该水果；
“/”——表示该年级一半人取用该水果。Top
13 楼mmmcd（超超）回复于 2006-03-30 14:20:41 得分 5
不能分果，就分人吧
四年级分成50＋50的2组
一 二 三 四(1) 四(2) 五 六
200 100 200 50 50 200 200
==================================================
a 550 1 1 1 1 0 0 0
b 600 1 0 1 0 0 1 0
c 700 1 1 0 0 0 1 1
d 700 1 1 1 0 0 1 0
e 650 1 0 0 0 1 1 1
f 500 1 1 1 0 0 0 0
g 500 1 1 0 0 0 0 1
h 600 1 1 0 1 1 0 1
i 600 1 1 0 1 1 1 0
j 500 0 1 1 0 0 1 0
==================================================Top
14 楼zzwu（未名）回复于 2006-03-30 14:29:49 得分 0
coldcool(寒冰)的思路有道理的,先把数量多水果品种先分掉,
这样可以避免剩下数目很多的水果分不出去.
但是否一定要先分给人数少的班级,就不一定了.
另外,数量多的水果也不一定要全分掉.
Top
15 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-03-30 15:21:11 得分 0
zzwu(未名) 提供的答案与我的似乎是一样的。
我的策略如下：
1、将班级人数从大到小排列，优先分配人数较多的；
2、随时将班级每人取用的水果剩余数排序，优先给需求量最大的班级；
3、随时将水果排序，优先选用剩余数目较多者。
不到两分钟就手工排出来了。Top
16 楼freshman520（freshman520）回复于 2006-03-30 18:33:09 得分 0
package com.won.sys;
import java.util.Arrays;
public class Util {
private int vec[] = { 550, 600, 700, 700, 650, 500, 500, 600, 600, 500 };
public Util() {
}
//persons为各年级人数, sums每人要求分到个数
public void testSort(int persons, int sums) {
try {
for (int i = vec.length - sums; i < vec.length; i++) {
int j = 0;
int temp = vec[i] - persons;
if (temp < 0) {
while (temp < 0) {
temp = vec[i] - persons + vec[j];
//说明一下：这个题目刚好一个年级能分到两种水果vec[i]+ vec[j]而不出现负数
//j一直加到10而不出现负数，不会陷入while死循环,不会出现数组溢出
//就是说两种水果不够怎么办？程序得重新写，如果能提供足够多的测试用例就好了
j = j + 1;
}
temp = vec[i] - persons + vec[j - 1];
vec[j - 1] = 0;
}
vec[i] = temp;
}
} catch (Exception e) {
}
Arrays.sort(vec);
}
//输出完毕
public String toString() {
try {
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
} catch (Exception e) {
}
return "";
}
}
package com.won.sys;
public class test {
private int vec[] = { 550, 600, 700, 700, 650, 500, 500, 600, 600, 500 };
public static void main(String[] args) {
/*
*
* 一年级 200人 每人要求分到：9个
*
* 二年级 100人 每人要求分到：8个
*
* 三年级 200人 每人要求分到：5个
*
* 四年级 100人 每人要求分到：3个
*
*
* 五年级 200人 每人要求分到：6个
*
* 六年级 200人 每人要求分到：4个
*
*/
Util util = new Util();
util.testSort(200, 9);
util.toString();
System.out.println("输出完毕");
util.testSort(100, 8);
util.toString();
System.out.println("输出完毕");
util.testSort(200, 6);
util.toString();
System.out.println("输出完毕");
util.testSort(200, 5);
util.toString();
System.out.println("输出完毕");
util.testSort(200, 4);
util.toString();
System.out.println("输出完毕");
util.testSort(100, 3);
System.out.println("输出完毕");
util.toString();
System.out.println("输出完毕");
}
}
Top
17 楼zzwu（未名）回复于 2006-03-31 08:55:23 得分 0
我认为最简单的方法是:
1.让学生们按年级排队,如
1,1,1,1,2,2,2,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,6
其中每个数字代表一个学生,1代表1年纪学生,2代表2年级学生,等
队列实际长度应=1000
2.把所有品种水果一种一种地拿来,依此1个别个地分给每个学生1个,
如果一种发完,就用另一种代替接着发,其形式为:
1,1,1,1,2,2,2,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,6
a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,b,b,b,b,b,b,b,b,b,b,b,b,b
b,b,b,b,b,b,c,c,c,c,c,c,c,c,c,c,c,c,c,c,c,c,...
3.不断发下去,一旦学生得到了应有数目的水果后,就自动离开队列,
这样,当所有水果分完,每个学生也就得到了应得的水果数.
由于没有一种品种的水果数目大于队列长度1000,
这种分配方法可以保证每个学生不会得到相同的水果.
[注]可以看出,学生不按年级排队也无所谓,如穿插地排成如下也可以:
3,1,4,6,1,2,1,2,3,4,3,6,4,2,4,1,4,1,5,5,2,5,4,6,1,1,2,6,3
只要得到应得数目的水果后,就自动离开,就可以了.
Top
18 楼zzwu（未名）回复于 2006-03-31 09:13:39 得分 0
没有对齐，重发（水果品种改用A,B,C...表示）
1.让学生们按年级排队,如
１，１，１，２，２，３，３，４，４，４，５，５，６，６，６
其中每个数字代表一个学生,1代表1年纪学生,2代表2年级学生,等
队列实际长度应=1000
2.把所有品种水果一种一种地拿来,依此一个个地分给每个学生,
如果一种发完,就用另一种代替接着发,分发的过程形式为:
１，１，１，２，２，３，３，４，４，４，５，５，６，６，６
Ａ，Ａ，Ａ，Ａ，Ａ，Ａ，Ａ，Ａ，Ａ，Ａ，Ｂ，Ｂ，Ｂ，Ｂ，Ｂ
Ｂ，Ｂ，Ｂ，Ｂ，Ｃ，Ｃ，Ｃ，Ｃ，Ｃ，Ｃ，Ｃ，Ｃ，Ｄ，Ｄ，Ｄ
Ｄ，Ｄ，Ｄ，...
3.不断发下去,一旦某个学生得到了应有数目的水果后,就自动离开队列,
这样,当所有水果分完,每个学生也就得到了应得的水果数.
由于没有一种品种的水果数目大于队列长度1000,
这种分配方法可以保证每个学生不会得到相同的水果.
[注]可以看出,学生不按年级排队也无所谓,如穿插地排成如下也可以:
3,1,4,6,1,2,1,2,3,4,3,6,4,2,4,1,4,1,5,5,2,5,4,6,1,1,2,6,3
只要得到应得数目的水果后,就自动离开,就可以了.
Top
19 楼poyi_820921（）回复于 2006-03-31 10:16:03 得分 0
谢谢各位的关注,其实这是我在做排考系统中遇到的一个小问题,我拿来了,改了一下外皮,愚人节快到了,也让大家开心一下,哈哈Top
20 楼iamwiner（烛泪）回复于 2006-03-31 10:23:38 得分 0
楼上的可能是问题,你要确定学生们按什么排序,水果按什么顺序发吧?不然可能到最后的时候会出现重复的现象Top
21 楼zzwu（未名）回复于 2006-03-31 11:46:41 得分 0
如果要求同一年级的学生拿到相同品种的水果, 怎么办?
这仍然一个没有彻底解决的"小问题"!!!
Top
22 楼zzwu（未名）回复于 2006-03-31 11:56:24 得分 0
补充: 前面示例中仍要求多的水果先发掉.
Top
23 楼poyi_820921（）回复于 2006-03-31 13:31:58 得分 0
今天晚上把我做的方法 贴上Top
24 楼zzwu（未名）回复于 2006-04-13 17:38:49 得分 0
贴?Top
