ACM蛮力法教程.ppt

蛮力法【暴力、枚举、穷举……】;所谓蛮力法，是指从可能的解集合（空间）中一一列举各情况，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。 采用蛮力法解题的基本思路如下： （1）建立问题的数学模型，确定问题的可能解的集合（可能解的空间）。 （2）逐一列出可能解集合中的元素，验证是否是问题的解。 程序优化的主要考虑方向是：通过加强约束条件，缩小可能解的集合的规模。 ;蛮力算法;例题：寻找水仙花数 一个三位数其各位数字的立方和等于它本身，这 样的数称为水仙花数。要求找出所有的水仙花数 分析：所求一定是三位数，所以范围一定在100-999之间，只要将这些数逐一列举，符合条件者为解 ;枚举算法;;;Var x,y,z:integer; begin //枚举可能解空间的元素 for x:=0 to 100 do for y:=0 to 100 do for z:=0 to 100 do if (x+y+z=100) and (x*3+y*2+z　div 3=100) and (z mod 3=0) //验证可能解 then WriteLn(Format((x,y,z)=(%3d,%3d,%3d),[x,y,z])); end. ;;程序需要循环100^3，即|S|=100^3。我们通过条件x+y+z=100来约束求解空间，缩小可能解的集合的规模： 　．．．．．． begin //枚举可能解空间的元素 for (x=0;x=100;x++) for (y=0;y=100-x;y++) begin z:=100-x-y; 　if (x+y+z=100) and (x*3+y*2+z div 3=100) and (z mod 3=0) ．．．．．． end; end. ; 两个程序运行结果相同，但是，优化后，后者的循环次数为100*101/2，是前者循环次数的1/200左右。 ;古堡算式福尔摩斯到某古堡探险，看到门上写着一个奇怪的算式：ABCDE * ? = EDCBA他对华生说：“ABCDE应该代表不同的数字，问号也代表某个数字！”华生：“我猜也是！”于是，两人沉默了好久，还是没有算出合适的结果来。请你利用计算机的优势，找到破解的答案。把 ABCDE 所代表的数字写出来。答案写在“解答.txt”中，不要写在这里！;注意首位和末位是否为0的情况。;枚举算法适用范围： 简单数值判断题； 简单逻辑判断题； 数据规模不大的问题； 没有想到更好解法的题，可用枚举求出一定???围内的解。 但：对于枚举算法，程序优化的主要考虑方向是：通过加强约束条件，缩小可能解的集合的规模。 简单，但是慎用！要注意问题的规模。很可能会超出时间限制，导致报错！;把一元钞票换成一分、二分、五分硬币（每种至少一枚），有哪些种换法？ 461 如何优化？;作为码农，小明有一个心仪的女孩陈婷，已经交往了一段时间。陈婷请小明帮忙解决一个计算机方面的问题，小明说包在我身上。问题是这样的，陈婷有一个E-MAIL邮箱的密码是一个5位数。但因为有一段比较长的日子没有打开这个邮箱了，陈婷把这个密码给忘了。不过陈婷自己是8月1日出生，而她妈妈的生日则是9月1日，她特别喜欢把同时是8l和9l的倍数用作密码。陈婷还记得这个密码的中间一位(百位数)是l。小明思考了许久没有任何头绪，作为小明的好友，你能帮小明设计一个程序将陈婷找回这个密码吗?亲昵指数会加分哦···;将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数. 这是1998年全国青少年信息学奥林匹克联赛普及组试题（简称NOIP1998pj）。