計(jì)算機(jī)程序設(shè)計(jì)上輾轉(zhuǎn)相除法的實(shí)際應(yīng)用分析

李彬

在計(jì)算機(jī)運(yùn)算和編程的過(guò)程中，最終運(yùn)算結(jié)果為正負(fù)數(shù)的現(xiàn)象是非常普遍存在的，而這些最終數(shù)據(jù)的正負(fù)數(shù)會(huì)直接影響到程序員設(shè)計(jì)計(jì)算機(jī)程序的效率問(wèn)題，如果在計(jì)算機(jī)編程的過(guò)程中使用輾轉(zhuǎn)相除法則可以避免這些問(wèn)題的出現(xiàn)。在計(jì)算機(jī)的計(jì)算程序中，輾轉(zhuǎn)相除法是代數(shù)計(jì)算的重要理論，輾轉(zhuǎn)相除法的運(yùn)算特點(diǎn)和計(jì)算機(jī)的運(yùn)行程序有著很大的共通性，在具體的運(yùn)算過(guò)程中可以使用輾轉(zhuǎn)相除法來(lái)求得最大公約數(shù)，那么就避免了最終輸出結(jié)果存在正負(fù)整數(shù)的問(wèn)題，程序員就可以在自然數(shù)的范圍之內(nèi)進(jìn)行，這樣的計(jì)算流程可以大大節(jié)省計(jì)算時(shí)間，同時(shí)也提高了計(jì)算結(jié)果的準(zhǔn)確性，有著非常良好的應(yīng)用前景。

一、輾轉(zhuǎn)相除法概念分析

輾轉(zhuǎn)相除法，又名euclidean algorithm，是一種求最大公約數(shù)的一種方法。它的具體流程為：用數(shù)列中較大的數(shù)來(lái)除以最小的數(shù)，然后用這兩個(gè)數(shù)相除得出的余數(shù)再去除以除數(shù)，接著再用這兩個(gè)數(shù)的余數(shù)來(lái)除以前面的第一個(gè)余數(shù)，按照這樣的流程反復(fù)相除，直至除到最后余數(shù)為零為止。那么最后一次的這個(gè)除數(shù)就是開(kāi)始計(jì)算時(shí)兩個(gè)數(shù)的最大公約數(shù)。

二、輾轉(zhuǎn)相除法、更相減損法、窮舉法對(duì)比分析

通過(guò)上述的概念分析，我們可以知道輾轉(zhuǎn)相除法有著較大的優(yōu)點(diǎn)，它的連續(xù)相除能夠使得整個(gè)計(jì)算流程以一種比較系統(tǒng)的方法來(lái)求出兩個(gè)數(shù)的最大公約數(shù)，而不需要我們?cè)賹?duì)兩個(gè)數(shù)進(jìn)行因式分解。因?yàn)樵诰唧w的計(jì)算和操作過(guò)程中，因數(shù)分解是一個(gè)比較困難的過(guò)程，尤其是數(shù)量比較大的時(shí)候，因數(shù)分解對(duì)于程序員來(lái)說(shuō)更是不小的挑戰(zhàn)，即便是現(xiàn)代最先進(jìn)的計(jì)算機(jī)加入，也是對(duì)此非常難以處理的。當(dāng)然，輾轉(zhuǎn)相除法也有著自身的缺點(diǎn)，從上文的論述中我們可以清晰地看出，輾轉(zhuǎn)相除法的運(yùn)算是非常繁瑣和復(fù)雜的，長(zhǎng)時(shí)間的運(yùn)算很容易出現(xiàn)差錯(cuò)，而且從算法的實(shí)現(xiàn)角度來(lái)看，這種方法對(duì)于運(yùn)行設(shè)備的存儲(chǔ)空間要求是比較大的，其運(yùn)算時(shí)間也是非常長(zhǎng)的，其運(yùn)算速度也不太快。而窮舉法的主要計(jì)算思想就是根據(jù)數(shù)量的主要特征來(lái)確定出大致的范圍，然后對(duì)數(shù)值進(jìn)行一個(gè)一個(gè)的驗(yàn)證，如果某一個(gè)情況是符合題目的條件的，那么就是該題目的唯一解，如果不符合條件，則無(wú)解。其主要的優(yōu)點(diǎn)就在于計(jì)算簡(jiǎn)單，但是其主要缺點(diǎn)是運(yùn)行所需要花費(fèi)的時(shí)間比較長(zhǎng)，在利用窮舉法的時(shí)候，我們通常采用的是三種列舉方法，第一是順序列舉，該方法是指在答案的范圍內(nèi)的各種情況是很容易和自然數(shù)進(jìn)行一一對(duì)應(yīng)的，或者說(shuō)本身就是自然數(shù)，那么具有這樣的特征的時(shí)候，我們就可以使用順序列舉;第二是排列列舉，該種方法主要指的是數(shù)據(jù)的形式是一組數(shù)的排列方式，我們可以列舉出所有答案所在范圍內(nèi)的排列，這就是所謂的排列列舉;第三是組合列舉，組合列舉是無(wú)序排列的，也是說(shuō)當(dāng)答案額度數(shù)據(jù)形式為一些元素的組合的時(shí)候，我們通常是要采用組合列舉的。

