2022年递归算法的应用 .pdf
《2022年递归算法的应用 .pdf》由会员分享,可在线阅读,更多相关《2022年递归算法的应用 .pdf(16页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、递归算法的应用摘要递归做为一种算法在程序设计语言中广泛应用。是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰。递归的主要优点在于:某些类型的算法采用递归比采用迭代算法要更加清晰和简单。例如快速排序算法按照迭代方法是很难实现的。还有其他一些问题,特别是人工智能问题,就依赖于递归提供解决方案。最后,有些人认为递归要比迭代简单递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。递归算法解决问
2、题的特点:(1)递归就是在过程或函数里调用自身。(2)在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。(3)递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。(4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。关键字:递归,程序设计,算法名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页,共 16 页 -递归算法的应用目录1.绪论.1 1.1 问题的提出.1 1.2 任务与分析.1 2.0-1背包.2 2.1 算法.2 2.2 程序.2 3.Hano
3、i塔.4 3.1 算法.4 3.2 程序.4 4.棋子移动.5 4.1 算法.5 4.2 程序.6 5.全排列.8 5.1 算法.8 5.2 程序.9 6.约瑟夫.10 6.1 算法.10 6.2 程序.11 结论.13 参考文献.14 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页,共 16 页 -1 递归算法的应用1.绪论1.1 问题的提出一个过程或函数直接或间接地调用自己本身称为递归,现在我们以具体例题来分析讲解递归问题。递归的一般思路:把原问题分解为更小的子问题,再从子问题里慢慢寻找原问题的解。解题时首先列出递归表达式,然后用程序语言的方式把他表现出来。往往递归都可转化为循环
4、或者模拟调用栈来实现,但是递归表达更利于理解。1.1.1 递归应用递归算法一般用于解决三类问题:(1)数据的定义是按递归定义的。(Fibonacci函数)(2)问题解法按递归算法实现。(回溯)(3)数据的结构形式是按递归定义的。(树的遍历,图的搜索)1.1.2 递归的缺点:递归算法解题的运行效率较低,在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。1.2 任务与分析(1)01 背包问题的递归算法和程序;(2)n 阶 hanoi塔的递归算法和程序;(3)棋子移动的递归算法和程序;(4)n 个元素全排列的递归算法和程序;(5)约瑟夫问题的递归算法和程
5、序;(6)总结可用递归算法实现的问题。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页,共 16 页 -2 递归算法的应用2.0-1 背包2.1 算法find(i,tw,tv)/判定是否放入该物品/输入:当前物品编号i,当前背包重量 tw 和物品总价值 tv/输出:问题解 opt1.n1 if tw+wi=limitW copi1 if imaxV if in1-1 find(i+1,tw,tv-vi)else for k=0 to n1 do optkcopk maxVtv-vi 2.2 程序/参数为物品 i,当前选择已经达到的重量和tw,本方案可能达到的总价值void find(i
6、nt i,double tw,double tv)int k;/物品 i 包含在当前方案的可能性if(tw+ai.weight=limitW)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页,共 16 页 -3 递归算法的应用copi=1;if(in1-1)find(i+1,tw+ai.weight,tv);else for(k=0;kmaxV)if(in1-1)find(i+1,tw,tv-ai.value);else for(k=0;kn1;+k)optk=copk;maxV=tv-ai.value;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页,共 16 页 -4 递归
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年递归算法的应用 2022 递归 算法 应用
限制150内