Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and the Yahoo Answers website is now in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

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
    Favorite 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.