`

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

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

邮箱:Fourinone@yeah.net
0
2
分享到:
评论
3 楼 287854442 2013-06-29  
其实linux下表示权限的概念和这个题得思路是一样的
2 楼 maxiao001 2012-12-18  
学习了,楼主很强。
1 楼 maxiao001 2012-12-18  
if(s == m-1)这个判断移到for外更清晰一些,虽然效率没有增加

相关推荐

    回溯法解鸡蛋放篮子问题

    在鸡蛋放篮子的问题中,每个鸡蛋都可以选择放入四个篮子中的任意一个,因此每个鸡蛋都有4种选择,总共有4^4=256种可能的组合。但是,由于鸡蛋是相同的,所以实际的放法数量需要去除重复的排列。这就需要我们使用回溯...

    基于深度学习的篮子期权定价数值算法.pdf

    基于深度学习的篮子期权定价数值算法 本文研究了基于深度学习的篮子期权定价数值算法。篮子期权是一种奇异期权,多用于许多外汇交易中进行对冲。多重标的资产价格的加权平均值决定了篮子期权的到期收益率。由于篮子...

    菜篮子工程数学建模图论及算法建立最短路径模型

    【摘要】中的“菜篮子工程”是一项旨在保障市民日常蔬菜供应的民生工程,而图论及算法在其中的应用则体现在资源的优化配置上。利用图论中的最短路径模型,可以有效地解决从蔬菜收购点到销售点的物流调度问题,以最小...

    趣味数学知识竞赛题库(138题及答案).pdf

    9. 第九题与第八题类似,答案是B.11分钟,半篮子是在满篮子前的一分钟。 10. 第十题是锦标赛问题,最少需要99场比赛决定冠军,答案是D.99场。 11. 第十一题是逻辑推理,西瓜数量为2,答案是B.2个。 12. 第十二题...

    数学建模研究菜篮子工程中的蔬菜种植问题.doc

    【数学建模在菜篮子工程中的应用】 数学建模是一种通过数学方法解决实际问题的科学,它在菜篮子工程中的应用旨在优化蔬菜种植、调配和运输过程,以达到经济效益最大化和社会效益均衡。在“数学建模研究菜篮子工程中...

    小学数学数学故事篮子里的鸡蛋

    首先,我们知道篮子里的鸡蛋数量每分钟增加1倍,这意味着每过一分钟,鸡蛋的数量就会翻一倍。如果在第12分钟时篮子满了,那么在第11分钟时篮子里的鸡蛋数量就是满篮子的一半。这是因为在第12分钟,数量再增加1倍,就...

    人工智能和机器学习之关联规则学习算法:Apriori算法:Apriori算法在市场篮子分析中的应用.docx

    人工智能和机器学习之关联规则学习算法:Apriori算法:Apriori算法在市场篮子分析中的应用.docx

    算法大全(包括各种算法及模型的详细介绍)

    《算法大全》是一份详尽的资源,涵盖了各种算法和模型的深度解析,旨在为数学建模以及其他实际问题的解决方案提供理论支持和技术指导。在这个压缩包中,包含了一个名为"算法大全pdf"的文件,我们可以期待它是一个...

    PHP 一筐鸡蛋的问题

    在这里,我们可以将高度作为搜索范围,每次将范围缩小一半,直到找到答案。这种方法的关键在于每次尝试都能排除掉一半的可能性,因此总尝试次数是对数级别的。 现在我们来看`demo.php`这个文件,它很可能是实现上述...

    人工智能和机器学习之关联规则学习算法:Apriori算法:Apriori算法在市场篮子分析中的应用.pdf

    人工智能和机器学习之关联规则学习算法:Apriori算法:Apriori算法在市场篮子分析中的应用.pdf

    数据解析算法合集(持续更新):FindS算法、凝聚层次聚类算法

    这种算法适用于大规模数据库,尤其在市场篮子分析、关联规则学习中表现出色。FindS通过高效的搜索策略减少了计算复杂性,能够快速找出满足特定支持度和置信度条件的频繁项集。在零售业,例如,FindS可以帮助商家找出...

    人工智能和机器学习之关联规则学习算法:Eclat算法在市场篮子分析中的应用.docx

    人工智能和机器学习之关联规则学习算法:Eclat算法在市场篮子分析中的应用.docx

    广工 数据挖掘 最新课后习题完整答案以及数据集

    2. **算法解析**:习题可能涉及到各种数据挖掘算法,如K-均值(K-Means)聚类、ID3决策树、C4.5、CART、Apriori关联规则挖掘等,解答会解释这些算法的工作原理和步骤。 3. **数据预处理**:包括数据清洗、缺失值处理...

    关于c,java算法的练习题

    ### 关于C、Java算法的练习题解析 #### 练习题概述 这份文档提供了48道关于算法的练习题,适用于学习C语言、Java、C#等编程语言的学习者进行算法训练。这些题目覆盖了从基础到进阶的各种算法问题,能够帮助学生更好...

    数据分析算法及模型模拟题三附答案.doc

    这是一个在市场篮子分析中广泛使用的算法,用于发现购物篮中商品之间的频繁项集和强关联规则。在这个问题中,设定的支持度阈值为2/7,置信度阈值为0.7,目的是找出那些至少被2个顾客同时购买的商品组合,并且这些...

    数据挖掘模拟题与部分答案

    ### 数据挖掘模拟题知识点解析 #### 一、选择题知识点解析 **1. 建模数据集的选择** - **选项解析**: - **A数据越多越好**:这种观点过于绝对,数据的质量比数量更重要。 - **B尽可能多的适合的数据**:这是...

    五年级下册小学数学思维训练题及答案.doc

    ### 数学思维训练题解析 #### 1. 新民小学133个少先队员担任卫生宣传,把他们分成几个人数相等的小组,有〔 〕种分法。 解析: - 首先需要找到133的所有因数。 - 133 = 7 × 19 - 因此,可以将133个少先队员分为7...

    关联规则挖掘算法apriori算法的实现

    关联规则挖掘是数据挖掘领域中的一个关键方法,用于发现大量数据集中的有趣关系。...尽管面临一些挑战,但通过不断优化和改进,Apriori算法仍然在数据挖掘中占据重要地位,尤其在零售、市场篮子分析等领域。

    数据挖掘(概念与技术)课后习题答案

    这些技术广泛应用于市场篮子分析等领域。 #### 六、分类与预测 - 分类和预测是监督学习的两种主要任务。分类是预测对象所属类别,而预测则是对数值型属性的估计。常用的分类与预测方法包括决策树、朴素贝叶斯、...

    金色的草地练习题及答案北师大版精选.doc

    总的来说,这份“金色的草地练习题及答案北师大版精选”涵盖了基础的语言知识和应用,旨在帮助小学生提高阅读理解、词汇运用和语境判断能力。通过这样的练习,学生可以深入理解课文内容,同时提升自身的语文素养。

Global site tag (gtag.js) - Google Analytics