深度优先搜索算法教程
[例 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;
