经典算法详解(9)寻找丑数
题目:我们把只含有因子2、3、5的数称为丑数。例如6、8都是丑数,而14不是丑数,因为它含有因子7.通常也把1当做丑数。编程找出1500以内的全部丑数。注意:使用的算法效率应尽量高。
C++实现:
1 #include<iostream> 2 3 using namespace std; 4 5 //判断一个数是否是丑数,uglynum=2*2……*2*3*3*……*3*5*5……*5组成 6 int isUglyNumber(int n) { 7 while (n%2==0) 8 { 9 n /= 2; 10 } 11 while (n%3==0) 12 { 13 n /= 3; 14 } 15 while (n%5==0) 16 { 17 n /= 5; 18 } 19 return n == 1; 20 } 21 //方法1:逐个判断是否是丑叔,思路简单,但是计算冗余,因为越到后面很多都不是丑数也在计算。 22 int get_Ugly_fir(int number) { 23 int i = 1; 24 int count = 0; 25 while (i<=number) 26 { 27 if (isUglyNumber(i)) { 28 cout << i << "\t"; 29 count++; 30 if (count % 10 == 0) 31 cout << endl; 32 } 33 i++; 34 } 35 return count; 36 } 37 38 //方法二:算法效率高。 39 //思路:(1)后面的丑数肯定是已存在的丑数乘以2、3或者5,找到比现有丑数大的且是最小的丑数作为下一个丑数(如何找是关键)。 40 //2分别从现有丑数中从前往后乘以丑数,找到第一个大于当前所有丑数的值以及位置,3、5同样如此,再把他们相乘之后的结果做对比,取最小的。 41 //下次将从上一次的位置开始往下找,这样将不会出现冗余,详细见如下函数。 42 43 int Next_Ugly(int ugly_arr[], int *loc2, int *loc3, int *loc5, int *index) { 44 while (ugly_arr[*loc2] * 2 <= ugly_arr[*index]) { //千万注意这里是小于等于,不要写成小于了 45 (*loc2)++; 46 } 47 while (ugly_arr[*loc3] * 3 <= ugly_arr[*index]) { 48 (*loc3)++; 49 } 50 while (ugly_arr[*loc5] * 5 <= ugly_arr[*index]) { 51 (*loc5)++; 52 } 53 if (ugly_arr[*loc2] *2< ugly_arr[*loc3]*3) { 54 return (ugly_arr[*loc2] * 2 < ugly_arr[*loc5] * 5) ? ugly_arr[*loc2] * 2 : ugly_arr[*loc5] * 5; 55 } 56 else { 57 return (ugly_arr[*loc3] * 3) < ugly_arr[*loc5] * 5 ? ugly_arr[*loc3] * 3 : ugly_arr[*loc5] * 5; 58 } 59 } 60 61 int get_Ugly_sec(int num) { 62 int ugly_arr[1000]; 63 int index = 0, value = 1; 64 int loc2=0, loc3=0, loc5=0; 65 while (value<=num) { 66 ugly_arr[index] = value; 67 cout << ugly_arr[index] << "\t"; 68 if ((index + 1) % 10 == 0) 69 cout << endl; 70 71 value = Next_Ugly(ugly_arr, &loc2, &loc3, &loc5, &index); 72 index++; 73 } 74 return index; 75 } 76 77 int main(int argc, char *argv[]) { 78 get_Ugly_fir(1500); 79 cout << endl; 80 get_Ugly_sec(1500); 81 getchar(); 82 return 0; 83 }
(1)说明:总共使用了两种办法,第一种算法效率低,编程简单,第二种算法效率高,编程相对复杂。
(2)方法二思路:后面的丑数肯定是已存在的丑数乘以2、3或者5,找到比现有丑数大的且是最小的丑数作为下一个丑数(如何找是关键)。用2分别从现有丑数中从前往后乘以丑数,找到第一个大于当前所有丑数的值以及位置,3、5同样如此,再把他们相乘之后的结果做对比,取最小的。下次将从上一次的位置开始往下找,这样将不会出现冗余。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
我的Java程序员工具箱
不知不觉已经毕业一年了,算上实习开发已有两年,在这两年的工作中学到了很多知识,涉及技术、沟通和效率等方面。开发工具是不得不提的内容,好的开发工具能大大提高我们的工作效率。作为Java程序员,除了必备的eclipse或intelij idea外,下面列举的工具对提升工作效率也有很大帮助: 设计工具 Gliffy Gliffy 是一个基于Web的在线作图应用,它可以帮助用户创建流程图、组织结构图、平面图、业务流程、网络图、技术图、线框图等等。Gliffy的基础版本免费。不过其在线制作的思维导图是公开的,高级版本有设置隐私权的权力。用户可以将其可以嵌入博客,办公室应用软件中,有很好的兼容性。通过Gliffy编辑的流程图图片可输出SVG、GPEG格式。本人用的Chrome插件版,主要用其画流程图。 XMind XMind 是一款采用Java语言开发的实用的思维导图软件。XMind不仅可以绘制思维导图,还能绘制鱼骨图、二维图、树形图、逻辑图、组织结构图。并且,可以方便地从这些展示形式之间进行转换。另外,其可以导入MindManager、FreeMind数据文件。灵活的定制节点外观、插入图标,丰富...
- 下一篇
Redis与Python进行交互
安装包 安装Redis的有3种方式https://github.com/andymccurdy/redis-py 第一种:进⼊虚拟环境,联⽹安装包redis pip install redis 第二种:进⼊虚拟环境,联⽹安装包redis easy_install redis 第三种:到中⽂官⽹-客户端下载redis包的源码,使⽤源码安装 一步步执行 wgethttps://github.com/andymccurdy/redis-py/archive/master.zipunzip master.zipcd redis-py-mastersudo python setup.py install 调⽤模块 引⼊模块 from redis import * 这个模块中提供了StrictRedis对象(Strict严格),⽤于连接redis服务器,并按照不同类型提供 了不同⽅法,进⾏交互操作 StrictRedis对象⽅法 通过init创建对象,指定参数host、port与指定的服务器和端⼝连接,host默认为localhost,port默认为6379,db默认为0 sr = StrictR...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS6,CentOS7官方镜像安装Oracle11G
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Hadoop3单机部署,实现最简伪集群
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果