C++與演算法

輾轉相除法(Euclidean algorithm)

輾轉相除法是歷史上最著名的演算法之一，是求兩數的 最大公因數(GCD) 極快速的方法。

維基百科 - 輾轉相除法

原理是兩個數字互相減來減去，最後就會剩下構成兩個數字的共通單位，也就是 最大公因數。

圖片來源:昌爸工作坊



[輸入說明]

兩個正整數a、b

[輸出說明]

兩數的最大公因數

[input]

34 10
20 30
30 20
72 96

[output]

2
10
10
24





code 1.0 - 模擬紙上的運算

  • 總是拿較大的數除以較小的數

  • 當其中一數變成0，另外一個數就是最大公因數

#include<iostream>
using namespace std;

int main()
{
    int a, b;
    while( cin >> a >> b )
    {
        while( a!=0 and b!=0 )
        {
            if( a >= b )
            {
                a = a%b;
            }
            else if( b > a )
            {
                b = b%a;
            }
        }

        if( a >= b )
        {
            cout << a << endl;
        }
        else
        {
            cout << b << endl;
        }
    }

    return 0;
}



code 2.0 - 免if版

  • 永遠讓 a是被除數、b是除數

  • 除完之後，除數、被除數互換

  • 當 除數為0，被除數(上一次的除數) 就是最大公因數

#include<iostream>
using namespace std;

int main()
{
    int a, b, t;

    while( cin >> a >> b )
    {
        while( b!=0 )
        {
            t = b;
            b = a%b;
            a = t;
        }
        cout << a << endl;
    }

    return 0;
}



code 3.0 - 遞迴版

  • 利用遞迴讓 被除數(a)、除數(b) 互換
#include<iostream>
using namespace std;

int f( int a, int b )
{
    if( b==0 )
        return a;
    return f( b, a%b );
}

int main()
{
    int a, b;

    while( cin >> a >> b )
    {
        cout << f(a,b) << endl;
    }

    return 0;
}



題目練習