C语言回溯算法

1、第五讲第五讲 回溯算法回溯算法 从问题的某一种可能出发从问题的某一种可能出发, , 搜索从这种情况出发所能达搜索从这种情况出发所能达到的所有可能到的所有可能, , 当这一条路走到当这一条路走到“ 尽头尽头 ”而没达到目的地的而没达到目的地的时候时候, , 再倒回再倒回上一个上一个出发点出发点, , 从另一个可能出发从另一个可能出发, , 继续搜索继续搜索. . 这这种不断种不断“ 倒回倒回 一步一步 寻找解的方法寻找解的方法, , 称作称作 回溯法回溯法 . . 回溯即是较简单、较常用的搜索策略回溯即是较简单、较常用的搜索策略,实质就是一种搜索实质就是一种搜索策略策略. .AB12345678

2、910从从A到到B的路线的路线:A-4-6-B如如:找一条从找一条从A到到B的路线的路线问题描述问题描述 学校放暑假时，信息学辅导教师有学校放暑假时，信息学辅导教师有n本书要分给参加培训的本书要分给参加培训的n个学生。如：个学生。如：A，B，C，D，E共共5本书要分给参加培训的张、刘、王、李、孙本书要分给参加培训的张、刘、王、李、孙5位学生，每人只能选位学生，每人只能选1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满表来分配书本，

3、希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。意。ABCDE张YY王YY刘YY孙Y李YY引例、借书问题引例、借书问题输入格式：第一行一个数输入格式：第一行一个数n（学生的个数，书的数量）（学生的个数，书的数量） 以下共以下共n行，每行行，每行n个个0或或1（由空格隔开），第（由空格隔开），第I行数据表行数据表示第示第i个同学对所有书的喜爱情况。个同学对所有书的喜爱情况。0表示不喜欢该书，表示不喜欢该书，1表示表示喜欢该书。喜欢该书。输出格式：依次输出每个学生分到的书号。输出格式：依次输出每个学生分到的书号。样例：样例：输入：输入：book.in50 0 1 1 01 1 0 0

4、 00 1 1 0 00 0 0 1 00 1 0 0 1输出：输出：book.out3 1 2 4 5分析分析: a:array1.maxn,1.maxnof 0.1; ai，j=1：第：第i个人喜欢第个人喜欢第j本书，本书，0表示不喜欢表示不喜欢 b:array1.maxnof integer; 记录分配方案记录分配方案:bi是第是第i个人借第个人借第bi本书本书 book:array1.maxnof boolean; booki:能否可以借第能否可以借第i本书本书,是否他人已借此书是否他人已借此书 初始初始:true,一旦有人借了一旦有人借了:就改为就改为:false算法设计算法设计:p

5、rocedure try(i:integer);要要搜索第搜索第i个人可以借的书个人可以借的书bi，说明前，说明前i-1个人已经借了书个人已经借了书 var j:integer; begin if i=n+1 then 输出结果；输出结果； for j:=1 to n do 搜索人搜索人i能够可以结的书能够可以结的书 if 第第i个人可以借第个人可以借第j 本书本书 then begin 记录下记录下bi=j; 标记第标记第j本数已被借：本数已被借：bookj=false; try(i+1); 删除书的被借标志删除书的被借标志; bookj=true；别人可以借；别人可以借 end; end;

6、const maxn=10;var a:array1.maxn,1.maxnof 0.1; b:array1.maxnof integer; book:array1.maxnof boolean; n:integer; procedure init;读入数据读入数据 var i,j:integer; begin fillchar(b,sizeof(b),0); fillchar(book,sizeof(book),true); readln(n); for i:=1 to n do for j:=1 to n do read(ai,j); end;procedure print; var i:

7、integer; begin for i:=1 to n-1 do write(bi, ); writeln(BN); end;procedure try(i:integer);要搜索第要搜索第i个人可以借的书个人可以借的书 var j:integer; begin if i=n+1 then print; 得到一组解得到一组解 for j:=1 to n do if bookj and (ai,j=1) then begin bi:=j; bookj:=false; try(i+1); bookj:=true; 回溯回溯 end; end;Begin init; try(1); end.回溯