更相減損法是出自于我們前人的《九章算術(shù)》中的一種算法，是一種求最大公約數(shù)的算法，它本來(lái)是為數(shù)據(jù)的約分而設(shè)計(jì)的，應(yīng)用是比較廣泛的，隨著計(jì)算機(jī)的興起，更相減損術(shù)作為一種算法也是廣泛應(yīng)用在數(shù)學(xué)和計(jì)算機(jī)工程中的。和輾轉(zhuǎn)相除法相比，這兩種方法都是求最大公因數(shù)的方法，在主要的計(jì)算方法上，輾轉(zhuǎn)相除法主要是以除法為主要算法，而更相減損術(shù)主要?jiǎng)t是以減法為算法，但是在計(jì)算的次數(shù)對(duì)比上來(lái)看，輾轉(zhuǎn)相除法的計(jì)算次數(shù)是相對(duì)較少的，但是如果兩個(gè)數(shù)字之間的大小差別很大的時(shí)候，兩者的計(jì)算次數(shù)是比較明顯的。從最終的結(jié)果體現(xiàn)形式來(lái)看，輾轉(zhuǎn)相除法最終的結(jié)果是相除的余數(shù)為0得到的，而更相減損術(shù)主要是和減數(shù)的差而得到的。更相減損法在兩個(gè)數(shù)量之間的差距比較大的時(shí)候可以將時(shí)間復(fù)雜度退化成0（N），而輾轉(zhuǎn)相除法則可以穩(wěn)定在0（logN）。所以，在目前的應(yīng)用中，輾轉(zhuǎn)相除法和計(jì)算機(jī)算法的結(jié)合較為緊密。

三、輾轉(zhuǎn)相除法計(jì)算最大公約數(shù)原理分析

輾轉(zhuǎn)相除法有著較大的優(yōu)點(diǎn)，它的連續(xù)相除能夠使得整個(gè)計(jì)算流程以一種比較系統(tǒng)的方法來(lái)求出兩個(gè)數(shù)的最大公約數(shù)，而不需要我們?cè)賹?duì)兩個(gè)數(shù)進(jìn)行因式分解。這樣可以避免因式分解中的盲目性，提供了運(yùn)算的效率。根據(jù)數(shù)學(xué)上最大公約數(shù)的定義，在使用輾轉(zhuǎn)相除法來(lái)求取數(shù)字的最大公約數(shù)的時(shí)候，我們主要是通過(guò)數(shù)字之間的反復(fù)計(jì)算、反復(fù)相除來(lái)求出最大公約數(shù)。具體的計(jì)算過(guò)程可以通過(guò)文字描述如下：對(duì)于題目中已知的兩個(gè)數(shù)量A、B，我們采用A÷B的算法，進(jìn)而求出A÷B的值，在大多數(shù)情況下，A÷B的值都不是一個(gè)整數(shù)，還會(huì)有余數(shù)現(xiàn)象的產(chǎn)生，我們將它們相除的余數(shù)用C來(lái)表示，一般而言，最終的計(jì)算結(jié)果可以分為兩種，第一，C=0，那么我們就將此時(shí)的B的值稱之為A、B的最大公約數(shù)，第二，C≠0，那么我們就接著用B÷C，這時(shí)同樣有兩種情況，當(dāng)結(jié)果不等于零的時(shí)候我們就接著按照上述的過(guò)程進(jìn)行計(jì)算，直至最終的結(jié)果為零為止，最終得到的結(jié)果就是A、B兩數(shù)的最大公約數(shù)。舉個(gè)具體的例子來(lái)說(shuō)，求整數(shù)31875和6375的最大公約數(shù)，按照上述的方法，我們首先拿31875÷6375，得到了結(jié)果為5，說(shuō)明此時(shí)的余數(shù)為0，那么31875和6375的最大公約數(shù)就為6375，而12345和765的最大公約數(shù)計(jì)算就和上述計(jì)算略有不同，首先我們先計(jì)算12345÷765最終的結(jié)果為16余105，這時(shí)候我們發(fā)現(xiàn)余數(shù)不等于0，那么就需要我們接著進(jìn)行下去，就拿765÷105，最終的結(jié)果為7余30，這時(shí)候的余數(shù)不為0，所以我們接著進(jìn)行上述的計(jì)算，用105÷30得到3余15，其余數(shù)依然不為零，那么我們就接著用30÷15得到了整數(shù)為2，這時(shí)候我們就可以認(rèn)為12345和765的最大公約數(shù)為15.這種循環(huán)往復(fù)的計(jì)算非常適合計(jì)算機(jī)的程序設(shè)計(jì)特點(diǎn)，所以我們?cè)谟?jì)算機(jī)的編程中輸入圖1所示的語(yǔ)句，在該式子中，M、N代表兩個(gè)整數(shù)，其中R作為余數(shù)，我們可以將上述的兩個(gè)例子帶入試算。

