李彬

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

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

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

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

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

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

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

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

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

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

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

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

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

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

六、結(jié)語

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

參考文獻：

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

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

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

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

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

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

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

責任編輯 魏家堅