常用算法——深度优先有哪些信誉好的足球投注网站.doc

常用算法——深度优先有哪些信誉好的足球投注网站 我们在对一些问题进行求解时,会发现有些问题很难找到规律,或者根本无规律可寻。对于这样的问题,可以利用计算机运算速度快的特点,先有哪些信誉好的足球投注网站查找所有可能出现的情况,再根据题目条件从所有可能的情况中,删除那些不符合条件的解。 【例题1】有A、B、C、D、E 5本书,要分给张、王、刘、赵、钱5位同学,每人只能选1本。每个人都将自己喜爱的书填写在下表中。请你设计一个程序,打印出让每个人都满意的所有分书方案。 ┌──┬───┬───┬───┬───┬───┐ │ │ A│B│C│D│E│ ├──┼───┼───┼───┼───┼───┤ │ 张│ │ │ √ │ √ │ │ 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 └──┴───┴───┴───┴───┴───┘ ★问题分析 题目中每人喜爱哪本书是随意的,无规律可循,所以用穷举方法解较为合适。按穷举法的一般算法,可以暂不考虑一些条件,先求出满足部分条件的解,即可行解。然后,再加上尚未考虑的条件,从可行解中删除不符合这些条件的解,留下的就是问题的解。具体到本题中,我们可以先不考虑“让每人都满意”这个条件,这样,就只剩“每人选一本且只能选一本”这一个条件了。在这个条件下,可行解是5本书的所有全排列,一共有5!=120种情况。从这120种可行解中删去不符合“每人都满意”这一条件的解,剩下的就是本题的解。 为编程方便,我们用1、2、3、4、5分别表示这5本书。这5个数字的—种全排列就是5本书的一种分法。例如54321就表示第五本书(即E)分给张,第四本书(即D)分给王……,第—本书(即A)分给钱。 每个人“喜爱书表”,在程序中我们用二维数组Like[i,j]来表示,1表示喜爱,0表示不喜爱。排列的产生可以用穷举法,也可以用专门算法。 ★算法设计: 第一步:产生5个数字的一个全排列; 第二步:检查所产生的全排列是否符合“喜爱书表”,如果符合就输出; 第三步:检查是否所有排列都产生了,如果没有产生完,则返回第一步; 第四步:结束。 根据题目给出的条件,还可以对上面算法进行一些改进。例如产生一个全排列12345时,第一个数1表示将第一本书给小张。但从表中可以看出,这是不可能的,因为小张只喜欢第三、第四本书。也就是说,1X X X X这一类分法是不符合条件的。由此使我们想到,如果选定第一本书后,就立即检查一下是否符合条件,当发现第一个数的选择不符合条件时,就不必再产生后面的4个数了,这样做可以减少很多的运算量。换句话说,第一个数只在3和4中选择,这样就可以减少3/5的运算量。同理,在选定了第一个数后,其他4个数字的选择也可以用类似的方法处理,即选择第二个数后,立即检查是否符合条件。例如,第一个数选3,第二个数选4后,立即进行检查,发现不符合条件,就另选第二个数。这样就又把34XXX 一类的分法删去了,从而又减少了一部分运算量。 综上所述,改进后本题算法应该是:在产生各种排列时,每增加一个数字,就检查一下该数的加入是否符合条件,如不符合,就立刻换一个;若符合条件,则再产生下一个数。因为从第i本书到第i+1本书的寻找过程是相同的,所以可以用递归方法编程。 ★算法框图 PROCEDURE TRY(i);(递归算法) ┌─────────────────────┐ │ For j:= 1 to 5 do │ ├─┬───────────────────┤ │ │ T \第I个学生喜爱第j本书/ F │ │ ├────────────┬──────┤ │ │ 记录第 i个数 │ │ │ ├────────────┤ │ │ │ \ i= 5 / │ │ │ │ T \ / F │ │ │ ├─────┬──────┤ │ │ │打印一个解│ Try(i+1) │ │ │ ├─────┴──────┤ │ │ │ 删去第i 个数字 │ │ └─┴────────────┴──────┘我们用二维数组like存放“喜爱书表”,用集合flag存放已分出书的编号,数组book存储各人所分得书的编号,如book[1]=3,则表示第一个同学(小张)分得编号为3的书。 递归程序如下(程序中将小张的喜欢的书改成了A CD): Program