程序设计实习：11.1枚举的基本思想

枚举：

基于已有知识进行答案猜测的一种问题求解策略 例如: 求小于N的最大素数

找不到一个数学公式, 使得根据N就可以计算出这个素数

N-1是素数吗? N-2是素数吗? ……

N-K是素数的充分必要条件: N-K不能被任何一个大于1, 小于N-K的素数整除 判断N-K是否是素数的问题 转化为求小于N-K的全部素数。

枚举 解决办法

2是素数, 记为PRIM0

根据PRIM0 , PRIM1 , …, PRIMk , 寻找比PRIMk大的 最小素数PRIMk+1

如果PRIMk+1大于N, 则PRIMk是我们需要找的素数, 否则继续寻找。

枚举的思想: 猜测 枚举 从可能的集合中一 一列举各元素

根据所知道的知识, 给一个猜测的答案

2是素数 枚举算法

对问题可能解集合的每一项

根据问题给定的检验条件判定哪些是成立的

使条件成立的即是问题的解

枚举的思想: 猜测 枚举过程

判断猜测的答案是否正确 2是小于N的最大素数吗?

进行新的猜测: 有两个关键因素要注意

猜测的结果必须是前面的猜测中没有出现过的. 每次猜测 是素数一定比已经找到的素数大

猜测的过程中要及早排除错误的答案. 除2之外, 只有奇数 才可能是素数

枚举中三个关键问题 问题一 给出解空间, 建立简洁的数学模型 可能的情况是什么 模型中变量数尽可能少, 它们之间相互独立

“求小于N的最大素数” 中的条件是 “n不能被[2,n)中任意 一个素数整除”

而不是 “n不能被[2,n)中任意一个整数整除”

枚举中三个关键问题

问题二

减少搜索的空间

利用知识缩小模型中各变量的取值范围, 避免不必要的

计算

减少代码中循环体执行次数

除2之外, 只有奇数才可能是素数, {2,2*i+1|1<=i, 2*i+1<n}

枚举中三个关键问题

问题三

采用合适的搜索顺序

搜索空间的遍历顺序要与模型中条件表达式一致

对{2,2*i+1|1<=i, 2*i+1<n}按照从小到大的顺序

中国古代的枚举问题 百钱百鸡问题

鸡翁一值钱五, 鸡母一值钱三, 鸡雏三值钱一. 百钱买百鸡, 问鸡翁, 鸡母, 鸡雏各几何 —— 张丘建《算经》

求解方法:

先构造可能的解的集合 S={(X,Y,Z)|0<=X,Y,Z<=100} X, Y, Z分别代表买公鸡, 母鸡和小鸡的只数

然后验证条件X+Y+Z=100, 5X+3Y+Z/3=100 复杂度: O(1002 ) 9

中国古代的枚举问题 百钱百鸡问题