ACM蛮力(穷举)

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,蛮力搜索,蛮力搜索,就像宝剑不是撬棍一样，科学也很少使用蛮力。,Edward Lytton(18031873),，,Leila,，,第二卷，第一章,蛮力搜索,定义,蛮力法（也叫穷举法）它要求设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法,蛮力搜索,定义,蛮力法是一种直接解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。,使用蛮力法的理由,显然蛮力法（也叫穷举法）不是一个最好的算法选择，但当我们想不出别的更好的办法时，它也是一种有效的解决问题的方法。,蛮力法逻辑清晰，编写程序简洁。,ACM,程序设计时间紧张，使用高效的、巧妙的算法可能忽略掉一些解，而测试数据往往针对你可能忽略的情况。,概 述,穷举法的基本思想是不重复、不遗漏地穷举所有,可能情况,(,问题的规模不是特别大,),，从中寻找满足条件的结果。,穷举法充分利用了计算机处理的高速特性，避免,复杂的逻辑推理过程，使问题简单化。,使用穷举法的关键是要确定正确的,穷举的范围,和满足,判断式,。,例,1,：百钱百鸡问题。 公鸡,5,文钱,1,只,母鸡,3,文钱,1,只,小鸡一文钱,3,只。,100,文钱如何卖,100,只鸡,?,条件分析,设买,x,只公鸡，,y,只母鸡，,z,只小鸡，则有：,x+y+z=100,5x+3y+z/3=100,且：,x,、,y,、,z,都是整数；,0 x 20,；,0 y 33,；,0 z 99,；,z,3,0,。,基本算法思想，,上述方程属于不定方程，解并不唯一，因此，可,用,穷举法,对,x,、,y,、,z,的所有组合情况，测试满足,条件的解。,具体是：,把,x,可能值,020,和,y,可能值,033,用二重循环来组,合，每个,x,和,y,组合都可得到,z,值，即,z=100-x-y,，,若,x,、,y,、,z,值使,5x+3y+z/3=100,成立，则该组,x,、,y,、,z,即为一组所求值。即：,穷举范围：,x : 020 , y : 033 , z : 100-x-y,判断式：,z%3=0&5*x+3*y+z/3=100,另一方法是：,把,x,可能值,020,、,y,可能值,033,和,z,可能值,099,用三重循环来组合，若,x,、,y,、,z,值使,5x+3y+z/3=100,和,x+y+z=100,同时成立，则该组,x,、,y,、,z,即为一组所求值。即：,穷举范围：,x : 020 , y : 033 , z : 099,判断式：,z%3=0&5*x+3*y+z/3=100&x+y+z=100,main( ),int,x, y, z, j=1;,printf(Possible,solutions to buy 100 fowls,whith,100,wen:n,);,for (x=0; x=20; x+),for (y=0; y=33; y+), z=100-x-y;,if (z%3=0&5*x+3*y+z/3=100), printf(%2d:cock=%-2d hen=%-2d,chicken=%-2dn, j, x, y, z);,j+;,运行结果：,Possible solutions to buy 100 fowls,whith,100,wen,:,1: cock=0 hen=25 chicken=75,2: cock=4 hen=18 chicken=78,3: cock=8 hen=11 chicken=81,4: cock=12 hen=4 chicken=84,例,2,：打印出所有的,“,水仙花数,”,。所谓,“,水仙花,数,”,是指一个三位正整数，其各位数字的立方和,等于该数本身，例如：,153=1,3,+5,3,+3,3,。,穷举范围：,即把所有的三位正整数,100999,按题,意一一进行判断。,判断式：,如果一个三位正整数,n,的百位、十位、,个位上的数字分别为,i,、,j,、,k,，,则判断式为：,n = i,3,+ j,3,+ k,3,如何分解三位数,n,的百位、十位、个位：,百位：,i = n/100;,十位：,j = ( n/10 )%10;,个位：,k = n%10;,#include ,stdio.h,main(),int,n,i,j,k;,for( n=100; n=999; n+ ), i = n /100;,j = ( n / 10 ) % 10 ;,k = n % 10 ;,if ( n= i*i*i + j*j*j + k*k*k ),printf(%d,= %d3 + %d3 + %d3n, n, i, j, k);,运行结果：,153,13 + 53 + 33,370,33 + 73 + 03,371,33 + 73 + 13,407,43 + 03 + 73,例,3,：,中国余数定理：“有物不知几何，三三数余一，,五五数余二，七七数余三，问：物有几何？”。,编程求,1000,以内所有解。,穷举范围：,整数,m,为：,11000,。,判断式：,m%3=1&m%5=2&m%7=3,#include ,stdio.h,main(),int,m, count=0;,for ( m=1; m=1000; m+ ),if ( m%3=1&m%5=2&m%7=3), printf(%5d,m);,count+;,if(count%5=0),printf(n,);,运行结果：,52 157 262 367 472,577 682 787 892 997,常用的蛮力法,1.,搜索所有的解空间。,2.,搜索所有的路径。,3.,直接进行计算。,搜索所有的解空间,案例,1,：假金币,案例,2,：现在的时间是多少？,案例,1,：假金币,False coin,Time Limit:3000MS,Memory Limit:10000K,Description,The Gold Barbank received information from reliable sources that in their last group of N coins exactly one coin is false and differs in weight from other coins (while all other coins are equal in weight). After the economic crisis they have only a simple balance available (like one in the picture). Using this balance, one is able to determine if the weight of objects in the left pan is less than, greater than, or equal to the weight of objects in the right pan. In order to detect the false coin the bank employees numbered all coins by the integers from 1 to N, thus assigning each coin a unique integer identifier. After that they began to weight various groups of coins by placing equal numbers of coins in the left pan and in the right pan. The identifiers of coins and the results of the weightings were carefully recorded. You are to write a program that will help the bank employees to determine the identifier of the false coin using the results of these weightings.,Input,The first line of the input file contains two integers N and K, separated by spaces, where N is the number of coins (2, or =. It represents the result of the weighting: means that the weight of coins in the left pan is greater than the weight of coins in the right pan, = means that the weight of coins in the left pan is equal to the weight of coins in the right pan.,Output,Write to the output file the identifier of the false coin or 0, if it cannot be found by the results of the given weightings.,Sample Input,5 3,2 1 2 3 4,1 1 4,=,1 2 5,=,Sample Output,3,假金币,时间限制,:3000MS,内存限制,:10000K,描述,“,Gold Bar,”,银行收到可靠消息：在前次的,N,个金币中有一枚重量不同的假金币,(,其他金币的重量都相同,),。经济危机之后他们只有一台天平可用。用这台天平，可以称量出左边托盘中的物体是轻于、重于或等于右边托盘中的物体。,为了分辨出假金币，银行职员将所有的金币编为,1,到,N,号。然后用天平称量不同的金币组合，每次仔细记载称量金币的编号和结果。,现在要求你编写一个程序，帮助银行职员根据称量记录来找出假金币的编号。,输入,第一行输入两个空格隔开的整数,N,和,K,，,N,是金币的总数,(2=N=1000 ),，,K,是称量的次数,(1=K=100),。,随后的,2K,行记录称量的情况和结果，连续两行记录一次称量：第一行首先是,Pi (1=Pi=N/2),，,表示两边托盘中放置的金币数目，随后是左边托盘中,Pi,个金币编号和右边托盘中,Pi,个金币编号，所有的数之间都由空格隔开；第二行用,，,=,和记录称量结果：,表示左边托盘中的金币比右边的重；,=,表示左右两边托盘中的金币一样重。,输出,输出假金币的编号。如果根据称量纪录无法确定假金币，输出,0,。,输入样例,5 3,2 1 2 3 4,1 1 4,=,1 2 5,=,输出样例,3,解题思路,这个题可以用蛮力搜索来解决,。,从题目描述，数据的规模不大，而时间限制足够大，选择暴力搜索可以使程序设计简单，而且因为是完全搜索，所以不会出现漏掉解的情况。,解题思路（续）,思路很简单：把所有的金币都试一遍。,Step 1:,依次假设,I,号金币是假的；,Step 2:,对称量的记录进行监测；如果假设与所有的记录都不矛盾，则有可能是假的。,Step 3:,如果有可能是假的金币只有,1,个，输出它的编号；否则，输出,0,。,数据结构与算法,不需要特殊的数据结构；,算法采用暴力搜索。,核心代码及解释,short,jd(int,j,int,*s, char c),/,函数判断假设,j,号金币是假的与称量结果是否矛盾,/s,是称量记录，其第一个元素是砝码个数,/c,是称量结果,m=s01;,for(i=f=1;i=m,/,判断本次称量有没有,j,号金币。,if(!f /,假设矛盾,return 1;,核心代码及解释,（续）,int,main(),int,num1001001; char s1000; /,输入内容,for(i=1,t=0;i=n;+i) /,暴力搜索所有可能,for(j=0;jk&,jd(i,numj,sj);+j,);,/,对所有的称量记录进行检测,if(j1)break;no=i; /t,保存嫌疑对象的个数,if(t-1)printf(0);else,printf(%d,no,);,案例,2,：,现在的时间是多少？,What time is it?,Time Limit:1000MS,Memory Limit:10000K,Description,An,accutron,shows time with four digits, from 0000 to 2359. Every digit is represented by 3*3 characters, including |s, _s and blanks. When the LCD screen works well, the digits look like the following:,_ _ _ _ _ _ _ _,| | | _| _| |_|_ |_ | |_| |_|,|_| |_ _| |_| |_| | |_| _|,There are two,accutrons,at hand. One shows the accurate time, and the other is 15 minutes late. For example, at 8:25am, the first,accutron,shows 0825, while the second shows 0810. Unfortunately, there is something wrong with the two LCD screens, namely some parts of the digits missed. Your task is to decide the accurate time, according to the fragmental digits showed on the two,accutrons,.,Input,The first line of the input is a single integer t (1 = t = 20), the number of test cases. Each case contains three lines, indicating the time on the accurate,accutron,and the time on the slow,accutron, separated by a blank column. (Please refer to the Sample Input.),Output,For each input, print the accurate time with four digits if it can be ensured, or otherwise the string Not Sure.,Sample Input,2,_ _ _ _ _,| _ _| | _ |,| _ |_ | | _ |_|,_ _ _ _ _ _,|_ _| | _| | |,| _ |_ | | | |_|,Sample Output,Not Sure,0825,现在的时间是多少？,时间限制,:1000MS,内存限制,:10000K,描述,电子钟用,4,位数字表示时间，从,0000,到,2359,。每位数字用一个,3*3,的字符（,|,、,_,和空格）来表示。如果,LCD,显示屏正常工作，,10,个数字显示如下：,_ _ _ _ _ _ _ _,| | | _| _| |_|_ |_ | |_| |_|,|_| |_ _| |_| |_| | |_| _|,现在有两个电子钟，一个显示正确的时间，另一个慢,15,分钟。如：上午,8:25,，第一个钟显示,0825,，同时第二个显示,0810,。 不幸的，两个钟的,LCD,显示屏有些问题，也就是说，有些数字的某些部分缺失。你的任务就是通过显示的剩余部分来决定正确的时间。,输入,第一行是一个整数,t (1 = t = 20),，,表明测试序列数目。每个测试序列包含,3,行，表示正确的时间和迟后的时间，有一个空列隔开。,(,参照输入样例。,),输出,如果能确定正确时间，输出该时间。否则输出,Not Sure,。,输入样例,2,_ _ _ _ _,| _ _| | _ |,| _ |_ | | _ |_|,_ _ _ _ _ _,|_ _| | _| | |,| _ |_ | | | |_|,输出样例,Not Sure,0825,解题思路,这个题可以用蛮力搜索来解决,。,从题目描述，数据的规模不大,(,为什么？每天只有,1440,分钟,),，选择暴力搜索可以使程序设计简单。,这题显示了暴力搜索的优势,解题思路（续）,首先将,LCD,管进行编码。,_ 0,|_| 123,|_| 456,0,123 172,补码：,0,5 155,将输入的内容进行编码。,解题思路（续）,检测某个时间是否是显示屏上的时间，只需要检测该时间与显示屏上显示的内容不冲突就可以了。如检测,1,时，,0,、,1,、,2,、,4,、,5,处就不应该有显示。如果有显示，意味显示的不可能是,1,。,所以只需将输入的内容与对应的数字作“,&”,运算。结果非,0,意味不可能是该数字。,数据结构与算法,不需要特殊的数据结构；,算法采用暴力搜索。,首先将输入的内容编码；,对于全天的,1440,分钟，进行比对；,如果只可能有一个时间，输出该时间。否则，“,not sure”,核心代码及解释,void,stime(int,t,int,*s)/,函数将时间,t,（,分钟）转换为数字序列,s,int,tt,;,tt,=t-15;if(tt0)tt+=1440;/tt,是晚,15,分钟,s3=t%10;s2=(t/10)%6;s1=(t/60)%10;s0=t/600; s7=tt%10;s6=(tt/10)%6;s5=(tt/60)%10;s4=tt/600;,/,如时间,t=0,s=0,0,0,0,2,3,4,5,核心代码及解释,（续）,Int,code(char *s1,char *s2,char *s3),/,将读入,3,行数据的数据编码,int,cod=0,i;char s10;,Strcat(s,s1);strcat(s,s2);strcat(s,s3);,For(I=0;I10;+I),if(sI!= )cod|=(1I);,Return cod;,核心代码及解释,（续）,short num10=4,55,66,18,49,24,8,54,0,16; /,数字的补码,int,main() ,scanf(%dn,&t,); while(t-),gets(s1);gets(s2);gets(s3); code(s1,s2,s3);/,编码,for(t1=0,ff=0;(t1=1440)t1+)/,这个循环遍历每一分钟,stime(t1,ss); /,时间转换为,8,个数字,for(k=0,f=1;k8+k),if(numssk&sk)f,=0;/,如果数字的补码与读入的数字非,0,，则不是该数字,if (ff=1) printf(“%d%d%d%dn”,hms0,hms1,hms2,hms3);else,printf(“Not,Suren”);,/,如果有且只有一个时间满足要求，输出该时间。,搜索所有的路径,案例,3,：矩阵,案例,3,：矩阵,Matrix,Time Limit:2000MS,Memory Limit:30000K,Description,Given an n*n matrix A, whose entries Ai,j are integer numbers ( 0 = i n, 0 = j n ). An operation SHIFT at row i ( 0 = i n ) will move the integers in the row one position right, and the rightmost integer will wrap around to the leftmost column.,You can do the SHIFT operation at arbitrary row, and as many times as you like. Your task is to minimize,max,0=j,n,Cj|Cj,=,0=i,n,A,i,j,Input,The input consists of several test cases. The first line of each test case contains an integer n. Each of the following n lines contains n integers, indicating the matrix A. The input is terminated by a single line with an integer 1. You may assume that 1 = n = 7 and |A,i,j,| 10,4,.,Output,For each test case, print a line containing the minimum value of the maximum of column sums.,Sample Input,2,4 6,3 7,3,1 2 3,4 5 6,7 8 9,-1,Sample Output,11,15,矩阵,时间限制,:2000MS,内存限制,:30000K,描述,给定一个,n*n,整数矩阵，定义对,I,行的,SHIFT,操作,( 0 = i n ),，,是将第,I,行,所有元素都右移一位，最右边的移到最左边。,你可以对任意行进行任意次,SHIFT,操作，使得：,max,0=j,n,Cj|Cj,=,0=i,n,A,i,j,最小化。,输入,第一行是一个整数,t (1 = t = 20),，,表明测试序列数目。每个测试序列包含,3,行，表示正确的时间和迟后的时间，有一个空列隔开。,(,参照输入样例。,),输出,输出最小值,。,输入样例,2,4 6,3 7,3,1 2 3,4 5 6,7 8 9,-1,输出样例,11,15,解题思路,这个题可以用蛮力搜索来解决,。,从题目描述，数据的规模不大（,n8,），,ACM,程序设计竞赛时间紧张，没有充裕的时间构筑高效、巧妙的算法。,解题思路（续）,把所有可能的移动都移动一遍，找到最小值。,数据结构与算法,不需要特殊的数据结构；,算法采用暴力搜索。,所有的可能情况都找出来：每一行都可能移,0,到,n-1,步，所以总的情况有,n,n,种，对每种情况进行编号。如,n=7,时，,7,进制的,0123456,表示第一行不动，第二行移动一次,核心代码及解释,void,inttoseries(int,i,int,*s),/,函数将序号化为移动的序列,for(k=0,j=i;kn-1;+k),sk=j%n;j/=n;,核心代码及解释,（续）,int,maxcolumn(int,*s),/,函数返回在指定移动情况下的最大值。,for(max=matrix00,i=1;in;+i),max+=matrixisi-1;,for(i=1;in;+i), for(j=1,temp=matrix0i;jmax)max=temp; return max;,核心代码及解释,（续）,int,main(), while(scanf(%d,&n),n+1),inttoseries(0,s);max=,maxcolumn(s,);,for(i=1;ik;+i) /,循环将遍历所有移动情况,inttoseries(i,s);temp,=,maxcolumn(s,);,if(tempmax)max=temp;,printf(%dn,max,); ,结果,Memory:28KTime:1140MS,Language:CResult:Accepted,这个效果就很差了，勉强通过。但在,ACM,中，,AC,就是一切。,直接进行计算,案例,5,：数的长度,案例,5,：数的长度,Time Limit:,1000ms,Memory Limit:,32768KB,Description,N! (N factorial) can be quite irritating and difficult to compute for large values of N. So instead of calculating N!, I want to know how many digits are in it. (,Remember,that N! = N * (N - 1) * (N - 2) * . * 2 * 1),Input,Each line of the input will have a single integer N on it 0 N 1000000 (1 million). Input is terminated by end of file.,Output,For each value of N, print out how many digits are in N!.,Sample Input,1,3,32000,1000000,Sample Output,1,1,130271,5565709,解题思路,这道题是蛮力法的反例，虽然蛮力法可以将他解出来；,另外，不知道巧妙的算法时，蛮力！,直接计算，这样的题还是很多的。,N!=1*2*N,Lg(N,!)=lg(2)+,lg(N,),数据结构与算法,不需要特殊的数据结构；,核心代码及解释,int,main(),while(scanf(%ld,&n,)!=EOF),sum=0.0;,for(i=2;i3)s=(c3+c1)/2.+n*(c3-c2)+1;,printf(%dn,s,);,Over,欢迎使用蛮力！,用好蛮力是进步的第一台阶！,