最大公約數問題

以上內容摘自《編程之美》P150-154。

為了方便使用，下面是可拷貝的代碼：

Math.h

#pragma once

class Math
{
public:
    Math(void);
    ~Math(void);

public :
    //編程之美P150-154

    //求最大公約數，歐幾里德——輾轉相除法
    static int Gcd1(int x, int y);

    //求最大公約數，歐幾里德——輾轉相除法（變相將除法變成了減法）
    static int Gcd2(int x, int y);

    static int Gcd3(int x, int y);

    inline static bool IsEven(int x);

    inline static int Absolute(int x);
};

Math.cpp

#include "Math.h"

Math::Math(void)
{
}

Math::~Math(void)
{
}

int Math::Gcd1(int x, int y)
{
    //y, x%y順序不能錯；
    return y ? Gcd1(y, x % y) : x;
}

int Math::Gcd2(int x, int y)
{
    //與Gcd1相同的方式，但由于x%y計算速度較x-y要慢，但效果相同，所以換用x - y
    // 但用減法和除法不同的是，比如和，%20=10，-20=70，也就是-4×=10
    // 也就是說迭代次數較Gcd1而言通常是增加了。
    return y ? Gcd1(y, x - y) : x;
}

int Math::Gcd3(int x, int y)
{
    if(x < y)
        return Gcd3(y, x);
    if(y == 0)
        return x;
    else
    {
        if(IsEven(x))
        {
            if(IsEven(y))
                return (Gcd3(x >> 1, y >> 1) << 1);
            else
                return Gcd3(x >> 1, y);
        }
        else
        {
            if(IsEven(y))
                return Gcd3(x, y >> 1);
            else
                return Gcd3(y, x - y);
        }
    }
}

bool Math::IsEven(int x)
{
    return !(bool)x & 0x0001;
}

int Math::Absolute(int x)
{
    return x < 0 ? -x : x;
}

Main.cpp

#include <stdafx.h>
#include <iostream>
#include "Math.h"

using namespace std;
int _tmain(const int & arg)
{
    cout<<"Math::Gcd1(42,30) = "<<Math::Gcd1(42,30)<<endl;
    cout<<"Math::Gcd1(30,42) = "<<Math::Gcd1(30,42)<<endl;
    cout<<"Math::Gcd1(50,50) = "<<Math::Gcd1(50,50)<<endl;
    cout<<"Math::Gcd1(0,0) = "<<Math::Gcd1(0,0)<<endl;
    cout<<"Math::Gcd1(-42,-30) = "<<Math::Gcd1(-42,-30)<<endl;
    cout<<"Math::Gcd1(-42,30) = "<<Math::Gcd1(-42,30)<<endl;

    cout<<"------------------------------"<<endl;

    cout<<"Math::Gcd2(42,30) = "<<Math::Gcd2(42,30)<<endl;
    cout<<"Math::Gcd2(30,42) = "<<Math::Gcd2(30,42)<<endl;
    cout<<"Math::Gcd2(50,50) = "<<Math::Gcd2(50,50)<<endl;
    cout<<"Math::Gcd2(0,0) = "<<Math::Gcd2(0,0)<<endl;
    cout<<"Math::Gcd2(-42,-30) = "<<Math::Gcd2(-42,-30)<<endl;
    cout<<"Math::Gcd2(-42,30) = "<<Math::Gcd2(-42,30)<<endl;

    cout<<"------------------------------"<<endl;

    cout<<"Math::Gcd3(42,30) = "<<Math::Gcd3(42,30)<<endl;
    cout<<"Math::Gcd3(30,42) = "<<Math::Gcd3(30,42)<<endl;
    cout<<"Math::Gcd3(50,50) = "<<Math::Gcd3(50,50)<<endl;
    cout<<"Math::Gcd3(0,0) = "<<Math::Gcd3(0,0)<<endl;
    cout<<"Math::Gcd3(-42,-30) = "<<Math::Gcd3(-42,-30)<<endl;
    cout<<"Math::Gcd3(-42,30) = "<<Math::Gcd3(-42,30)<<endl;

    return 0;
}

不過有一點值得一提，就是所謂性能最好效率最高的Gcd3不支持負數，也就是最后兩行測試代碼無法通過。但是限于對負數的最大公約數并沒有定義，也就是說即便上面的Gcd1和Gcd2好像算出了負數，但它們的結果沒有意義。

posted on 2009-03-04 23:52 volnet 閱讀(1058) 評論(0)  編輯 收藏 引用 所屬分類: 知識庫(KnowledgeLibrary)