算法分析TheAnalysisofAlgorithms.ppt_第1页
算法分析TheAnalysisofAlgorithms.ppt_第2页
算法分析TheAnalysisofAlgorithms.ppt_第3页
算法分析TheAnalysisofAlgorithms.ppt_第4页
算法分析TheAnalysisofAlgorithms.ppt_第5页
已阅读5页，还剩24页未读， 继续免费阅读

下载本文档

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

文档简介

算法分析和设计analysistenddesignofcomputeralgorithms第5章减法计算方法DecreaseandConquer，教学内容，减法方法和变种插入排序深度优先查找和生成宽度组合对象的算法减少因子算法可变大小算法要求减少方法的基本思路及其在一般问题中的应用。减法，减法技术利用一种关系：问题的给定实例的解决方案和同一问题的较小实例的解决方案之间的关系。建立此关系后，可以从上到下(递归)或从下到上(递归)使用。减法有三种大小的变体：1)减去常数2，再减去常数系数3。减法(1)治理技术，大小n的问题，大小n-1的子问题，子问题的解决方案，原始问题的解决方案，原始问题的解决方案，f (n)=anf (n-1) * an1f().在j-1)的精确位置Repeat A(j)，算法insertonsort(A0.n-1)/使用插入排序对给定阵列进行排序/输入：一个可排序阵列/输出：非连续阵列a for1吨-1地-1地；while(j0a NDAjv) aj 1 aj；jj-1； aJ1v；，89 | 45690293417，4589 | 6890293417，4567889 | 90293417，4588990 | 293417，29488990 | 3417，2934455.按an生成排序，算法JohnsonTrotter(n)/n生成阵列数/输入：一个正整数n/输出：1，n中的所有数组将第一个数组初始化为12 12.nwhile具有最大移动整数kdo，它将k及其箭头指向的相邻整数互换，以反转大于k的所有整数的方向。课后思考：按字母顺序a1a2.如何生成an之后的数组？子集生成，背包问题中给定项目集合的所有子集如何贫困？a=a1，a2，an=a1，a2，an-1 an，假币问题(Fake-Coin)，n1点W(n)=W(n/2) 1，W(1)=0，以及，偶数情况：J(2k)=2J(k)-1奇数情况：J(2k 1)=2J(k)1；二进制表示：J(6)=J(1102)=，J(n，m)=(J(n-1，m) m)modnJ(1，m)=0，可选问题(SelectionProblem)，包含问题说明n个元素，分割元素时，kj中具有小K元素的集合，K=j中的小K元素分割元素，选取问题，procedureselect (a，n，k) intern，Km1；r n 1；a(
人人文库> 全部分类> 应用文书 > 项目管理

温馨提示

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

最新文档

评论

0/150

提交评论