題目：把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， 由此便容易理解標准答案的實現了。
如果使用蠻力計算出所有組合，再逐一過濾篩選也可以實現，但是程序肯定要比上面繁瑣，效率較低。
希望通過該題目能篩選到編程上有天賦的學生，特別是能獨立完成構思和代碼編寫的，應該是很有潛力的。只是該類型的題目並不是特別適合筆試，很多學生寫了大段代碼邏輯難以判斷是否能正確輸出，筆試只適合考基礎知識，進一步可安排其上機檢查其程序技能。
按照以上的思路，寫了一下代碼。
[cpp]
#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;
}
else
return;
}
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;
}
}
#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;
}
else
return;
}
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;
}
}
