北京大学教程w1枚举基本思想_第1页
北京大学教程w1枚举基本思想_第2页
北京大学教程w1枚举基本思想_第3页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、1枚举 基本思想郭炜程序设计实习枚举基于已有知识进行猜测的一种问题求解策略例如: 求小于N的最大素数 找不到一个数学公式, 使得根据N就可以计算出这个素数 N-1是素数吗? N-2是素数吗? N-K是素数的充分必要条件:N-K不能被任何一个大于1, 小于N-K的素数整除N-K是否是素数的问题àà转化为求小于N-K的全部素数2枚举解决办法 2是素数, 记为PRIM0 根据PRIM0, PRIM1 , , PRIMk, 寻找比PRIMk大的最小素数PRIMk+1 如果PRIMk+1大于N, 则PRIMk是我们需要找的素数,否则继续寻找3枚举的思想: 猜测枚举从可能的集合中一 一

2、列举各元素 根据所知道的知识, 给一个猜测的 2是素数枚举算法 对问题可能解集合的每一项 根据问题给定的检验条件判定哪些是成立的 使条件成立的即是问题的解4枚举的思想: 猜测枚举过程猜测的是否正确à 2是小于N的最大素数吗? 进行新的猜测: 有两个关键因素要注意 猜测的结果必须是前面的猜测中没有出现过的. 每次猜测是素数一定比已经找到的素数大 猜测的过程中要及早排除错误的才可能是素数. 除2之外, 只有奇数5枚举中三个关键问题问题一给出解空间, 建立简洁的数学模型可能的情况是什么à模型中变量数尽可能少, 它们之间相互 “求小于N的最大素数” 中的条件是 “n不能被2,n)中

3、任意一个素数整除” 而不是 “n不能被2,n)中任意一个整数整除”6枚举中三个关键问题问题二减少搜索的空间利用知识缩小模型中各变量的取值范围, 避免不必要的计算à减少代码中循环体执行次数 除2之外, 只有奇数才可能是素数, 2,2*i+1|1<=i, 2*i+1<n7枚举中三个关键问题问题三采用合适的搜索顺序搜索空间的遍历顺序要与模型中条件表达式一致 对2,2*i+1|1<=i, 2*i+1<n按照从小到大的顺序8中国古代的枚举问题百钱百鸡问题 鸡值钱五, 鸡值, 鸡雏三值钱一.百钱买百鸡, 问鸡翁, 鸡母, 鸡雏各几何建算经 求解方法: 先构造可能的解的集合 S=(X,Y,Z)|0<=X,Y,Z<=100X, Y, Z分别代表买公鸡, 母鸡和小鸡的只数 然后验证条件X+Y+Z

人人文库> 全部分类> 应用文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论