蛮力法 (2)

18
13
#include <stdio.h> void main() {int A, B, C,D, E; for(A=0;A<2;A++) for(B=0;B<2;B++) for(C=0;C<2;C++) for(D=0;D<2;D++) for(E=0;E<2;E++) if(( A==0 && B+C+D+E==1) ||( A==1 && B+C+D+E!=0)) if((B==0 && A+C+D+E==4) ||(B==1 && A+C+D+E!=4)) if((C==0 && A+B+D+E==3)||(C==1 && A+B+D+E!=3)) if((D==0 && A+B+C+E==0) || (D==1 && A+B+C+E!=0)) { printf("A头上贴的是%s\n", A==0 ? "白纸" : "黑纸"); printf("B头上贴的是%s\n", B==0 ? "白纸" : "黑纸"); printf("C头上贴的是%s\n", C==0 ? "白纸" : "黑纸"); printf("D头上贴的是%s\n", D==0 ? "白纸" : "黑纸"); printf("E头上贴的是%s\n", E==0 ? "白纸" : "黑纸"); }
10
#include <stdio.h> main( ) {int A,B,C,D,E,F; for(A=3;A<=9;A++) for(D=1;D<=9;D++) { E= D*100000+D*10000+D*1000+D*100+D*10+D; if( E%A==0) { F=E/A; if(F/10000==A && F%100/10= =A && F/1000%10==F%10) printf( "%d*%d=%d\n", F,A,E); } } }
8
算法1如下： #include <stdio.h> void main() { int A,B,C,D,E,E1,F,G1,G2,i; for(A=3; A<=9; A++) for(B=0; B<=9; B++) for(C=0; C<=9; C++) { F=A*10000+B*1000+C*100+A*10+B; E=F*A; E1=E; G1=E1%10; for(i=1; i<=5; i++) { G2=G1; E1=E1/10; G1= E1%10; if(G1!=G2 ) break; } if(i==6) printf( "%d*%d=%d\n", F,A,E); } }
4
#include <stdio.h> 算法分析：此算 void main( ) 法需要枚举尝试 { int x,y,z; 20*34*100=68000 次。算法的效率 for(x=1;x<=20;x=x+1) 显然太低。 for(y=1;y<=33;y=y+1) for (z=1;z<=100;z++) if(x+y+z==100 && 5*x+3*y+z/3.0==100) { printf("the cock number is %d",x); printf("the hen number is %d", y); printf("the chick number is %d\n",z); } }
搜索算法等。
2
1 枚举法
枚举法（穷举法）是蛮力策略的一种表现形式，根据问题 中条件将可能情况一一列举出来，逐一尝试从中找出满足 问题条件的解。但有时一一列举出的情况数目很大，则需 要进一步考虑，排除一些明显不合理的情况，尽可能减少 问题可能解的列举数目。 通常从两个方面进行算法设计： 1）找出枚举范围：分析问题所涉及的各种情况。 2）找出约束条件：分析问题的解需要满足的条件，并 用逻辑表达式表示。
蛮力法
1
蛮力法
蛮力法是基于计算机运算速度快这一特性，在解决问题 时采取的一种“懒惰” 策略。这种策略不经过（或者说经过 很少）思考，把问题所有情况或所有过程交给计算机去一 一尝试，从中找出问题的解。 蛮力策略应用：选择排序、冒泡排序、插入排序、顺序 查找、朴素的字符串匹配等。比较常用还有枚举法、盲目
14
蛮力算法的优缺点：
（1）可以用来解决广阔领域的问题； （2）算法设计思想简单明了； （3）可以解决一些小规模的问题； （4）算法的效率不高，随着问题规模的增大，算法效率急剧下降； （5）问题规模过大时，在时间上，有些蛮力算法不可行。
15
作业1：用蛮力算法求解古堡问题
福尔摩斯到某古堡探险，看到门上写着一个奇怪的算式： ABCDE * ? = EDCBA 他对华生说：“ABCDE应该代表不同的数字，问号也代表某个数字！” 华生：“我猜也是！” 于是，两人沉默了好久，还是没有算出合适的结果来。 请你利用计算机的优势，找到破解的答案。 把 ABCDE 所代表的数字写出来。
12
1)枚举范围为： A：0—1,B：0—1,C：0—1 D:0—1 E:0—1 0表示贴白纸，1表示贴黑纸 2)约束条件为： A说：“我看见有三人额头上帖的是白纸，一人额头上帖的是黑纸” B说：“我看见其他四人额头上帖的都是黑纸” C说：“我看见有一人额头上帖的是白纸，其他三人额头上帖的是黑纸” D说：“我看见其他四人额头上帖的都是白纸” E说：什么也没有说 现在已知额头上帖黑纸的人说的都是谎话，额头上贴白纸的人说的都 是实话。 每次尝试五人的各种贴纸的方式，若某种方式满足约束条件则找到了问 题的解。
5
算法设计2：
在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量 z就固定为：100-x-y，无需再进行枚举了。 此时约束条件只有一个： 5*x+3*y+z/3=100。
6
#include <stdio.h> void main( ) { int x, y,z; for (x=1;x<=20;x=x+1) for (y=1;y<=33;y=y+1) { z=100-x-y; if( 5*x+3*y+z/3.0==100) { printf(" the cock number is %d",x); printf(" the hen number is %d", y); printf(" the chick number is %d\n",z); } } }
算法分析：以上算法只需枚举尝试20*33=660次。百度文库现时约束条 件为：“5*x+3*y+z/3.0=100”，进一步提高了算法效率。
7
【例】解数字迷
A B C A B × A D D D D D D 算法设计1：按乘法枚举 1)枚举范围为： A=1,2时积不 会得到六位 A：3—9,B：0—9,C：0—9 数 五位数表示:A*10000+B*1000+C*100+A*10+B,尝试800次。 2)约束条件为： 每次尝试，先求五位数与A的积，再测试积的各位是否相 同，若相同则找到了问题的解。 测试积的各位是否相同比较简单的方法是，从低位开始， 每次都取数据的个位，然后整除10，使高位的数字不断变 成个位，并逐一比较。
17
作业3：用蛮力算法求解四皇后问题
在一个国际象棋中的 的4*4的棋盘上放置4个皇后， 为了使其中
的任何2个皇后都不能相互“攻击”，希望寻求4个皇后的安全放置 位置。 该问题的不能相互“攻击”相当于要求任意两个皇后不能在
同一行、同一列或同一斜线上。求解可能的方案及方案数。
思考：
假设用一台计算机使用蛮力算法求解四皇后问题需要的时间为1秒 钟，那么使用该台计算机使用蛮力算法求解八皇后问题需要多少时间？
11
【例】贴纸问题 有A、B、C、D、E五人，每人额头上都帖了一张黑或白的纸。五人对 坐，每人都可以看到其他人额头上的纸的颜色。五人相互观察后， A说：“我看见有三人额头上帖的是白纸，一人额头上帖的是黑纸” B说：“我看见其他四人额头上帖的都是黑纸” C说：“我看见有一人额头上帖的是白纸，其他三人额头上帖的是黑纸” D说：“我看见其他四人额头上帖的都是白纸” E说：什么也没有说 现在已知额头上帖黑纸的人说的都是谎话，额头上贴白纸的人说的都 是实话，请你编写程序，求出这五个人谁的额头上帖的白纸，谁的额 头上帖的黑纸。
16
作业2：用蛮力算法求解比酒量问题
有一群海盗（不多于20人），在船上比拼酒量。过程如下：打开一瓶 酒，所有在场的人平分喝下，有几个人倒下了。再打开一瓶酒平分，又 有倒下的，再次重复...... 直到开了第4瓶酒，坐着的已经所剩无几， 海盗船长也在其中。当第4瓶酒平分喝下后，大家都倒下了。等船长醒 来，发现海盗船搁浅了。他在航海日志中写到：“.....昨天，我正好喝 了一瓶.......奉劝大家，开船不喝酒，喝酒别开船......” 请你根据这些信息，推断开始有多少人，每一轮喝下来还剩多少人。 如果有多个可能的答案，请列出所有答案，
算法分析1：该算法 的尝试范围是A： 3—9，B：0—9， C：0—9 。共尝试 800次，不是一个 好的算法。
9
算法设计 2 ：将算式变形为除法： DDDDDD/A=ABCAB 。 此时只需枚举 A：3—9 D： 1—9，共尝试7*9=63次。 每次尝试，测试商的万位、十位与除数是否相同， 千位与个位是否相同，都相同时为解。
3
【例】百钱百鸡问题。中国古代数学家张丘建在《算经》中提 出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值 钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何? 算法设计1： 通过对问题的理解，可能会想到列出两个三元一次方程， 去解这个不定解方程，就能找出问题的解。这确实是一种办法， 但这里我们要用“懒惰”的枚举策略进行算法设计： 设x，y，z分别为公鸡、母鸡、小鸡的数量。 尝试范围：由题意给定共100钱要买百鸡，若全买公鸡最多 买100/5=20只，显然x的取值范围1~20之间；同理，y的取值范 围在1~33之间，z的取值范围在1~100之间。 约束条件： x+y+z=100 且 5*x+3*y+z/3=100