| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 19952 | Accepted: 8856 |
Description
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
Output
Sample Input
1
2
9
0
Sample Output
1
2
10
Source
这种思路的关键在于怎样确保数组里面的丑数是排好序的。我们假设数组中已经有若干个丑数，排好序后存在数组中。我们把现有的最大丑数记做M。现在我们来生成下一个丑数，该丑数肯定是前面某一个丑数乘以2、3或者5的结果。我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个结果小于或等于M的。由于我们是按照顺序生成的，小于或者等于M肯定已经在数组中了，我们不需再次考虑；我们还会得到若干个大于M的结果，但我们只需要第一个大于M的结果，因为我们希望丑数是按从小到大顺序生成的，其他更大的结果我们以后再说。我们把得到的第一个乘以2后大于M的结果，记为M2。同样我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5三个数的最小者。
前面我们分析的时候，提到把已有的每个丑数分别都乘以2、3和5，事实上是不需要的，因为已有的丑数是按顺序存在数组中的。对乘以2而言，肯定存在某一个丑数T2，排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以2得到的结果都会太大。我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候，去更新这个T2。对乘以3和5而言，存在着同样的T3和T5。
以上是借用：http://zhedahht.blog.163.com/blog/static/2541117420094245366965/ 感觉自己讲不出来。。
除了这种思路外，看到还有大牛用STL中的set自动删除重复元素，这样就更加简单了。
还有一种，纯粹为了A题目，利用第一种方法先得出题目给的1500范围内的所有丑数，然后打表，有点无赖的感觉
http://blog.csdn.net/coder_xia/article/details/6707600 这个大牛总结了很多方法，值得借鉴。
#include <iostream>
#include <cstdio>
using namespace std; int Min(int a,int b,int c)
{
int temp = a>b?b:a;
return (temp>c?c:temp);
} int main()
{
int n;
int Uglynumber[]={,};
int num_1=,num_2=,num_3=;
for(int i = ;i<=;i++)
{
Uglynumber[i]= Min(Uglynumber[num_1]*,Uglynumber[num_2]*,Uglynumber[num_3]*);
if(Uglynumber[num_1]*==Uglynumber[i])
{
num_1++;
}
if(Uglynumber[num_2]*==Uglynumber[i])
{
num_2++;
}
if(Uglynumber[num_3]*==Uglynumber[i])
{
num_3++;
}
}
while(scanf("%d",&n)!=EOF&&n!=)
{
printf("%d\n",Uglynumber[n]);
}
return ;
}