查看: 572|回復: 8

[TOJ] 132 - 資源回收場填充問題

[複製鏈接]
  • TA的每日心情
    鬱悶
    2015-5-15 22:38
  • 簽到天數: 33 天

    [LV.5]常住居民I

    75

    主題

    302

    帖子

    766

    積分

    版主

    TFcis - 105 附設監工官

    Rank: 7Rank: 7Rank: 7

    積分
    766

    台南一中資訊社程式設計達人 - 2014

    發表於 2014-9-20 20:58:28 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 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;
    }







    點評

    jd3
    喔喔真的耶sorry...  發表於 2014-9-23 00:19
    第九行應該是 return a; 吧  發表於 2014-9-22 23:42

    評分

    參與人數 1金幣 +4 收起 理由
    domen111 + 4 給個讚!

    查看全部評分

    <這是個人簽名欄位>
    回復

    使用道具 檢舉

  • TA的每日心情
    開心
    2014-11-18 21:47
  • 簽到天數: 9 天

    [LV.3]偶爾看看II

    1

    主題

    40

    帖子

    343

    積分

    好好學生

    Rank: 3Rank: 3

    積分
    343

    程式設計達人 - 2014新手達陣台南一中資訊社

    發表於 2014-9-20 21:44:46 | 顯示全部樓層
    所以要少用 __gcd 嗎...
    星期五比賽用了...

    點評

    我是覺得比賽用__gcd沒什麼關係(不過要注意編譯器是g++),如果是開發當然就不該用,不過事實上我也很少用c++開發  發表於 2014-9-21 00:45
    jd3
    像是 Visual的和DEV的常常就底線數量不一樣  發表於 2014-9-20 23:39
    本來就不應該用,只是為了比賽方便才提出__gcd,此函數不是標準函數/外部使用的函數,設計師也不應該使用  發表於 2014-9-20 21:53
    回復 支持 反對

    使用道具 檢舉

  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2014-9-21 00:49:10 | 顯示全部樓層
    本帖最後由 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(){}


    點評

    jd3
    恩恩忘記講遞迴了......................不要用swap啦會變慢  發表於 2014-9-21 22:58
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復 支持 反對

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表