竹園論壇

標題: 132 - 資源回收場填充問題 [打印本頁]

作者: jd3 時間: 2014-9-20 20:58
標題: 132 - 資源回收場填充問題
本帖最後由 jd3 於 2014-9-23 00:19 編輯

讀完題目應該能發現其實只是求最大公因數(GCD)

標準作法：輾轉相除

作弊作法：__gcd() ---> 請不要使用這個不營養的東西，參考函式內容就好

Q:為什麼不使用__gcd()
A:不一定到哪都能用，有的比賽也不給你CE訊息會悲劇
只要看到底線就要知道這是一堆工程師避免衝突的共同壞習慣所產生的，一個底線用完不夠就再加一個，前面太多了就加後面......
自己實作也比較容易懂，如果你要打比賽以後也會用到輾轉相除法的延伸

輾轉相除法：

遞迴式：
(a>b) gcd(a,b) = gcd(b, a%b)

證明：
我用個我認為比較好說明的方法
a%b 必定是 a 減去整數*b
所以只要能證明 gcd(a,b) = gcd(a, a-b) 就就好了

令 gcd(A,B) = x , gcd(B, A-B) = y

讓我們把已知條件列出來(管他有沒有用到)
首先可知：
A%x = 0
B%x = 0
B%y = 0
(A-B)%y = 0
由於A,B 都是 x 的整數倍：
(A-B)%x = 0
由於(A-B), B 都是 y 的整數倍：
A%y = 0

綜合以上，稍微找一下就能證明：
x 是 gcd(A,B) 且 y是A,B的公因數
所以y<=x
y 是 gcd(B, A-B) 且 x是B,(A-B)的公因數
所以x<=y

這樣就知道 x=y

得證： gcd(a,b) = gcd(a, a-b) 成立

實作：
以下附上簡短的實作方法
速度算快的

首先是__gcd()裡的方法

[C++] 純文本查看 復制代碼

inline void GCD(int a, int b)

{

    while (b != 0)

    {

        int c = a % b;

        a = b;

        b = c;

    }

    return a;

}

再來是最簡短的方法
雖然用到比較多次MOD
但是少了交換，速度不會差多少

[C++] 純文本查看 復制代碼

inline void GCD(int a, int b)

{

    while((a%=b) && (b%=a));

    return a+b;

}

作者: Brad 時間: 2014-9-20 21:44
所以要少用 __gcd 嗎...
星期五比賽用了...

作者: domen111 時間: 2014-9-21 00:49
本帖最後由 domen111 於 2014-9-21 10:30 編輯

附上我之前做過的研究
遞迴那麼簡短又好寫的方法你居然沒提到! gcd_3這種方法我覺得太不直觀自己要寫出來會很麻煩

[C++] 純文本查看 復制代碼

#include<algorithm>

#include<cmath>

using namespace std;

int gcd_1(int a,int b)//遞迴，我最習慣的，time:849 

{

        if(b==0)return a;

        return gcd_1(b,a%b);

}

int gcd_2(int a,int b)//迴圈，time:1130 

{

        //注意:需要<algorithm>,<cmath>

        while(b)swap(a%=b,b);

        return abs(a);

}

int gcd_3(int a,int b)//迴圈，time:848 

{

        while((a%=b)&&(b%=a));

        return a+b;

}

int main(){}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)