鸡蛋篮子算法题
题目：把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， 由此便容易理解标准答案的实现了。
如果使用蛮力计算出所有组合，再逐一过滤筛选也可以实现，但是程序肯定要比上面繁琐，效率较低。
希望通过该题目能筛选到编程上有天赋的学生，特别是能独立完成构思和代码编写的，应该是很有潜力的。只是该类型的题目并不是特别适合笔试，很多学生写了大段代码逻辑难以判断是否能正确输出，笔试只适合考基础知识，进一步可安排其上机检查其程序技能。
按照以上的思路，写了一下代码。
#include <iostream>#include <vector>using namespace std;void eggProblem(int N, int M, int& count, int sum, int i, vector<int>& vec){if (i == M){if (sum == N){count++;cout<<"The "<<count<<" way: ";vector<int>::iterator it;for (it = vec.begin(); it != vec.end(); it++){cout<<*it<<" ";}cout<<endl;return;}elsereturn;}if (i == M-1 && N-sum > sum+1){if ((N-sum > sum+1)||(N-sum)<vec.back())//对倒数第二个次进行剪枝。{return;}}if (i == 0){vec.push_back(1);count=0;sum=1;i++;}if (!vec.empty()){int temp = vec.back();for (int j = temp; j <= sum+1; j++){i++;sum += j;vec.push_back(j);eggProblem(N, M, count, sum, i, vec);i--;sum -= j;vec.pop_back();}}}int main(){int N = 20, M = 6;int count, sum;vector<int> vec;eggProblem(N, M, count, sum, 0, vec);if (count == 0){cout<<"sorry we cannot find.."<<endl;}}