《2022年递归算法的应用 .pdf》由会员分享，可在线阅读，更多相关《2022年递归算法的应用 .pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 递归
7、算法的应用图 1、0-1 背包3.Hanoi 塔3.1 算法hanoi(n,a,b,c)/Hanoi 塔的移动算法/输入：盘子数 n,起始、辅助和目标柱a、b、c/输出：Hanoi 塔的移动步骤if n=1 output(a,c)else hanoi(n-1,a,c,b)output(a,c)hanoi(n-1,b,a,c)3.2 程序void hanoi(int n,char a,char b,char c)/*递归函数*/if(n=1)output(a,c);名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 16 页 -5 递归算法的应用else hanoi(n-1,a,c,b
8、);/*a 借助 b 到 c*/output(a,c);hanoi(n-1,b,a,c);/*b 借助 a 到 c*/图 2、Hanoi 4.棋子移动4.1 算法move(a1.N3,n,m)/黑白棋的移动算法/输入：初始状态 a1.N3、当前移动棋子规模n 和总规模 m/输出：棋子的移动过程名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 16 页 -6 递归算法的应用if n=4 swap2(a3,a4,a8,a9)output(a,m)swap2(a7,a8,a3,a4)output(a,m)swap2(a1,a2,a7,a8)output(a,m)swap2(a6,a7,a
9、1,a2)output(a,m)swap2(a0,a1,a6,a7)output(a,m)k3k3+5 return swap2(an-1,an,a2*n,a2*n+1)output(a,m)k3k3+1 if n4 Error()return swap2(an-1,an,a2*n-2,a2*n-1)output(a,m)move(a,n-1,m)k3k3+1 4.2 程序void move(int aN3,int n,int m)if(n=4)swap2(&a3,&a4,&a8,&a9);output(a,m);swap2(&a7,&a8,&a3,&a4);output(a,m);swap2
10、(&a1,&a2,&a7,&a8);名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 16 页 -7 递归算法的应用output(a,m);swap2(&a6,&a7,&a1,&a2);output(a,m);swap2(&a0,&a1,&a6,&a7);output(a,m);k3+=5;return;swap2(&an-1,&an,&a2*n,&a2*n+1);output(a,m);k3+;if(n m for i=0 to m do output(listi)ss+1 else for i=k to m do swap(listk,listi)perm(list,k+1,m
11、)swap(&listk,&listi)名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 16 页 -9 递归算法的应用5.2 程序void perm(int list,int k,int m)int i;if(k m)for(i=0;i=m;i+)printf(%d,listi);printf(n);s+;else for(i=k;i outn,+c,pos+1);/输出basepos=0;/踢掉while(j-k5)if(basepos=(pos+1)%n)j+;/递归点,每次数到几这个k5 就改到几make(base,n,pos,c);/递归 名师资料总结-精品资料欢迎下载
12、-名师精心整理-第 13 页，共 16 页 -12 递归算法的应用图 5、约瑟夫名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 16 页 -13 递归算法的应用结论本文的设计题目是:递归算法的应用，主要涉及背包问题的递归n 阶 hanoi塔的递归；棋子移动的递归出 n 个元素全排列的递归；出约瑟夫问题的递归名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 16 页 -14 递归算法的应用参考文献1 Anany Levitin,算法设计与分析基础。清华大学出版社2 宋文等编，算法设计与分析.重庆：重庆大学出版社，2001 3 周培德，算法设计与分析.北京：电子工业出版社，2000 4 王晓东，算法设计与分析.北京：电子工业出版社，2004 名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 16 页 -