递归与回溯算法

会计学1递归与回溯算法2也就是说，求解N!的过程可以用以下递归方法来表示：在这里，为了定义n!，就必须先定义(n-1)!，为了定义(n-1)!，又必须先定义(n-2)!……，上述这种用自身的简单情况来定义自己的方式称为递归定义。一个递归定义必须是有确切含义的，也就是说，必须一步比一步简单，最后是有终结的，决不允许无限循环下去。上面的例子中，当N=0时定义一个数1，是最简单的情况，称为递归的边界，它本身不再使用递归定义。与递推一样，每一递归都有其边界条件。但不同的是，递推是由边界条件出发，通过递推式来求值，而递归则是从自身出发来达到边界条件。第1页/共50页3递归的调用

在Pascal程序中，子程序可以直接自己调用自己或间接调用自己，则将这种调用形式称之为递归调用。其中，我们将前者的调用方式称为简单递归，后者称为间接递归。由于目前我们介绍、掌握的知识尚还无法实现间接递归，只有留待在以后的内容中我们再作介绍。本节只介绍直接递归。递归调用时必须符合以下三个条件：

（1）可将一个问题转化为一个新的问题，而新问题的解决方法仍与原问题的解法相同，只不过所处理的对象有所不同而已，即它们只是有规律的递增或递减。

（2）可以通过转化过程使问题回到对原问题的求解。

（3）必须要有一个明确的结束递归的条件，否则递归会无止境地进行下去。

下面我们通过一些例子，来解释递归程序的设计。第2页/共50页4programaa;vart:longint;n:integer;functionfac(n:integer):longint;beginifn=0thenfac:=1

elsefac:=fac(n-1)*n;end;例1：按照以上的分析，用递归的方法来求N！的解。程序如下：测试数据：输入：inputn=5输出：5!=120beginwrite('inputn=');read(n);ifn<0thenwriteln('n<0,dataerrer')elsebegint:=fac(n);writeln(n,'!=',t)endend.第3页/共50页5如图展示了程序的执行过程：

在这里，因为函数FAC的形参是值形参，因此每调用一次该函数，系统就为本次调用的值形参N开辟了一个存储单元，以便存放它的实参的值。也就是说，对于递归函数或递归过程，每当对它调用一次时，系统都要为它的形式参数与局部变量（在函数或过程中说明的变量）分配存储单元（这是一个独立的单元，虽然名字相同，但实际上是互不相干的，只在本层内有效），并记下返回的地点，以便返回后程序从此处开始执行。第4页/共50页6例2：读入一串字符倒序输出，以字符’&’为结束标志，用过程来实现。分析：由题意可知，读一串字符当然只能一个个地读入，要倒序输出，就要一直读到字符’&’。如输入的一段字符为ABCDEFGH&’，则倒序输出的结果应该是’&HGFEDCBA’。（1）读入一个字符；（2）读（该字符后的）子串并倒序输出；（3）然后输出读入字符（指（1）读入的字符）（4）在（2）中若子串是空（即遇字符’&’），表示子串已完，不再处理子串。

以上（2）表示一操作依赖另一操作，所以需要用递归调用。（4）表示已知操作（递归的终止）。第5页/共50页7程序如下：programaa;procedurereverse;varch:char;beginread(ch);ifch<>'&'thenreverse;write(ch);end;beginreverse;writeln;end.测试数据：输入：abcdefghijklmn&输出：&nmlkjihgfedcba第6页/共50页8例3：利用递归，将一个十进制整数K转化为N进制整数（N<=10）。测试数据：输入：K和N的值193输出：转化后的N进制整数201programaa;varn,k:integer;proceduretentok(k,n:integer);varr:integer;beginr:=kmodn;

k:=kdivn;ifk<>0thententok(k,n);write(r);end;beginread(k,n);tentok(k,n);writeln;end.第7页/共50页9递归的一般适合场合1．数据的定义形式是按递归定义的.如：裴波那契数列的定义为：Fn=Fn-1+Fn-2F1=0F2=1beginread(n);s:=fib(n);writeln(s);end.测试数据：输入：5输出：3programaa;varn:integer;s:longint;FunctionFIB(N:integer):integer;BeginIfn=1thenFIB:=0Elseifn=2thenFIB:=1

