淘宝算法实习生的一个笔试题，智商被鄙视了…
好像是个经典的问题，有点思路但就是写不好代码。发出来给大家交流交流。
问题：有N个蛋和M个篮子，把蛋放到M个篮子里，每个篮子都不能为空。另外，需要满足：任意一个小于N的正整数，都能由某几个篮子内蛋的数量相加的和得到。写出程序，使得输入一个(N,M)，输出所有可能的分配情况。
[解决办法]
组合数学的内容 运用鸽巢定理可以解决
[解决办法]
昨天好像看见了同样的帖子。。。好像是二进制。。。
[解决办法]
1.先取M个蛋放入M个篮子（一个篮子一个蛋）
2.剩下的（N-M）个蛋按照1，2，4，。。方式依次维持各个篮子中蛋的数量（要有一个篮子保持只有一个蛋），若最后的蛋不是2的方次，有多少放入一个篮子
3.取L(L<=N)个蛋时，应按二进制编码值考虑，如13个蛋：13的二进制码值是1101，则取有8个、4个和1个蛋的篮子即可。
另外：题目不完整，N与M应该有数量关系：M<=N且N<2的M次方
[解决办法]
看来楼主参加了 昨天的笔试。 我觉得条件： 任意一个小于N的正整数，都能由某几个篮子内蛋的数量相加的和得到，已经限制了楼主说的：9个蛋5个篮子，51111、11124、11223、12222都可以的其中的一些选择的可能性
[解决办法]
充分条件：需要编号n的篮子放的鸡蛋数<=前面的鸡蛋数总和+1
n=1时显然满足，然后用归纳法：现在假设前面n个篮子能表示1-Sn（Sn表示前n个篮子鸡蛋总数之和），则第n+1个篮子取1-Sn+1对应能表示1-2Sn+1.总能满足对现有排序方法对应的篮子数M和鸡蛋数N满足上述条件。
必要条件：如果存在需要编号n的篮子放的鸡蛋数>前面的鸡蛋数总和+1，又因为升序，所以前面的鸡蛋数总和+1该数取不到
[解决办法]
期待高人的标准答案
[解决办法]
using System;
using System.Collections.Generic;
using System.Text;
namespace CmpSplitEgg
{
class Program
{
static void Main(string[] args)
{
SplitEgg();
}
public static bool SplitEgg()
{
// 初始化变量，差额diffNum = 鸡蛋数eggNum - 篮子数basketNum
int eggNum = 0, basketNum = 0, diffNum;
// 输入鸡蛋数、篮子数
Input(ref eggNum, ref basketNum);
// 排列结果，并初始化
int[] resultEggs = new int[basketNum];
for(int i=0;i<basketNum;i++)
{
resultEggs[i] = 1;
}
// 差额 = 鸡蛋数 - 篮子数
diffNum = eggNum - basketNum;
if (diffNum < 0)
{
Console.WriteLine("You can't make N < M");
return DoAgain() && SplitEgg();
}
else if (Math.Pow(2, basketNum) <= eggNum)
{
Console.WriteLine("You can't make N > 2^M");
return DoAgain() && SplitEgg();
}
// 对任意一个小于N的数 总能使几个篮子里的鸡蛋总数等于它，则需要编号n的篮子放的鸡蛋数<=前面的鸡蛋数总和+1
// 基于2进制编码是能表示所有数字且位数最小的编码方式，上面条件由此推出
// 假设组合为升序排列，第一个篮子必然为1个鸡蛋
RandomLay(resultEggs, 1, eggNum);
// 是否重新做一次
return DoAgain() && SplitEgg();
}
/// <summary>
/// 重新选择
/// </summary>
public static bool DoAgain()
{
Console.WriteLine();
Console.WriteLine("if you want to enter the N and M again?Yes（Note: if not enter 'Y' or 'y', the application will quit...）");
string choice = Console.ReadLine();
return choice.ToLower() == "y";
}
/// <summary>
/// 输入
/// </summary>
/// <param name="eggNum">鸡蛋数量</param>
/// <param name="basketNum">篮子数量</param>
public static void Input(ref int eggNum, ref int basketNum)
{
while (true)
{
try
{
Console.WriteLine("Please enter the egg number N:");
eggNum = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Please enter the basket number M:");
basketNum = Convert.ToInt32(Console.ReadLine());
break;
}
catch (Exception)
{
Console.WriteLine("Enter error: please input integer!");
Console.WriteLine();
continue;
}
}
}
/// <summary>
/// 随即放置鸡蛋
/// </summary>
/// <param name="result">结果</param>
/// <param name="beginIndex">开始索引</param>
/// <param name="total">鸡蛋数</param>
public static void RandomLay(int[] result, int index, int total)
{
// iMax为index对应可取鸡蛋数上限
int iMax = 1, basketNum = result.Length;
for (int j = 0; j < index; j++)
{
iMax += result[j];
}
// 复制
int[] copyResult = new int[basketNum];
for (int i = 0; i < basketNum; i++)
{
copyResult[i] = result[i];
}
// 结束条件1：已为最后一个篮子
if (index == basketNum - 1)
{
int mBasket = total - iMax + 1;
if (mBasket <= iMax)
{
copyResult[index] = mBasket;
Console.Write("Split solution: ");
foreach (int res in copyResult)
Console.Write(res + " ");
Console.WriteLine();
}
return;
}
for (int ii = copyResult[index - 1]; ii <= iMax; ii++)
{
// 结束条件2：当前至少需要鸡蛋数
int nowNum = ii * (basketNum - index) + iMax - 1;
// 表示无法再按升序放置鸡蛋
if (nowNum > total)
break;
copyResult[index] = ii;
RandomLay(copyResult, index + 1, total);
}
}
}
}
[解决办法]
[解决办法]
如果篮子不能交换的话，总的个数是M的阶乘个数，篮子里面放的个数是2的n(0.1.2.....M-1),最后一个篮子里面放的个数是M-1个篮子里面放了还剩的个数也就是a[M]= N-Sum，Sum= 2?0 +2?1 + 2?3 + .......+2?（M-1），a[i] = 2?i （i从0开始循环到M-1）。
[解决办法]
[解决办法]
我上面说的M阶乘个数，是指总的情况，是没有判断最后剩下的鸡蛋个数是不是跟前面篮子里面有重的，如8个鸡蛋，4个篮子的话，放法是这样的a[i] = {1,2,4,1}，总的情况就是排列组合的问题了