少儿编程网

　　上一节我们通过更相减损法来实现scratch求两个数的最大公约数，并且提到了辗转相除法（也叫欧几里德算法）。

　　定理：两个整数的最大公约数等于其中较小的那个数和两数的相除余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。

   gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

实现步骤：【本站作品专区有该实例的作品展示】代码由：大白兔提供

1、新建必要的变量

2、新建功能模块（如图所示，点开选项，可以添加数字参数和文本标签）

3、程序主题脚本：这里有两段脚本，分别是利用递归和循环进行计算，注意的是循环用的是“重复执行直到余数=0”，这也是欧几里得算法的重点。

本站内容未经许可，禁止任何网站及个人进行转载。