首先將整數(shù)31875輸入到程序框內(nèi)，然后在接著的程序框中輸入整數(shù)6375，按下運(yùn)算鍵1之后，我們可以得到的結(jié)果顯示為：？/31875/？/6375/6375-Disp-。在第二個(gè)例子的試算中，我們將整數(shù)12345輸入到程序框中，在接著的程序框中輸入765，同樣按下運(yùn)算鍵1，最終得到的結(jié)果顯示為：？/12345/？/765/15/-Disp-。

四、輾轉(zhuǎn)相除法計(jì)算最小公倍數(shù)原理分析

利用計(jì)算機(jī)的程序計(jì)算兩個(gè)數(shù)的最小公倍數(shù)其原理是和求最大公倍數(shù)有著相似的特點(diǎn)的，是在求最大公約數(shù)的基礎(chǔ)上進(jìn)行的，在求A、B兩數(shù)的最小公倍數(shù)時(shí)，首先要計(jì)算出A×B的值，然后再計(jì)算出A×B的值除以A與B的最大公約數(shù)的值，然后得到的商C就是A、B的最小公倍數(shù)。

舉個(gè)例子來(lái)說(shuō)，求12345和765的最小公倍數(shù)，那么按照上述的計(jì)算流程就是先用12345×765，計(jì)算出的結(jié)果為9443925，然后根據(jù)上文的計(jì)算結(jié)果，我們知道12345和765的最大公約數(shù)為15，那么我們就拿9443925÷15得到結(jié)果629595，那么12345和765的最小公倍數(shù)就是629595，具體的計(jì)算機(jī)系統(tǒng)編程語(yǔ)言見(jiàn)圖2所示。在下圖中，A、B是代表兩個(gè)整數(shù)，我們將12345輸入到對(duì)話框中，接著輸入765，按下運(yùn)算鍵1，得到了最終的結(jié)果為629595，計(jì)算機(jī)的編程顯示為：？/12345/？/765/629595/-Disp-。

五、二元一次不定方程整數(shù)解的求解過(guò)程分析

從二元一次不定方程整數(shù)解的求解原理來(lái)看，其主要的核心是判斷二元一次不定方程的整數(shù)解是否存在的問(wèn)題，也是說(shuō)通過(guò)判定兩個(gè)系數(shù)的最大公約數(shù)和最小公倍數(shù)的基礎(chǔ)上綜合進(jìn)行的。例如，我們假設(shè)二元一次方程為ax+by=C，其中abc均為整數(shù)，那么在計(jì)算的過(guò)程中就是尋找該方程是否具有整數(shù)解的過(guò)程。在求解的過(guò)程中，我們首先要計(jì)算出a和b的最大公約數(shù)，該過(guò)程可以利用輾轉(zhuǎn)相除法進(jìn)行求解，求出的最大公約數(shù)我們將其命名為d，然后使用c÷d，如果c÷d的余數(shù)為0，那么就說(shuō)明二元一次不定方程ax+by=C是存在著整數(shù)解的，而且整數(shù)解的數(shù)量是無(wú)窮個(gè)，如果c÷d的值不為零，那么就說(shuō)明ax+by=C二元一次不定方程不存在整數(shù)解，也就是說(shuō)該等式的整數(shù)解為零。舉個(gè)具體的例子來(lái)說(shuō)，我們來(lái)判斷一下28x+12y=200是否存在著整數(shù)解。我們可以參照上述的方法來(lái)進(jìn)行運(yùn)算。首先利用我們所述的輾轉(zhuǎn)相除法來(lái)計(jì)算出28和12的最大公約數(shù)，也就是用28除以12，得到結(jié)果為2余4，此時(shí)的結(jié)果不為零，那么我們就接著用12除以4等于3，此時(shí)得到了整除，那么我們可以認(rèn)為4為28和12的最大公約數(shù)，然后計(jì)算出200÷4=50，也就是說(shuō)此時(shí)的余數(shù)為0，也就是說(shuō)該等式28x+12y=200是存在著整數(shù)解的，而且整數(shù)解有無(wú)數(shù)個(gè)。再舉個(gè)例子來(lái)說(shuō)，我們要求2x+4y=1是否具有整數(shù)解。首先，我們采用輾轉(zhuǎn)相除法來(lái)計(jì)算出2和4的最大公約數(shù)，通過(guò)計(jì)算4÷2我們知道其結(jié)果為2，是整除的，那么就說(shuō)明，4和2的最大公約數(shù)為2，然后再計(jì)算1÷2的值，我們發(fā)現(xiàn)并不能整除，那么就說(shuō)明該等式2x+4y=1是不存在整數(shù)解的，在具體的應(yīng)用中我們主要是利用N-S的結(jié)構(gòu)化流程圖來(lái)描述其算法，詳細(xì)見(jiàn)圖3所示。

