輾轉(zhuǎn)相除法與更相減損術(shù)高二數(shù)學(xué)第一章算法初步知識點整理

　　一、輾轉(zhuǎn)相除法與更相減損術(shù)

　　1、輾轉(zhuǎn)相除法。也叫歐幾里德算法，用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：

　　（1）：用較大的數(shù)m除以較小的數(shù)n得到一個商

　　S和一個余數(shù)

　　R；（2）：若

　　R＝0，則n為m，n的最大公約數(shù)；若

　　R0，

　　則用除數(shù)n除以余數(shù)0

　　R得到一個商

　　1

　　S和一個余數(shù)

　　1

　　R；（3）：若

　　1

　　R＝0，則

　　1

　　R為m，n的最大公約數(shù)；若

　　1

　　R0，則用除數(shù)

　　R除以余數(shù)

　　1

　　R得到一個商

　　2

　　S和一個余數(shù)

　　2

　　R； 依次計算直至

　　n

　　R＝0，此時所得到的

　　1

　　nR即為所求的最大公約數(shù)。

　　二、更相減損術(shù)

　　我國早期也有求最大公約數(shù)問題的算法，就是更相減損術(shù)。在《九章算術(shù)》中有更相減損術(shù)求最大公約數(shù)的步驟：可半者半之，不可半者，副置分母子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。

　　翻譯為：

　　（1）：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。

　�。�2）：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的.差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。

　　例2 用更相減損術(shù)求98與63的最大公約數(shù). 分析：（略）

　　3、輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：

　　（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。

　�。�2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到

【輾轉(zhuǎn)相除法與更相減損術(shù)高二數(shù)學(xué)第一章算法初步知識點整理】相關(guān)文章：

算法初步高二數(shù)學(xué)必修3知識點01-30

高二數(shù)學(xué)算法初步統(tǒng)計概率的知識點11-15

高二相關(guān)作文01-29

高二數(shù)學(xué)算法的概念知識點12-05

心弦相和心相融經(jīng)典散文05-27

初二數(shù)學(xué)數(shù)據(jù)的整理與初步處理知識點10-31

算法的概念高二數(shù)學(xué)知識點11-10

高二數(shù)學(xué)下冊《算法》知識點講解04-08

高二數(shù)學(xué)知識點整理03-07