8、算法：回溯算法：假设问题的解的形式为（假设问题的解的形式为（x1,x2,x3,.xn）,x1S1, x2S2, xnSn基本思路：基本思路： 若已有满足约束条件的部分解，若已有满足约束条件的部分解， 不妨设为（不妨设为（x1,x2,x3,xi），），In, 则添加属于则添加属于s(i+1)一个一个 x(i+1) ， 检查检查(x1,x2,xi,x(i+1)是否满足条件，满足了就继续是否满足条件，满足了就继续添加一个添加一个x(i+2) s(i+2)，若所有的，若所有的x(i+1) s(i+1)都不能得都不能得到部分解，即找不到一个到部分解，即找不到一个x(i+1) s(i+1)满足条件满足条件

9、, 就去掉当就去掉当前前xi，回溯到，回溯到(xi,x2,x(i-1)，添加那些未考察过的，添加那些未考察过的xi Si，看其是否满足约束条件，为此反复进行，直至得到解或证明看其是否满足约束条件，为此反复进行，直至得到解或证明无解。无解。递归算法框架递归算法框架: :procedure try(i);搜索第搜索第i个分量个分量Xi begin if i=n +1 then print; 得到一种解得到一种解 for Xi Si且使得（且使得（X1,X2,.,Xi-1,Xi）满足约束条件）满足约束条件 do begin 记录满足条件的记录满足条件的Xi; 添加相应的标志添加相应的标志; try(

10、i+1) 删除标志删除标志;恢复之前的状态恢复之前的状态,根据具体情况选择根据具体情况选择 end end问题描述问题描述 在在nn的国际象棋盘上，放置的国际象棋盘上，放置n个皇后，使任何一个皇后都不能吃个皇后，使任何一个皇后都不能吃掉另一个掉另一个,要使任何一个皇后都不能吃掉另一个，需满足的条件是：要使任何一个皇后都不能吃掉另一个，需满足的条件是：同一行、同一列、同一对角线上只能有一个皇后。求放置方法同一行、同一列、同一对角线上只能有一个皇后。求放置方法. 如如:n=4时时,有以下有以下2种放置方法种放置方法.*一一 N皇后问题皇后问题输出：输出：2 4 1 33 1 4 2方法一：分析方法

11、一：分析:1、问题解的形式：、问题解的形式： x:array 1.n of integer; xi:第第i个皇后放在第个皇后放在第i行，第行，第xi列，保证所有皇后不同行列，保证所有皇后不同行 问题的解变成求（问题的解变成求（x1，x2，。，。Xn）;xi 1,2,3,4 4皇后问题的解皇后问题的解： （2，4，1，3），）， （3，1，4，2）*2、放置第、放置第k(1=k=n)个皇后的递归算法：个皇后的递归算法： procedure try(k); 搜索第搜索第k个皇后所在的列个皇后所在的列xk=？,前前k -1个已放好个已放好,即已求得即已求得x1xk-1 var i:integer;

12、begin if k=n+1 then print（输出放置方案：数组（输出放置方案：数组x）; for i:=1 to n do 搜索第搜索第k个皇后所在的列个皇后所在的列j if 第第k个皇后能够放置在第个皇后能够放置在第i列列 then begin 放置第放置第k个皇后在第个皇后在第j列（列（xk=i）；）； try（k+1）；）； end; end;3、怎样判断：第、怎样判断：第k个皇后能否放置在第个皇后能否放置在第i列列 ：function place(k,i:integer):boolean; 第第k个皇后能否放在第个皇后能否放在第i列列var j:integer; begin f

13、or j:=1 TO K-1 do if (xj=i) or (abs(xj-i)=abs(j-k) then begin place:=false; exit end; place:=true; end;4、输出解：、输出解： procedure print; var j:integer; begin count:=count+1; write(answer,count,:); for j:=1 to n-1 do write(xj, ); writeln(xn); end;主程序主程序：try（1）方法二：方法二： 方法一的缺点：每次调用函数方法一的缺点：每次调用函数place（I,j）判

14、断第）判断第i个皇后能否放在个皇后能否放在j列时：列时： 有一个有一个for循环判断，显然浪费时间。循环判断，显然浪费时间。function place(k,i:integer):boolean;第第k个皇后能否放在第个皇后能否放在第i列列var j:integer; begin for j:=1 TO K-1 do if (xj=i) or (abs(xj-i)=abs(j-k) then begin place:=false; exit end; place:=true; end;var x:array1.n of integer; a:array1.n of boolean; 列控制标志

15、：列控制标志：true：可以放，：可以放，false：不能放：不能放 b:array2.2*n of boolean; 左上右下方斜线控制标志，左上右下方斜线控制标志，true：可以放，：可以放，false：不能放：不能放 c:array1-n.n-1of boolean; 左下右上方斜线控制标志，左下右上方斜线控制标志，true：可以放，：可以放，false：不能放：不能放初始时：初始时： fillchar(x,sizeof(x),0); fillchar(a,sizeof(a),true); fillchar(b,sizeof(b),true); fillchar(c,sizeof(c),

16、true);递归算法：递归算法： procedure try(i:integer); var j:integer; begin if i=n+1 then print else for j:=1 to n do if aj and bi+j and ci-j then begin xi:=j; aj:=false; 列控制标志列控制标志 bi+j:=false; 左上右下方斜线控制标志左上右下方斜线控制标志 ci-j:=false; 左下右上方斜线控制标志左下右上方斜线控制标志 try(i+1); 如果不能递归进行，既如果不能递归进行，既aj and bi+j and ci-j=false：

17、无法放置无法放置i+1个皇后，说明当前皇后个皇后，说明当前皇后i放置不正确，要回溯，消放置不正确，要回溯，消除标志除标志 aj:=true; bi+j:=true; ci-j:=true end; end;2、无重复元素的全排列、无重复元素的全排列输入输入n（=10）个不同的小些字母，输出）个不同的小些字母，输出n个字符的全部排列。个字符的全部排列。样例：样例：输入：输入：abc输出：输出：1:abc2:acb3:bac4:bca5:cab6:cbavar s:string; a:array1.10 of char;记录生成的排列序列记录生成的排列序列 can:array1.10 of 0.1

18、;是否已在排列序列中是否已在排列序列中 n,i,count:integer;procedure print; 输出一种排列输出一种排列 var i:integer; begin inc(count); write(count,:); for i:=1 to n do write(ai); writeln; end;procedure try(i:integer);开始搜第开始搜第i个字符个字符ai var j:integer; begin if i=n+1 then print;得到一种排列输出数组得到一种排列输出数组a for j:=1 to n do 找第找第i个字符个字符 if canj

19、=0 then 没进序列没进序列 begin ai:=sj; 加入到排序序列加入到排序序列 canj:=1; 标记已用了标记已用了 try(i+1); 找第找第i+1个字符个字符 canj:=0; 恢复标记，以便继续使用恢复标记，以便继续使用 end; end;Begin主程序主程序 readln(s); n:=length(s); fillchar(can,sizeof(can),0); count:=0; try(1);开始生成第一个字符开始生成第一个字符end.3、有重复元素的全排列、有重复元素的全排列输入输入n（0 then只要还有没拿的只要还有没拿的 begin ai:=j; 记下当

20、前字符记下当前字符 dec(numj); 当前字符数量减少一个当前字符数量减少一个 try(i+1); 找下一个找下一个 inc(numj); 恢复原来数量恢复原来数量 end; end;Begin主程序主程序 readln(s); n:=length(s); for i:=1 to n do inc(numsi); 统计出现的字符个数统计出现的字符个数 count:=0; try(1);找第一个找第一个end.4、自然数、自然数n的分解的分解分解（一）分解（一）输入自然数输入自然数n（n=ak)and(x-j=j) then begin inc(k); ak:=j; try(x-j); de

21、c(k); end; end;begin readln(n); count:=0; for i:=1 to n div 2 do先分解成先分解成i+（n-i）两）两项和项和 begin k:=1;分解项分解项 a1:=i; try(n-i); end;end.分解（二）分解（二）输入自然数输入自然数n和和m（n，m100），输出所有分解，分解后的每一项都不超大于），输出所有分解，分解后的每一项都不超大于m的。不能重复。如：的。不能重复。如：4=1+1+2；4=1+2+1;4=2+1+1 属于一种分解形式。属于一种分解形式。如：如：输入：输入：74输出：输出：1:7=1+1+1+42:7=1+1

22、+1+1+33:7=1+1+1+1+1+24:7=1+1+1+1+1+1+15:7=1+1+1+2+26:7=1+1+2+37:7=1+2+48:7=1+2+2+29:7=1+3+310:7=2+2+311:7=3+4begin readln(n); readln(m); count:=0; for i:=1 to n div 2 do begin k:=1; a1:=i; try(n-i); end;end.var n,m,k,i,count:integer; a:array1.100 of integer;procedure print(i,x:integer); var j:intege

23、r; begin inc(count); write(count,:,n,=); for i:=1 to k do write(ai,+); writeln(x); end;procedure try(x:integer);x是第是第k+1项项 var i,j:integer; begin if x=ak)and(x-j=j) then begin inc(k); ak:=j; try(x-j); dec(k); end; end;分解（三）分解（三）输入自然数输入自然数n和和m（n，m100），输出所有分解项数不超过），输出所有分解项数不超过m的所有形式。的所有形式。不能重复。如：不能重复。

24、如：4=1+1+2；4=1+2+1;4=2+1+1 属于一种分解形式。属于一种分解形式。如：如：输入：输入：7 4输出：输出：1:7=1+62:7=1+1+53:7=1+1+1+44:7=1+1+2+35:7=1+2+46:7=1+2+2+27:7=1+3+38:7=2+59:7=2+2+310:7=3+4var n,m,k,i,count:integer; a:array1.100 of integer;procedure print(i,x:integer); var j:integer; begin inc(count); write(count,:,n,=); for i:=1 to

25、k do write(ai,+); writeln(x); end;procedure try(x:integer);x是第是第k+1项项 var i,j:integer; begin if k=ak)and(x-j=j) then begin inc(k); ak:=j; try(x-j); dec(k); end; end;begin readln(n); readln(m); count:=0; for i:=1 to n div 2 do begin k:=1; a1:=i; try(n-i); end;end.算法的缺点？改进优化？if k=m then exit;剪枝优化剪枝优化

26、5、骑士的游历、骑士的游历设有下图所示的一个棋盘，在棋盘上的设有下图所示的一个棋盘，在棋盘上的A(0,0)点有一个中国象棋马，并点有一个中国象棋马，并约定马走的规则：约定马走的规则： 1、马只向右走；、马只向右走； 2、马走、马走“日日“字。字。找出所有从找出所有从A到到B的路径。的路径。输入：输入：B的坐标的坐标n，m（=15）。）。输出：所有走法。输出：所有走法。如：如：输入：输入：8 4输出：（输出：（0,0)(2 1)(4 0)(5 2)(6 0)(7 2)(8 4)1112345671231分析：分析：1、马跳的方向：马跳的方向： x:array1.4,1.2of integer=

