题目内容
设计一个算法,求840与1 764的最大公因数.
【探究】根据对自然数素因数分解的方法来设计算法,可以按以下思路进行.
首先,对两数分别进行素因数分解：
840=23×3×5×7,1 764=22×32×72.
其次,确定两数的公共素因数：2,3,7.
最后,确定公共素因数的指数：对于公共素因数2,22是1 764的因数,23是840的因数,因此22是这两个数的公因数,这样就确定了公共素因数2的指数为2.同样可以确定出公因数3和7的指数均为1.这样,就确定了840与1 764的最大公因数为：22×3×7=84.
【解】算法步骤如下：
S1 先将840进行素因数分解：840=23×3×5×7;
S2 将1 764进行素因数分解：1 764=22×32×72;
S3 确定它们的公共素因数：2,3,7；
S4 确定公共素因数的指数：公共素因数2,3,7的指数分别是2,1,1；
S5 最大公因数为22×31×71=84.
规律总结 以上步骤就是求两个正整数的最大公因数的一个算法.这个算法的思想具有一般性,它可以帮助设计者求三个或者三个以上正整数的最大公因数.在这个算法的设计中,对自然数进行素因数分解是基础,是解决这个问题的“平台”；同样,求两个非零自然数的最大公因数的算法,也可以成为解决其他问题的“平台”。“平台”的思想是算法设计中最基本的思想之一,也是数学中思考问题的一个重要思想.
练习册系列答案
相关题目