PASCAL递归和回溯算法.ppt

递归与回溯算法 山东省实验中学 王乃广 判断（x,y）位置能否放数值k的函数 function ok(x,y,k:integer):boolean; begin ok:=true; if x1 then if not (p[b[x-1,y]+k]) then 　　　　　　　　 ok:=false; if y1 then if not (p[b[x,y-1]+k]) then ok:=false; end; procedure try(x,y,dep:integer);//递归搜索（x,y）处放第 dep 个数 var i:integer; begin if dep=n*n+1 then print else //如果已放了n*n个数，得出一种方法 for i:=1 to n*n do if not(used[i]) and ok(x,y,i) then begin b[x,y]:=i; used[i]:=true; if y=n then try(x+1,1,dep+1) //如果当前是最右边一列，则转到下一行首列 else try(x,y+1,dep+1); //继续放当前行的下一列 used[i]:=false; //释放标志 end; end; procedure print; var i,j:integer; begin for i:=1 to n do begin for j:=1 to n do write(b[i,j]:4); writeln; end; halt; end; 主程序： begin readln(n); if n=1 then begin writeln(NO);halt;end; prime; b[1,1]:=1; for i:=2 to n*n do used[i]:=false; used[1]:=true; try(1,2,2); writeln(NO); end. 例 单词接龙(NOIP2000) 单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们己知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的龙（每个单词都最多在龙 中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。 【输入】 输入的第一行为一个单独的整数n(n=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表来“龙”开头的字母，你可以假定以此字母开头的龙一定存在。 【输出】 只需输出以此字母开头的最长的“龙”的长度。 【样例输入】 5 at touch cheat choose tact a 【样例输出】 23 //连成的“龙”为atoucheatactactouchoose 【分析】 深度优先搜索。第一步选择以某一个单词为龙头，确定以后将记录单词使用次数的数组清零，作为龙头的单词使用次数加一，然后每次判断是否可以再连接单词，如果可以，向下继续递归搜索，否则判断是否需要更新最优解。 【参考程序】 program shdj; var a:array[1..21] of integer; i,m,n,ans,k:longint; b:array[1..21] of string; s,dra:string; c:char; * * 递归的定义： 在定义一个过程或函数时出现调用本过程或本函数的成分，称为递归。若调用自身，称为直接递归。若过程或函数p调用过程或函数q，而q又调用p，则称为间接递归。 在程序设计中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。 例： function jiech(n:integer):longint; begin if n=0 then jiech:=1 else jiech:=n*jiech(n-1); end; function fib(n:integer):longint; begin if(n=0)or(n=1)then fib:=1 else fib:=fib(n-1)+fib(n-2); end; 爬楼梯时可以1次走1个台阶，也可以1次走2个台阶。对于由n个台