27、(1,-2),(2,-1),(2,1),(1,2); 4个方向横向和纵向的增量。个方向横向和纵向的增量。2、记录马经过的位置坐标、记录马经过的位置坐标 a:array1.16,1.2of integer; 第第i步所在的位置，步所在的位置，1：横坐标：横坐标 2：纵坐标：纵坐标3、马的当前位置、马的当前位置：（：（aI,1,aI,2）下一个位置可能是：下一个位置可能是：(aI,1+xj,1,aI,2+xj,2) 1=j=0)and(ai,1+xj,1=0)and(ai,2+xj,2=m)判界判界 then begin ai+1,1:=ai,1+xj,1; ai+1,2:=ai,2+xj,2;

28、try(i+1); end; end;begin assign(output,house1.out); rewrite(output); readln(n,m); t:=0; a1,1:=0;起始位置作为第起始位置作为第1个点个点 a1,2:=0; try(1); close(output);end.求最少步到达求最少步到达B点。点。Best:最短路线，最短路线，a：临时得到的一个路线。：临时得到的一个路线。Min：最少步。：最少步。procedure try(i:integer); 搜索到当前第搜索到当前第i个点个点 var j:integer; begin if (ai,1=n) and

29、(ai,2=m)and(imin) then begin min:=i;best:=a;exit;end; 记下当前最短路径和最少步数记下当前最短路径和最少步数 if (ai,1n) or (ai,2m)and(i=min) then exit; 剪枝优化剪枝优化 for j:=1 to 4 do if (ai,1+xj,1=0)and(ai,1+xj,1=0)and(ai,2+xj,2(2,2)-(3,3)-(3,4)-(4,5)-(3,6)-(3,7)-(2,8)-(1,8)分析分析: a:array0.maxn+1,0.maxn+1of 0.1; 记录迷宫坐标记录迷宫坐标 b:array

30、0.maxn*maxn,1.2 of integer;记录路径记录路径 dx,dy:array1.8of integer; 方向位移方向位移 8个方向的位移个方向的位移: dx1:=0; dy1:=-1; dx2:=1; dy2:=-1; dx3:=1; dy3:=0; dx4:=1; dy4:=1; dx5:=0; dy5:=1; dx6:=-1; dy6:=1; dx7:=-1; dy7:=0; dx8:=-1; dy8:=-1;const maxn=20;递归算法递归算法 dx:array1.8of integer=(0,1,1,1,0,-1,-1,-1); dy:array1.8of

31、integer=(-1,-1,0,1,1,1,0,-1);var a:array0.maxn+1,0.maxn+1of 0.1; b:array0.maxn*maxn,1.2 of integer; n,m,k,i,j,x,y:integer; sum:longint;procedure init; begin for i:=0 to maxn+1 do for j:=0 to maxn+1 do ai,j:=1; readln(n); for i:=1 to n do for j:=1 to n do read(ai,j);End； procedure print(i:integer); v

32、ar j:integer; begin inc(sum); write(sum,:); for j:=1 to i do write(,bj,1, ,bj,2,); writeln; end;procedure try(i:integer); var k:integer; begin if (bi,1=1)and(bi,2=n) then print(i); for k:=1 to 8 do begin if abi,1+dxk,bi,2+dyk=0 then begin bi+1,1:=bi,1+dxk; bi+1,2:=bi,2+dyk; abi+1,1,bi+1,2:=1; try(i+

33、1); abi+1,1,bi+1,2:=0; end; end; end;Beginmain init; sum:=0; b1,1:=1; b1,2:=1; a1,1:=1; try(1); if sum=0 then writeln(no answer);end.7 7、细胞、细胞 一矩形阵列由数字一矩形阵列由数字0 0到到9 9组成组成, ,数字数字1 1到到9 9代表细胞代表细胞, ,细胞细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞, ,求给定矩形阵列的细胞个数。求给定矩形阵列的细胞个数。输入：整数输入：整数m,n(mm,n(m

34、行，行，n n列列) ) 矩阵矩阵输出：细胞的个数。输出：细胞的个数。样例样例: :输入输入: : 4 10 4 1002345000670234500067103456050010345605002045600671204560067100000000890000000089输出输出:4:40234500067103456050020456006710000000089program xibao;细胞个数细胞个数const dx:array1.4 of -1.1=(-1,0,1,0); dy:array1.4 of -1.1=(0,1,0,-1);var s:string; pic:arra

35、y1.50,1.80 of 0.1; m,n,i,j,num:integer; h:array1.4000,1.2 of byte; 队列：存细胞的坐标队列：存细胞的坐标procedure init; begin fillchar(pic,sizeof(pic),0);num:=0; fillchar(h,sizeof(h),0); assign(input,b5.in);reset(input); readln(m,n); for i:=1 to m do begin readln(s); for j:=1 to n do if sj=0 then pici,j:=0 else pici,j

36、:=1; end; close(input); end;procedure try(i,j:integer); var k,t,w,x,y:integer; begin pici,j:=0; for k:=1 to 4 do 沿细胞的上下左右四个方向搜索细胞沿细胞的上下左右四个方向搜索细胞 begin x:=i+dxk;y:=j+dyk; if (x=1) and (x=1) and (y=n) and (picx,y=1) then begin picx,y:=0; try(x,y); end;为细胞的入队为细胞的入队 end; end;Begin 主程序主程序 init; for i:=1

37、 to m do for j:=1 to n do if pici,j=1 then begin try(i,j);在矩阵中寻找细胞在矩阵中寻找细胞 inc(num); end; writeln(num);end.8、组合、组合（一）无重复元素的组合（一）无重复元素的组合输入一串小些字母（无重复字母），从中取出输入一串小些字母（无重复字母），从中取出k个字母，输出组合情况。个字母，输出组合情况。样例：样例：输入：输入：abcd3输出：输出：abcabdacdbcdvar s:string; n,m:integer; a:array1.10of char;procedure print; var

38、 j:integer; begin for j:=1 to m do write(aj); writeln; end;procedure try(i,k:integer); 搜索组合的第搜索组合的第p个元素，个元素，x搜索位置搜索位置 var j:integer; begin if i=m+1 then print; for j:=k to n do begin ai:=sj; try(i+1,j+1); end; end;begin readln(s); readln(m); n:=length(s); try(1,1);end.（二）、有重复元素的组合（二）、有重复元素的组合输入一串小些字

39、母（有重复字母），从中取出输入一串小些字母（有重复字母），从中取出k个字母，输出组合情况。个字母，输出组合情况。样例：样例：输入：输入：aabbcc4输出：输出：1:aabb2:aabc3:aacc4:abbc5:abcc6:bbcc9、数字排列、数字排列(li3.txt)在一个在一个N*N的棋盘上（的棋盘上（1=n=10),填入填入1,2,.,n*n共共n*n个数，个数，使得任意两个相临的数之合为素数使得任意两个相临的数之合为素数例如：例如： n=2 时，有时，有:1 2 4 3n=41 2 11 1216 15 8 513 4 9 146 7 10 3分析：分析： 逐行搜索逐行搜索1到到n

