信息学竞赛入门 枚举算法.pdfVIP

2015 山东省信息学夏令营讲义（基础二班） 资料整理：赵宗昌 王乃广 2015.7.24 第一讲 枚举算法 1 一 . 基础 1 例1-1 水仙花数 1 例1-2 抽签游戏 1 例1-3 周长最大三角形 2 二 . 提高 3 例1-4 数字排列 3 例1-5 最大连续区间和 3 例1-6 分数拆分 uva 10976 4 三 . 课后训练 5 练习1-1 直角三角形个数 5 练习1-2 除法 uva 725 5 第一讲 枚举算法 “枚举算法”：把问题所有的可能情况都一一列举出来，然后根据要求逐一判断，最后找到问题的解。 枚举算法在问题范围不是很大的情况下往往很有效，而且准确率也很高，同时还能起到验证其他算法的正 确性的作用，在比赛中有时候也能得到部分分，是最基本的算法。 最简单的枚举往往使用循环（嵌套）就能轻易实现，所有比较简单，但也有技巧。 枚举算法的关键是合理的确定枚举范围：范围过大，浪费时间；范围过小，容易漏解。 一 . 基础 例1-1 水仙花数 3 3 3 3 3 3 若三位数abc，满足a +b +c =abc，则称abc 为水仙花数。如153，1 +5 +3 =1+125+27=153，则153称 为水仙花数。 编程求100～999 中的所有的水仙花数。 【分析】 枚举范围：i：100～999，分别求出百位a，十位b，个位c，然后判断是否满足条件： 3 3 3 a +b +c =i 用到取模（余）运算和整除运算符：pascal: mod,div; C:% ,/ 尝试：是否还有其他的枚举方法？ 例1-2 抽签游戏 【问题描述】 你和你的朋友在玩一个简单的游戏：你的朋友将写有数字的n 个纸片放在他的口袋中，你可以从他的 口袋中抽出4 次纸片，每次抽出纸片后记下纸片上的数字后再将其放在口袋中，如果这4 个数字的和恰好 是m ，就算你赢，否则你的朋友赢。 1 / 6 2015 山东省信息学夏令营讲义（基础二班） 资料整理：赵宗昌 王乃广 2015.7.24 你挑战了好几回都没赢，于是想写个程序验证是否有赢的可能性，即是否存在抽取4 次和为m 的方案， 如果存在输出yes ，否则输出no 。 【输入】 第一行：n 。 第二行：m 。 第三行：k1,k2, …,kn。分别代表n 个纸片上的数字。 【输出】 如果存在收取4 次的和为m ，输出yes ，不存在输出no 。 【样例1】 输入： 输出： 3 yes 10 1 3 5 【样例2 】 输入： 输出： 3 no 9 1 3 5 【样例3 】 输入： 输出： 7 yes 17 2 3 1 6 7 5 2 【数据限制】 8