《信息学竞赛入门 枚举算法》由会员分享，可在线阅读，更多相关《信息学竞赛入门 枚举算法（6页珍藏版）》请在金锄头文库上搜索。
1、2015 山东 省信息学夏令营 讲义（基础二 班） 资料 整理：赵宗昌 王 乃广 2015.7.24 1 / 6 第一讲 枚举算法 . 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 第一讲 枚举 算法 “ 枚举算法 ”：把问题所有的可能情况都 一一 列举出来，然后根据要求逐一
2、判断，最后找到问题的解。枚举 算法 在问题范围不是很大的情况下往往很有效，而且准确率也很高 ， 同时还能 起到 验证其他算法的正确性 的 作用， 在比赛 中 有时候 也能得到部分分 ， 是最 基本的算法。 最简单 的枚举 往往使用循环（嵌套） 就能轻易 实现，所有比较简单， 但也有技巧。 枚举 算法的关键是 合理 的确定枚举范围 ： 范围过大，浪费时间；范围过小，容易漏解。 一 . 基础 例 1-1 水仙花 数 若三位数 abc， 满足 a3+b3+c3=abc，则称 abc为水仙 花 数。如 153， 13+53+33=1+125+27=153，则 153称为水仙 花 数。 编程 求 100
3、 999中的 所有的 水仙 花 数。 【分析 】 枚举 范围： i： 100 999， 分别求出百位 a，十位 b，个位 c， 然后 判断是否满足条件： a3+b3+c3=i 用到 取模（ 余 ） 运算和 整除运算符： pascal: mod,div; C:% ,/ 尝试 ： 是否 还有其他的枚举方法？ 例 1-2 抽签游戏 【问题描述】 你和你的朋友在玩一个简单的游戏：你的朋友将写有数字的 n 个纸片放在他的口袋中，你可以从他的口袋中抽出 4 次纸片，每次抽出纸片后记下纸片上的数字后再将其放在口袋中，如果这 4 个数字的和恰好是 m，就算你赢，否则你的朋友赢。 2015 山东 省信息学夏令营
4、 讲义（基础二 班） 资料 整理：赵宗昌 王 乃广 2015.7.24 2 / 6 你挑战了好几回都没赢，于是想写个程序验证是否有赢的可能性，即是否存在抽取 4次和为 m的方案，如果存在输出 yes，否则输出 no。 【输入】 第一行： n。 第二行： m。 第三行： k1,k2, ,kn。分别代表 n 个纸片上的数字。 【输出】 如果存在收取 4 次的和为 m，输出 yes，不存在输出 no。 【样例 1】 输入： 输出： 3 10 1 3 5 yes 【 样例 2】 输入： 输出： 3 9 1 3 5 no 【 样例 3】 输入： 输出： 7 17 2 3 1 6 7 5 2 yes 【数
5、据限制】 100%的数据： 1 using namespace std; （ 2） Pascal：加库 math uses math; 也 可以自己编写自定义函数。 尝试 利用 max函数实现（ 在 源程序基础上修改即可）。 二 . 提高 例 1-4 数字 排列 用 19 组成 3 个三位数 abc,def,ghi，每个数字恰好使用一次，要求 abc:def:ghi=1:2:3。请按“ abc:def:ghi=1:2:3”的格式输出所有的解。 其中 一个解： 192:384:576=1:2:3 【分析】 只需枚举 abc,即可求出 def和 ghi。 知识点： （ 1） 数组 f每次都要清 0
6、. c语言： 加 头文件 ； 语句 ： memset(f,0,sizeof(f); Pascal语言： fillchar(f,sizoef(f),0); （ 2） 判断 a1a9正好是 19的一个全排列的方法： f19=0,然后 fa1a9=1之后，看 f19的和是否为 9。 例 1-5 最大 连续区间 和 输入 n 个元素组成的序列 S，你需要找出一个 和 最大的连续子序列。如果这个最大的 和 不是正数，应输出 0。 1k；又 x=y，所有 1/k=2/y ，即 y=2k，所以 y 的 枚举区间 k+1， 2k，然后求出 x， 当 1/k - 1/y=(y-k)/(y*k)的 化简 结果分子
7、为 1 即为一组解。 可以根据 :y-k 是 y*k 的 一个因数 （ y*k 能 被 y-k 整除 ） ，即 ： (y*k) mod (y-k)=0 扩展 ：如果先输出方案数量，然后再输出方案，怎样修 改程序？ 2015 山东 省信息学夏令营 讲义（基础二 班） 资料 整理：赵宗昌 王 乃广 2015.7.24 5 / 6 三 . 课后 训练 例 1-1例 1-6 中 部分 题目后面的尝试和扩展尽可能的在原题的基础上完成。 练习 1-1 直角 三角形个数 问题 ： 已知 n=100， 求 边长 不超过 n 的 所有 的 直角三角形 。 输出 边长 a,b,c。 以及 个数 。 边长 为 a，
8、 b， c 的三角形， 如果 满足 a2+b2=c2， 则为直角三角形， 最长 的 c 为斜边 。 如 ： a=3,b=4,c=5。 输出时 ： a=b=c。 如 ： 3 4 5 5 12 13 6 8 10 尝试 ： n=1000;n=2000;n=3000;n=10000。 练习 1-2 除法 uva 725 给你一个数 n(2 = n = 79)，输出所有形如 abcde/fghij=n 的表达式，期中 aj 是 09 的一个排列 （可以包含前导 0，如 02345 也算） 。 如 ： 输入 ： 61 输出 ： There are no solutions for 61. 输入 ： 62 输出： 79546 / 01283 = 62 2015 山东 省信息学夏令营 讲义（基础二 班） 资料 整理：赵宗昌 王 乃广 2015.7.24 6 / 6 94736 / 01528 = 62
