3蛮力法

1蛮力法2蛮力法蛮力法是基于计算机运算速度快这一特性，在解决问题时采取的一种“懒惰”策略。这种策略不经过（或者说经过很少）思考，把问题所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。蛮力策略应用：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等。比较常用还有枚举法、盲目搜索算法等。31枚举法枚举法（穷举法）是蛮力策略的一种表现形式，根据问题中条件将可能情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。通常从两个方面进行算法设计：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=1005算法1如下：main(){intx,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+zand100=5*x+3*y+z/3){print(thecocknumberis,x)；print(thehennumberis,y)；print(thechicknumberis,z);}}算法分析：此算法需要枚举尝试20*34*100=68000次。算法的效率显然太低。6算法设计2：在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量z就固定为100-x-y，无需再进行枚举了。此时约束条件只有一个：5*x+3*y+z/3=100.7main(){intx,y,z;for(x=1;x=20;x=x+1)for(y=1;y=33;y=y+1){z=100-x-y;if(zmod3=0and5*x+3*y+z/3=100){print(thecocknumberis,x)；print(thehennumberis,y)；print(thechicknumberis,z);}}}算法分析：以上算法只需枚举尝试20*33=660次。实现时约束条件限定Z能被3整除时，才判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术运算和条件判断，进一步提高了算法效率。8【例3.2】解数字迷ABCAB×ADDDDDD算法设计1：按乘法枚举1)枚举范围为：A：3——9,B：0——9,C：0——9六位数表示:A*10000+B*1000+C*100+A*10+B,尝试800次。2)约束条件为：每次尝试，先求六位数与A的积，再测试积的各位是否相同，若相同则找到了问题的解。测试积的各位是否相同比较简单的方法是，从低位开始，每次都取数据的个位，然后整除10，使高位的数字不断变成个位，并逐一比较。A=1,2时积不会得到六位数9算法1如下：main（）{intA,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=E1mod10;for(i=1;i=5;i++){G2=G1;E1=E1/10;G1=E1mod10;if(G1G2)break;}if(i=6)print(F，”*”，A，”=”，E);}}算法分析1：该算法的尝试范围是A：3—9，B：0—9，C：0—9。共尝试800次，不是一个好的算法。10算法设计2：将算式变形为除法：DDDDDD/A=ABCAB。此时只需枚举A：3——9D：1——9，共尝试7*9=63次。每次尝试，测试商的万位、十位与除数是否相同，千位与个位是否相同，都相同时为解。11main（）{intA,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(EmodA=0)F=E\A;if(F\10000=Aand(Fmod100)\10=A)and(F\1000=Fmod10)print(F，”*”，A，”=”，E);}}12蛮力法的表现形式非常多，如例2.6等。本节将通过蛮力策略，用算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，并与经过数学建模后的算法进行效率上的比较。2其它范例13【例3.3】编程打印有如下规律的n×n方阵。例如下图：使左对角线和右对角线上的元素为0，它们上方的元素为1，左方的元素为2，下方元素为3，右方元素为4，下图是一个符合条件的5阶矩阵。011102010422044203040333014构造趣味矩阵：经常用二维数组来解决根据趣味矩阵中的数据规律，设计算法把要输出的数据存储到一个二维数组中，最后按行输出该数组中的元素。基本常识：1）当对二维表按行进行操作时，应该“外层循环控制行；内层循环控制列”；反之若要对二维表按列进行操作时，应该“外层循环控制列；内层循环控制行”。2）二维表和二维数组的显示输出，只能按行从上到下连续进行，每行各列则只能从左到右连续输出。所以，只能用“外层循环控制行；内层循环控制列”。1523）用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；16算法如下：main(){inti,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=jori+j=n+1)a[i][j]=0;if(i+jn+1andij)a[i][j]=1;if(i+jn+1andij)a[i][j]=2;if(i+jn+1andij)a[i][j]=3;if(i+jn+1andij)a[i][j]=4;}for(i=1;i=n;i=i+1){print(“换行符”);for(j=1;j=n;j=j+1)print(a[i][j]);}}17【例3.4】大整数乘法问题在某些情况下，需要处理很大的整数，它无法在计算机硬件能直接允许的范围内进行表示和处理。若用浮点数来存储它，只能近似地参与计算，计算结果的有效数字会受到限制。若要精确地表示大整数，并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。请设计一个有效的算法，可以进行两个n位大整数的乘法运算。数据结构设计：首先用数组存储大整数数据，再将两个乘数和积都按由低位到高位逐位存储到数组元素中。算法设计：存储好两个高精度数据后，模拟竖式乘法，让两个高精度数据按位交叉相乘，并逐步累加即可得到精确的结果，用二重循环就可实现。18只考虑正整数的乘法，算法细节设计如下：1)对于大整数比较方便的输入方法是，按字符型处理，存储在字符数组s1、s2中，计算结果存储在整型数组a中。2)通过字符的ASCII码，数字字符可以直接参与运算，k位数字与j位数字相乘的表达式为：(s1[k]-48)*(s2[j]-48)（这是C语言的处理方法）。3)每一次数字相乘的结果位数是不固定的，而结果数组中每个元素只存储一位数字，所以用变量b暂存结果，若超过1位数则进位，用变量d存储。每次计算的表达式为：b=a[i]+(s1[k]-48)*(s2[j]-48)+d19main(){longb,c,d;inti,i1,i2,j,k,n,n1,n2,a[256];chars1[256],s2[256];input(s1);input(s2);for(i=0;i255;i++)a[i]=0;n1=strlen(s1);n2=strlen(s2);d=0;for(i1=0,k=n1-1;i1n1;i1++,k--){for(i2=0,j=n2-1;i2n2;i2++,j--){i=i1+i2;b=a[i]+(s1[k]-48)*(s2[j]-48)+d;a[i]=bmod10;d=b/10;}while(d0){i=i+1;a[i]=a[i]+dmod10;d=d/10;}n=i;}for(i=n;i=0;i--)print(a[i]);}i表示乘法正在运算的位，也是计算结果存储的位置。循环变量j、k分别是两个乘数字符串的下标。i1表示字符串str1由低位到高位的位数20算法分析：算法是以n1,n2代表两个乘数的位数，由算法中的循环嵌套知，算法的主要操作是乘法，算法的时间复杂度是O（n1*n2）。21【例3.5】狱吏问题某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1间转动一次；问通过n次后，哪些牢房的锁仍然是打开的？22算法设计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]为0时，该牢房的囚犯得到大赦。23main1(){int*a,i,j,n;input(n);a=calloc(n+1,sizeof(int));//申请存储空间for(i=1;i=n;i++)a[i]=1;for(i=1;i=n;i++)for(j=i;j=n;j=j+i)a[i]=1-a[i];for(i=1;i=n;i++)if(a[i]=0)print(i,”isfree.”);}算法分析1：以一次开关锁计算，算法的时间复杂度为n(1+1/2+1/3+……+1/n)=O(nlogn)。24问题分析2：转动门锁的规则可以有另一种理解，第一次转动的是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢房；第三次转动的是编号为3的倍数的牢房；……则狱吏问题是一个关于因子个数的问题。令d(n)为自然数n的因子个数，这里不计重复的因子，如4的因子为1，2，4共三个因子，而非1，2，2，4。则d(n)或为奇数，或为偶数，见下表:表3.1编号与因数个数的关系n12345678910111213141516……d(n)1223242434262445……数学模型2：d(n)有的为奇数，有的为偶数，由于牢房的门开始是关着的，这样编号为i的牢房，所含1——i之间的不重复因子个数为奇数时，牢房最后是打开的；反之，牢