差比和演算法

1. c語言編程-求最大公約數

求差判定法．

如果兩個數相差不大，可以用大數減去小數，所得的差與小數的最大公約數就是原來兩個數的最大公約數．例如：求78和60的最大公約數．78－60＝18，18和60的最大公約數是6，所以78和60的最大公約數是6．

如果兩個數相差較大，可以用大數減去小數的若干倍，一直減到差比小數小為止，差和小數的最大公約數就是原來兩數的最大公約數．例如：求92和16的最大公約數．92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公約數是4，所以92和16的最大公約數就是4．

輾轉相除法．

當兩個數都較大時，採用輾轉相除法比較方便．其方法是：

以小數除大數，如果能整除，那麼小數就是所求的最大公約數．否則就用余數來除剛才的除數；再用這新除法的余數去除剛才的余數．依此類推，直到一個除法能夠整除，這時作為除數的數就是所求的最大公約數．

例如：求4453和5767的最大公約數時，可作如下除法．

5767÷4453＝1餘1314

4453÷1314＝3餘511

1314÷511＝2餘292

511÷292＝1餘219

292÷219＝1餘73

219÷73＝3

於是得知，5767和4453的最大公約數是73．

輾轉相除法適用比較廣，比短除法要好得多，它能保證求出任意兩個數的最大公約數．

--------------------------------------------------------------------------------

小學數學溫習過後，先來個兩個數遞歸版的

int GetGCDRec(int n, int m)
{
if (m < n)
{
m ^= n;
n ^= m;
m ^= n;
}

if (n == 0)
return m;
else
return GetGCDRec(n, m % n);
}
輾轉相除法，求一個數組中所有數的最大公約數

int GetGCD(int *arr, int len)
{
int iMax = arr[0], iCurr, iRemainder;

for(int i = 1; i < len; i++)
{
iCurr = arr[i];

if (iMax < iCurr)
{
iMax ^= iCurr;
iCurr ^= iMax;
iMax ^= iCurr;
}

iRemainder = iMax % iCurr;

while (iRemainder)
{
iMax = iCurr;
iCurr = iRemainder;
iRemainder = iMax % iCurr;
}

iMax = iCurr;
}//for

return iMax;

}
最小公倍數就是乘積除以最大公約數

int GetLCM(int *arr, int len)
{
int multiple = 1;

for (int i = 0; i < len; i++)
multiple *= arr[i];

return multiple / GetGCD(arr, len);
}