ElseFIB:=FIB(n-1)+FIB(n-2)

End;第8页/共50页10例如；著名的Hanoi塔（汉诺塔）问题。3．数据之间的结构关系按递归定义的例如：大家将在后面的学习内容中遇到的树的遍历、图的搜索等问题。2．问题的求解方法是按递归算法来实现的。第9页/共50页11判断运行结果1.programd1;

var

s,n:integer;

functionf(n:integer):integer;

begin

ifn=1thenf:=1

elsef:=n*n+f(n-1);

end;

begin

write('inputn:');readln(n);

s:=f(n);

writeln('f(',n,')=',s)

end.输入:inputn:3输出:练习一第10页/共50页122．programd2;

var

a,b:integer;

functionf(n:integer):integer;

begin

ifn=1thenf:=1

elseifn=2thenf:=2

elsef:=f(n-1)+f(n-2);

end;

begin

read(a);

b:=f(a);

writeln(b);

end.输入:4输出:第11页/共50页133．programd3;

var

a,b,c,d:integer;

procedurep(a:integer;varb:integer);

var

c:integer;

begin

a:=a+1;b:=b+1;c:=2;d:=d+1;

writeln('m',a,b,c,d);

ifa<3thenp(a,b);

writeln('n',a,b,c,d)

end;

begin

a:=1;b:=1;c:=1;d:=1;

writeln('x',a,b,c,d);

p(a,b);

writeln('y',a,b,c,d);

end.第12页/共50页14程序设计1.（文件名：d4.pas）利用递归过程，将一个十进制整数K转化为7进制整数。测试数据：输入：十进制数K19输出：7进制整数25第13页/共50页152.（文件名：d5.pas）楼梯有N阶台阶，上楼可以一步上一阶，也可以一步上二阶，计算共有多少种不同走法。测试数据：输入：输入N的值6输出：走法总数13提示：N=1f(1)=1N=2f(2)=2当N>=3时f(N)=f(N-1)+f(N-2)第14页/共50页16递归及其应用请计算ack(m,n)的值。(m,n<=5)例4:已知:ack(m,n)函数的计算公式如下:第15页/共50页17programaa;

var

m,n:longint;

a:longint;

functionack(m,n:longint):longint;

begin

ifm=0thenack:=n+1

elseifn=0thenack:=ack(m-1,1)

elseack:=ack(m-1,ack(m,n-1))

end;

begin

read(m,n);

a:=ack(m,n);

writeln(a);

end.测试数据输入：34输出：125第16页/共50页18其Pascal程序如下：例5:用辗转相除法求两个自然数m,n的最大公约数。思路：辗转相除法规定：求两个正整数m,n（m>=n）的最大公约数，应先将m除以n；求得余数r,如果等于零，除数n就是m,n的最大公约数；如果r不等于零，就用n除以r，再看所得余数是否为零。重复上面过程，直到余数r为零时，则上一次的余数值即为m,n的最大公约数。用其数学方式描述如下:第17页/共50页19programaa;

var

m,n,t:integer;

functionf(m,n:integer):integer;

varr:integer;

begin

if(mmodn)=0thenf:=n

else

begin

r:=mmodn;

f:=f(n,r);

end;

end;begin

readln(m,n);

ifm<nthen

begin

t:=m;

m:=n;

n:=t;

end;

