文档章节

算法:枚举

植瑞
 植瑞
发布于 2016/03/11 11:15
字数 604
阅读 17
收藏 0

枚举

  • 基于已知知识进行答案猜测的一种问题解决策略

例子:求小于N的最大素数

  • 找不到一个数学公式,使得根据N就可以计算出这个素数
  • N-1是素数吗?N-2是素数吗……
  • N-K是素数的一个必要条件
  • N-k不能被大于1小于N-k的任何素数整除
    ->判断N-k是否是素数的问题
    ->转换成为求小于N-k的所有素数

解决办法:

  • 2为素数,记为PRIM0
  • 根据PRIM 0,PRIM 1……PRIM k寻找比PRIM k大的最小素数PRIM k+1
  • 如果PRIM k+1大于N,则PRIM k就是我们要找的素数

枚举思想:猜测

枚举:

从可能的集合中一一列举出各种元素

  • 根据所知道的知识,给出一个猜测的答案
  • 2是素数

枚举算法:

  • 对问题可能解集的每一项
  • 根据问题给定的检验条件判定哪些是成立的
  • 使条件成立的即是问题的解

枚举过程

  • 判断猜测的答案是否正确
    ->2是小于N的最大素数吗?
  • 进行新的猜测:有两个关键因素要注意
    1. 猜测的结果必须是前面的猜测中没有出现过的。每次猜测的素数一定比已经找到的素数大
    2. 猜测的过程中要及早排除错误的答案->除2外只有奇数才有可能是素数

枚举中三个关键的问题

问题一

  • 给出解空间,建立简洁的数学模型,可能的情况是什么
  • ->模型中变量数要尽可能的少,他们之间相互独立
  • “求小于N的最大素数”中的条件是“能不能被[2,n)中的任意一个素数整除”
  • 而不是“n不能被[2,n)中任意一个整数整除

问题二

  • 减少搜索空间
  • 利用知识缩小模型中名变量的取值范围,避免不必要的计算
  • -> 减少代码中循环体的执行次数
  • 除2之外只有奇数才有可能是素数{2,2i+1|1<=i,2i+1<n}

问题三

  • 采用合理的搜索顺序
  • 搜索空间的遍历顺序要与模型中的条件表达式一致
  • 对{2,2i+1|1<=i,2i+1<n}按照从小到大的顺序

© 著作权归作者所有

植瑞
粉丝 0
博文 1
码字总数 604
作品 0
成都
网页/平面设计
私信 提问
分布式 | MyCat如何迁移到DBLE之分片算法对比解析:enum分片

原创作者: 钟悦 关于作者 钟 悦 - 资深DBLE用户 某宇宙行资深架构师,在大型重点项目中使用 DBLE。 常年与 MySQL 纠缠不清,经常运用技术处理大企业病的技术or非技术问题的一个挨踢从业者。...

爱可生
07/09
12
0
iOS设计模式--迭代器模式

何为迭代器模式? 迭代器提供了一种顺序访问集合对象中元素的方法,而无需暴漏结构的底层表示和细节。遍历集合中元素的职能从集合本身转移到迭代器对象。迭代器定义了一个用于访问集合元素并...

国士梅花
2015/08/28
124
0
Codeforces B. Minimum Possible LCM

题目描述: B. Minimum Possible LCM time limit per test 4 seconds memory limit per test 1024 megabytes input standard input output standard output You are given an array aconsist......

小张人
07/28
0
0
枚举——完美立方

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 | 云+社区 1. 枚举 枚举是基于逐个尝试答案的一种问题求解策略。 2. 完美立方 形如 的等式被称为完美立方等式。例如 问题:编写程序,对任...

Quincuntial
2017/12/18
0
0
Swift讲解专题九——枚举

Swift讲解专题九——枚举 一、引言 在Objective-C语言中,没有实际上是整型数据,Swift中的枚举则更加灵活,开发者可以不为其分配值类型把枚举作为独立的类型来使用,也可以为其分配值,可以...

珲少
2016/05/15
195
0

没有更多内容

加载失败,请刷新页面

加载更多

分布式协调服务zookeeper

ps.本文为《从Paxos到Zookeeper 分布式一致性原理与实践》笔记之一 ZooKeeper ZooKeeper曾是Apache Hadoop的一个子项目,是一个典型的分布式数据一致性的解决方案,分布式应用程序可以基于它...

ls_cherish
今天
4
0
redis 学习2

网站 启动 服务端 启动redis 服务端 在redis 安装目录下 src 里面 ./redis-server & 可以指定 配置文件或者端口 客户端 在 redis 的安装目录里面的 src 里面 ./redis-cli 可以指定 指定 连接...

之渊
昨天
2
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
昨天
4
0
hash slot(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
昨天
4
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
昨天
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部