淘宝校招鸡蛋篮子算法题标准答案

又到一年校招时,阿里集团虽然今年休养生息,缩紧招聘,但是现在继续开放校招,不过只招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

邮箱:[e-mail]

评论

3 楼 287854442 2013-06-29  

其实linux下表示权限的概念和这个题得思路是一样的

2 楼 maxiao001 2012-12-18  

学习了，楼主很强。

1 楼 maxiao001 2012-12-18  

if(s == m-1)这个判断移到for外更清晰一些，虽然效率没有增加