淘宝校招鸡蛋篮子算法题标准答案(javascript实现)

fourinone 发布于 2012/09/24 10:30
阅读 1K+
收藏 13

又到一年校招时,阿里集团虽然今年休养生息,缩紧招聘,但是现在继续开放校招,不过只招a类学生,也就是重点学校的最优学生(面试官认为),以往多半是研究生居多,本科生录用比率减少,但是编程逻辑思维好的学生仍然是不多的,这是去年出的一道原创题和它的标准答案,做对的人非常少。

题目:把N个鸡蛋放到M个篮子里,每个篮子不能为空,要求满足:任意给出一个不超过N的数量,都能找到其中某几个篮子的鸡蛋和等于它。
请写一个程序,输入N,M,然后输出所有的鸡蛋放法。
题目解释:例如6个鸡蛋放3个篮子的一种可能为1,2,3,任意给出1<=x<=6的值,都可以找到1,2,3中的组合的和等于x.

该题目最早是我在网上看到一道600个鸡蛋放在10个篮子的放法,答案是给出了一个按2的乘积放的特例。我将其改编后用来招聘时考察工程师上机编程技能。

解题思路如下:
假设第一个篮子放一个鸡蛋:
那么1,X2中,X2可以放鸡蛋的范围是1<= X2<=2, 如果X2=3,便满足不了给出n=2的情况了
取X2=2
那么1,2,X3中,X3可以放鸡蛋的范围是2<= X3<=4
…..
可以推出数学公式:在前m个篮子满足要求时,第m+1个篮子可以放置的鸡蛋数范围应该是: Xm<=Xm+1<=N+1
该范围同时也是搜索解的空间,比较好用递归实现,对于每找到一个符合范围的Xm,可以进一步深度遍历寻找下一个Xm+1, 由此便容易理解标准答案的实现了。

如果使用蛮力计算出所有组合,再逐一过滤筛选也可以实现,但是程序肯定要比上面繁琐,效率较低。

希望通过该题目能筛选到编程上有天赋的学生,特别是能独立完成构思和代码编写的,应该是很有潜力的。只是该类型的题目并不是特别适合笔试,很多学生写了大段代码逻辑难以判断是否能正确输出,笔试只适合考基础知识,进一步可安排其上机检查其程序技能。

参考答案(保存成html运行即可):
<script>
var n=20,m=5;
var total=0;
var arr = new Array(m);
function exerun(j,t,s){
         for(var i=j;i<t+2;i++){
             if(s==m-1){
                 if(n-t<t+2&&n-t>=j){
                     arr[s]=n-t;
                     document.writeln(arr+"<br>");
                     total++;
                 }
                 break;
             }else if(t+i<n){
                 arr[s]=i;
                 exerun(i,t+i,s+1);
             }else break;
         }
}
exerun(1,0,0);
document.writeln("total:"+total);
</script>

思维延伸:对于太巨大的数字会超出单台机器的计算局限导致缓慢,对次,可考虑采用并行计算方式设计算法,分解到不同机器计算,再合并结果,留给读者去思考。
淘宝分布式并行计算框架fourinone(java实现)下载地址:
http://www.skycn.com/soft/68321.html
企鹅群:241116021
邮箱:Fourinone@yeah.net

加载中
0
狂风萧萧

这种实现方法行的通吗?从1 - 蛋个数 循环。到哪只蛋不够了就准备当前 个数 的篮子。可容纳的蛋的个数 增加到篮子的总数。

0
sxgkwei
sxgkwei
题目有问题吧?我输入6,再输入1,你输出什么呢?
狂风萧萧
回复 @fourinone : 一个 篮子 只有 选和不选 两个状态。状态除了 0就是1。我想应该只能是2进制存放。其它的进制肯定会丢失状态。给那么多篮子,不是少就该是浪费了。
fourinone
fourinone
回复 @sxgkwei : 你应该还没有看清楚题意: 要求输出所有的鸡蛋放法, 根据你给的m,n,找不到符合要求的放法,因此输出0
sxgkwei
sxgkwei
回复 @fourinone : 。。。晕死,输出0有啥用呢,还以为必定会输出一个篮子编号呢
fourinone
fourinone
那6个鸡蛋只能放在1个篮子,任意给出一个1-5的鸡蛋数,都找不到篮子满足,因此,答案输出0
0
fourinone
fourinone
回复 @狂风萧萧 : 呵呵,题目已经要求了每个篮子不能为空,你说的二进制摆放并不是这道题目的答案. 该题目之前网上已经有很多讨论,但很多解答并不正确http://www.oschina.net/code/snippet_54100_8729
0
狂风萧萧

引用来自“fourinone”的答案

回复 @狂风萧萧 : 呵呵,题目已经要求了每个篮子不能为空,你说的二进制摆放并不是这道题目的答案. 该题目之前网上已经有很多讨论,但很多解答并不正确http://www.oschina.net/code/snippet_54100_8729
按你 题目中 20 和 10 举例,最优答案 我想是 1 2 4 8  5(最大16)。 如果 篮子不能为空。1 2 4  8 1 1 1 1 1.我想也是可以的吧。
0
fourinone
fourinone

引用来自“狂风萧萧”的答案

引用来自“fourinone”的答案

回复 @狂风萧萧 : 呵呵,题目已经要求了每个篮子不能为空,你说的二进制摆放并不是这道题目的答案. 该题目之前网上已经有很多讨论,但很多解答并不正确 http://www.oschina.net/code/snippet_54100_8729
按你 题目中 20 和 10 举例,最优答案 我想是 1 2 4 8  5(最大16)。 如果 篮子不能为空。1 2 4  8 1 1 1 1 1.我想也是可以的吧。
1 2 4 8 1 1 1 1 1你数一下只有9个,应该是1,1,1,1,1,1,1,2,4,7,而且这仅仅是其中一个解,运行一下答案n=20,m=10,结果总共有40种解。这道题考核的就是程序试探寻找所有解的能力,如果仅仅找出一个特例, 那这个程序太容易编写了.
0
书凡世界
n=4,m=4.结果应该是1、1、1、1,X3的范围不应该只是2到4吧
返回顶部
顶部