【Scratch数学编程】求最大公约数

有两个自然数a和b,如果a能被b整除,那么,b就叫做a的约数。两个或多个自然数的共有约数中最大的一个,叫做它们的最大公约数,也称最大公因数、最大公因子。求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、辗转相减法、更相减损法等。

【问题】输入两个正整数a和b,求它们的最大公约数。

【Scratch编程解题】下面我们将分别介绍使用辗转相除法、更相减损法来求两个数的最大公约数。

一、辗转相除法

辗转相除法,又称欧几里德算法,用于计算两个正整数a、b的最大公约数。它是已知最古老的算法,其可追溯至公元前300年前。

辗转相除法的算法步骤是,对于给定的两个正整数a、b(a>b),用a除以b得到余数c。若余数c不为0,就将b和c构成新的一对数(a=b,b=c),继续上面的除法,直到余数c为0,这时b就是原来两个数的最大公约数。
因为这个算法需要反复进行除法运算,故被形象地命名为“辗转相除法”。

举例说明,用辗转相除法求255和75的最大公约数。给定两个数:255,75;第一次:用255除75,余30;第二次:用75除30,余15;第三次:用30除15,余0;这时就得到255和75的最大公约数是15。

我们把辗转相除法的算法用流程图表示。
【Scratch数学编程】求最大公约数-少儿编程网
注:a mod b,即a除以b的余数。

根据上面的算法步骤,我们编写一个名为“辗转相除法”的模块,用来求两个数的最大公约数。该模块的完整代码如下:

【Scratch数学编程】求最大公约数-少儿编程网

下面编写调用“辗转相除法”模块的主程序,用来求255和75的最大公约数。主程序的代码如下:

【Scratch数学编程】求最大公约数-少儿编程网

点击绿旗运行程序,求得255和75的最大公约数是15。

二、更相损减法

《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数。该书成于公元一世纪左右,书中内容十分丰富,系统总结了战国、秦、汉时期的数学成就。

更相损减法的算法步骤:

第一步:任意给定两个正整数,判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的差和减数相等为止。
第三步:最后把第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
这里所说的“等数”,就是最大公约数,求“等数”的办法就是“更相减损法”,所以,更相减损法也叫等值算法。

举例说明,用更相减损术求260和104的最大公约数。
第一步:由于260和104均为偶数,首先用2约简得到130和52,再用2约简得到65和26;
第二步:此时65是奇数,而26不是奇数,故把65和26辗转相减:65-26=39,39-26=13,26-13=13;
第三步:最后把第一步中约掉的两个2和“等数”13相乘:13×2×2=52
所以,260与104的最大公约数是52。

我们把更相减损法的算法用流程图表示:

【Scratch数学编程】求最大公约数-少儿编程网

注:GCD,即最大公约数。

根据上面的算法步骤,我们编写一个名为“更相减损法”的模块,用来求两个数的最大公约数。该模块的完整代码如下:

【Scratch数学编程】求最大公约数-少儿编程网

下面编写调用“更相减损法”模块的主程序,用来求260和104的最大公约数。主程序的代码如下:

【Scratch数学编程】求最大公约数-少儿编程网

点击绿旗运行程序,求得260和104的最大公约数是52。

三、辗转相减法

如果去掉“更相减损法”中对两个正整数均为偶数时做的除法运算,只保留减法运算,也能求出两数的最大公约数。
这种方法叫辗转相减法,即尼考曼彻斯法,其特色是做一系列减法,从而求得最大公约数。

例如:用辗转相减法求两个自然数35和14的最大公约数。35 – 14 = 21 用大数减去小数,21 – 14 = 7, 7小于14,要做一次交换,把14作为被减数,14 – 7 = 7 求得“等数”,这样也就求出了最大公约数7。

请你试一试,用Scratch编写一个名为“辗转相减法”的模块,用来求两个数的最大公约数。

*文章为作者独立观点,不代表少儿编程网立场
发表评论

坐等沙发
相关文章
适合孩子学编程的教育游戏APP有哪些?
适合孩子学编程的教育游戏APP有哪些?
为什么大多数学编程的孩子表达能力高于同龄人?
为什么大多数学编程的孩子表达能力高于…
编程少年丨崔少天:幼儿园里学编程的6岁男孩
编程少年丨崔少天:幼儿园里学编程的6岁…
如果孩子系统学完Scratch、Python、NOIP,编程能力可以达到什么水平?
如果孩子系统学完Scratch、Python、NOIP…
编程少年丨夏启航:10岁男孩的“慢”哲学
编程少年丨夏启航:10岁男孩的“慢”哲学
编程少年丨林于森:一个7岁男孩的编程奇缘
编程少年丨林于森:一个7岁男孩的编程奇缘
Scratch是由麻省理工学院(MIT)设计开发的一款面向少年的简易编程工具,是适合于全世界儿童学习编程和交流的工具和平台