40、*n之间的数放在（之间的数放在（i，j）处，依次判断他与）处，依次判断他与上方（上方（i-1,j）的数和左边）的数和左边(I,j-1)的数的和是否为素数，是就放的数的和是否为素数，是就放(I,j)处，再放（处，再放（I,j+1);如果不是素数，则继续在如果不是素数，则继续在1到到n*n之间之间搜索搜索合适的数能放在合适的数能放在(I,j)处。处。const maxn=100;var i,j,k,m,n,x,y,nn:integer; p: array1.2*maxn*maxnof boolean; 素数表：素数表：pi=true :i是素数，是素数， pi=false :i不是素数不是素数 b

41、:array1.maxn,1.maxnof integer;坐标坐标 used:array1.maxn*maxnof boolean;检查是否该数是否用过检查是否该数是否用过筛选法创建素数表筛选法创建素数表procedure prime; var i,j,s:integer; begin fillchar(p,sizeof(p),true); p1:=false; for i:=2 to 3*n div 2 do 依次搜索素数依次搜索素数i并筛掉是并筛掉是i倍数的数倍数的数 if pi then begin j:=2*i; while j1 then if not (pbx-1,y+k) th

42、en ok:=false; if y1 then if not (pbx,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; 如果已放了如果已放了n*n个数，得出一种方法个数，得出一种方法 for i:=1 to n*n do if not(usedi) and ok(x,y,i) then begin bx,y:=i; usedi:=true; if y=n then try(x+1

43、,1,dep+1) 如果当前是最右边一列，则转到下一行首列如果当前是最右边一列，则转到下一行首列 else try(x,y+1,dep+1); 继续放当前行的下一列继续放当前行的下一列 usedi:=false;释放标志释放标志 end;end;procedure print; var i,j:integer;begin for i:=1 to n do begin for j:=1 to n do write(bi,j:4); writeln; end; halt;end;主程序：主程序：begin readln(n); prime; b1,1:=1; for i:=2 to n*n do usedi:=false; used1:=true; try(1,2,2); writeln(NO);end.const maxn=100