張凡

摘 要：最大公因數(shù)，在數(shù)學(xué)領(lǐng)域運(yùn)用十分廣泛，也是計算機(jī)領(lǐng)域自發(fā)展以來的熱門話題之一。本文就高中數(shù)學(xué)課本中所羅列的輾轉(zhuǎn)相除法與更相減損法以C語言為工具，對這兩種算法在實際計算機(jī)的應(yīng)用中做出的檢驗做出評價與分析，并給出實驗的測試數(shù)據(jù)。

關(guān)鍵詞：C語言;最大公因數(shù);算法思想

中圖分類號：TP311.11 文獻(xiàn)標(biāo)識碼：A 文章編號：1671-2064（2019）04-0037-02

0 引言

我們在高中學(xué)習(xí)中，曾學(xué)習(xí)過一個章節(jié)算法與程序框圖，這一章中，我們詳細(xì)地了解了有關(guān)怎樣尋找最大公因數(shù)的應(yīng)用算法以及有關(guān)的程序框圖，算法包括輾轉(zhuǎn)相除法和更相減損法。在現(xiàn)代計算機(jī)社會中，一個算法能否在實際中快速有效地達(dá)到目的是非常重要的一個參考指標(biāo)，它決定著算法的優(yōu)劣。因此，本文旨在以實際操作的方式，對這兩種算法進(jìn)行深入的剖析研究，并對其實用性做出論定。最大公因數(shù)，又稱最大公約數(shù)，是指兩個或兩個以上整數(shù)共有約數(shù)中最大的一個，本文著重介紹對兩個數(shù)最大公約數(shù)的實際檢驗。

1 質(zhì)因數(shù)分解法

學(xué)生時代剛剛接觸到最大公因數(shù)這個概念的時候，老師通常會讓我們使用質(zhì)因數(shù)分解法。所謂質(zhì)因數(shù)分解，它指的是將一個合數(shù)（除了1和自身外還有其他因數(shù)的數(shù)）分解為若干質(zhì)數(shù)（只有1和自身這兩個因數(shù)）的乘積的形式。舉個簡單的例子，對于數(shù)字180，我們對從2開始的質(zhì)數(shù)進(jìn)行逐個的檢驗，首先：180=2*90，那么可以分解出了一個2;繼續(xù)分解，90=2*45，這個時候，不難發(fā)現(xiàn)45不能被2整除，那么可以檢驗是否能被3整除，通過45=3*15，15=3*5這兩個算式，可以得到了5，而5是一個質(zhì)數(shù)，故分解完畢后180=2*2*3*3*5。那么如果要計算180和120的最大公因數(shù)，只需要對120也做上述工作，這樣可以得到120=2*2*2*3 *5，再將兩個數(shù)字分解后多個質(zhì)因數(shù)中的相同部分，選出并計算其乘積，如對180和120進(jìn)行上述運(yùn)算可以得到2*2*3*5=60，那么180和120的最大公因數(shù)就是60。

質(zhì)因數(shù)分解法，看似非常簡單的一個方法，在計算機(jī)程序的運(yùn)行中卻很少涉及，其原因在于計算機(jī)的運(yùn)行方式和人不同，計算機(jī)更習(xí)慣于重復(fù)的、循環(huán)的、相同的任務(wù)體系。對于計算機(jī)，我們要尋求更加方便“計算機(jī)”領(lǐng)悟的方法技巧，這也是本文接下來要給大家介紹的這兩種方法。

2 輾轉(zhuǎn)相除法

2.1 算法原理

輾轉(zhuǎn)相除法[2]，最早是由歐幾里得在公元前300年左右提出的，因此又叫歐幾里得算法。它是指用開始的兩個數(shù)（本文只討論兩數(shù)中最大公約數(shù)的求法，下同）中較大的數(shù)除以較小的數(shù)，得到商和余數(shù)，由于初始兩數(shù)與所得余數(shù)的最大公因數(shù)相等，所以用較小的數(shù)和余數(shù)重復(fù)上述過程，最終得到兩個數(shù)，其中一個能被另一個整除。在計算機(jī)的算法中，這種重復(fù)的、可操作性強(qiáng)的方法，比起傳統(tǒng)的質(zhì)因數(shù)分解法，它更適合計算機(jī)程序進(jìn)行工作。

