博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
N个鸡蛋放进M个篮子问题
阅读量:6964 次
发布时间:2019-06-27

本文共 3814 字,大约阅读时间需要 12 分钟。

题目:

有N个鸡蛋和M个篮子,把鸡蛋放到M个篮子里,每个篮子都不能为空。另外,需要满足:任意一个小于N的正整数,都能由某几个篮子内蛋的数量相加的和得到。写出程序,使得输入一个(N,M),输出所有可能的分配情况。

 

从题意中应该可以得出,对于(1,1,2,2)和(1,2,1,2)这两种组合,应该是一样的。

因而对于这M个篮子中的鸡蛋数量,我们用数组basket[M]来表示,我们按照非递减顺序进行排列,即basket[i] <= basket[i+1]

1.我们利用归纳法来总结出一个规律:

   对于前n个篮子,其鸡蛋数量总和为Sn,那么对于第n+1个篮子,其鸡蛋数量应该满足:
   basket[n+1] <= Sn + 1,如果basket[n+1] > Sn + 1,那么Sn + 1这个数将无法通过相应的篮子鸡蛋数相加来获得。
   由于是非递减序列,因而
   basket[n] <= basket[n+1] <= Sn + 1

 

2.我们来证明符合上式的数组能够满足条件“任意一个小于N的正整数,都能由某几个篮子内蛋的数量相加的和得到”。

   当M = 1时,basket[0] = 1,当M=2时,取basket[1] = 1,能够满足上述条件。
                                                         取basket[1] = 2,也能够满足上述条件。
   假设M = n-1时,满足上述条件,我们来证明当M = n时亦满足。
   前n-1个篮子的鸡蛋数量总和为Sn-1,此时加上第n个篮子,总和为Sn = Sn-1 + basket[n-1]。即证明Sn - 1,Sn - 2,Sn - 3,Sn - (basket[n-1] - 1)都可以由某几个篮子内蛋的数量相加的和得到。由于basket[n-1] <= Sn-1,而且小于或者等于Sn-1的数能由某几个篮子内蛋的数量相加的和得到,所以Sn - 1,Sn - 2,Sn - 3,Sn - (basket[n-1] - 1)亦可得到。
   证毕。

3.对于N和M的值,我们在输入后即可做一个判断。

   2.1  当N < M,明显有篮子为空,因而不符。
   2.2  当N >= M时,第一个篮子必然要放1个鸡蛋,其后面的篮子我们按照basket[n] <= basket[n+1] <= Sn + 1取最大值,依次为2,4,8,16......,鸡蛋总数为2^M - 1,即M个篮子的鸡蛋数量最大值。

   所以M <= N < 2^M

 

4.代码要点

   4.1 对于函数

void solve(int current_sum, int basket_id, int current_num, int* basket, int N, int M)

   其中current_sum表示当前所有篮子鸡蛋的总和,

         basket_id表示当前篮子的序号,

         current_num表示将要放到当前篮子去的鸡蛋数量,
         basket, N, M值都是main函数中的原值,在递归中这三个参数基本没变。
   初始化为(0, 0, 1, basket, N, M)表示此时所有鸡蛋数量为0,将要把1个鸡蛋放进第0个篮子里面。

   4.2 对于函数solve中的

if ((current_sum + current_num*(M - basket_id)) > N || (current_sum + (current_sum + 1)*((1<<(M - basket_id)) - 1)) < N)        return;

         我们采用的是搜索中的剪枝技术,即在每次递归时,通过预先判断来看此路是否走得通。

