欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

http://blog.csdn.net/jtujtujtu/article/details/4407171

2009

參考：http://zhidao.baidu.com/question/50322580.html

輾轉相除法求最大公約數：

輾轉相除法, 又名歐幾里德算法（Euclidean algorithm）乃求兩個(gè)正整數之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出現于歐幾里德的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術(shù)》。它并不需要把二數作質(zhì)因子分解。


證明：
設兩數為a、b(b＜a)，求它們最大公約數gcd(a、b)的步驟如下：用b除a，得a＝bq1＋r1（0≤r1＜b）。若r1=0，則gcd(a，b)＝b；若r1≠0，則再用r1除b，得b＝r1q2＋r2（0≤r2＜r1）。若r2＝0，則gcd(a，b)＝r1，若r2≠0，則繼續用r2除r1，……如此下去，直到能整除為止。其最后一個(gè)非零余數即為gcd(a，b)。

算法:
輾轉相除法是利用以下性質(zhì)來(lái)確定兩個(gè)正整數 a 和 b 的最大公因子的：

   1. 若 r 是 a ÷ b 的余數, 則

          gcd(a,b) = gcd(b,r)

   2. a 和其倍數之最大公因子為 a。

另一種寫(xiě)法是：

   1. a ÷ b，令r為所得余數（0≤r＜b）

          若 r = 0，算法結束；b 即為答案。

   2. 互換：置 a←b，b←r，并返回第一步。

c/c++ 代碼：

遞歸法：

循環(huán)法：

另：考慮大數時(shí)，需要分析可行性，由此得到一些簡(jiǎn)化方法，譬如：

若x, y均為偶數，f（x, y）= 2 * f（x/2, y/2）= 2 * f（x>>1, y>>1）

若x為偶數，y為奇數，f（x, y）= f（x/2, y）= f（x>>1, y）

若x為奇數，y為偶數，f（x, y）= f（x, y/2）= f（x, y>>1）

若x, y均為奇數，f（x, y）= f（x, x - y），

那么在f（x, y）= f（x, x - y）之后，（x - y）是一個(gè)偶數，下一步一定會(huì )有除以2的操作。

因此，最壞情況下的時(shí)間復雜度是O（log₂（max（x, y））。

考慮如下的情況：

       f（42, 30）= f（101010₂, 11110₂）

                       = 2 * f（10101₂, 1111₂）

                       = 2 * f（1111₂, 110₂）

                       = 2 * f（1111₂, 11₂）

                       = 2 * f（1100₂, 11₂）

                       = 2 * f（11₂, 11₂）

                       = 2 * f（0₂, 11₂）

                       = 2 * 11₂

                       = 6

根據上面的規律，具體代碼實(shí)現如下：

代碼清單2-16

{

    if(x < y)

        return gcd(y, x);

    if(y == 0)

        return x;

    else

    {

        if(IsEven(x))

        {

            if(IsEven(y))

                return (gcd(x >> 1, y >> 1) << 1);

            else

                return gcd(x >> 1, y);

        }

        else

        {

            if(IsEven(y))

                return gcd(x, y >> 1);

            else

                return gcd(y, x - y);

        }

    }