我們先來看一下這種算法的普通應(yīng)用。以高中教材的數(shù)據(jù)為例，使用輾轉(zhuǎn)相除法求8251和6105的最大公因數(shù)，首先用其中較大的那個數(shù)除以較小數(shù)，所得商和余數(shù)8251=6105*1+2146。通過這個式子，可以得到了余數(shù)2146。由最大公因數(shù)的定義可知，6105、8251以及所得余數(shù)2146它們的最大公約數(shù)其實是相等的，那么接下來只需要計算6105與2146的最大公約數(shù)，這無疑大大地減少了計算量，距離得到結(jié)果又更近了一步。

我們對6105和2146重復(fù)上述步驟（使用輾轉(zhuǎn)相除的時候，我們盡量選擇較小的兩個數(shù)，這樣可以大大地減少計算量）：

6105=2146*2+1813

2146=1813*1+333

1813=333*5+148

333=148*2+37

148=37*4

到這里，不難發(fā)現(xiàn)，我們得到了一個無法取余的式子，那么這個時候，求出的最大公約數(shù)即為37。

2.2 算法實現(xiàn)

經(jīng)過對輾轉(zhuǎn)相除的嘗試，可以初步了解輾轉(zhuǎn)相除法的基本流程，對于其在計算機(jī)上的實用性，我們采用了最常用的開發(fā)工具M(jìn)icrosoft Visual C++進(jìn)行了實驗的檢測[1，4]，整個程序與算法所使用的方式基本一致，我們首先采用了課本中所給出的數(shù)據(jù)，并且類似地進(jìn)行了以下幾組實驗：

實驗所用代碼如下：

#include

int main（）

{

int a，b，m;

printf（"請輸入兩個正整數(shù)，該程序?qū)⑹褂幂氜D(zhuǎn)相除法求其最大公因數(shù)：a="）;

scanf（"%d"，&a）;

printf（"b="）;

scanf（"%d"，&b）;

while（a%b！=0）

{

m=a%b;

a=b;b=m;

}

printf（"a與b最大公因數(shù)為%d＼n"，b）;

return 0;

}

2.3 算法結(jié)果及評價

將實驗中所使用的數(shù)據(jù)列成一張表格，實驗結(jié)果如表1所示。

對于每一個實驗，均采用了變量交換的方法進(jìn)行驗證，這樣做可以更全面地確定實驗的準(zhǔn)確性與完整性。除去課本上的例子，我們還選取了一組數(shù)值較大且明顯互質(zhì)的數(shù)字進(jìn)行檢驗。

計算機(jī)所呈現(xiàn)出來的結(jié)果與我們所預(yù)想的結(jié)果基本一致，在重重考核下，計算機(jī)都出色地完成了任務(wù)。此后進(jìn)行的其他多組重復(fù)數(shù)據(jù)，也向我們證實了輾轉(zhuǎn)相除法在計算機(jī)領(lǐng)域中應(yīng)用的優(yōu)勢。

那么是不是直接使用輾轉(zhuǎn)相除計算最大公因數(shù)就可以了呢？當(dāng)然不是，從數(shù)據(jù)結(jié)構(gòu)的角度而言，輾轉(zhuǎn)相除還有許多不夠完善的方面。諸如，當(dāng)我們涉及到較大的變量時，由于計算機(jī)的除法運(yùn)算和我們的除法運(yùn)算的機(jī)理是完全不同的，計算機(jī)的除法需要進(jìn)行許多額外的繁雜工作，這樣高額的除法運(yùn)算量所帶來的工作量在實際生產(chǎn)生活中無疑會帶來巨大的成本問題。

3 更相減損法

3.1 算法原理

更相減損術(shù)出自《九章算術(shù)》，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之”。用現(xiàn)在的話來講，就是先判斷是否都為偶數(shù)，用2約減后，再以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個操作，直到所得的數(shù)大小相等為止，則這個數(shù)與開始約減的數(shù)乘積即為所求最大公約數(shù)[3]。

也就是說，輾轉(zhuǎn)相除法分為兩個步驟，一個步驟為“約減”，另一個為“減損”，舉個例子，我們計算196和126的最大公因數(shù)，首先這兩個數(shù)都是偶數(shù)，那么同時將其除以2，得到98和63。顯然，98和63的最大公因數(shù)也是196和126的公因數(shù)，只是比196和126的最大公因數(shù)要少了一半。進(jìn)行這個環(huán)節(jié)以后，由于63不是偶數(shù)，那么約減完畢，接下來就是進(jìn)行減損工作。把98和63以大數(shù)減小數(shù)，并進(jìn)行“輾轉(zhuǎn)相減”，得到：

