蛮力法.

Presentation on theme: "蛮力法."— Presentation transcript:

1 蛮力法

2 蛮力法 蛮力法是基于计算机运算速度快这一特性，在解决问题时采取的一种“懒惰” 策略。这种策略不经过（或者说经过很少）思考，把问题所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。 蛮力策略应用：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等。比较常用还有枚举法、盲目搜索算法等。

3 1 枚举法 枚举法（穷举法）是蛮力策略的一种表现形式，根据问题中条件将可能情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。 通常从两个方面进行算法设计： 1）找出枚举范围：分析问题所涉及的各种情况。 2）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。

4 【例3.1】百钱百鸡问题。中国古代数学家张丘建在《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?
算法设计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

5 print("the hen number is", y)； print("the chick number is ",z); } }
算法1如下： main( ) { int x,y,z;   for(x=1;x<=20;x=x+1)     for(y=1;y<=34;y=y+1)       for(z=1;z<=100;z=z+1)           if(100=x+y+z and 100=5*x+3*y+z/3)      {print("the cock number is",x)； print("the hen number is", y)； print("the chick number is ",z); } } 算法分析：此算法需要枚举尝试20*34*100=68000次。算法的效率显然太低。

6 算法设计2： 在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量z就固定为100-x-y，无需再进行枚举了。   此时约束条件只有一个： 5*x+3*y+z/3=100.

7 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(z mod 3=0 and 5*x+3*y+z/3=100)                                                 {print("the cock number is",x)； print("the hen number is", y)； print("the chick number is ",z);}          } } 算法分析：以上算法只需枚举尝试20*33=660次。实现时约束条件限定Z能被3整除时，才判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术运算和条件判断，进一步提高了算法效率。

8 六位数表示:A*10000+B*1000+C*100+A*10+B,尝试700次。 2)约束条件为：
D D D D D D 算法设计1：按乘法枚举 1)枚举范围为： A：3——9,B：0——9,C：0——9 六位数表示:A*10000+B*1000+C*100+A*10+B,尝试700次。 2)约束条件为： 每次尝试，先求六位数与A的积，再测试积的各位是否相 同，若相同则找到了问题的解。 测试积的各位是否相同比较简单的方法是，从低位开始，每次都取数据的个位，然后整除10，使高位的数字不断变成个位，并逐一比较。 A=1,2时积不会得到六位数

9 if(G1<>G2 ) break; } if(i=6) print( F，”*”，A，”=”，E); }
算法分析1：该算法的尝试范围是A：3—9，B：0—9， C：0—9 。共尝试700次，不是一个好的算法。 算法1如下： 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 mod 10; for(i=1; i<=5; i++) { G2=G1; E1=E1/10; G1= E1 mod 10; if(G1<>G2 ) break; } if(i=6) print( F，”*”，A，”=”，E); }

10 算法设计2：将算式变形为除法：DDDDDD/A=ABCAB。此时只需枚举A：3——9 D：1——9，共尝试7

