Question

設(shè)計(jì)一個(gè)算法．求84與1764的最大公因數(shù)．

Answer 1

答案：略
解析：

解：算法步驟如下： (1)先將84進(jìn)行素因數(shù)分解：； (2)將1764進(jìn)行素因數(shù)分解：； (3)確定它們的公共素因數(shù)：2，3，7； (4)確定公共素因數(shù)的指數(shù)，公共素因數(shù)2，3，7的指數(shù)分別是2，1，1； (5)最大公因數(shù)為． 以上步驟就是求兩個(gè)正整數(shù)的最大公因數(shù)的一個(gè)算法．這個(gè)算法的思想具有一般性，它可以幫助設(shè)計(jì)者求三個(gè)或者三個(gè)以上正整數(shù)的最大公因數(shù)．在這個(gè)算法的設(shè)計(jì)中，對(duì)自然數(shù)進(jìn)行素因數(shù)分解是基礎(chǔ)，是解決這個(gè)問(wèn)題的“平臺(tái)”；同樣，求兩個(gè)非零自然數(shù)的最大公因數(shù)的算法，也可以成為解決其他問(wèn)題的“平臺(tái)”．“平臺(tái)”的思想在算法設(shè)計(jì)中是一個(gè)最基本的思想，也是數(shù)學(xué)中思考問(wèn)題的一個(gè)重要思想．

提示：

根據(jù)對(duì)自然數(shù)素因數(shù)分解的方法來(lái)設(shè)計(jì)算法，可以按以下思路進(jìn)行． 首先，對(duì)兩數(shù)分別進(jìn)行素因數(shù)分解：，． 其次，確定兩數(shù)的公共素因數(shù)：2，3，7． 最后，確定公共素因數(shù)的指數(shù)：對(duì)于公共素因數(shù)2，是1764的因數(shù)，是84的因數(shù)，因此是這兩個(gè)數(shù)的公因數(shù)，這樣就確定了公共素因數(shù)2的指數(shù)為2．同樣可以確定出公因數(shù)3和7的指數(shù)均為1．這樣，就確定了84與1764的最大公因數(shù)為：．