ACM之蛮力搜索(经典例题).ppt

蛮力搜索,主讲：吴昊,蛮力搜索,就像宝剑不是撬棍一样，科学也很少使用蛮力。EdwardLytton(18031873)，Leila，第二卷，第一章,蛮力搜索定义,蛮力法（也叫穷举法）它要求设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法,蛮力搜索定义,蛮力法是一种直接解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。,使用蛮力法的理由,显然蛮力法（也叫穷举法）不是一个最好的算法选择，但当我们想不出别的更好的办法时，它也是一种有效的解决问题的方法。蛮力法逻辑清晰，编写程序简洁。ACM程序设计时间紧张，使用高效的、巧妙的算法可能忽略掉一些解，而测试数据往往针对你可能忽略的情况。,常用的蛮力法,1.搜索所有的解空间。2.搜索所有的路径。3.列出解涉及的所有对象。4.直接进行计算。5.模拟和仿真。,搜索所有的解空间,案例1：假金币案例2：现在的时间是多少？,案例1：假金币,FalsecoinTimeLimit:3000MSMemoryLimit:10000K,Description,TheGoldBarbankreceivedinformationfromreliablesourcesthatintheirlastgroupofNcoinsexactlyonecoinisfalseanddiffersinweightfromothercoins(whileallothercoinsareequalinweight).Aftertheeconomiccrisistheyhaveonlyasimplebalanceavailable(likeoneinthepicture).Usingthisbalance,oneisabletodetermineiftheweightofobjectsintheleftpanislessthan,greaterthan,orequaltotheweightofobjectsintherightpan.Inordertodetectthefalsecointhebankemployeesnumberedallcoinsbytheintegersfrom1toN,thusassigningeachcoinauniqueintegeridentifier.Afterthattheybegantoweightvariousgroupsofcoinsbyplacingequalnumbersofcoinsintheleftpanandintherightpan.Theidentifiersofcoinsandtheresultsoftheweightingswerecarefullyrecorded.Youaretowriteaprogramthatwillhelpthebankemployeestodeterminetheidentifierofthefalsecoinusingtheresultsoftheseweightings.,Input,ThefirstlineoftheinputfilecontainstwointegersNandK,separatedbyspaces,whereNisthenumberofcoins(2,or=.Itrepresentstheresultoftheweighting:meansthattheweightofcoinsintheleftpanisgreaterthantheweightofcoinsintherightpan,=meansthattheweightofcoinsintheleftpanisequaltotheweightofcoinsintherightpan.,Output,Writetotheoutputfiletheidentifierofthefalsecoinor0,ifitcannotbefoundbytheresultsofthegivenweightings.,SampleInput,5321234114=125=,SampleOutput,3,假金币,时间限制:3000MS内存限制:10000K,描述,“GoldBar”银行收到可靠消息：在前次的N个金币中有一枚重量不同的假金币(其他金币的重量都相同)。经济危机之后他们只有一台天平可用。用这台天平，可以称量出左边托盘中的物体是轻于、重于或等于右边托盘中的物体。为了分辨出假金币，银行职员将所有的金币编为1到N号。然后用天平称量不同的金币组合，每次仔细记载称量金币的编号和结果。现在要求你编写一个程序，帮助银行职员根据称量记录来找出假金币的编号。,输入,第一行输入两个空格隔开的整数N和K，N是金币的总数(2，=和记录称量结果：表示左边托盘中的金币比右边的重；=表示左右两边托盘中的金币一样重。,输出,输出假金币的编号。如果根据称量纪录无法确定假金币，输出0。,输入样例,5321234114=125=,输出样例,3,解题思路,这个题可以用蛮力搜索来解决。从题目描述，数据的规模不大，而时间限制足够大，选择暴力搜索可以使程序设计简单，而且因为是完全搜索，所以不会出现漏掉解的情况。,解题思路（续）,思路很简单：把所有的金币都试一遍。Step1:依次假设I号金币是假的；Step2:对称量的记录进行监测；如果假设与所有的记录都不矛盾，则有可能是假的。Step3:如果有可能是假的金币只有1个，输出它的编号；否则，输出0。,数据结构与算法,不需要特殊的数据结构；算法采用暴力搜索。,核心代码及解释,shortjd(intj,int*s,charc)/函数判断假设j号金币是假的与称量结果是否矛盾/s是称量记录，其第一个元素是砝码个数/c是称量结果m=s01;for(i=f=1;i=m,核心代码及解释（续）,intmain()intnum1001001;chars1000;/输入内容for(i=1,t=0;i1)break;no=i;/t保存嫌疑对象的个数if(t-1)printf(0);elseprintf(%d,no);,案例2：现在的时间是多少？,Whattimeisit?TimeLimit:1000MSMemoryLimit:10000K,Description,Anaccutronshowstimewithfourdigits,from0000to2359.Everydigitisrepresentedby3*3characters,including|s,_sandblanks.WhentheLCDscreenworkswell,thedigitslooklikethefollowing:_|_|_|_|_|_|_|_|_|_|_|_|_|_|Therearetwoaccutronsathand.Oneshowstheaccuratetime,andtheotheris15minuteslate.Forexample,at8:25am,thefirstaccutronshows0825,whilethesecondshows0810.Unfortunately,thereissomethingwrongwiththetwoLCDscreens,namelysomepartsofthedigitsmissed.Yourtaskistodecidetheaccuratetime,accordingtothefragmentaldigitsshowedonthetwoaccutrons.,Input,Thefirstlineoftheinputisasingleintegert(1=t=20),thenumberoftestcases.Eachcasecontainsthreelines,indicatingthetimeontheaccurateaccutronandthetimeontheslowaccutron,separatedbyablankcolumn.(PleaserefertotheSampleInput.),Output,Foreachinput,printtheaccuratetimewithfourdigitsifitcanbeensured,orotherwisethestringNotSure.,SampleInput,2_|_|_|_|_|_|_|_|_|_|_|_|_|,SampleOutput,NotSure0825,现在的时间是多少？,时间限制:1000MS内存限制:10000K,描述,电子钟用4位数字表示时间，从0000到2359。每位数字用一个3*3的字符（|、_和空格）来表示。如果LCD显示屏正常工作，10个数字显示如下：_|_|_|_|_|_|_|_|_|_|_|_|_|_|现在有两个电子钟，一个显示正确的时间，另一个慢15分钟。如：上午8:25，第一个钟显示0825，同时第二个显示0810。不幸的，两个钟的LCD显示屏有些问题，也就是说，有些数字的某些部分缺失。你的任务就是通过显示的剩余部分来决定正确的时间。,输入,第一行是一个整数t(1=t=20)，表明测试序列数目。每个测试序列包含3行，表示正确的时间和迟后的时间，有一个空列隔开。(参照输入样例。),输出,如果能确定正确时间，输出该时间。否则输出NotSure。,输入样例,2_|_|_|_|_|_|_|_|_|_|_|_|_|,输出样例,NotSure0825,解题思路,这个题可以用蛮力搜索来解决。从题目描述，数据的规模不大(为什么？每天只有1440分钟)，选择暴力搜索可以使程序设计简单。这题显示了暴力搜索的优势,解题思路（续）,首先将LCD管进行编码。_0|_|123|_|4560123172补码：05155将输入的内容进行编码。,解题思路（续）,检测某个时间是否是显示屏上的时间，只需要检测该时间与显示屏上显示的内容不冲突就可以了。如检测1时，0、1、2、4、5处就不应该有显示。如果有显示，意味显示的不可能是1。所以只需将输入的内容与对应的数字作“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,核心代码及解释（续）,Intcode(char*s1,char*s2,char*s3)/将读入3行数据的数据编码intcod=0,i;chars10;Strcat(s,s1);strcat(s,s2);strcat(s,s3);For(I=0;I10;+I)if(sI!=)cod|=(1I);Returncod;,核心代码及解释（续）,shortnum10=4,55,66,18,49,24,8,54,0,16;/数字的补码intmain()scanf(%dn,/如果有且只有一个时间满足要求，输出该时间。,结果,Memory:20KTime:0MSLanguage:CResult:Accepted无论时间还是空间，包括代码长度，都是该题在POJ上的第一。-,搜索所有的路径,案例3：矩阵,案例3：矩阵,MatrixTimeLimit:2000MSMemoryLimit:30000K,Description,Givenann*nmatrixA,whoseentriesAi,jareintegernumbers(0=in,0=jn).AnoperationSHIFTatrowi(0=in)willmovetheintegersintherowonepositionright,andtherightmostintegerwillwraparoundtotheleftmostcolumn.YoucandotheSHIFToperationatarbitraryrow,andasmanytimesasyoulike.Yourtaskistominimizemax0=jnCj|Cj=0=inAi,j,Input,Theinputconsistsofseveraltestcases.Thefirstlineofeachtestcasecontainsanintegern.Eachofthefollowingnlinescontainsnintegers,indicatingthematrixA.Theinputisterminatedbyasinglelinewithaninteger1.Youmayassumethat1=n=7and|Ai,j|104.,Output,Foreachtestcase,printalinecontainingtheminimumvalueofthemaximumofcolumnsums.,SampleInput,246373123456789-1,SampleOutput,1115,矩阵,时间限制:2000MS内存限制:30000K,描述,给定一个n*n整数矩阵，定义对I行的SHIFT操作(0=in)，是将第I行所有元素都右移一位，最右边的移到最左边。你可以对任意行进行任意次SHIFT操作，使得：max0=jnCj|Cj=0=inAi,j最小化。,输入,第一行是一个整数t(1=t=20)，表明测试序列数目。每个测试序列包含3行，表示正确的时间和迟后的时间，有一个空列隔开。(参照输入样例。),输出,输出最小值。,输入样例,246373123456789-1,输出样例,1115,解题思路,这个题可以用蛮力搜索来解决。从题目描述，数据的规模不大（n8），ACM程序设计竞赛时间紧张，没有充裕的时间构筑高效、巧妙的算法。,解题思路（续）,把所有可能的移动都移动一遍，找到最小值。,数据结构与算法,不需要特殊的数据结构；算法采用暴力搜索。所有的可能情况都找出来：每一行都可能移0到n-1步，所以总的情况有nn种，对每种情况进行编号。如n=7时，7进制的0123456表示第一行不动，第二行移动一次,核心代码及解释,voidinttoseries(inti,int*s)/函数将序号化为移动的序列for(k=0,j=i;kn-1;+k)sk=j%n;j/=n;,核心代码及解释（续）,intmaxcolumn(int*s)/函数返回在指定移动情况下的最大值。for(max=matrix00,i=1;imax)max=temp;returnmax;,核心代码及解释（续）,intmain()while(scanf(%d,结果,Memory:28KTime:1140MSLanguage:CResult:Accepted这个效果就很差了，勉强通过。但在ACM中，AC就是一切。,列出解涉及的所有对象,案例4：素数距离,案例4：素数距离,PrimeDistanceTimeLimit:1000MSMemoryLimit:30000K,Description,Thebranchofmathematicscallednumbertheoryisaboutpropertiesofnumbers.Oneoftheareasthathascapturedtheinterestofnumbertheoreticiansforthousandsofyearsisthequestionofprimality.Aprimenumberisanumberthatishasnoproperfactors(itisonlyevenlydivisibleby1anditself).Thefirstprimenumbersare2,3,5,7buttheyquicklybecomelessfrequent.Oneoftheinterestingquestionsishowdensetheyareinvariousranges.Adjacentprimesaretwonumbersthatarebothprimes,buttherearenootherprimenumbersbetweentheadjacentprimes.Forexample,2,3aretheonlyadjacentprimesthatarealsoadjacentnumbers.Yourprogramisgiven2numbers:LandU(1=LU=2,147,483,647),andyouaretofindthetwoadjacentprimesC1andC2(L=C1C2=U)thatareclosest(i.e.C2-C1istheminimum).Ifthereareotherpairsthatarethesamedistanceapart,usethefirstpair.YouarealsotofindthetwoadjacentprimesD1andD2(L=D1D2=U)whereD1andD2areasdistantfromeachotheraspossible(againchoosingthefirstpairifthereisatie).,Input,Eachlineofinputwillcontaintwopositiveintegers,LandU,withLU.ThedifferencebetweenLandUwillnotexceed1,000,000.,Output,ForeachLandU,theoutputwilleitherbethestatementthattherearenoadjacentprimes(becausetherearelessthantwoprimesbetweenthetwogivennumbers)oralinegivingthetwopairsofadjacentprimes.,SampleInput,2171417,SampleOutput,2,3areclosest,7,11aremostdistant.Therearenoadjacentprimes.,素数距离,时间限制:1000MS内存限制:30000K,描述,数论，数学的一个分支，是研究数的性质。其中素数领域的研究几千年来一直吸引着人们的注意力。一个素数是除了自己和1以外没有别的整数可以整除它的数。最开始的素数有2，3，5，7等，但很快将变得很稀疏。一个有趣的问题是素数在不同范围内的密度。相邻素数是两个素数，他们之间没有别的素数。如2，3就是相邻素数。你的程序将输入2个数，L和U(1=LU=2,147,483,647)，你要找出2个相邻素数C1和C2(L=C1C2=U)是距离最小的。（也就是说C2-C1最小）。如果最小距离的相邻素数不止一对，选择最初的。你还需要找出2个相邻素数D1和D2(L=D1D2=U)是距离最大的（同样在有多对的情况选择最初的）。,输入,每行输入2个正整数，L和U，LU。L和U的差不超过1,000,000。,输出,对于每组L和U，如果没有相邻素数输出一行“Therearenoadjacentprimes.”，否则输出给定的两对相邻素数。,输入样例,2171417,输出样例,2,3areclosest,7,11aremostdistant.Therearenoadjacentprimes.,解题思路,这个题初看觉得不能用蛮力法解决；但在没有好的方法之前，用蛮力法试一试；给定范围了，如果把其间的所有素数都找出来，然后再把最大距离、最小距离求出来。标准的蛮力。找素数，当然用筛法。数据范围到达21亿，不能把所有的素数存下来，否则肯定超空间了。,解题思路（续）,因为区间长度小于1000000，所以可以考虑把这个区间的所有素数找出来。2,147,483,647内的数或者是素数，或者能被sqrt(2,147,483,647)内的素数整除sqrt(2,147,483,647)内的素数有4792个（先计算出来）。根据素数分布定律n/ln(n),1000000个数中最多80000个素数。,解题思路（续）,采用2次筛法解决本问题；第一次计算出sqrt(2,147,483,647)内的素数第二次利用已经计算出来的sqrt(2,147,483,647)内的素数，来筛掉指定区间所有非素数。,数据结构与算法,不需要特殊的数据结构；算法采用暴力搜索。指定区间内的所有素数都找出来。,核心代码及解释,intp4792;longpp80000;/2,147,483,647内的数或者是素数，或者能被sqrt(2,147,483,647)内的素数整除。/sqrt(2,147,483,647)内的素数有4792个（先计算出来）。/根据素数分布定律n/ln(n),1000000个数中最多80000个素数。,核心代码及解释（续）,voidpcal()/这个函数计算sqrt(2,147,483,647)内所有素数因子shortprime23170;inti,j;/sqrt(2,147,483,647)/2=23170for(i=0;i23170;+i)primei=1;/可以用memset,假设所有奇数是素数。for(i=0;i106;+i)if(p