poj 1338 Ugly Numbers(丑数模拟)「建议收藏」

poj 1338 Ugly Numbers(丑数模拟)

大家好,又见面了,我是全栈君。

转载请注明出处:题目链接:Description

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, … 

shows the first 10 ugly numbers. By convention, 1 is included. 

Given the integer n,write a program to find and print the n’th ugly number. 

Input

Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0.

Output

For each line, output the n’th ugly number .:Don’t deal with the line with n=0.

Sample Input

1
2
9
0

Sample Output

1
2
10


PS:用一个长度为1500的数组存储这些数,另有三个游标x,y,z;


a[1]=1。x=y=z=1,代表第一个数为1,此后的数都是通过已有的数乘以2,3,5得到的,
那么x,y,z分别代表a[x],a[y],a[z]能够通过乘以2,3,5来得到新的数,i递增。每次取2*a[x], 3*a[y], 5*a[z]
中的最小值。得到a[i]后。能够将相应的x(或y,z)右移,当然假设原本通过3*2得到6,那么2*3也能得到6,
因此可能x和y都须要递增。


详见代码:

#include <iostream>
using namespace std;
int min(int a, int b, int c)
{
	return min(a,min(b,c));
}
int main()
{
	int a[1517];
	int x, y, z, i;
	x = y = z = 1, a[1] = 1;
	for(i = 2; i <= 1500; i++)
	{
		a[i] = min(2*a[x],3*a[y],5*a[z]);
		if(a[i] == 2*a[x])
		x++;
		if(a[i] == 3*a[y])
		y++;
		if(a[i] == 5*a[z])
		z++;
	}
	int n;
	while(cin >> n && n)
	{
		cout<<a[n]<<endl;
	}
	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115414.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Python语音信号处理

    Python语音信号处理个人博客:http://www.chenjianqu.com/原文链接:http://www.chenjianqu.com/show-44.html语言信息是多种信息的混合载体,其中包括内容信息、说话人信息和情感信息。本文介绍了一些语音的基本知识,和使用Python进行处理。时域特征使用wave模块读取wav音频文件,画图时域图像,代码如下。import…

  • 睿智的目标检测29——Keras搭建YoloV4目标检测平台

    睿智的目标检测29——Keras搭建YoloV4目标检测平台睿智的目标检测29——Keras搭建YoloV4目标检测平台学习前言什么是YOLOV4YOLOV4改进的部分(不完全)改进点解析1、主干特征提取网络Backbone2、主干特征提取网络Backbone学习前言哈哈哈我最喜欢的YOLO更新了!什么是YOLOV4YOLOV4是YOLOV3的改进版,在YOLOV3的基础上结合了非常多的小Tricks。尽管没有目标检测上革命性的改变,但是YOLOV4依然很好的结合了速度与精度。根据上图也可以看出来,YOLOV4在YOLOV3的基础上,在FPS不下降的

  • 如何将a4排版成a3双面打印_A4如何双面打印

    如何将a4排版成a3双面打印_A4如何双面打印A4排成A3双面打印怎么操作?A3纸张的尺寸是297mm×420mm,其大小相当于两张A4的大小,A4是大家工作及生活中使用较多的纸张尺寸,A3纸张不常用,但是遇到一些比较重要的画报、图纸等之类的资料,A3纸张就比较突出了。在城市周边打印店,打印资料时多以使用A4纸张居多,所以如果您到打印店打印A3纸张,很有可能会被打印店告知:无法打印。有时候可能不是打印店员工不会帮您排版,而是打印店的设备不支持为大家打印A3大小的纸张资料。今天小编给大家介绍一个比较专业的网上在线打印平台——易桌面打印室,这是一个网

  • php用哪个版本_php什么版本好

    php用哪个版本_php什么版本好一. PHP5.2、5.3、5.4、5.5、5.6版本区别对比以及新功能详解1.php5.2以前1.1autoload的使用;当在代码中使用一个未定义的类的时候,该函数就会被调用

  • ScriptManager.RegisterStartupScript方法[通俗易懂]

    ScriptManager.RegisterStartupScript方法[通俗易懂]出处:忘记了,致歉作者 如果页面中不用Ajax,cs中运行某段js代码方式可以是:Page.ClientScript.RegisterStartupScript(Page.GetType(),””,”window.open(‘default2.aspx’)”);如果页面中使用了Ajax,则上述代码即使执行也无效果。对这种情况我们通常采用:ScriptManag

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号