算法设计与分析课件 38 组合_第1页
算法设计与分析课件 38 组合_第2页
算法设计与分析课件 38 组合_第3页
算法设计与分析课件 38 组合_第4页
算法设计与分析课件 38 组合_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

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

文档简介

算法设计与分析本节要点CONTENTS组合组合给定两个整数n和r，按照字典序输出自然数1到n中所有的r个数的组合。例如n=4，r=2，所有组合为：[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]。问题分析：本题是一个组合问题。组合不区分次序，[1,2]和[2,1]是一样的，而对于排列，[1,2]和[2,1]是不同的。本题要求枚举1~n区间中r个数的所有组合。组合例如，求解[1,2,3,4]中所有的2个数的组合。组合在回溯法中，使用for循环实现横向枚举，使用递归实现纵向扩展。（1）横向枚举开始：第一层枚举的开始为1，其它层枚举的开始为上一层选择的数字i再加上1，例如上一层选择的数字i=2，则当前层从3（i+1）开始枚举。结束：因为要选择r个数的组合，当余下的数不够r个时，就不需要枚举了。上图中需要选择2个数，第一层的最后一个分支已经不够2个数，无需枚举。因此枚举的结束位置为n-r+1。组合（2）纵向扩展在第一层，原问题是从1~n区间中选择r个数；在第二层，子问题变为从i+1~n区间中选择r-1个数，…，当k=0时，到达叶子，将递归过程中收集到的r个数作为一个组合放入答案数组中。组合（1）递归函数的参数2个参数：r，start，表示选择r个数，当前枚举的起点为start。（2）递归函数的结束条件从第一层开始，从区间中选择r个数，第二层，从区间中选择r-1个数，当递减到0时，递归结束。组合算法设计（3）横向枚举横向枚举用for语句实现，从开始start到结束n-r+1，逐个枚举即可。（4）纵向扩展纵向扩展，进入下一层时，第1个参数r变为r-1，第2个参数枚举的开始start变为i+1，i为上一层选择的数字。在进入下一层之前，用ans收集分支上的数，ans.push_back(i)，在递归结束回归时，需要还原现场，将该数弹出，ans.pop_back()。组合算法实现组合算法分析时间复杂度：本题组合数为C(n,r)，从树根到叶子得到一个组合的时间为O(r)，时间复杂度为O(r×C(n,r))。空间复杂度：

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

温馨提示

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

最新文档

评论

0/150

提交评论