當前位置:文檔下載 > 所有分類 > 自然科學 > 數學 > 輾轉相減法求多個數的最大公約數的遞歸實現_白海東
侵權投訴

輾轉相減法求多個數的最大公約數的遞歸實現_白海東

第5卷 第3期2005年6月

             

雞西大學學報JOURNALOFJIXIUNIVERSITY

           

Vo.l5 No.3Jun.2005

文章編號:1672-6758(2005)03-0039-2

輾轉相減法求多個數的最大公約數的遞歸實現

白海東 朱麗敏

  摘 要:求最大公約數是一個較為經典的問題。利用輾轉相減算法,一次可以求出任意多個數的最大公約數,并編程予以實現。其效率較傳統的輾轉相除算法有很大程度的提高。

關鍵詞:輾轉相減法,輾轉相除法,最大公約數,遞歸中圖分類號:O141.3    文獻標識碼:A

  1 引言

求最大公約數有很多種算法可以實現,傳統的算法多用輾轉相除法,但該算法每次只能求兩個數的最大公約數,其算法可描述為:首先用較大

數作為被除數,用較小數作除數進行除法運算,若余數不為0,再把上次的除數作為下次的被除數,把上次的余數作為下次的除數,繼續去除,直到余數是0為止,此時的除數即為兩數的最大公約數。因此算法需連續多次作除法運算,故形象地命名為“輾轉相除法”。

如求(108,204)的最大公約數,步驟如下:(1)用204除以108,余數為96。(2)因余數不為0,故用108作被余數,96作除數,繼續去除,得余數為12。(3)因余數仍不為0,繼續用96作被除數,12作除數去除,此時余數為0,結束,此時的除數12便是兩數的最大公約數。

輾轉相除算法的不足之處是它每次只能求出兩個數據的最大公約數,若要求多個數據的最大公約數,則必須多次調用該程序,非常繁瑣。而利用輾轉相減法則可以一次求出任意多個數的最大公約數,效率較輾轉相除法有所提高。

2 輾轉相減算法描述

輾轉相減算法的實現過程可描述為,對任意多個數據a1,a2,...an:

(1)將最小數乘以不同的因子與其余各數進行減法運算。

例如,設an最小,則計算公式為:ai-an*INT(ai/an),i=1,2,...,n。其中INT(ai/an)表示ai

余以an的商,因必須保證差不能為負值,所以各因子應為相應的各數除以最小數的商)。

(2)將差為0的數據篩選掉,若只剩余兩個數,且其中一個為0時,則結束,此時的非0數據便是所求的最大公約數,否則執行步驟3。

(3)重復步驟(1)(2)。例如:求36,108,204的最大公約數

輾轉相減法求多個數的最大公約數的遞歸實現_白海東

:

因此,36、108、204的最大公約數就是12。3 算法分析與實現

因為可能原始數據較多,所以可用數組來存儲。過程描述如下:

(1)把原始數據保存在一數組中,如array(1)、array(2)...array(n)。

(2)將數組按由大到小排序,則a(n)就是該組數據中的最小數。(3)求出array(1)、array(2)...、array(n-1)除以array(n)的商,將其結果保存在變量temp中,即temp=array(i)/array(n)

(4)進行減法運算,即array(i)=array(i)-temp*array(n)

(5)再次將更新后數組按由大到小排序,此時若array(1)<>0,而其余各元素均為0,則結束,array(1)便是所求的最大公約數。否則進行步驟(6)

(6)檢索數組中為0的元素的個數,設為k,將它們篩選掉(只需令n=n-k即可),轉到步驟(3)。

如此反復,輾轉相減,最終便能求出其最大公約數。本文作者使用C語言的函數遞歸調用實現了本算法,參考程序如下:#include"stdio.h"

作者簡介:白海東,講師,大慶市第五十七中學,大慶。郵政編碼:163000

第1頁

免費下載Word文檔免費下載:輾轉相減法求多個數的最大公約數的遞歸實現_白海東

(下載1-2頁,共2頁)

我要評論

TOP相關主題

返回頂部
多乐彩开奖