枚举：
基于已有知识进行答案猜测的一种问题求解策略 例如: 求小于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
中国古代的枚举问题 百钱百鸡问题
热门跟贴