輾轉(zhuǎn)相除法與更相減損術(shù)高二數(shù)學(xué)第一章算法初步知識(shí)點(diǎn)整理
一、輾轉(zhuǎn)相除法與更相減損術(shù)
1、輾轉(zhuǎn)相除法。也叫歐幾里德算法，用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：
�。�1）：用較大的數(shù)m除以較小的數(shù)n得到一個(gè)商
S和一個(gè)余數(shù)
R；（2）：若
R＝0，則n為m，n的最大公約數(shù)；若
R0，
則用除數(shù)n除以余數(shù)0
R得到一個(gè)商
1
S和一個(gè)余數(shù)
1
R；（3）：若
1
R＝0，則
1
R為m，n的最大公約數(shù)；若
1
R0，則用除數(shù)
R除以余數(shù)
1
R得到一個(gè)商
2
S和一個(gè)余數(shù)
2
R； 依次計(jì)算直至
n
R＝0，此時(shí)所得到的
1
nR即為所求的最大公約數(shù)。
二、更相減損術(shù)
我國早期也有求最大公約數(shù)問題的算法，就是更相減損術(shù)。在《九章算術(shù)》中有更相減損術(shù)求最大公約數(shù)的步驟：可半者半之，不可半者，副置分母子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。
翻譯為：
�。�1）：任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。
（2）：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的.差比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所求的最大公約數(shù)。
例2 用更相減損術(shù)求98與63的最大公約數(shù). 分析：（略）
3、輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：
�。�1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。
�。�2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到
【輾轉(zhuǎn)相除法與更相減損術(shù)高二數(shù)學(xué)第一章算法初步知識(shí)點(diǎn)整理】相關(guān)文章：
算法初步高二數(shù)學(xué)必修3知識(shí)點(diǎn)01-30
高二數(shù)學(xué)算法初步統(tǒng)計(jì)概率的知識(shí)點(diǎn)11-15
高二相關(guān)作文01-29
高二數(shù)學(xué)算法的概念知識(shí)點(diǎn)12-05
心弦相和心相融經(jīng)典散文05-27
初二數(shù)學(xué)數(shù)據(jù)的整理與初步處理知識(shí)點(diǎn)10-31
算法的概念高二數(shù)學(xué)知識(shí)點(diǎn)11-10