NOJ1167 丑陋數 想法題

NOJ1167 丑陋數 想法題

題意

丑陋數n的意思是n的所有素數因子只有2,3,5。
求出前1500個丑陋數。(第一個丑陋數是1)

思路

用一個數組維護所有的丑陋數。一開始數組中只有一個數就是1。
現在可以確定的丑陋數還有1*2,1*3,1*5。把這三個數中最小的2放進數組。然後變成了2*2,1*3,1*5。再把最小的一個數放進數組…依次執行下去，直到倒數第三個數填滿整個丑陋數數組。
用c2 c3 c5確定目前的和2 3 5相乘的丑陋數。

注意判斷三個數有相等的情況。

代碼

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1510;
int s[maxn];
int main()
{
    s[1] = 1;
    int c2=1,c3=1,c5=1;
    for(int i = 2 ; i < maxn ; i ++) {
        //????s[i]????
        int s2 = s[c2]*2,s3 = s[c3]*3,s5 = s[c5]*5;
        if(s2 < s3) {
            if(s2 < s5) {
                s[i] = s2;
                c2 ++;
                continue;
            }else if(s2 > s5) {
                s[i] = s5;
                c5 ++;
                continue;
            }else {
                s[i] = s5;
                c2 ++; c5 ++;
                continue;
            }
        }else if(s2 > s3) {
            if(s3 < s5) {
                s[i] = s3;
                c3 ++;
                continue;
            }else if(s3 > s5) {
                s[i] = s5;
                c5 ++;
                continue;
            }else {
                s[i] = s5;
                c5 ++; c3 ++;
                continue;
            }
        }else {//s2 = s3
            if(s2 < s5) {
                s[i] = s2;
                c2 ++; c3 ++;
                continue;
            }else if(s2 > s5){
                s[i] = s5;
                c5 ++;
                continue;
            }else {
                s[i] = s2;
                c2 ++; c3 ++; c5 ++;
                continue;
            }
        }
    }
    int n;
    while(scanf("%d",&n) && n) printf("%d\n",s[n]);
    return 0;
}