关于N个鸡蛋放在M个篮子里等系列问题详解

2024-04-04 14:38

本文主要是介绍关于N个鸡蛋放在M个篮子里等系列问题详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

N > M。求出满足如下要求的所有鸡蛋方法。要求:1.篮子不能为空;2.对于任意正整数n<=N, 能取x个篮子,使篮子里的鸡蛋数总和等于n。

 

实现方法一:

#include <cstring>
#include <iostream>//namespace al{
int min(int x, int y)
{return x<=y?x:y;
}
void egg (int n, int m, int *&a,int size)
{ // n是鸡蛋数,m是篮子数,a数组用来存储结果,size是a数组的大小for (int i=min((n+1)/2, a[m]); i>=1; --i){if (n<m) {continue;}else if (n == m){for (int j=m-1; j>=0; --j){a[j] = 1;}m = 1;n = 0;}if (m == 1) {if (n > 1) {continue;}else{for (int k=0; k<size; ++k)std::cout<<a[k]<<" ";std::cout<<std::endl;return ;}} else {a[m-1] = i;egg (n-i, m-1, a, size);}}
}
//} //namespace alint main()
{int n=20;int m=10;int* a = new int[m];a[0] = 1;int *&aa = a;for (int i=(n+1)/2; i>=1; --i){ //由于egg函数中有i=min((n+1)/2, a[m])这句,所以数组最后一位是a[m-1],不存在a[m],所以这里初始处理下memset(a, 0, m);a[m-1] = i;//al::egg (n-i, m-1, aa, m);}
}

 

实现方法二:

#include <iostream>   
using namespace std;   
long pow2[20];   
int N,M;   
int ans[1000];   
void solve( int n , int m , int Min )   
{   if(n == N && m == M)   {   for(int i=0;i<M;i++)   {   cout<<ans[i]<<" ";         }    cout<<endl;   return ;         }    else if( n + (M-m)*Min > N || N > pow2[M-m]*n + pow2[M-m]-1)   return ;   else  {   for(int i = Min; i <= n+1; i++)   {   ans[m] =  i;       solve(n+i,m+1,i);    }                  }             
}     
int main()   
{   pow2[0] = 1;   for(int i=1;i<20;i++)   {   pow2[i] = pow2[i-1]<<1;          }   cin>>N>>M;   if( M > N || pow2[M]-1 < N)   {   cout<<"没有有效解"<<endl;               }          solve( 0 , 0 , 1 );   system("pause");       return 0;      
}  


说明:

1.n + (M-m)*Min > N 剪枝条件:放n个鸡蛋后,后面的篮子里即使都放Min个,总鸡蛋数都超过了N个。说明鸡蛋太少了
2.当前篮子放n个鸡蛋,下一个篮子放鸡蛋的个数为Min~n+1,也就是最多放n+1个,再下一个篮子最多放2n+2,4n+4...(n+1)*2^(M-m-1)
   当前篮子放n个,如果以后按最多的放,所有篮子的鸡蛋总和如果小于N,说明鸡蛋太多,放不完,要剪枝。即 
    n+(n+1)(2^0+2^1+2^2+2^3+...+2^(M-m-1))<N
    化简得:
    N > pow2[M-m]*n + pow2[M-m]-1

    此外main函数里的判断pow2[M]-1 < N也是按照这个思路推导的。

实现方法三:

#include <iostream>
using namespace std;#define MAX_M   32
int ar[ MAX_M + 1 ];
int egg = 9 , box = 5;void place_egg( int n , int m , int max )
{if( m == 1 ){ar[ 1 ] = n;for( int i = 1 ; i <= box ; i++ )cout << " " << ar[ i ];cout << endl;return;}if( m > n || n > ( 1 << m ) - 1 )return;if( ( n + 1 ) / 2 < max )max = ( n + 1 ) / 2;for( int i = max ; i >= ( n + m - 1 ) / m ; i-- ){ar[ m ] = i;place_egg( n - i , m - 1 , i );}
}int main()
{place_egg( egg , box , egg );return 0;
}


实现方法四:

/** * 假设 n>m 并且 n小于100 * @author Jason * 2011.3.30 */  
public class Test {  private int m;  private int n;  private int eggs[];  private int numAnswer;  Test(){  m=10;  n=20;  numAnswer=0;  eggs =  new int[m];  for(int i=0;i<m;i++){  eggs[i]=0;  }  }  private void fill(boolean [] state, int step, int sum){  if(step>=m){  state[sum] = true;  return ;  }  fill(state,step+1,sum);  fill(state,step+1,sum+eggs[step]);  }  /** * 判断是否满足:任意一个小于N的正整数,都能由某几个篮子内蛋的数量相加的和得到 * 算法:暴力枚举所有篮子的组合 * @return */  private boolean judge(){  boolean [] state = new boolean [n+1];  for(int i=0;i<=n;i++){  state[i] = false;  }  fill(state,0,0);  for(int i=1;i<=n;i++){  if(!state[i]){  return false;  }  }  return true;  }  /** * 给每个篮子分鸡蛋,升序(后一个篮子的鸡蛋必须不小于前一个篮子,避免重复计算) * @param pre 前一个篮子鸡蛋数 * @param already 前step个篮子 已使用的鸡蛋数 * @param step 第step个篮子 */  public void solve(int pre,int already, int step){  if(step==m-1){  //最后一个篮子   eggs[m-1]=n-already;  //不符合条件   if(eggs[m-1]<pre)    return;  //判断是否满足:任意一个小于N的正整数,都能由某几个篮子内蛋的数量相加的和得到   if(judge()) {  for(int i=0;i<m;i++){  System.out.print(eggs[i]+" ");  }  System.out.println();  numAnswer++;  }  return ;  }  // 给第step个篮子装鸡蛋,pre 到 n-already 种可能   for(int i=pre; i<=n-already; i++){  eggs[step]=i;  //递归   solve(i,already+i,step+1);  }  }  public static void main(String arg []  ){  Test test = new Test();  test.solve(1,0,0);  System.out.println("可能情况的数量:"+test.numAnswer);  }  
}  



 



这篇关于关于N个鸡蛋放在M个篮子里等系列问题详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/876056

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)