递归算法的应用

递归算法的应用摘要递归做为一种算法在程序设计语言中广泛应用。是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰。递归的主要优点在于：某些类型的算法采用递归比采用迭代算法要更加清晰和简单。例如快速排序算法按照迭代方法是很难实现的。还有其他一些问题，特别是人工智能问题，就依赖于递归提供解决方案。最后，有些人认为递归要比迭代简单递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点：(1)递归就是在过程或函数里调用自身。(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3)递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。(4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。。关键字：递归，程序设计，算法递归算法的应用目录1.绪论.............................................................11.1问题的提出..................................................11.2任务与分析..................................................12.0-1背包.........................................................22.1算法........................................................22.2程序........................................................23.Hanoi塔.........................................................43.1算法........................................................43.2程序........................................................44.棋子移动.........................................................54.1算法........................................................54.2程序........................................................65.全排列...........................................................85.1算法........................................................85.2程序........................................................96.约瑟夫..........................................................106.1算法.......................................................106.2程序.......................................................11结论...............................................................13参考文献...........................................................141递归算法的应用1.绪论1.1问题的提出一个过程或函数直接或间接地调用自己本身称为递归，现在我们以具体例题来分析讲解递归问题。递归的一般思路：把原问题分解为更小的子问题，再从子问题里慢慢寻找原问题的解。解题时首先列出递归表达式，然后用程序语言的方式把他表现出来。往往递归都可转化为循环或者模拟调用栈来实现，但是递归表达更利于理解。1.1.1递归应用递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。(Fibonacci函数)(2)问题解法按递归算法实现。(回溯)(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)1.1.2递归的缺点：递归算法解题的运行效率较低，在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。1.2任务与分析（1）0\1背包问题的递归算法和程序；（2）n阶hanoi塔的递归算法和程序；（3）棋子移动的递归算法和程序；（4）n个元素全排列的递归算法和程序；（5）约瑟夫问题的递归算法和程序；（6）总结可用递归算法实现的问题。2递归算法的应用2.0-1背包2.1算法find(i,tw,tv)//判定是否放入该物品//输入：当前物品编号i,当前背包重量tw和物品总价值tv//输出：问题解opt[1..n1]iftw+w[i]=limitWcop[i]←1ifin1-1find(i+1,tw+w[i],tv)elsefork=0ton1doopt[k]←cop[k]maxV←tvcop[i]←0iftv-v[i]maxVifin1-1find(i+1,tw,tv-v[i])elsefork=0ton1doopt[k]←cop[k]maxV←tv-v[i]2.2程序//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值voidfind(inti,doubletw,doubletv){intk;//物品i包含在当前方案的可能性if(tw+a[i].weight=limitW){3递归算法的应用cop[i]=1;if(in1-1)find(i+1,tw+a[i].weight,tv);else{for(k=0;kn1;++k)opt[k]=cop[k];maxV=tv;}}cop[i]=0;//物品i不包含在当前方案的可能性if(tv-a[i].valuemaxV){if(in1-1)find(i+1,tw,tv-a[i].value);else{for(k=0;kn1;++k)opt[k]=cop[k];maxV=tv-a[i].value;}}}4递归算法的应用图1、0-1背包3.Hanoi塔3.1算法hanoi(n,a,b,c)//Hanoi塔的移动算法//输入：盘子数n,起始、辅助和目标柱a、b、c//输出：Hanoi塔的移动步骤ifn=1output(a,c)elsehanoi(n-1,a,c,b)output(a,c)hanoi(n-1,b,a,c)3.2程序voidhanoi(intn,chara,charb,charc)/*递归函数*/{if(n==1)output(a,c);5递归算法的应用else{hanoi(n-1,a,c,b);/*a借助b到c*/output(a,c);hanoi(n-1,b,a,c);/*b借助a到c*/}}图2、Hanoi4.棋子移动4.1算法move(a[1..N3],n,m)//黑白棋的移动算法//输入：初始状态a[1..N3]、当前移动棋子规模n和总规模m//输出：棋子的移动过程6递归算法的应用ifn=4swap2(a[3],a[4],a[8],a[9])output(a,m)swap2(a[7],a[8],a[3],a[4])output(a,m)swap2(a[1],a[2],a[7],a[8])output(a,m)swap2(a[6],a[7],a[1],a[2])output(a,m)swap2(a[0],a[1],a[6],a[7])output(a,m)k3←k3+5returnswap2(a[n-1],a[n],a[2*n],a[2*n+1])output(a,m)k3←k3+1ifn4Error()returnswap2(a[n-1],a[n],a[2*n-2],a[2*n-1])output(a,m)move(a,n-1,m)k3←k3+14.2程序voidmove(inta[N3],intn,intm){if(n==4){swap2(&a[3],&a[4],&a[8],&a[9]);output(a,m);swap2(&a[7],&a[8],&a[3],&a[4]);output(a,m);swap2(&a[1],&a[2],&a[7],&a[8]);7递归算法的应用output(a,m);swap2(&a[6],&a[7],&a[1],&a[2]);output(a,m);swap2(&a[0],&a[1],&a[6],&a[7]);output(a,m);k3+=5;return;}swap2(&a[n-1],&a[n],&a[2*n],&a[2*n+1]);output(a,m);k3++;if(n4){printf(error!);return;}/**/swap2(&a[n-1],&a[n],&a[2*n-2],&a[2*n-1]);output(a,m);move(a,n-1,m);k3++;}8递归算法的应用图3、棋子移动5.全排列5.1算法perm(list,k,m)//全排列的生成算法//输入：初始数组a[1..n]、当前移动数编号k和总数目m//输出：全排列的所有组合ifkmfori=0tomdooutput(list[i])s←s+1elsefori=ktomdoswap(list[k],list[i])perm(list,k+1,m)swap(&list[k],&list[i])9递归算法的应用5.2程序voidperm(intlist[],intk,intm){inti;if(km){for(i=0;i=m;i++)printf(%d,list[i]);printf(\n);s++;}else{for(i=k;i=m;i++){swap(&list[k],&list[i]);perm(list,k+1,m);swap(&list[k],&list[i]);}}}10递归算法的应用图4、全排列6.约瑟夫6.1算法make(base,n,pos,c)//约瑟夫的模拟算法//输入：初始数组a[1..n]、总人数n、淘汰位置pos和当前淘汰人数c//输出：约瑟夫的整个过程j←0ifc=n-111递归算法的应用output(++c,pos+1)returnoutput(++c,pos+1)base[pos]←0whilej-k5ifbase[pos←(pos+1)modn]j←j+1make(base,n,pos,c)6.2程序voidmake(int*base,intn,intpos,intc){intj=0;if(c==n-1){printf(%d:thelastone_NO.%dwin!\n,++c,pos+1);return;//出口}printf(%d:NO.%d-out\n,++c,pos+1);//输出base[pos]=0;//踢掉while(j-k5)if(base[pos=(pos+1)%n])j++;//递归点,每次数到几这个k5就改到几make(base,n,pos,c);//递归}12递归算法的应用图5、约瑟夫13递归算法的应用结论本文的设计题目是:递归算法的应用，主要涉及背包问题的递归n阶hanoi塔的递归；棋子移动的递归出n个元素