11 main（） {int A,B,C,D,E,F; for(A=3;A<=9;A++) for(D=1;D<=9;D++) { E = D* D*10000+D*1000+D*100+D*10+D; if(E mod A=0) F=E\A; if(F\10000=A and (F mod 100)\10=A) and (F\1000=F mod 10) print( F，”*”，A，”=”，E); }

12 【例3.3】编程打印有如下规律的n×n方阵。 例如下图：使左对角线和右对角线上的元素为0，它们上方的元素为1，左方的元素为2，下方元素为3，右方元素为4，下图是一个符合条件的5阶矩阵。

13 构造趣味矩阵：经常用二维数组来解决 根据趣味矩阵中的数据规律，设计算法把要输出的数据存储到一个二维数组中，最后按行输出该数组中的元素。
基本常识： 1）当对二维表按行进行操作时，应该“外层循环控制行； 内层循环控制列”；反之若要对二维表按列进行操作时，应该“外层循环控制列；内层循环控制行”。 2）二维表和二维数组的显示输出，只能按行从上到下连续进行，每行各列则只能从左到右连续输出。所以，只能用“外层循环控制行；内层循环控制列”。

14 3）用i代表行下标，以j代表列下标（除特别声明以后都遵守此约定），则对n*n矩阵有以下常识： 主对角线元素：i=j；
2 3）用i代表行下标，以j代表列下标（除特别声明以后都遵守此约定），则对n*n矩阵有以下常识： 主对角线元素：i=j； 副对角线元素：下标下界为1时i+j=n+1； 下标下界为0时i+j=n-1； 主上三角◥元素： i <=j； 主下三角◣元素： i >=j； 次上三角◤元素：下标下界为1时i+j<=n+1， 下标下界为0时i+j<=n-1； 次下三角◢元素：下标下界为1时i+j>=n+1， 下标下界为0时i+j>=n-1；

15 算法如下： main( ) {int i,j,a[100][100],n; input(n); for(i=1;i<=n;i=i+1) for(j=1;j<=n;j=j+1) {if (i=j or i+j=n+1) a [i][j]=0; if (i+j<n+1 and i<j) a [i][j]=1; if (i+j<n+1 and i>j) a [i][j]=2; if (i+j>n+1 and i>j) a [i][j]=3; if (i+j>n+1 and i<j) a [i][j]=4;} { print( “换行符”); for( j=1;j<=n;j=j+1) print(a[i][j]); }

16 【例3.5】狱吏问题 某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁, 每转动一次, 原来锁着的被打开, 原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。 转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1 间转动一次；问通过n次后，哪些牢房的锁仍然是打开的？

17 算法设计1： 1）用n个空间的一维数组a[n],每个元素记录一个锁的状 态，1为被锁上，0为被打开。 2）用数学运算方便模拟开关锁的技巧，对i号锁的一次开 关锁可以转化为算术运算：a[i]=1-a[i]。 3）第一次转动的是1，2，3，……n号牢房； 第二次转动的是2，4，6，……号牢房； 第三次转动的是3，6，9，……号牢房； …… 第i次转动的是i，2i，3i，4i，……号牢房，是起点为i，公差为i的等差数列。 4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最后当第i号牢房对应的数组元素a[i]为 时，该牢房的囚犯得到大赦。

18 main1( ) { int *a,i,j,n; input(n); a=calloc(n+1,sizeof(int)); //申请存储空间 for (i=1; i<=n;i++) a[i]=1; for (j=i; j<=n;j=j+i) a[i]=1-a[i]; if (a[i]=0) print(i,”is free.”); } 算法分析1：以一次开关锁计算，算法的时间复杂度为 n(1+1/2+1/3+……+1/n)=O(nlogn)。

19 问题分析2：转动门锁的规则可以有另一种理解，第一次转动的是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢房；第三次转动的是编号为3的倍数的牢房；……则狱吏问题是一个关于因子个数的问题。
令d(n)为自然数n的因子个数，这里不计重复的因子，如4的因子为1，2，4共三个因子，而非1，2，2，4。则d(n)或为奇数，或为偶数，见下表: 表3.1 编号与因数个数的关系 n …… d(n) …… 数学模型2：d(n)有的为奇数，有的为偶数，由于牢房的门开始是关着的，这样编号为i的牢房，所含1——i之间的不重复因子个数为奇数时，牢房最后是打开的；反之，牢房最后是关闭的。

20 算法设计2:　 1）算法是求出每个牢房编号的不重复的因子个数，当它为奇数时，这里边的囚犯得到大赦。 2）一个数的因子是没有规律的，只能从1——n枚举尝试。 main2( ) { int s,i,j,n; input(n); for (i=1; i<=n;i++) { s=1; for (j=2; j<=i;j=j++) if （i mod j=0） s=s+1; if （s mod 2 =1） print(i,”is free.”); } } 为什么从2开始？

21 算法分析2： 狱吏开关锁的主要操作是a[i]=1- a[i]；共执行n*(1+1/2+1/3+……+1/n)次，时间复杂度近似为O（n logn）。使用了n个空间的一维数组。算法2没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其主要操作是判断i mod j是否为0，共执行了1+2+3+……+n次，时间复杂度为O（n2 /2）。 蛮力法并不总是因为减少了人脑的思维，就一定是效率差的算法。对规模不是太大的问题，蛮力法还是一种比较好的算法策略。

22 表3.1 编号与因数个数的关系 n …… d(n) …… 数学模型3：仔细观察表3.1，发现当且仅当n为完全平方数时,d(n)为奇数；这是因为n的因子是成对出现的,也即当n=a*b且a≠b时，必有两个因子a，b; 只有n为完全平方数，也即当n=a2时,才会出现d(n)为奇数的情形。 算法设计3：只需找出小于n的平方数即可。

23 main3( ) {int s,i,j,n; input(n); for (i=1;i<=n;i++) if（i*i<=n） print(i,”is free.”); else break; } 结论：在对运行效率要求较高的大规模的数据处理问题时，必须多动脑筋找出效率较高的数学模型及对应算法。

24 3 蛮力法的优点 可以用来解决广阔领域的问题； 对于一些重要的问题，它可以产生一些合理的算法； 解决问题的实例很少时，它让你花费较少的代价；
3 蛮力法的优点 可以用来解决广阔领域的问题； 对于一些重要的问题，它可以产生一些合理的算法； 解决问题的实例很少时，它让你花费较少的代价； 可以解决一些小规模的问题； 可以作为其他高效算法的衡量标准。

25 小结 掌握蛮力法的基本思想：蛮力法是一种简单直接地解决问题的方法，通常直接基于问题的描述和所涉及的概念定义； 掌握蛮力策略的具体应用；
蛮力法的主要优点是它广泛的适用性和简单性；它的主要缺点是大多数蛮力算法的效率都不高。

26 螺旋阵：任意给定n值，按如下螺旋的方式输出方阵：
作业 螺旋阵：任意给定n值，按如下螺旋的方式输出方阵： n=3 输出： 2    9 6 3    4 5 n=4 输出： 2    3   

27 算法设计1： n=4 输出： 2    3    按照“摆放”数据的过程，逐层（圈）分别处理每圈的左侧、下方、右侧、上方的数据。以n=4为例详细设计如下： 把“1——12”看做一层（一圈）“13-16”看做二层……以层做为外层循环，下标变量为i。以上两个例子，n=3、4均为两层，用n\2表示下取整，（n+1）/2表示对n/2上取整。所以下标变量i的范围1——（n+1）/2。

28 n=4 输出： 2    3    i层内“摆放”数据的四个过程（四角元素分别归四个边）： 1）i列(左侧)，从i行到n-i行 （n=4，i=1时“摆放1，2，3”） 2）n+1-i行（下方），从i列到n-i列 （n=4，i=1时“摆放4，5，6”） 3）n+1-i列（右侧），从n+1-i行到i+1行 （n=4，i=1时“摆放7，8，9”） 4）i行（上方），从n+1-i列到i+1列 （n=4，i=1时“摆放10，11，12”） 四个过程通过四个循环实现，用j表示i层内每边中行或列的下标。

29 for(i=1;i<=n/2;i=i+1)
main( ) {int i,j,a[100][100],n,k; input(n); k=1; for(i=1;i<=n/2;i=i+1) {for( j=i;j<=n-i;j=j+1) { a [j][i]=k； k=k+1;} /左侧/ for( j=i;j<=n-i;j=j+1) { a [n+1-i][j]=k; k=k+1;} /下方/ for( j=n-i+1;j>=i+1;j=j-1){a[j][n+1-i]=k;k=k+1;} /右侧/ for( j=n-i+1;j>=i+1;j=j-1) {a[i][j]=k; k=k+1;} /上方/ } if (n mod 2=1) {i=(n+1)/2; a[i][i]=n*n;} for(i=1;i<=n;i=i+1) { print(“换行符”); for( j=1;j<=n;j=j+1) print(a[i][j]); n为奇数时，中间一层只有一个数据

30 算法设计2： n=4 输出： 2    3    约定：四角数据分别属于先处理的行或列；用k纪录行或列处理的元素个数，存放最外圈的情况如下： j=1 i=i n k=n //左侧 i=n j=j n k=n-1 //下方 j=n i=i-1 n k=n-1 //右侧 i=1 j=j-1 n k=n-2 //上方

31 2. 为用统一的表达式表示循环变量的范围，引入变量k，表示在某一方向上数据的个数，k初值是n，每当数据存放到左下角时，k就减1，又存放到右上角时，k又减1；此时k值又恰好是下一圈左侧的数据个数。 将向下和向上“摆放”数据时，行下标i的变化用统一表达式表示；也将向右和向左“摆放”数据时，列下标j的变化用统一表达式表示。引入符号变量t，t初值为1，表示处理前半圈：左侧i向下变大，j向右变大；t变为-1；表示处理后半圈：右侧i向上变小，j向左变小。则一圈内下标变化如下： j=1 i=i+t n k=n i=n j=j+t n k=k-1 t= -t 前半圈共2*k-1个 j=n i=i+t n i=1 j=j+t n k=k-1 t= -t 后半圈共2*k-1个

32 b[0]=0; b[1]=1; k=n; t=1; x=1; while x<=n*n
main( ) {int i,j,k,n,a[100][100],b[2],x,y; b[0]=0; b[1]=1; k=n; t=1; x=1; while x<=n*n {for (y=1;y<=2*k-1;y++) // t=1时处理左下角 { b[y/(k+1)]=b[y/(k+1)]+t; //t= -1时处理右上角 a[b[0]][b[1]]=x; x=x+1;} k=k-1; t=-t; } for( i=1;i<=n;i++) {print(“换行符”); for(j=1;j<=n;j++) print(a[i][j]); x模拟摆放的数据 y模拟半圈内数据的处理

33 算法说明： 在“算法设计”中，由“a[b[0]][b[1]]=x;”可知，数组元素b[0]表示存储矩阵的数组a的行下标，数组元素b[1]是数组a的列下标。为什么不用习惯的i,j作行、列的下标变量呢？使用数组元素作下标变量的必要性是什么？表达式“b[y/(k+1)]= b[y/(k+1)]+t;”的意义又是什么？ y作循环变量，模拟半圈内数据的处理过程。变化范围是1—2*k-1。在半圈里，当y=1—k时，是行下标在变化，列下标不变；此时y/(k+1)的值为0，确实实现了行下标b[0]的变化（加1或减1，由t决定）。当y=k+1—2*k-1时, 是行下标在不变，列下标在变化；此时y/(k+1)的值为1，确实实现了列下标b[1]的变化。这又验证了利用一维数组“便于循环”的技巧，当然这离不开对数组下标的构造。 综上所述，引入变量t，k和数组b后，通过算术运算将一圈中上下左右四种不同变化情况，归结构造了一个循环“不变式”。