計算機程序設(shè)計上輾轉(zhuǎn)相除法的實際應(yīng)用研究

王鵬

摘要：本文從最大公約數(shù)、最小公倍數(shù)以及判斷二元一次不定方程整數(shù)解等三個問題闡述了計算機程序設(shè)計上對于輾轉(zhuǎn)相除法的實際應(yīng)用過程。旨在明確輾轉(zhuǎn)相除法在計算機程序設(shè)計方面的重要利用價值，通過應(yīng)用輾轉(zhuǎn)相除法更加快速、高效的解決大部分的數(shù)據(jù)計算問題，表明計算機程序具有簡單、快捷的廣泛運用前景。

關(guān)鍵詞：計算機程序設(shè)計；輾轉(zhuǎn)相除法；實際應(yīng)用

中圖分類號：TP311.1 文獻標(biāo)識碼：A 文章編號：1007-9416（2017）06-0078-02

1 利用輾轉(zhuǎn)相除法求最大公約數(shù)

根據(jù)最大公約數(shù)的代數(shù)定義，在利用輾轉(zhuǎn)相除法求取算式的最大公約數(shù)時，通過數(shù)字之間的反復(fù)、重復(fù)相除過程實現(xiàn)該算式最大公約數(shù)的求取。具體過程如下：設(shè)定已知的整數(shù)X和Y，列式“X÷Y”，并計算X除以Y的值。主要觀察式子“X÷Y”所得余數(shù)的數(shù)值，用字母Z表示。會有如下兩種計算結(jié)果：第一，當(dāng)“Z=0”時，這種情況較為簡單，此時Y稱之為X與Y的最大公約數(shù)。第二，當(dāng)“Z≠0”時，列式“Y÷Z”繼續(xù)進行計算，再判斷所得余數(shù)Z1是否為0。當(dāng)“Z1=0”時，此時Z就是X與Y的最大公約數(shù)；當(dāng)“Z1≠0”時，再列式“Z÷Z1”進行計算，得到余數(shù)Z2，繼續(xù)判斷Z2是否為0，重復(fù)和按照上一循環(huán)的判斷標(biāo)準(zhǔn)，直至“Zn=0”的情況出現(xiàn)，此時計算得到Zn算式中的分母Zn-1就是X和Y的最大公約數(shù)[1]。

例一：（a）求整數(shù)31260和6252的最大公約數(shù)。（b）求整數(shù)12345與765的最大公約數(shù)。具體計算過程如下：（a）根據(jù)“X÷Y”列式計算得“31260÷6252=5”，此時余數(shù)為0，因此整數(shù)31260和6252的最大公約數(shù)為6252。（b）根據(jù)“X÷Y”列式計算得“12345÷765=16……105”，此時余數(shù)不為0，因此繼續(xù)列式計算得“765÷105=7……30”，此時余數(shù)仍然不為0，因此繼續(xù)列式計算“105÷30=3……15”，此時余數(shù)不為0，因此繼續(xù)列式計算“30÷15=2”，此時余數(shù)為0，最終計算得到12345與765的最大公約數(shù)為15。

運用計算機技術(shù)，利用輾轉(zhuǎn)相除法求最大公約數(shù)，所需要的編成表達如圖1所示。

其中M、N分別指代的兩個整數(shù)，R指代余數(shù)，分別將題（a）和題（b）中的數(shù)據(jù)帶入計算機程序中進行運用，具體做法如下：

（a）直接將整數(shù)31260輸入程序框內(nèi)，提行輸入整數(shù)6252，按下運算鍵“1”之后得到的計算結(jié)果顯示為：？/31260/？/6252/6252/-Disp-.（b）直接將整數(shù)12345輸入程序框內(nèi)，提行輸入整數(shù)765，按運算鍵“1”之后得到計算結(jié)果顯示為：？/12345/？/765/15/-Disp-。

2 利用輾轉(zhuǎn)相除法求最小公倍數(shù)

算式與整數(shù)的最小公倍數(shù)求法，是在求得其最大公約數(shù)的基礎(chǔ)上進行的。利用輾轉(zhuǎn)相除法計算整數(shù)X與Y的最小公倍數(shù)，首先要將計算式子“X×Y”的結(jié)果Z，然后再計算X與Y的乘積除以X與Y最大公約數(shù)的結(jié)果，此時得到的商A就是X與Y的最小公倍數(shù)[2]。

