递归与回溯算法课件.ppt

《递归与回溯算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归与回溯算法1递归的定义：在定义一个过程或函数时出现调用本过程或本函数的成分，称为递归。若调用自身，称为直接递归。若过程或函数p调用过程或函数q，而q又调用p，则称为间接递归。在程序设计中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。递归的使用：1.定义是递归的Functionjiech(n:integer):longint;Beginifn=0thenjiech:=1elsejiech:=n*jiech(n-1);End;2Functionfib(n:integer):longint;Beginif(n=0)or(n=1)t

2、henfib:=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，则有：32.有些数据结构是递归定义的，采用递归的方法编写算法既方便又有效。如单链表：Ty

3、penode=^lnodelnode=recorddata:integer;next:node;end;求一个不带头结点的单链表head的所有data域之和的递归算法如下：Functionsum(head:node):integer;Beginifhead=nilthensum:=0elsesum:=head^.data+sum(head.next);End;43.问题的求解方法是递归的例：整数划分问题（版本1）为避免重复，记设f(n,k)为把正整数n分成k份的分法，那么：先考虑特殊情况：f(n,1)=1(n=n)f(n,n)=1(n=1+

4、1+……+1)当k>n时，f(n,k)=0(4)若n1=1，则：其分法为f(n-1,k-1)；5(5)若n1>1,则其分法为f(n-k,k)。6整数划分问题（版本2）在正整数n的所有不同的划分中，将最大加数n1不大于m的划分个数记作q(n,m)。我们可以建立如下的递归关系。(1)q(n,1)=1,n>=1；当最大加数n1不大于1时，任何正整数n只有一种划分形式，即：n=1+1+……+1。(2)q(n,m)=q(n,n)，m>=n；最大加数n1实际上不能大于n。因此，q(1,m)=1。(3)q(n,n)=1+q(n,n-1)；正整数n的划分有

5、n1=n的划分和n1<=n-1的划分组成。(4)q(n,m)=q(n,m-1)+q(n-m,m)，n>m>1;n的最大加数n1不大于m的划分由n1=m的划分和n1<=m-1的划分组成。7Functionq(n,m:integer):integer;Beginif(n<1)or(m<1)thenexit(0);if(n=1)or(m=1)thenexit(1);ifn

6、n,n)。}8递归过程或函数直接（或间接）调用自身，但如果仅有这些操作，那么将会由于无休止地调用而引起死循环。因此一个正确的递归程序虽然每次调用的是相同的子程序，但它的参数、输入数据等均有所变化，并且在正常的情况下，随着调用的深入，必定会出现调用到某一层时，不再执行调用而是终止函数的执行。递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决。递归分解不是随意地分解，要保证“大问题”和“小问题”相似。例：采用递归算法求实

7、数数组A[0..n]中的最小值。9算法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]中的最小值。而求解子表中的最小值方法与总表相同，即再分别把它们分成两个更小的子表，如此不断分解，直到表中只有一个元素为止(该元素就是该表中的最小值)。10fu

8、nctionmin(i,j:integer):real;varmid:integer;min1,min2:real;beginifi=jthenmin:=a[i]elsebegi