今天看到一个面试题目,题目大意:将n个鸡蛋放到m个篮子,同时保证不能有空篮子,且对于任意小于等于n的数,都能保证有几个篮子的鸡蛋数等于这个数

题目分析

第一眼看到这个题目时,感觉像是整数拆分问题,但是有两个限制:1. 不能有空篮子 2.保证能够针对任意<=n的数,都可以用几个篮子的鸡蛋的和来表示,所以应该不是整数拆分问题。

首先想到是就是穷举,也就是深度搜索,但是如何判断搜索的一个结果是否满足第二个条件呢?

这里可以通过归纳的方法,假设当前的前n个数为Sn,同时任意<=Sn的数都可以用前n个数某些数的和来表示,那么第n+1个数的范围是什么呢?

这里应该可以想到,如果第n+1个数>(Sn) + 1 的话,相当于有间隔,那么(Sn) + 1这个就无法表示,所以第n+1个数应该是<= Sn + 1,这样就可以满足

任意的<=S(n+1) 的数都可以用前n+1个数来表示;

同时在搜索的过程中保证序列是非降序的,而且会有剪枝的方法,实现具体看代码

代码实现

/*
 * Author: liyangguang <liyangguang@software.ict.ac.cn>
 * http://www.yaronspace.cn/blog
 *
 * File: 1312.cc
 * Create Date: 2011-07-05 22:39:34
 *
 */
#include <stdio.h>
 
#define MAX_N 100000
#define MAX_M 1000
static int s_arrAns[MAX_M];
static int s_iM;
static int s_iN;
 
void
search(int iCurSum, int iIdx, int iCurNum)
{
    if (iCurSum == s_iN && iIdx == s_iM) {
 
        for (int i = 0; i < s_iM; ++i) {
            printf("%d ", s_arrAns[i]);
        }
        printf("\n");
    }
    else if (iCurSum > s_iN || iIdx >= s_iM) {
        return;
    }
    //存在两个剪枝的优化,分别放最少和最多的鸡蛋
    if ((iCurSum + iCurNum * (s_iM - iIdx)) > s_iN || iCurSum + (iCurSum +1)*((1 << (s_iM - iIdx)) - 1) < s_iN) {
        return ;
    }
    else {
        for (int i = iCurNum; i <= iCurSum + 1; ++i) {
 
            s_arrAns[iIdx] = i;
            search(iCurSum+i, iIdx+1, i);
        }
    }
}
 
int 
main(int argc, char* argv[])
{
 
    while (scanf("%d %d", &s_iN, &s_iM) != EOF) {
        search(0, 0, 1);
    }
    return 0;
}
 
 
 
/* vim: set ts=4 sw=4: */
来自yaronspace.cn  本文链接:http://yaronspace.cn/blog/archives/1312