六、結(jié)語(yǔ)

計(jì)算機(jī)的發(fā)明和使用為人們的計(jì)算提供了更多的便利，在計(jì)算機(jī)的計(jì)算程序中，輾轉(zhuǎn)相除法是代數(shù)計(jì)算的重要理論，將其編制在計(jì)算機(jī)程序中能夠?qū)λ惴ㄟM(jìn)行較大程度的改良，換句話說(shuō)，輾轉(zhuǎn)相除法的運(yùn)算特點(diǎn)和計(jì)算機(jī)的運(yùn)行程序有著很大的共通性，因此，輾轉(zhuǎn)相除法應(yīng)用到計(jì)算機(jī)程序之中能夠更好地與計(jì)算機(jī)的性能結(jié)合，能夠更加快速和便捷地求出一些較為復(fù)雜算式中的最大公約數(shù)和最小公倍數(shù)，同時(shí)還能夠解決計(jì)算機(jī)算法中的一些疑難問(wèn)題，有著非常好的應(yīng)用效果。通過(guò)上述的論述和研究，我們也可以清晰地看出輾轉(zhuǎn)相除法在解決一些計(jì)算機(jī)中的復(fù)雜問(wèn)題具有比較強(qiáng)的優(yōu)勢(shì)，尤其是在處理和解決整數(shù)之間求取最大公約數(shù)、最小公倍數(shù)以及二元一次方程的整數(shù)解等方面的問(wèn)題有著較好的準(zhǔn)確性。本文的研究也是立足于理論，比較和分析了輾轉(zhuǎn)相除法的優(yōu)勢(shì)與特點(diǎn)，從當(dāng)前的實(shí)際應(yīng)用情況出發(fā)，對(duì)于程序設(shè)計(jì)中的輾轉(zhuǎn)相除法的相關(guān)適用情況和算法語(yǔ)句進(jìn)行了深入分析，明確了輾轉(zhuǎn)相除法的基本原理以及使用范圍，對(duì)于輾轉(zhuǎn)相除法中的程序設(shè)計(jì)問(wèn)題也進(jìn)行了探討，并且從程序運(yùn)行的角度來(lái)解決數(shù)據(jù)計(jì)算的問(wèn)題，這樣可以解決實(shí)際操作過(guò)程中的一些問(wèn)題，大大的提高的運(yùn)算的效率和質(zhì)量，提高運(yùn)算的精度，為計(jì)算機(jī)的運(yùn)算提供了新的思路。

參考文獻(xiàn)：

[1]楊妮，魏春強(qiáng). 輾轉(zhuǎn)相除法的統(tǒng)一公式及其應(yīng)用[J]. 安康學(xué)院學(xué)報(bào)，2018，30（01）：107-109.

[2]汪仲文，官春梅，王和香，鄒庭榮. 多項(xiàng)式最大公因式的啟發(fā)式教學(xué)實(shí)踐[J]. 大學(xué)數(shù)學(xué)，2017，33（01）：103-108.

[3]王鵬. 計(jì)算機(jī)程序設(shè)計(jì)上輾轉(zhuǎn)相除法的實(shí)際應(yīng)用研究[J]. 數(shù)字技術(shù)與應(yīng)用，2017（06）：78-79.

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

[5]何躍. 基于Small Basic的最大公約數(shù)算法的實(shí)現(xiàn)及其效率驗(yàn)證[J]. 科技展望，2016，26（30）：198-199.

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

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

責(zé)任編輯 魏家堅(jiān)