用C語(yǔ)言對(duì)高中教材中關(guān)于計(jì)算最大公因數(shù)算法的實(shí)際檢驗(yàn)

張凡

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

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

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

0 引言

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

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

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

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

2 輾轉(zhuǎn)相除法

2.1 算法原理

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

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

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

6105=2146*2+1813

2146=1813*1+333

1813=333*5+148

333=148*2+37

148=37*4

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

2.2 算法實(shí)現(xiàn)

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

實(shí)驗(yàn)所用代碼如下：

#include

int main（）

{

int a，b，m;

printf（"請(qǐng)輸入兩個(gè)正整數(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é)果及評(píng)價(jià)

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

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

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

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

3 更相減損法

3.1 算法原理

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

也就是說，輾轉(zhuǎn)相除法分為兩個(gè)步驟，一個(gè)步驟為“約減”，另一個(gè)為“減損”，舉個(gè)例子，我們計(jì)算196和126的最大公因數(shù)，首先這兩個(gè)數(shù)都是偶數(shù)，那么同時(shí)將其除以2，得到98和63。顯然，98和63的最大公因數(shù)也是196和126的公因數(shù)，只是比196和126的最大公因數(shù)要少了一半。進(jìn)行這個(gè)環(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)行最后一步操作后得到的是兩個(gè)相等的整數(shù)，那么7就是98和63的最大公因數(shù)了（這也側(cè)面反映了計(jì)算兩個(gè)奇數(shù)的最大公因數(shù)，使用輾轉(zhuǎn)相減法是個(gè)非常不錯(cuò)的方法）。但是要計(jì)算196和126的最大公因數(shù)，我們還要將7乘上剛才所約掉的2。

3.2 算法實(shí)現(xiàn)

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

#include

int main（）

{

long a，b，m，t，r;

printf（"請(qǐng)輸入兩個(gè)正整數(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é)果及評(píng)價(jià)

更相減損實(shí)驗(yàn)結(jié)果，如表2所示。

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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