計算機程序設計上輾轉相除法的實際應用分析

李彬

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

一、輾轉相除法概念分析

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

二、輾轉相除法、更相減損法、窮舉法對比分析

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

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

三、輾轉相除法計算最大公約數原理分析

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

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

四、輾轉相除法計算最小公倍數原理分析

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

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

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

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

六、結語

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

參考文獻：

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

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

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

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

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

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

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

責任編輯 魏家堅