《ACM蛮力(穷举)》由会员分享，可在线阅读，更多相关《ACM蛮力(穷举)（86页珍藏版）》请在金锄头文库上搜索。
1、蛮力搜索 蛮力搜索 就像宝剑不是撬棍一样 科学也很少使用蛮力 EdwardLytton 1803 1873 Leila 第二卷 第一章 蛮力搜索 定义 蛮力法 也叫穷举法 它要求设计者找出所有可能的方法 然后选择其中的一种方法 若该方法不可行则试探下一种可能的方法 蛮力搜索 定义 蛮力法是一种直接解决问题的方法 常常直接基于问题的描述和所涉及的概念定义 使用蛮力法的理由 显然蛮力法 也叫穷举法 不是一个最好的算法选择 但当我们想不出别的更好的办法时 它也是一种有效的解决问题的方法 蛮力法逻辑清晰 编写程序简洁 ACM程序设计时间紧张 使用高效的 巧妙的算法可能忽略掉一些解 而测试数据往往针对你
2、可能忽略的情况 概述 穷举法的基本思想是不重复 不遗漏地穷举所有可能情况 问题的规模不是特别大 从中寻找满足条件的结果 穷举法充分利用了计算机处理的高速特性 避免复杂的逻辑推理过程 使问题简单化 使用穷举法的关键是要确定正确的穷举的范围和满足判断式 例1 百钱百鸡问题 公鸡5文钱1只 母鸡3文钱1只 小鸡一文钱3只 100文钱如何卖100只鸡 条件分析设买x只公鸡 y只母鸡 z只小鸡 则有 x y z 1005x 3y z 3 100且 x y z都是整数 0 x 20 0 y 33 0 z 99 z 3 0 基本算法思想 上述方程属于不定方程 解并不唯一 因此 可用穷举法对x y z的所有组
3、合情况 测试满足条件的解 具体是 把x可能值0 20和y可能值0 33用二重循环来组合 每个x和y组合都可得到z值 即z 100 x y 若x y z值使5x 3y z 3 100成立 则该组x y z即为一组所求值 即 穷举范围 x 0 20 y 0 33 z 100 x y判断式 z 3 0 5 x 3 y z 3 100 另一方法是 把x可能值0 20 y可能值0 33和z可能值0 99用三重循环来组合 若x y z值使5x 3y z 3 100和x y z 100同时成立 则该组x y z即为一组所求值 即 穷举范围 x 0 20 y 0 33 z 0 99判断式 z 3 0 5 x
4、3 y z 3 100 x y z 100 main intx y z j 1 printf 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 打印出所有的 水仙花数 所
5、谓 水仙花数 是指一个三位正整数 其各位数字的立方和等于该数本身 例如 153 13 53 33 穷举范围 即把所有的三位正整数100 999按题意一一进行判断 判断式 如果一个三位正整数n的百位 十位 个位上的数字分别为i j k 则判断式为 n i3 j3 k3 如何分解三位数n的百位 十位 个位 百位 i n 100 十位 j n 10 10 个位 k n 10 include stdio h main 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 d 3 d 3
6、 d 3 n n i j k 运行结果 153 1 3 5 3 3 3370 3 3 7 3 0 3371 3 3 7 3 1 3407 4 3 0 3 7 3 例3 中国余数定理 有物不知几何 三三数余一 五五数余二 七七数余三 问 物有几何 编程求1000以内所有解 穷举范围 整数m为 1 1000 判断式 m 3 1 m 5 2 m 7 3 include stdio h main intm count 0 for m 1 m 1000 m if m 3 1 运行结果 52157262367472577682787892997 常用的蛮力法 1 搜索所有的解空间 2 搜索所有的路径 3
7、直接进行计算 搜索所有的解空间 案例1 假金币案例2 现在的时间是多少 案例1 假金币 FalsecoinTimeLimit 3000MSMemoryLimit 10000K Description The GoldBar bankreceivedinformationfromreliablesourcesthatintheirlastgroupofNcoinsexactlyonecoinisfalseanddiffersinweightfromothercoins whileallothercoinsareequalinweight Aftertheeconomiccrisistheyhav
8、eonlyasimplebalanceavailable likeoneinthepicture Usingthisbalance oneisabletodetermineiftheweightofobjectsintheleftpanislessthan greaterthan orequaltotheweightofobjectsintherightpan Inordertodetectthefalsecointhebankemployeesnumberedallcoinsbytheintegersfrom1toN thusassigningeachcoinauniqueintegerid
9、entifier Afterthattheybegantoweightvariousgroupsofcoinsbyplacingequalnumbersofcoinsintheleftpanandintherightpan Theidentifiersofcoinsandtheresultsoftheweightingswerecarefullyrecorded Youaretowriteaprogramthatwillhelpthebankemployeestodeterminetheidentifierofthefalsecoinusingtheresultsoftheseweightin
10、gs Input ThefirstlineoftheinputfilecontainstwointegersNandK separatedbyspaces whereNisthenumberofcoins 2 or Itrepresentstheresultoftheweighting meansthattheweightofcoinsintheleftpanisgreaterthantheweightofcoinsintherightpan meansthattheweightofcoinsintheleftpanisequaltotheweightofcoinsintherightpan
11、Output Writetotheoutputfiletheidentifierofthefalsecoinor0 ifitcannotbefoundbytheresultsofthegivenweightings SampleInput 5321234 114 125 SampleOutput 3 假金币 时间限制 3000MS内存限制 10000K 描述 GoldBar 银行收到可靠消息 在前次的N个金币中有一枚重量不同的假金币 其他金币的重量都相同 经济危机之后他们只有一台天平可用 用这台天平 可以称量出左边托盘中的物体是轻于 重于或等于右边托盘中的物体 为了分辨出假金币 银行职员将所有
12、的金币编为1到N号 然后用天平称量不同的金币组合 每次仔细记载称量金币的编号和结果 现在要求你编写一个程序 帮助银行职员根据称量记录来找出假金币的编号 输入 第一行输入两个空格隔开的整数N和K N是金币的总数 2 和记录称量结果 表示左边托盘中的金币比右边的重 表示左右两边托盘中的金币一样重 输出 输出假金币的编号 如果根据称量纪录无法确定假金币 输出0 输入样例 5321234 114 125 输出样例 3 解题思路 这个题可以用蛮力搜索来解决 从题目描述 数据的规模不大 而时间限制足够大 选择暴力搜索可以使程序设计简单 而且因为是完全搜索 所以不会出现漏掉解的情况 解题思路 续 思路很简单
13、 把所有的金币都试一遍 Step1 依次假设I号金币是假的 Step2 对称量的记录进行监测 如果假设与所有的记录都不矛盾 则有可能是假的 Step3 如果有可能是假的金币只有1个 输出它的编号 否则 输出0 数据结构与算法 不需要特殊的数据结构 算法采用暴力搜索 核心代码及解释 shortjd intj int s charc 函数判断假设j号金币是假的与称量结果是否矛盾 s是称量记录 其第一个元素是砝码个数 c是称量结果 m s 0 1 for i f 1 i m 核心代码及解释 续 intmain intnum 100 1001 chars 1000 输入内容for i 1 t 0 i1
14、 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 Therea
15、retwoaccutronsathand Oneshowstheaccuratetime andtheotheris15minuteslate Forexample at8 25am thefirstaccutronshows 0825 whilethesecondshows 0810 Unfortunately thereissomethingwrongwiththetwoLCDscreens namelysomepartsofthedigitsmissed Yourtaskistodecidetheaccuratetime accordingtothefragmentaldigitssho
16、wedonthetwoaccutrons Input Thefirstlineoftheinputisasingleintegert 1 t 20 thenumberoftestcases Eachcasecontainsthreelines indicatingthetimeontheaccurateaccutronandthetimeontheslowaccutron separatedbyablankcolumn PleaserefertotheSampleInput Output Foreachinput printtheaccuratetimewithfourdigitsifitcanbeensured orotherwisethestring NotSure SampleInput 2 SampleOutput NotSure0825 现在的时间是多少 时间限制 1000MS内存限制 10000K 描述 电子钟用4位数字表示时间 从0000到2359 每位数字用一个3 3的字符 和空格 来表示 如果LCD显示屏正常工作 10个数字显示如下 现在有两个电子钟 一个显示正确的时
