2011年七月







[编程之美]N个鸡蛋放到M个篮子的方法

今天看到一个面试题目,题目大意:将n个鸡蛋放到m个篮子,同时保证不能有空篮子,且对于任意小于等于n的数,都能保证有几个篮子的鸡蛋数等于这个数

题目分析

第一眼看到这个题目时,感觉像是整数拆分问题,但是有两个限制:1. 不能有空篮子 2.保证能够针对任意<=n的数,都可以用几个篮子的鸡蛋的和来表示,所以应该不是整数拆分问题。

首先想到是就是穷举,也就是深度搜索,但是如何判断搜索的一个结果是否满足第二个条件呢?

这里可以通过归纳的方法,假设当前的前n个数为Sn,同时任意<=Sn的数都可以用前n个数某些数的和来表示,那么第n+1个数的范围是什么呢?

这里应该可以想到,如果第n+1个数>(Sn) + 1 的话,相当于有间隔,那么(Sn) + 1这个就无法表示,所以第n+1个数应该是<= Sn + 1,这样就可以满足

任意的<=S(n+1) 的数都可以用前n+1个数来表示;

同时在搜索的过程中保证序列是非降序的,而且会有剪枝的方法,实现具体看代码

代码实现

更多 >