淘宝笔试最后一题！该怎么处理

2012-06-21

淘宝笔试最后一题！！！！！！！！！！有N个鸡蛋和M个篮子，把鸡蛋放到篮子里，每个篮子都不为空，要求：对于任意一个小

淘宝笔试最后一题！！！！！！！！！！
有N个鸡蛋和M个篮子，把鸡蛋放到篮子里，每个篮子都不为空，要求：对于任意一个小于N的数量，都能找到几个篮子里鸡蛋的和等于这个数量，输入M、N，输出所有鸡蛋的方法。

[解决办法]
N=1+2+4+..2^n+m
m<2^n
下面的自己弄，比较好弄
[解决办法]

探讨

楼上的各位是什么意思呀，题目记错了？二进制？完全不明白各位想说什么呀？

[解决办法]
对任意一个小于N的数总能使几个篮子里的鸡蛋总数等于它

充分条件：需要编号n的篮子放的鸡蛋数<=前面的鸡蛋数总和+1
n=1时显然满足，然后用归纳法：现在假设前面n个篮子能表示1-Sn（Sn表示前n个篮子鸡蛋总数之和），则第n+1个篮子取1-Sn+1对应能表示1-2Sn+1.总能满足对现有排序方法对应的篮子数M和鸡蛋数N满足上述条件。

必要条件：如果存在需要编号n的篮子放的鸡蛋数>前面的鸡蛋数总和+1，又因为升序，所以前面的鸡蛋数总和+1该数取不到。
[解决办法]
用C#写的程序，.net framework 2.0, 欢迎大家指正。
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);
}
}
}
}

[解决办法]
今天早上用C++写完了，考虑所有可能的情况。主要是几个约束条件。这题目复杂度的增加不是线性的，后面有好多种方式。大家有兴趣可以看看，有错的过不清楚的可以交流下。
论坛上贴代码不太会用，放我博客里了，看起来清爽些：
http://blog.csdn.net/hiyounger/archive/2011/03/29/6285553.aspx

热点排行

C语言

淘宝笔试最后一题！该怎么处理