(current_sum + current_num*(M - basket_id)) > N 表示之后的所有篮子都添加最小鸡蛋数量,如果这都大于N,那么肯定不符。
(current_sum + (current_sum + 1)*((1<<(M - basket_id)) - 1)) < N  表示之后的所有篮子都添加相应的最大值,如果这都小于N,那么肯定也不符。     

        其中(current_sum + 1)*((1<<(M - basket_id)) - 1) 可以这样解释:

        假设前面的篮子总和为n,那么紧挨着的后一个篮子里鸡蛋数量最大值为n+1,其后的一个篮子最大值为n + (n + 1) + 1 = 2n + 2,这之后的一个篮子的最大值为n + (n + 1) + (2n + 2) + 1 = 4n + 4......(即这里取的都是S+ 1)

        依次类推,我们发现n + 1 + (2n + 2) + (4n + 4) + ...... = (2^count - 1)*(n + 1),count表示相应的篮子数量。

 

5.代码如下:

N eggs M baskets
1 #include 
2 #include
3 4 void solve(int current_sum, int basket_id, int current_num, int* basket, int N, int M) 5 { 6 if (current_sum == N && basket_id == M) 7 { 8 int i; 9 for (i = 0; i < M; i++)10 printf("%d\t", basket[i]);11 printf("\n");12 return;13 }14 15 if (current_num > N || basket_id >= M)16 return;17 18 if ((current_sum + current_num*(M - basket_id)) > N || 19 (current_sum + (current_sum + 1)*((1<<(M - basket_id)) - 1)) < N)20 return;21 22 int j;23 for (j = current_num; j <= current_sum + 1; j++)24 {25 basket[basket_id] = j;26 solve(current_sum + j, basket_id + 1, j, basket, N, M);27 }28 }29 30 int main()31 {32 int N;//the number of eggs33 int M;//the number of baskets34 while (scanf("%d%d", &N, &M) != EOF)35 {36 if (N < M || N >= 1<

 

1 #include 
2 3 void solve(int current_sum, int basket_id, int current_num, int* basket, int N, int M) 4 { 5 if (current_sum == N && basket_id == M) 6 { 7 int i; 8 for (i = 0; i < M; i++) 9 printf("%d\t", basket[i]);10 printf("\n");11 return;12 }13 14 if (current_num > N || basket_id >= M)15 return;16 17 if ((current_sum + current_num*(M - basket_id)) > N || 18 (current_sum + (current_sum + 1)*((1<<(M - basket_id)) - 1)) < N)19 return;20 21 int j;22 for (j = current_num; j <= current_sum + 1; j++)23 {24 basket[basket_id] = j;25 solve(current_sum + j, basket_id + 1, j, basket, N, M);26 }27 }28 29 int main()30 {31 int N;//the number of eggs32 int M;//the number of baskets33 while (scanf("%d%d", &N, &M) != EOF)34 {35 if (N < M || N >= 1<

转载地址:http://ycwsl.baihongyu.com/

你可能感兴趣的文章
lamp-配置防盗链、访问控制Directory(针对目录)、访问控制(针对单文件)
查看>>
Cacti中文版在Centos上的安装(1)
查看>>
转:路由器MTU值对于网络通讯的影响(解决部分网站打不开问题)
查看>>
状态模式
查看>>
PHP,安卓,ios相互适用的AES加密算法
查看>>
我的友情链接
查看>>
LitePal的使用
查看>>
查找旁站路径的几种方法
查看>>
Cisco路由配置入门
查看>>
图片数据&大文本数据存储
查看>>
我的友情链接
查看>>
创建并调用 DLL(1)
查看>>
lvs+keepalived实现DR模式热备
查看>>
各种媒体数据以 base64 编码方式直接嵌入网页中的写法
查看>>
微软ASP.NET 电商网站开发实战 MVC6 +HTML5 +WCF+WebAPI+NoSQL+mongoDB+Redis+Core视频 代码 面试题...
查看>>
由客户现场引发的思考
查看>>
ORACLE 查看数据库文件的位置
查看>>
Android应用及应用管理
查看>>
开发第一个Hibernate项目,实现插入数据功能
查看>>
Xcode8 missing file 报出 ”xx“is missing from working copy 的问题 解决方法汇总
查看>>