Question

設(shè)計一種算法，求288和123的最大公約數(shù)．

Answer 1

答案：略
解析：

算法1：輾轉(zhuǎn)相除法：用較大的數(shù)除以較小的數(shù)，將所得余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則較小的數(shù)就是兩數(shù)的最大公約數(shù)． 288=123×2＋42； 123=42×2＋39； 42=39×1＋3； 39=3×13． ∴288和123的最大公約數(shù)是3． 算法2：更相減損術(shù)：以較大的數(shù)減去較小的數(shù)，接著把所得差與較小數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個操作，直到所得數(shù)相等為止，則這個數(shù)就是兩數(shù)的最大公約數(shù)． 288－123=165； 165－123=42； 123－42=81； 81－42=39； 42－39=3； 此處可以用39－3×13=0代替．