n=2^i*3^j*5^k，ijk是自然数。可以得到n序列 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
求此序列第N个数是多少。
一般的人会这样：
把可能的数都算出来，去重，再排序，得到序列
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
set<int>::iterator it = s.begin();
//此处使用1600而非1500，是为了防止类似*it*5 > *(++it)*2的情况出现而导致循环结束时较小的丑数仍未插入容器
while(s.size()<=1600)
{
s.insert(*it*2);
s.insert(*it*3);
s.insert(*it*5);
it++;
}
int n;
while(cin>>n&&n)
{
it = s.begin();
int i = n;
while(--i){
++it;
}
cout<<"The "<<n<<"th ugly number is "<<*it<<"."<<endl;
}
return 0;
}
明白一些的人思路是这个：http://online-judge.uva.es/board/viewtopic.php?f=22&t=26972
引用原文代码是：
int main(void)
{
int N;
while(scanf("%d", &N)){
if(N <= 0) continue;
int v, p, temp;
v = 1; p = 1;
while(p < N){
v++;
temp = v;
while(temp % 2 == 0) temp /= 2;
if(temp == 1) { p++; continue;}
while(temp % 3 == 0) temp /= 3;
if(temp == 1) { p++; continue;}
while(temp % 5 == 0) temp /= 5;
if(temp == 1) { p++; continue;}
}
printf("%d\n", v);
}
return 0;
}
数小还可以，数大了就会很慢了
然后算法更精一些的人还可以这样：http://www.2cto.com/kf/201306/222203.html
引用原文代码是：
#include<stdio.h>
int main(void)
{
int un[1505]={0};
int m2=0,m3=0,m5=0,n,t;
un[0]=1;
for(n=1;n<1500;n++)
{
if(2*un[m2]>3*un[m3])
t=un[m3]*3;
else
t=un[m2]*2;
if(t>un[m5]*5)
t=un[m5]*5;
if(t == 2*un[m2]) m2++;
if(t == 3*un[m3]) m3++;
if(t == 5*un[m5]) m5++;
un[n]=t;
}
printf("The 1500'th ugly number is %d.\n",un[1499]);
return 0;
}
算法思路就是先定义一个集合，该集合中有元素1，如果x在集合中，并且y是x的下一个丑数，那么x*2，x*3，x*5也在集合中，其它数不再集合中，这三个数中必定是2x最小，因此首先放入数组中，而此时*2最小的应该是x的下一个丑数y*2，此时应该找出y*2，x*3，x*5中最小的数放入数组，以此类推，具体操作如下：
1
*2
*3
*5
选出乘积最小的，加入到结果集中，相应指针右移
1 2
*3 *2
*5
选出乘积最小的，加入到结果集中，相应指针右移
1 2 3
*5 *2
*3
选出乘积最小的，加入到结果集中，相应指针右移
1 2 3 4
*5 *3 *2
选出乘积最小的，加入到结果集中，相应指针右移
1 2 3 4
*3 *2
*5
以此类推，直到获得足够长的结果集
嗯。算是空间换时间吧。目的下标不确定的话需要自己处理数组空间。不过速度与前者比较那是相当的快啊。
不知道还有没有更好的解法。
