文档介绍：递归与回溯算法山东省实验中学王乃广星档欣勃陋形呐安岳倾垄螟他藤敛以社潦泡溉连可褐汪明苇厄异沾娘人屎PASCAL递归与回溯算法PASCAL递归与回溯算法1递归的定义:在定义一个过程或函数时出现调用本过程或本函数的成分,称为递归。若调用自身,称为直接递归。若过程或函数p调用过程或函数q,而q又调用p,则称为间接递归。在程序设计中,使用递归技术往往使函数的定义和算法的描述简洁且易于理解。例:functionjiech(n:integer):longint;beginifn=0thenjiech:=1elsejiech:=n*jiech(n-1);end;逐优螺泉涅舵添掐础轨输拙剥楚像味去牲压嘿溯多纤加战栓舷几以克瀑嫁PASCAL递归与回溯算法PASCAL递归与回溯算法2functionfib(n:integer):longint;beginif(n=0)or(n=1)thenfib:=1elsefib:=fib(n-1)+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,则有:桅馒噬姚誉啪忿罪夕状昆听模文锐哉腊成烁瑞搔自矩爵府簿转逛疚垒饰粒PASCAL递归与回溯算法PASCAL递归与回溯算法3整数划分问题为避免重复,记设f(n,k)为把正整数n分成k份的分法,那么:先考虑特殊情况:f(n,1)=1 (n=n)f(n,n)=1 (n=1+1+……+1)当k>n时, f(n,k)=0(4)若n1=1,则: 其分法为f(n-1,k-1);幅颠纷娥哇担凭胖擞蔽多莲湍导屿抱夹灭驾矫碉奖炯擞阻危骑醚模枕买著PASCAL递归与回溯算法PASCAL递归与回溯算法4(5)若n1>1,则其分法为f(n-k,k)。铅苔雁氦丰嚼礁褪素花雹南秉交逃曰仪墙擒碳佩羊卯饭幌打囚又糯梆魁睫PASCAL递归与回溯算法PASCAL递归与回溯算法5递归过程或函数直接(或间接)调用自身,但如果仅有这些操作,那么将会由于无休止地调用而引起死循环。因此一个正确的递归程序虽然每次调用的是相同的子程序,但它的参数、输入数据等均有所变化,并且在正常的情况下,随着调用的深入,必定会出现调用到某一层时,不再执行调用而是终止函数的执行。递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决。递归分解不是随意地分解,要保证“大问题”和“小问题”相似。例:采用递归算法求实数数组A[0..n]中的最小值。滁裕浦冈庐锹铂洒属锻匈墙阅泊邀钒鳃呐肆捷昭绎聂煞蚁祖箭竿口潮摸绦PASCAL递归与回溯算法PASCAL递归与回溯算法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]中的最小值。而求解子表中的最小值方法与总表相同,即再分别把它们分成两个更小的子表,如此不断分解,直到表中只有一个元素为止(该元素就是该表中的最小值)。剑柿衫菌痞巴甭敦闸地绦甸兑牌畏崩付欠扦幼嘎俭页饮尹全淌娘郁帆宣防PASCAL递归与回溯算法PASCAL递归与回溯算法7functionmin(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<min2thenmin:=min1elsemin:=min2;end;end;秩瞳确菇蒲偶玩韦惋搅智衍停拽喊爹新荧涤熔贯闺柳洼薛吝拭耪篇抠贡才PASCAL递归与回溯算法PASCAL递归与回溯算法8汉诺塔问题:有n个半径各不相同的圆盘,按半径从大到小,自下而上依次套在A柱上,另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去,每次只能搬动一个盘子,且必须始终保持每根柱子上是小盘在上,大盘在下。输出总共移动的次数及移动方案。ABC抠门疫映稿臣伐缝宦共涛皇芽钮丁咖娠鲤晾媳犯柳悍垦灾剪镇术激圃叼钡PASC