算法设计与分析 课件 3.4-递归 - 典型应用 - 整数划分_第1页
算法设计与分析 课件 3.4-递归 - 典型应用 - 整数划分_第2页
算法设计与分析 课件 3.4-递归 - 典型应用 - 整数划分_第3页
算法设计与分析 课件 3.4-递归 - 典型应用 - 整数划分_第4页
算法设计与分析 课件 3.4-递归 - 典型应用 - 整数划分_第5页
已阅读5页，还剩3页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析递归-典型应用-整数划分信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版将一个正整数表示成一系列正整数之和。正整数n的一个这种表示称为它的一个划分。正整数n的不同划分个数称为正整数n的划分数。问题：给出一个正整数n，求出其划分数。比如对于6而言,其划分共11种：6；5＋1；4＋2，4＋1＋1；3＋3，3＋2＋1，3＋1＋1＋1；2＋2＋2，2＋2＋1＋1，2＋1＋1＋1＋1；1＋1＋1＋1＋1＋1；在正整数n的所有不同划分中，将最大加数不大于m的划分个数记作q(n,m)。可以建立如下递归关系：（1）q(n,1)=1,n>=1;（2）q(n,m)=q(n,n),m>=n;（3）q(n,n)=1+q(n,n-1);（4）q(n,m)=q(n,m-1)+q(n-m,m)n>m>1;q(n,m)=1n=1orm=11+q(n,n-1)n=m>1q(n,n)n<mq(n,m-1)+q(n-m,m)n>m>1用一个形如intq(intn,intm)的函数表示输入：n,m输出：n的最大整数不超过m的划分数1、if(n<1)or(m<1)thenreturn0;2、if(n=1)or(m=1)thenreturn1;3、if(n<m)thenreturnq(n,n);4、if(m=n)thenreturnq(n,m-1)+1;5、returnq(n,m-1)+q(n-m,m);求正整数n的划分数p(n)，执行算法q(n,n)即可。问题：打印整数n的全部划分。用不完全归纳法：n=2可拆分成2=1+1n=3可拆分成3=1+2=1+1+1n=4可拆分成4=1+3=1+1+2=1+1+1+1=2+2……n=7可拆分成7=1+6=1+1+5=1+1+1+4=1+1+1+1+3=1+1+1+1+1+2=1+1+1+1+1+1+1=1+1+1+2+2=1+1+2+3=1+2+4=1+2+2+2=1+3+3=2+5=2+2+3=3+4分析：用数组a存储n的一种拆分,可得出以下递归关系对于一个n而言,按a[1]分类，有a[1]=1,a[1]=2,…,a[1]=n/2,共n/2大类拆分。每一类拆分时，a[1]=i,a[2]=n-i,从k=2，继续从a[k]开始拆分，a[k]能否再拆分取决于：

a[k]/2是否大于等于a[k-1]。split(intt)：对数a[t]进行划分输入：t表示要拆分的数在a数组中的下标输出：a[t]的划分1：fork=1totdo2：

输出a[k];3：j=t;L=a[j];4：fori=a[j-1]toL/2dobegin5：a[j]=i;a[j+1]=L-i;6：split(j+1);7：end;求n的划分fori=1ton/2dobegina[0]

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论