writeln('gd=',f(m,n));end.测试数据输入：2018输出：gd=2第18页/共50页20functionfib(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，则有：第19页/共50页21

递归过程或函数直接（或间接）调用自身，但如果仅有这些操作，那么将会由于无休止地调用而引起死循环。因此一个正确的递归程序虽然每次调用的是相同的子程序，但它的参数、输入数据等均有所变化，并且在正常的情况下，随着调用的深入，必定会出现调用到某一层时，不再执行调用而是终止函数的执行。

递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决。

递归分解不是随意地分解，要保证“大问题”和“小问题”相似。例：采用递归算法求实数数组A[0..n]中的最小值。第20页/共50页22算法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]中的最小值。而求解子表中的最小值方法与总表相同，即再分别把它们分成两个更小的子表，如此不断分解，直到表中只有一个元素为止(该元素就是该表中的最小值)。第21页/共50页23functionmin(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;第22页/共50页24汉诺塔问题：

有n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。输出总共移动的次数及移动方案。ABC第23页/共50页25思路：假定可以通过某个过程把1针上面的N-1个盘搬到过渡针2中，然后把1针中剩下的1个盘移动到3针，然后再把过渡针2中的N-1个盘移到3针去，这样完成了移盘。思路是很明确的，我们把N个盘子移动问题转化成N-1个盘子移动问题，即如何从1针把N-1个盘子移动到2针和从2针把N-1个盘子移动到3针。同理，移N-1个盘子问题又可以进一步简化为移N-2盘子问题，这种简化过程实质就是一个递归过程。但递归过程不能永远递归下去，必须有边界条件令过程停止调用。显然，边界条件是当只有一个盘子时，仅需作最后一次移动即可。下面为移盘子游戏PASCAL程序。第24页/共50页26programaa;

var

n:integer;

proceduremove(n,a,b,c:integer);

begin

ifn=1then

writeln(a,'------>',c)

else

begin

move(n-1,a,c,b);

writeln(a,'------>',c);

move(n-1,b,a,c);

end;

end;

begin

readln(n);

move(n,1,2,3);

end.测试数据：输入:3输出:1------>31------>23------>21------>32------>12------>31------>3第25页/共50页27例7:数的计算（1）问题描述我们要求找出具有下列性质数的个数(包含输入的自然数n):先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:1、不作任何处理;2、在它的左边加上一个自然数,但该自然数不能超过原数的一半;3、加上数后,继续按此规则进行处理,直到不能再加自然数为止.第26页/共50页28样例:

输入:

6

满足条件的数为

6(此部分不必输出)

16

26

126

36

136输出:

6第27页/共50页29Var

ans,n:Longint;

proceduredfs(m:Longint);

vari:Longint;

begininc(ans);

fori:=1tomdiv2dodfs(i);

end;

begin

ans:=0;

read(n);

dfs(n);

writeLn(ans);

end.参考程序第28页/共50页30例8:反序输出（1）问题描述从键盘输入一个多位数(N>0,N位数小于等于9位），用递归方法把这个多位数颠倒过来输出。（2）问题解析由于N比较大，所以需要长整型。长整型的位数<=10位。（3）测试数据输入：12345678输出：87654321第29页/共50页31programaa;

varn:Longint;

procedurerd(number:Longint);

begin

write(numbermod10:1);

number:=numberdiv10;

ifnumber<>0thenrd(number);

end;

begin

write('inputn=');

readLn(n);

rd(n);

end.第30页/共50页321.(文件名:d6.pas)有一对雌雄兔，每两个月就繁殖各一对兔子。问N个月后共有多少对兔子？提示：测试数据:输入:10输出:55练习二第31页/共50页332.(文件名:d7.pas)计算组合数提示：测试数据:输入:62输出:15第32页/共50页343.前N项和（1）问题描述给定N(N>=1)，用递归的方法计算1+2+3+4+......+(N-1)+N,结果赋值给S。（2）测试数据输入:5输出:s=15第33页/共50页35程序提示:programaa;

vart:integer;s:Longint;

functionfac(n:integer):Longint;

begin

ifn=1thenfac:=

（1）

eLsefac:=

（2）;

end;

begin

read(t);s:=fac(t);

writeLn('s=',

（3）);

end.

第34页/共50页36搜索算法

对于给定的问题,如果有简明的数学模型揭示问题的本质,我们尽量用解析法求解；如果无法建立数学模型,或者即使有一定的数学模型,但采用数学方法解决有一定的困难,我们只好用模拟或搜索来求解。

尽管搜索的时间复杂度一般是指数级的，但在缺乏解决问题的有效模型时，搜索却是一种行之有效的解决问题的基本方法，而且使用搜索算法解决问题时，在实现过程中有很大的优化空间。信息学奥赛中考察搜索算法，一是考察选手算法运用能力，二是考察选手算法优化能力。枚举法（穷举法）回溯（深度优先搜索）广度优先搜索第35页/共50页37

回溯法是搜索算法中的一种控制策略，它是从初始状态出发，运用题目给出的条件、规则，按照深度优先搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。即：从问题的某一种可能出发,搜索从这种情况出发所能达到的所有可能,如果有路可以走下去，就走到下一个状态，继续按照这种规则搜索；当这一条路走到“尽头”而没达到目标状态的时候,再倒回上一个出发点,从另一个可能出发,继续搜索，直到达到目标状态。第36页/共50页38例：迷宫求解

从迷宫的入口进去后是如何找到出口的？

如果你不了解迷宫结构显然只能是摸索着前进，比如先往一个方向走，若走不通那就只能退回来再试试另一个方向。但在走的过程中你一定会有意识地“记住”你已经走过的路，否则你会被困在迷宫中永远也走不出来了。

计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。

先看两个动画演示的例子。第37页/共50页39第38页/共50页40第39页/共50页41由此，求迷宫中一条路径的算法的基本思想是：

若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索；

若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。

第40页/共50页42

例：n皇后问题

在n×n的国际象棋棋盘上，放置n个皇后，使任何一个皇后都不能吃掉另一个,需满足的条件是：

同一行、同一列、同一对角线上只能有一个皇后。求所有满足要求的放置方案。第41页/共50页43【分析】一、问题解的形式：x:array[1..n]ofinteger;//x[i]:第i个皇后放在第i行，第x[i]列，保证所有皇后不同行问题的解变成求（x[1]，x[2]，…，x[n]）4皇后问题的解：（2，4，1，3），（3，1，4，2）第42页/共50页44二、放置第k(1<=k<=n)个皇后的递归算法：Procedurettry(k);//搜索第k个皇后所在的列x[k],前k-1个已放好,即已求得x[1]…x[k-1]vari:integer;beginifk=n+1thenprint//输出放置方案：数组xelsefori:=1tondo//搜索第k个皇后所在的列iif第k个皇后能够放置在第i列thenbegin放置第k个皇后在第i列（x[k]=i）；

ttry（k+1）；

end;end;第43页/共50页45三、如何判断第k行的皇后能不能放在第i列：方法一：定义函数functionok(k,i:integer):boolean;varj:integer;beginforj:=1tok-1do

if(x[j]=i)or(x[j]+j=k+i)or(x[j]-j=k-i)thenbeginok:=false;exit;end;ok:=true;end;第44页/共50页46方法二：设置标志col:array[1..n]ofboolean;//col[i]=true，表示第i列上已有皇后left:array[2..2*n]ofboolean;//left[i]=true,表示行列和为i的对角线上已有皇后right:array[1-n..n-1]ofboolean;//right[i]=true,表示行列差为i的对角线上已有皇后programqueen;//递归算法constmaxn=10;varx:array[1..maxn]ofinteger;n,i,tot:integer;col:array[1..maxn]ofboolean;left:array[2..2*maxn]ofboolean;right:array[1-maxn..maxn-1]ofboolean;procedureout;//输出解vari:integer;beginfori:=1ton-1dowrite(x[i],'');writeln(x[n]);end;第45页/共50页47procedurettry(k:integer);//搜索第k个皇后的位置vari:integer;beginifk=n+1thenbegintot:=tot+1;out;end;//n个皇后都放置完毕，输出解fori:=1tondoifnot(col[i]orleft[k+i]orright[k-i])thenbeginx[k]:=i;//记录第k行皇后的位置col[i]:=true;left[k+i]:=true;right[k-i]:=true;ttry(k+1);//搜索第k+1个皇后的位置col[i]:=false;left[k+i]:=false;right[k-i]:=false;//回溯end;end;第46页/共50页48beginassign(input,’queen.in’);reset(input);assign(output,’queen.out’);rewrite(output);