正在进行安全检测...
发布时间：1714339063 来源：文档文库
小
中
大
字号：
§1 深度优先搜索 DFS
我们在对一些问题进行求解时，会发现有些问题很难找到规律，或者根本无规律可寻。对于这样的问题，可以利用计算机运算速度快的特点，先搜索查找所有可能出现的情况，再根据题目条件从所有可能的情况中，删除那些不符合条件的解。 【例题1】 有A、B、C、D、E 5本书，要分给张、王、刘、赵、钱5位同学，每人只能选1本。每个人都将自己喜爱的书填写在下表中。请你设计一个程序，打印出让每个人都满意的所有分书方案。 ┌──┬───┬───┬───┬───┬───┐ ││Ａ │ Ｂ │ Ｃ │ Ｄ │ Ｅ │ ├──┼───┼───┼───┼───┼───┤ │张│││√│√││00110 ├──┼───┼───┼───┼───┼───┤ │王│√│√│││√│11001 ├──┼───┼───┼───┼───┼───┤ │刘││√│√│││01100 ├──┼───┼───┼───┼───┼───┤ │赵││││√││00010 ├──┼───┼───┼───┼───┼───┤ │钱││√│││√│01001 └──┴───┴───┴───┴───┴───┘ ★问题分析
题目中每人喜爱哪本书是随意的，无规律可循，所以用穷举方法解较为合适。按穷举法的一般算法，可以暂不考虑一些条件，先求出满足部分条件的解，即可行解。然后，再加上尚未考虑的条件，从可行解中删除不符合这些条件的解，留下的就是问题的解。具体到本题中，我们可以先不考虑“让每人都满意”这个条件，这样，就只剩“每人选一本且只能选一本”这一个条件了。在这个条件下，可行解是5本书的所有全排列，一共有5!=120种情况。从这120种可行解中删去不符合“每人都满意”这一条件的解，剩下的就是本题的解。
为编程方便，我们用1、2、3、4、5分别表示这5本书。这5个数字的—种全排列就是5本书的一种分法。例如54321就表示第五本书(即E分给张，第四本书(即D分给王„„，第—本书(即A分给钱。
每个人“喜爱书表”，在程序中我们用二维数组Like[i,j]来表示，1表示喜爱，0表示不喜爱。排列的产生可以用穷举法，也可以用专门算法。 ★算法设计：
第一步：产生5
