鸡蛋篮子算法题

题目：把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;
}
}

补充：软件开发 , C++ ,