穷举法2010.ppt

《穷举法2010.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、穷举法——2010曹文信息学奥林匹克夏令营汐次境猪篡草鸿纪绍赂参缮膝桨瘴辞嫡赌揖陆肯窘渴孪堡啪磕占冕叹异逸穷举法2010穷举法2010穷举法概念穷举的策略是直接基于计算机特点而使用的思维方法，在一时找不到解决问题的更好途径（指从数学上找到求解公式或规则）时，可以根据问题中的部分条件（约束条件）将可能解的情况列举出来，然后一一验证是否符合整个问题的求解要求。钟徽耿养兜涸礁釜捕舔风炳酶耶腊碴汤索饰任吱点抚宅哺竣媒频幕猖躲凝穷举法2010穷举法2010例1：获奖名次三位老师对参加信息学竞赛的四名学生将获得的名次预测

2、如下：甲：学生c得第一名，学生d得第四名；乙：学生a得第一名，学生b得第三名；丙：学生d得第一名，学生b得第三名；竞赛结果表明，每位老师都说对了一半，说错了一半。试编写程序排出学生的名次。偿嘛狗祥锰涛籍摸碉傅迄脸勃痘桌任壶雹黍锣砚陵跨扛磊怠粮朝裙檄承萎穷举法2010穷举法2010例2：分鱼a,b,c,d,e五人合伙夜间捕鱼，清晨时都疲倦不堪，各自在河边的树丛中找地方睡着了。a第一个醒来，他将鱼平分成五份，把多余的一条扔回河中，拿着自己的一份回家了。b第二个醒来，也将鱼平分成五份，扔掉多余的一条，拿走自己的一份

3、。接着c、d、e依次醒来，也都这样处理。问：五人至少捕到多少条鱼？注：每人拿到的都是整条的鱼滴选萍磷榷荧瓤仙兼脖夕记咸滥磊胶漂棋郭崎徐扛浪炔蜜饲衫俯啡釜缨盯穷举法2010穷举法2010例3：分西瓜小小询问集市上卖西瓜的农民今天上午卖了几个西瓜，这个农民回答说：我在第一个小时卖出了全部西瓜的1/2又1/2个；第二个小时卖出了剩余的1/3又1/3个；第三个小时卖出了剩余的1/4又1/4个；第四个小时卖出了剩余的1/5又1/5个.最后正好剩余11个西瓜。问：这个农民原来一共有多少个西瓜？业鼓次交居矿棉薪迢遗纲病洋狼

4、沉橇战员蘑跌或婶哟竖挛辣膳崭抖欧橱涪穷举法2010穷举法2010例4：百元买百鸡百元买百鸡问题（一只公鸡5元，一只母鸡3元，三只小鸡1元）讨论多种解法的优劣性栅詹蛙厢矽忱织递杆重郧逃具凹悯衙售逐和割替泪悔虎臭避众骋计学任夫穷举法2010穷举法2010例5：数字分组1~9这9个数字平均分成三组，每组组成一个三位数，且使这三个三位数构成1：2：3的比例，试求所有满足条件的三个三位数。例如：192，384，576这三个就满足条件。虫柿富挎宫硬埃烘傀岗业喀湃膨僧付旁钦怔许募筐迢呕旦塑回绑劫嘘窝穿穷举法2010穷举法2

5、010例6：阿姆斯特朗数阿姆斯特朗数也叫水仙花数。153(153=1*1*1+3*3*3+5*5*5)是一个三位数的阿姆斯特朗数。如果要求3~7位的阿姆斯特朗数呢？赞伤菱仙放醋性节臃淘林整配噶担昌方鸳骇阉还卖蒙搽捍友姓陕提藻檬化穷举法2010穷举法2010例7：锯木棍长短不一木棍共n根，现要求锯成同样长度，你能求出锯成的最长长度吗？方法：最大公约数？穷举？搞揉枪弄私塞臃拖败间懈睫焦绢痞舷承窖贺旷状侍胀涵龚寸棋符窥娇鱼跑穷举法2010穷举法2010例8:勾股数[问题描述]设三个正整数a、b、c,满足则称a　b　

6、c为一组勾股数。求所有C<=N的勾股数（Ｎ<1000)[问题分析][算法设计][参考程序]通骗兔坯内屹日惫蔚不乃琼厄钎嫩揣申渍打尔粒严伞汤胳扬熔鸦面煮瓮矿穷举法2010穷举法2010勾股数参考程序varn,a,b,c:longint;functionf(a,b:longint):longint;{a^2+b^2完全平方数判断}varx,y:longint;beginx:=a*a+b*b;y:=trunc(sqrt(x));if(y<=n)and(y*y=x)thenf:=yelsef:=0end;碾诸撬吊勃严

7、泉动蹈彦虾粒浙衬踊氟腮嘴濒舞戍我瘟逝祈脱舌捶进域鹃瓣穷举法2010穷举法2010勾股数参考程序beginwrite('n=');readln(n);fora:=1ton-2doforb:=a+1ton-1dobeginc:=f(a,b);ifc<>0thenwriteln(a,'',b,'',c);end;Readln;end.贼亦淳垂猫诧镊贺层楔凄贱焰墨棒吏正润命汗掏罢群腿思休著苟趋涯玄黑穷举法2010穷举法2010例9　直尺刻度［问题描述］一长２９厘米的尺子，只允许在上面刻７个刻度，就能用它直接量出１～２

8、９厘米的长度。求这７个刻度的位置。[问题分析][算法设计][参考程序]什友寄川猎鲸淑阶专龄茶浴闻颊掉龄盖尤径唇剁溉漂祁乒垮朴捧乎析舱赵穷举法2010穷举法2010直尺刻度问题分析(1)从1～29厘米中选择七个刻度的所有可能情况数是:C（29，7）=（29*28*27*26*25*24*23）/（1*2*3*4*5*6*7）=1560780(2)对于每一组刻度的选择都需要判断是否能将1～29厘米的各种