高级编程实践---枚举与模拟.ppt

枚举 枚举法 又称穷举法 指在一个有穷的可能的解的集合中 对每一个元素 判断是否符合条件 例1 求最大公约数 分析 a b的最大公约数的穷举范围 k b b 1 1满足条件 a k 0 Voidmain for k b k 1 k if a k 0 特点 算法简单 计算量大 减少计算量的方法 使用尽可能少的变量减少代码嵌套层次避免不必要的判断选择合适的搜索顺序 例2 6位分段和平方数 思路1 对所有6位整数 判断是否是一个平方数 如是 再利用整数和求余运算把a分为两个3位整数x y 若满足a x y 2 即找到一个解 思路2 对所有平方为6位整数的3位整数b 求出a b2 把a分为前后两个3位整数x y 判断b是否等于x y 例3 整币兑零问题 思路 对6个变量进行穷举 穷举范围 0 p1 n 0 p2 n 2 0 p5 n 5 0 p10 n 10 0 p20 n 20 0 p50 n 50满足 p1 2 p2 5 p5 10 p10 20 p20 50 p50 n 找到一种兑换方法 优化1 5个变量确定以后 第6个可以计算出来 p1 n 2 p2 5 p5 10 p10 20 p20 50 p50 优化2 循环条件可以加以限制 如 P5循环从0 n 5改进为0 n 2 p2 5 例 完美立方Description寻找所有四元组 a b c d 使得a3 b3 c3 d3 其中1 a b c d N Input正整数N N 100 Output每行输出一个完美立方 按照a的值从小到大依次输出 当两个完美立方等式中a的值相同时 依次按照b c d的升序排列输出 分析 对四个变量按照d c b a的顺序进行枚举 考虑如何减少循环次数 1 对于a 6 a N2 b c d满足a b c d3 b c d都小于a4 预先计算每个整数的立方 例 数字三角形Description将A B C D E F六个变量排成三角形 六个变量分别取 1 6 上不相同的证书 且使三角形三条边上的变量之和相等 Input一个1 6之间的整数AOutput所有以A为顶的三角形 分析 当A确定后 对B C D E F各变量在取值范围内 逐个检验是否满足三边相等 在各变量的循环中 对已经出现的值将不再考虑 对于F可以通过其他变量的值计算获得 可减少一个变量的循环 模拟 对于无法找到公式或规律进行求解的问题 采用模拟的方法 用计算机模拟人解决问题的方法来寻找答案 运算模拟 操作过程模拟 例 n个1的数字游戏Description给定一个正整数p 个位数不为5的奇数 求另一个正整数q 使得p和q的积全是1组成的整数 Input第1行是测试数据的组数t 每组测试数据占1行 每行包括一个个位数字不是5的奇数p Output对应每组测试数据输出共t行 每行输出两个整数 之间有一个空格分隔 一个是q 一个是p和q的乘积 分析 采用模拟除运算 模拟除的参量 1 原始数据 个位数字不是5的奇数p2 初始量 c 11 n 23 循环条件 c 04 构造量 m 1 例 数字七段显示Description数字可以通过控制7个发光器件组成 Input输入包括多行 每行包括三个整数w h n w h表示显示数字的尺寸 n是要显示的数字 Output显示方式是 用w个 表示一个水平线段 用h个 表示一个垂直线段 每个数字需要占