98-63=35;63-35=28;35-28=7;28-7=14;14-7=7

由于進(jìn)行最后一步操作后得到的是兩個相等的整數(shù)，那么7就是98和63的最大公因數(shù)了（這也側(cè)面反映了計算兩個奇數(shù)的最大公因數(shù)，使用輾轉(zhuǎn)相減法是個非常不錯的方法）。但是要計算196和126的最大公因數(shù)，我們還要將7乘上剛才所約掉的2。

3.2 算法實現(xiàn)

如同輾轉(zhuǎn)相除法，針對更相減損法，我們也進(jìn)行了實際檢驗的過程，所使用的代碼如下：

#include

int main（）

{

long a，b，m，t，r;

printf（"請輸入兩個正整數(shù)，該程序?qū)⑹褂酶鄿p損法求其最大公因數(shù)：a="）;

scanf（"%d"，&a）;

printf（"b="）;

scanf（"%d"，&b）;

t=1;

while（（a%2==0）&&（b%2==0））

{

t=t*2;

a=a/2;

b=b/2;

}

while（1）

{

if（a

{

r=b;

b=a;

a=r;

}

while（（a！=b）&&（a>b））

{

m=b;

b=a-b;

a=m;

}

if（a==b） break;

}

a=a*t;

printf（"a與b最大公因數(shù)為%d＼n"，a）;

return 0;

}

3.3 算法結(jié)果及評價

更相減損實驗結(jié)果，如表2所示。

經(jīng)過實驗可以發(fā)現(xiàn)，更相減損法也是計算最大公因數(shù)的良好途徑之一。然而實驗發(fā)現(xiàn)，更相減損所需要的代碼比輾轉(zhuǎn)相除多一倍之多，此時我們要將約減和減損分開作為一個程序的兩個不同的部分進(jìn)行分別處理。而如果去掉約減環(huán)節(jié)，大量的迭代會使較大的、有一定規(guī)律的數(shù)據(jù)的處理效率顯著降低。比如計算999999和3的最大公因數(shù)，使用輾轉(zhuǎn)相除法可以一步到位，然而使用更相減損卻要進(jìn)行巨大的工作量。除了約減的繁瑣以外，每循環(huán)一次，都要進(jìn)行一次對變量a，b的大小比較，也就是說，這一程序一共需要進(jìn)行三次不同的循環(huán)迭代，包括一個循環(huán)的嵌套，在一個較大的程序中，計算最大公因數(shù)不過是一個極小的環(huán)節(jié)而已，如果這樣一個小環(huán)節(jié)都需要耗費(fèi)如此經(jīng)歷，那么這個算法也是不夠成熟的。

4 結(jié)語

雖然說計算兩個數(shù)的最大公因數(shù)，在我們看來也許是非常簡單容易的操作，但是在現(xiàn)代的計算機(jī)領(lǐng)域卻仍然存在各種各樣的問題。除了高中數(shù)學(xué)課本中給我們所展示的這兩種算法外，計算兩個數(shù)的最大公因數(shù)的辦法還有許多，許多方法仍然需要我們?nèi)ゲ粩嗤晟婆c修改。相信在科技的不斷發(fā)展中，一定會有更加完美的算法去適應(yīng)當(dāng)今的時代趨勢。

參考文獻(xiàn)

[1] 譚浩強(qiáng).C程序設(shè)計（第四版）[J].計算機(jī)教育，2010，No.128（20）：113-113.

[2] 邊晶，杜威.深入探析計算機(jī)求解大整數(shù)最大公約數(shù)問題[J].長春大學(xué)學(xué)報，2012，（12）：1476-1479.

[3] 邱建林，劉維富，顧暉.C語言程序設(shè)計教學(xué)的研究與實踐[J].電氣電子教學(xué)學(xué)報，2003，25（4）：96-98.

[4] 黃定華，孫炳達(dá).嵌入式系統(tǒng)中的軟件設(shè)計技術(shù)──語言程序設(shè)計[J].工業(yè)控制計算機(jī)，2001，14（5）：3-6.