淘宝校园笔考题

淘宝校园笔试题
N个鸡蛋放到M个篮子中，篮子不能为空，要满足：对任意不大于N的数量，能用若干个篮子中鸡蛋的和表示。写出函数，对输入整数N和M，输出所有可能的鸡蛋的放法。

比如对于9个鸡蛋5个篮子
解至少有三组：
1 2 4 1 1
1 2 2 2 2
1 2 3 2 1

[解决办法]

引用:

算法思想：
  递归调用，调用的时候注意在a[m]数组中有三个条件：a[0]=1，a[i]<=a[i+1],然后最后一个条件就是循环调用递归的条件a[i]取值必须在[(n-a[i+1]-a[i+2]-...-a[m-1])/2]取上天花板函数，假设计算这个数为k，那么a[i]就从k逐渐递减为1。
稍微说下代码:(这里用[]表示取上天花板函数)
egg(x, y, a){ //有x个鸡蛋，放入……

更正一下：

算法思想：
  递归调用，调用的时候注意在a[m]数组中有三个条件：a[0]=1，a[i]<=a[i+1],然后最后一个条件就是循环调用递归的条件a[i]取值必须在[(n-a[i+1]-a[i+2]-...-a[m-1])/2]取上天花板函数，假设计算这个数为k，那么a[i]就从k逐渐递减为1。

这里n-a[i+1]-a[i+2]-...-a[m-1]的值必须大于等于筐数以确保每个筐至少一个鸡蛋(下面的例子中就是x>=y)，分配到最后就是a数组的所有位置的鸡蛋数已经确定，那么如果还有鸡蛋没有分配完，表示分配失败。

稍微说下代码:(这里用[]表示取上天花板函数)
egg(x, y, a){ //有x个鸡蛋，放入y个篮子
  for(int j=min([x/2], a[y]); j>=1; --j){ //这里min函数保证了a[i]<=a[i+1]
    if(y == 1){
      //这里就是a中所有位置的鸡蛋数已经确定，如果鸡蛋还没有分配完，那么就是失败的分配，就直接跳过这一结果
    }else{
       a[y-1] = j; //最后一个篮子放j个鸡蛋
        egg(x-j, y-1, a);
    }
  }
}
上面只是伪代码，具体细节不写了，算法思想就是递归调用。
[解决办法]
http://blog.csdn.net/qq675927952/archive/2011/04/09/6312255.aspx

查看更多 下一篇