例二：求整數(shù)12345與765的最小公倍數(shù)。具體計算過程如下：首先計算“12345×765=9443925”，然后計算“9443925÷15=629595”，因此12345與765的最小公倍數(shù)為629595。計算機程序設(shè)計過程如圖2所示。

其中A、B指代的是兩個整數(shù)，先將整數(shù)12345輸入到程序框內(nèi)，替換掉A的位置，提行輸出正如765，替換掉B的位置。按下運算鍵“1”之后，得到629595的運算結(jié)果，計算機顯示為：？/12345/？/765/629595/-Disp-。

3 利用輾轉(zhuǎn)相除法判斷二元一次不定方程的整數(shù)解問題

二元一次不定方程整數(shù)解存在與否的判斷過程，需要在最大公約數(shù)和最小公倍數(shù)的基礎(chǔ)上進行。二元一次不定方程的表達式如下：aX+bY=c。其中a、b、c均為已知整數(shù)，要判斷該方程式是否存在整數(shù)解，首先要利用輾轉(zhuǎn)相除法求得a與b的最大公約數(shù)d，然后按照“c÷d”進行計算，判斷c能否將a與b的最大公約數(shù)整除，如果計算“c÷d”得到的余數(shù)為0，則說明方程式“aX+bY=c”存在整數(shù)解，且整數(shù)解的數(shù)量為無數(shù)多個；如果計算“c÷d”得到的余數(shù)不為0，說明方程式“aX+bY=c”不存在整數(shù)解，即整數(shù)解的個數(shù)為0[3]。

例三：（a）判斷方程式28X+12Y=200是否存在整數(shù)解。（b）判斷方程式2X+4Y=1是否存在整數(shù)解。

具體計算過程如下：（a）首先利用輾轉(zhuǎn)相除法計算28和12存在的最大公約數(shù)，28÷12=2……4，此時余數(shù)不為0，因此繼續(xù)列式計算“12÷4=3”，此時余數(shù)為0，也就是說28與12存在的最大公約數(shù)為4。然后列式計算“200÷4=50”，余數(shù)為0證明方程式28X+12Y=200存在整數(shù)解，且整數(shù)解的數(shù)量為無數(shù)個。（b）同樣先利用輾轉(zhuǎn)相除法計算2和4的最大公約數(shù)，4÷2=2，余數(shù)為0，因此2與4的最大公約數(shù)為2。再通過式子1÷2的計算結(jié)果，判斷出1不能夠?qū)?整除，因此方程式2X+4Y=1不存在整數(shù)解。利用N-S結(jié)構(gòu)化流程圖來描述其算法如圖3所示。

4 結(jié)語

綜上所述，通過論述求取整數(shù)最大公約數(shù)、最小公倍數(shù)以及判斷二元一次方程式整數(shù)解問題等實例，分析了計算機程序設(shè)計中輾轉(zhuǎn)相除法的實際應(yīng)用情況，不僅明確了輾轉(zhuǎn)相除法的基本原理和應(yīng)用范圍，同時了解了利用輾轉(zhuǎn)相除法進行計算機程序設(shè)計，能夠更加方便的解決大部分的數(shù)據(jù)計算問題，省去了在程序設(shè)計中的不少麻煩，提高了計算機編程人員的變成效率與質(zhì)量。

參考文獻

[1]王玉新.計算機程序設(shè)計上輾轉(zhuǎn)相除法的實際應(yīng)用研究[J].數(shù)字技術(shù)與應(yīng)用，2016，（3）：116.

[2]王曉英.輾轉(zhuǎn)相除法求解二元一次不定方程[J].赤峰學(xué)院學(xué)報：自然科學(xué)版，2014，（23）：6-7.

[3]陳占鐵.輾轉(zhuǎn)相除法反推計算的矩陣表達式[J].遼寧省交通高等?？茖W(xué)校學(xué)報，2015，（5）：32-33+39.

Abstract：This article from the common denominator， LCM and judge two indeterminate problem three integer solution of equation describes the application process of computer program design for the Euclidean algorithm. To clear division algorithm and use in computer program design value， through the application of Euclidean algorithm to calculate the problem more quickly and efficiently solve most of the data shows that the computer program is simple， fast and widely application prospect.

Key Words：computer programming； divide by phase； practical applicationendprint