热久久国产精品,久久国产乱子精品免费女,囯产精品久久久久久久久蜜桃

數論(1)-----歐幾里得算法

一. 歐幾里得算法------求最大公約數

1.公式：
     gcd(a,b)=gcd(b,a mod b)    (a為非負整數，b為正整數)

2.證明：
      思路：
           兩個整數a和b，如果a|b&&b|a（即a,b能互相整除），那么a=b.

      基礎知識準備：
           A. (a mod b)=a-qb , q=(int)a/b;
           B. d|a&&d|b => d|(xa+yb) x,y為任意整數
           C. d|a&&d|b => d|gcd(a,b)

      過程：（1）證：gcd(a,b)|gcd(b,a mod b)

                  設d=gcd(a,b)=>d|a&&d|b,
                  由A和B知道，d|a&&d|b=>d|(xa+yb)=>d|(a mod b)
                  由C知道，d|b&&d|(a mod b)=>d|gcd(b,a mod b)=>gcd(a,b)|gcd(b,a mod b);

            (2) 證：gcd(b,a mod b)|gcd(a,b)

                  設d=gcd(b,a mod b)=>d|b&&d|(a mod b),
                  由A和B知道, d|b&&d|(a mod b)=>d|(xb+y(a mod b)=>d|a(由A，a=qb+(a mod b))
                  由C知道，d|a&&d|b=>d|gcd(a,b)=>gcd(b,a mod b)|gcd(a,b)

             由（1）和（2），可以知道我們得證了。

3.程序模板：

//遞歸版本

int gcd(int a,int b)

{

return b?gcd(b,a%b):a;

}

//循環版本

int gcd1(int a,int b)

{

for(int c=a%b;c;a=b,b=c,c=a%b);

return b;

}

4.學習心得

    歐幾里得算法是之后很多數論算法的基礎，了解它的原理是很有必要的。
    自己要舉幾個例子來熟悉一下算法的執行過程中的每一步驟，這樣才能記憶深刻。
    上述的基礎知識也是很有用的，平時注意積累。不懂的地方就幾個實例看一下。

posted on 2009-09-05 15:48 原語餓狼閱讀(420) 評論(0) 編輯收藏引用所屬分類: 數論

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 數論(4)--------求解模線性方程數論(3)-------歐拉phi函數數論(2)-------擴展歐幾里得算法數論(1)-----歐幾里得算法

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

yuanyuelang

導航

留言簿

隨筆分類

文章分類

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

最新評論

數論(1)-----歐幾里得算法