ACM 136 ugly number 問更快速的算法

Ugly Number的定義為:該數之質因數必須為 2, 3 或 5

當然了,依照慣例,1 也算是 Ugly Number。

在此列舉一串數列:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15

這些就是前 11 個 Ugly Numbers。

請寫一個程式求出第1500個Ugly Number。

有沒有人有很快速的算法,要在30秒內跑完唷,不能直接輸出答案,要算式喔

Update:

可以解說一下你的邏輯麼

1 Answer

Rating
  • ?
    Lv 4
    1 decade ago
    Best Answer

    4377252 2006/03/02 13:08:02.450 Accepted 0:00.000 64 34985 C++ 136 - Ugly Numbers

    #include<iostream>

    using namespace std;

    long long findmin(int a,int b,int c)

    {

    int min=a;

    if(b<a)min=b;

    if(c<min)min=c;

    return min;

    }

    int main()

    {

    int n;

    long long a[1500]={1},na=0,nb=0,nc=0,t;

    for(t=1;t<1500;t++)

    {

    a[t]=findmin(2*a[na],3*a[nb],5*a[nc]);

    if(a[t]%2==0)na++;

    if(a[t]%3==0)nb++;

    if(a[t]%5==0)nc++;

    }

    cout<<"The 1500'th ugly number is "<<a[1499]<<"."<<endl;

    }

    利用動態程式(Dynamic Programming)規劃技巧來避免重覆計算子問題....

    由於避免掉了子問題的計算...於是程式速度就加快很多.不會吃到TLE.....

    2006-09-01 15:36:05 補充:

    如果有問題再問吧...你可以自己畫一棵樹形圖...就會發現這問題會有子問題重覆的情況.避掉重覆子問題計算就可以省下不少時間.

    2006-09-02 14:39:06 補充:

    1 分別乘上 2 3 5 有 2 3 5三種ugly number 2 分別乘上 2 3 5 有 4 6 10三種ugly number3 分別乘上 2 3 5 有 6 9 15三種ugly number 4 分別乘上 2 3 5 有 8 12 20三種ugly number 5 分別乘上 2 3 5 有 10 15 25三種ugly number 6 分別乘上 2 3 5 有 12 18 30三種ugly number你看到我們在做什麼嗎?我們由最小的ugly number 1去找出所有的ugly number

    2006-09-02 14:39:43 補充:

    如此一來..我們可以避免掉(Brute Force)暴力法的多餘計算..連一些不是ugly number都算或是原本是ugly number 確要一直mod 2,3,5直到整除耗費很多mod時間.那na,nb,nc是做啥? 它們是控制現在我們的子問題已經解決到何種程度...也就是2,3,5的下一個uglynumber 分別由第na,nb,nc個ugly number所推來.

    2006-09-02 14:40:11 補充:

    na代表乘上2的下一個ugly number是由a[na]所推來 nb代表乘上3的下一個ugly number是由a[nb]所推來 nc代表乘上5的下一個ugly number是由a[nc]所推來一開始設 na,nb,nc皆為0 表示說接下來我們推導的最小ugly number是由a[0]分別乘上2,3,5推導出來於是我們得到 2,3,5可能是下一個ugly number.那最小的當然是我們的答案.此時 2 只有被2整除使得na++;變成na=1.表示下一次推導出來的ugly number是由a[1]=2所推得.

    2006-09-02 14:40:50 補充:

    我們可以看一下跑法0 1 2 3 4 5-------------------1 2 3 4 5 62 3 5 na=0,nb=0,nc=0 4 3 5 na=1,nb=0,nc=04 6 5 na=1,nb=1,nc=06 6 5 na=2,nb=1,nc=06 6 10 na=2,nb=1,nc=1 //有看到這一步嗎... 由於6都可以由2,3所整除.因此na++,nb++表示它們不用由a[2],a[1]推起8 9 10 na=3,nb=2,nc=1 這就是它大概的運作...如果哪裡有問題可以再問

    Source(s): 曾解過
Still have questions? Get your answers by asking now.