PASCAL递归与回溯算法.ppt

PASCAL递归与回溯算法.ppt

ID:48731506

大小:625.50 KB

页数:49页

时间:2020-01-20

PASCAL递归与回溯算法.ppt_第1页
PASCAL递归与回溯算法.ppt_第2页
PASCAL递归与回溯算法.ppt_第3页
PASCAL递归与回溯算法.ppt_第4页
PASCAL递归与回溯算法.ppt_第5页
资源描述:

《PASCAL递归与回溯算法.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、递归与回溯算法山东省实验中学王乃广1递归的定义:在定义一个过程或函数时出现调用本过程或本函数的成分,称为递归。若调用自身,称为直接递归。若过程或函数p调用过程或函数q,而q又调用p,则称为间接递归。在程序设计中,使用递归技术往往使函数的定义和算法的描述简洁且易于理解。例:functionjiech(n:integer):longint;beginifn=0thenjiech:=1elsejiech:=n*jiech(n-1);end;2functionfib(n:integer):longint;beginif(n=0)or(n=1)thenfib:=1elsefib:=fib(n-1

2、)+fib(n-2);end;爬楼梯时可以1次走1个台阶,也可以1次走2个台阶。对于由n个台阶组成的楼梯,共有多少种不同的走法?1个台阶:只有1种走法;2个台阶:有两种走法;(1+1;2)n个台阶(n>2),记走法为f(n):第1次走1个台阶,还剩(n-1)个台阶,走法为f(n-1);第1次走2个台阶,还剩(n-2)个台阶,走法为f(n-2)。所以,f(n)=f(n-1)+f(n-2)。定义f(0)=1,则有:3整数划分问题为避免重复,记设f(n,k)为把正整数n分成k份的分法,那么:先考虑特殊情况:f(n,1)=1(n=n)f(n,n)=1(n=1+1+……+1)当k>n时,f(n,

3、k)=0(4)若n1=1,则:其分法为f(n-1,k-1);4(5)若n1>1,则其分法为f(n-k,k)。5递归过程或函数直接(或间接)调用自身,但如果仅有这些操作,那么将会由于无休止地调用而引起死循环。因此一个正确的递归程序虽然每次调用的是相同的子程序,但它的参数、输入数据等均有所变化,并且在正常的情况下,随着调用的深入,必定会出现调用到某一层时,不再执行调用而是终止函数的执行。递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决。递归分解不是随意地分解,要保

4、证“大问题”和“小问题”相似。例:采用递归算法求实数数组A[0..n]中的最小值。6算法1:设f(a,i)为数组元素a[0]..a[i]中的最小值。当i=0时,有f(a,i)=a[0];假设f(a,i-1)已求出,则:算法2:设f(i,j)为a[i]..a[j]中的最小值。将a[0]..a[n]看作一个线性表,它可以分解成a[0]..a[i]和a[i+1]..a[n]两个子表,分别求得各自的最小值x和y,较小者就是a[0]..a[n]中的最小值。而求解子表中的最小值方法与总表相同,即再分别把它们分成两个更小的子表,如此不断分解,直到表中只有一个元素为止(该元素就是该表中的最小值)。7f

5、unctionmin(i,j:integer):real;varmid:integer;min1,min2:real;beginifi=jthenmin:=a[i]elsebeginmid:=(i+j)div2;min1:=min(i,mid);min2:=min(mid+1,j);ifmin1

6、总共移动的次数及移动方案。ABC9分析:在移动盘子的过程当中发现要搬动第n个盘子,必须先将前n-1个盘子从A柱搬到B柱去,再将A柱上的最后一个盘子搬到C柱,最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的,递归处理。当只需搬一个盘子时,直接搬动,不需要递归。10programhannuota;varn:integer;tot:longint;procedurehanoi(n:integer;s,t,d:char);beginifn>0thenbeginhanoi(n-1,s,d,t);tot:=tot+1;writeln(s,’->’,d);hano

7、i(n-1,t,s,d);end;end;beginreadln(n);tot:=0;hanoi(n,’A’,’B’,’C’);writeln(tot);end.11搜索算法对于给定的问题,如果有简明的数学模型揭示问题的本质,我们尽量用解析法求解;如果无法建立数学模型,或者即使有一定的数学模型,但采用数学方法解决有一定的困难,我们只好用模拟或搜索来求解。尽管搜索的时间复杂度一般是指数级的,但在缺乏解决问题的有效模型时,搜索却是一种行之有效的解决

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。