2011/10/11

[C++]求解兩數GCD、LCM (非遞迴)

今天碰到的題目
利用輾轉相除法來做
非遞迴的版本


#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    int max,min,tmpm,tmpn,temp;
 
    cout << "請輸入第一個數:";
    cin >> max;
    cout << "請輸入第二個數:";
    cin >> min;
 
    if(max < min)
    {
        temp = max;
        max = min;
        min = temp;
    }
 
    tmpm = max;
    tmpn = min;
 
    if(max % min == 0)
    {
        cout << "GCD = " << min << endl;
        cout << "LCM = " << max << endl;
    }
    //
    else
    {
        while(min > 0)
        {
            max = max % min;
            min = min % max;
            if(min == 0)
            {
                cout << "GCD = " << max << endl;
                cout << "LCM = " << max*(tmpm/max)*(tmpn/max) << endl;
            }
        }
    }
 
    system("PAUSE");
    return EXIT_SUCCESS;
}