首页 > 算法 > Ugly Numbers

Ugly Numbers

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

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

  1. 还没有评论
评论提交中, 请稍候...

留言

请输入正确的验证码

可以使用的标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
Trackbacks & Pingbacks ( 0 )
  1. 还没有 trackbacks