深度优先搜索算法教程 [例1] 有A、B、C、D、E 五本书，要分给张、王、刘、赵、钱五位同学，每人只能选一本。事先让每个人将自己喜爱的书填写在下表中。希望你设计一个程序，打印分书的所有可能方案，当然是让每个人都满意。（如下图所示） [分析] 这个问题中喜爱的书是随机的，没有什么规律，所以用穷举法比较合适。 为编程方便，用1、2、3、4、5 分别表示这五本书。这五本书的一种全排列就是五本书的一种分法。例如54321 表示第5 本书（即E）分给张，第4 本书（即D分给王，）„„第1 本书（即A 分给钱）。“喜爱书表”可以用二维数组来表示，1 表示喜爱，0 表示不喜爱。 [算法设计]： 1、产生 5 个数字的一个全排列； 2、检查是否符合“喜爱书表”的条件，如果符合就打印出来。 3、检查是否所有排列都产生了，如果没有产生完，则返回 1。 4、结束。 [算法改进]：因为张只喜欢第3、4 本书，这就是说，1* * * *一类的分法都不符合条件。所以改进后的算法应当是：在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立即换一个，符合条件后，再产生下一个数。因为从第i 本书到第i+1 本书的寻找过程是相同的，所以可以用递归算法。算法如下： procedure try(i); {给第I 个同学发书} begin for j:=1 to 5 do begin if 第i 个同学分给第j 本书符合条件 then begin 记录第i 个数; {即j 值} if i=5 then 打印一个解 else try(i+1); 删去第i 个数字 end end end; 具体如下： ◆递归算法 program zhaoshu; const like:array[1..5,1..5] of 0..1 =((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1)); name:array[1..5] of string[5] =('zhang','wang','liu','zhao','qian'); var book:array[1..5] of 0..5; flag:set of 1..5; c:integer; procedure print; var i:integer; begin inc(c); writeln('answer',c,':'); for i:=1 to 5 do writeln(name[i]:10,':',chr(64+book[i])); end; procedure try(i:integer); var j:integer; begin for j:=1 to 5 do if not(j in flag) and (like[i,j]>0) then begin flag:=flag+[j]; book[i]:=j; if i=5 then print else try(i+1); flag:=flag-[j]; book[i]:=0; end; end; {=====main====} begin flag:=[]; c:=0; try(1); readln; end. C 语言代码：...
VIP
