热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

N个鸡蛋放进M个篮子问题

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

题目:
有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    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))  

        其中(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 )
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 eggs
33 int M;//the number of baskets
34 while (scanf("%d%d", &N, &M) != EOF)
35 {
36 if (N = 1<0)
37 printf("Wrong data!\n");
38 else
39 printf("The combinations are as below:\n");
40
41 int* basket = (int*)malloc(sizeof(int)*M);
42 solve(0, 0, 1, basket, N, M);
43 free(basket);
44 }
45 return 0;
46 }

 

 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 )
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 eggs
32 int M;//the number of baskets
33 while (scanf("%d%d", &N, &M) != EOF)
34 {
35 if (N = 1<0)
36 printf("Wrong data!\n");
37 else
38 printf("The combinations are as below:\n");
39
40 int* basket = new int[M];
41 solve(0, 0, 1, basket, N, M);
42 delete[] basket;
43 }
44 return 0;
45 }

推荐阅读
  • 题面:P3178[HAOI2015]树上操作好像其他人都嫌这道题太容易了懒得讲,好吧那我讲。题解:第一个操作和第二个操作本质上是一样的&# ... [详细]
  • 来自FallDream的博客,未经允许,请勿转载,谢谢。一天一套noi简直了.昨天勉强做完了noi2011今天教练又丢出来一套noi ... [详细]
  • 本文详细解析 Skynet 的启动流程,包括配置文件的读取、环境变量的设置、主要线程的启动(如 timer、socket、monitor 和 worker 线程),以及消息队列的实现机制。 ... [详细]
  • 深入解析C++ Atomic编程中的内存顺序
    在多线程环境中,为了防止多个线程同时修改同一数据导致的竞争条件,通常会使用内核级同步对象,如事件、互斥锁和信号量等。然而,这些方法往往伴随着高昂的上下文切换成本。本文将探讨如何利用C++11中的原子操作和内存顺序来优化多线程编程,减少不必要的开销。 ... [详细]
  • ED Tree HDU4812 点分治+逆元
    这道题非常巧妙!!!我们进行点分治的时候,算出当前子节点的所有子树中的节点,到当前节点节点的儿子节点的距离,如下图意思就是当前节点的红色节点,我们要求出红色节点的儿子节点绿色节点, ... [详细]
  • 本文档旨在提供C语言的基础知识概述,涵盖常量、变量、数据类型、控制结构及函数定义等内容。特别强调了常量的不同类型及其在程序中的应用,以及如何正确声明和使用函数。 ... [详细]
  • HDU 2537 键盘输入处理
    题目描述了一个名叫Pirates的男孩想要开发一款键盘输入软件,遇到了大小写字母判断的问题。本文提供了该问题的解决方案及实现方法。 ... [详细]
  • 本文介绍了一种使用链剖分(Link-Cut Tree, LCT)来维护动态树结构的方法,特别是如何通过 LCT 来高效地管理子树的信息,如子树大小等。 ... [详细]
  • 本题旨在通过实现矩阵加法,加深对多维数组的理解。题目要求读取两个 n×m 的矩阵 A 和 B,并计算它们的和。 ... [详细]
  • 离散数学与C语言在逻辑推理中的应用
    本文探讨了如何结合离散数学的知识和C语言编程技巧,解决具体的逻辑推理问题。通过实例分析,展示了从问题抽象到程序实现的完整过程。 ... [详细]
  • 探讨如何在给定数组中寻找一个连续子数组,使其和至少达到指定值s,同时确保子数组长度最短。 ... [详细]
  • 深入理解Java字节码:方法调用详解
    本文详细介绍了Java字节码中的方法调用机制,通过具体示例解析了字节码如何处理方法调用及其参数传递。文章由Mahmoud Anouti撰写,原文链接:https://dzone.com/articles/introduction-to-java-bytecode ... [详细]
  • Lua字符串1.字符串常见形式字符串或串(String)是由数字、字母、下划线组成的一串字符。Lua语言中字符串可以使用以下三种方式来表示:•单引号间的一串字符。 ... [详细]
  • java datarow_DataSet  DataTable DataRow 深入浅出
    本篇文章适合有一定的基础的人去查看,最好学习过一定net编程基础在来查看此文章。1.概念DataSet是ADO.NET的中心概念。可以把DataSet当成内存中的数据 ... [详细]
  • 本文详细探讨了select和epoll两种I/O多路复用技术的内部实现原理,分析了它们在处理大量文件描述符时的性能差异,并通过具体示例代码展示了select的工作流程。 ... [详细]
author-avatar
小森林
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有