递归算法.ppt

1、搜索与回朔算法搜索与回朔是计算机解题中常用的算法，很多无法根据某种确定的计算法则来求解的问题，可以利用搜索与回朔方法求解。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索的过程中，一旦发现原来的选择是错误的，就退回一步重新选择，然后再继续向前探索，如此反复进行，直到得到解或证明无解为止。如迷宫问题，先可以随意选择一个前进方向，一步步向前探索，如果遇到死路了，先看看还有没有其它路可以走；如果没有，则返回一步，再看其它方向是否还有路可走。如果有路可走，就按原则不断往前探索，直到找到新的出路或返回原来入口处为止。这就是典型的边搜索边回朔的方法。递归回朔算法框架Procedure

2、 search(k:integer,参数表 )；beginif 到目的地 then 输出解else for i:=1 to 算符种数 do if 满足条件 then begin保存结果；search(k+1,参数表 ); 向前继续探索 回朔；end;end;例 1 素数环问题素数环：把 1-20这 20个数摆成一个环，要求相邻两个数的和是一个素数。【 算法分析 】这是一道回朔的题目。从 1开始，每个空位有 20种可能，只要填进去的数合法，即与前面数不同、与前面相邻数和为一个素数。注意最后还要判定第 20个数和第一个数的和是否为素数。【 算法程序 】program sushuhuan;var a

3、:array0.20 of integer; b:array0.20 of boolean;total:integer;function pd(x,y:integer):boolean;begini:=x+y; pd:=true;for j:=2 to trunc(sqrt(i) ) do if I mod j=0 then pd:=false;end;procedure search(t:integer);var i:integer;beginif t20 then beginif pd(a20,a1) then print;exit;end;for i:=1 to 20 doif pd(a

4、t-1,i) and bi thenbeginat:=i;bi:=false;search(t+1);bi:=true;end;end;beginfillchar(b,sizeof(b),true);total:=0;search(1);write(total);end.【 参考程序 】 Program pailie;type se=set of 1.100;var s:se;n,r,num:integer;a:array1.100 of integer;procedure print;var i:integer;begininc(num);for i:=1 to r do write(ai,

5、 );writeln;end;例 2 n个整数从中任意取 r个数的排列Procedure search(k:integer);var i:integer;beginif kr then begin print;exit;end;for i:=1 to n doif i in s thenbeginak:=i;s:=s-i;search(k+1);s:=s+i;end;end;beginreadln(n,r);s:=1.n;num:=0;search(1);writeln(num);end;1、任何一个大于 1的自然数 n，总可以拆分成若干个小于 n的自然数之和。如 n=7，共有14种拆分方法。

6、7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4Total=14上机练习【 参考程序 】 Procedure search(s,t:integer);var i:integer;beginif s8 then begin 输出； exit； end；for 第 i行皇后的位置 =1 to 8 do if 满足条件begin放置第 i个皇后；对放置皇后的位置进行标记；search（ i+1）；对放置的皇后的

7、位置释放标记，尝试下一个位置是否可行；end；End；【 算法分析 】显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后，可以从矩阵的特点上找到规律。从图可验证：如果在同一行，则行号相同；如果再同一列，则列号；如果同在 /斜线上，则行列值之和相同；如果同在 斜线上，则行列值之差相同。 建立标志数组 b1.8控制同一列只能有一个皇后，若两皇后在同一对角线上，则其行列坐标之和或行列坐标之差相等。1 2 3 4 5 6 7 812345678【 参考程序 】Program ex5_4;var a:array1.8 of integer;b:array-16.16 of boolea

8、n;c:array-16.16 of boolean;d:array-16.16 of boolean;sum:integer;Procedure print;var i:integer;Begininc(sum);write(sum=,sum);for i:=1 to 8 do write(ai:4);end;Procedure search(t:integer);var j:integer;Beginif t8 then begin print; exit;end;for j:=1 to 8 doif bj and ct+j and dt-j thenbeginat:=j;bj:=fals

9、e;ct+j:=false;dt-j:=false;search(t+1);bj:=true;ct+j:=true;dt-j:=true; end; end;Beginfillchar(b,sizeof(b),true);fillchar(c,sizeof(c),true);fillchar(d,sizeof(d),true);sum:=0;search(1);writeln(the total:,sum);End.3、马的遍历问题；【 问题描述 】 有一个半张中国象棋棋盘。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。编程将所经过路线打印出来。【 输出 】0， 02， 13， 31， 43， 52， 74， 80 112 3 4 5 6 7 8234马4、分配工作；【 问题描述 】 设有 A、 B、 C、 D、 E五人从事五项工作，每人只能从事一项，他们的效益如图。每人选择五项工作中一项，在各种选择的组合中，找到效益最高的一种组合输出。【 输出 】 A 5B 3Job1 job2 job3 job4 job5ABCDE13 11 10 4 713 10 10 8 55 9 7 7 415 12 10 11 510 11 8 8 4