ACM蛮力(穷举)ppt课件

.,蛮力搜索,.,蛮力搜索,就像宝剑不是撬棍一样，科学也很少使用蛮力。EdwardLytton(18031873)，Leila，第二卷，第一章,.,蛮力搜索定义,蛮力法（也叫穷举法）它要求设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法,.,蛮力搜索定义,蛮力法是一种直接解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。,.,使用蛮力法的理由,显然蛮力法（也叫穷举法）不是一个最好的算法选择，但当我们想不出别的更好的办法时，它也是一种有效的解决问题的方法。蛮力法逻辑清晰，编写程序简洁。ACM程序设计时间紧张，使用高效的、巧妙的算法可能忽略掉一些解，而测试数据往往针对你可能忽略的情况。,.,概述,穷举法的基本思想是不重复、不遗漏地穷举所有可能情况(问题的规模不是特别大)，从中寻找满足条件的结果。穷举法充分利用了计算机处理的高速特性，避免复杂的逻辑推理过程，使问题简单化。使用穷举法的关键是要确定正确的穷举的范围和满足判断式。,.,例1：百钱百鸡问题。公鸡5文钱1只,母鸡3文钱1只,小鸡一文钱3只。100文钱如何卖100只鸡?条件分析设买x只公鸡，y只母鸡，z只小鸡，则有：x+y+z=1005x+3y+z/3=100且：x、y、z都是整数；0x20；0y33；0z99；z30。,.,基本算法思想，上述方程属于不定方程，解并不唯一，因此，可用穷举法对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=0printf(Possiblesolutionstobuy100fowlswhith100wen:n);for(x=0;x=20;x+)for(y=0;y=33;y+)z=100-x-y;if(z%3=0,.,运行结果：Possiblesolutionstobuy100fowlswhith100wen:1:cock=0hen=25chicken=752:cock=4hen=18chicken=783:cock=8hen=11chicken=814:cock=12hen=4chicken=84,.,例2：打印出所有的“水仙花数”。所谓“水仙花数”是指一个三位正整数，其各位数字的立方和等于该数本身，例如：153=13+53+33。穷举范围：即把所有的三位正整数100999按题意一一进行判断。判断式：如果一个三位正整数n的百位、十位、个位上的数字分别为i、j、k，则判断式为：n=i3+j3+k3如何分解三位数n的百位、十位、个位：百位：i=n/100;十位：j=(n/10)%10;个位：k=n%10;,.,#includestdio.hmain()intn,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);,运行结果：15313+53+3337033+73+0337133+73+1340743+03+73,.,例3：中国余数定理：“有物不知几何，三三数余一，五五数余二，七七数余三，问：物有几何？”。编程求1000以内所有解。穷举范围：整数m为：11000。判断式：m%3=1for(m=1;m=1000;m+)if(m%3=1,运行结果：52157262367472577682787892997,.,常用的蛮力法,1.搜索所有的解空间。2.搜索所有的路径。3.直接进行计算。,.,搜索所有的解空间,案例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,/如果有且只有一个时间满足要求，输出该时间。,.,搜索所有的路径,案例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(scan