輕微&花花

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
以此类推，直到获得足够长的结果集
嗯。算是空间换时间吧。目的下标不确定的话需要自己处理数组空间。不过速度与前者比较那是相当的快啊。
不知道还有没有更好的解法。