Scratch Scratch3.0编程与数学:求最大公因数(3辗转相除法)

发布时间:2021-05-03 22:22:44 浏览 1
辗转相除法,又称欧几里得算法欧几里得算法,是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《几何原本》(The Elements)中最早描述了这种算法,所以被命名为欧几里得算法。

Scratch3.0编程与数学:求最大公因数(3辗转相除法)PvW状课网-少儿编程在线网课平台

Scratch3.0编程与数学:求最大公因数(3辗转相除法)PvW状课网-少儿编程在线网课平台

1.用较大的数除以较小的数,得到一个余数; 2.用上一步骤中的除数除以余数,得到一个新的余数; 3.重复步骤2,直到余数为0,最后的除数就是最大公约数;   假如需要求 255和 75 两个正整数的最大公约数,用欧几里得算法,是这样进行的:    255÷75=3……30;     75÷30=2……15;     30÷15=2……0; 所以255和75的最大公因数是15。 程序设计: 1.定义4个变量,分别是数字1、数字2,余数、中间数。在辗转相除法中,用大数除以小数,根据余数的情况来进行判断的,中间数是防止先输入了小数,再输入大数。两数在进行交换时用到变量中间数。

Scratch3.0编程与数学:求最大公因数(3辗转相除法)PvW状课网-少儿编程在线网课平台

2.将余数的初始值设为1,这个很重要奥!(思考一下为什么?)分别询问并输入两个数字。

Scratch3.0编程与数学:求最大公因数(3辗转相除法)PvW状课网-少儿编程在线网课平台

 

3.假如先输入了大数,再输入小数,利用中间数,将两个数的值进行交换。PvW状课网-少儿编程在线网课平台

Scratch3.0编程与数学:求最大公因数(3辗转相除法)PvW状课网-少儿编程在线网课平台

  4.利用辗转相除法算出数字1和数字2的最大公因数。用数字1除以数字2,判断余数是否为0。如果余数为0,此时的除数,就是两数的最大公因数,否则,将数字2的值赋给数字1,将此时余数的值赋给数2,继续判断余数的值。PvW状课网-少儿编程在线网课平台
Scratch3.0编程与数学:求最大公因数(3辗转相除法)  PvW状课网-少儿编程在线网课平台
5.输出两数的最大公因数是多少。特别注意,因数第4步的赋值情况,数字1的值是上次循环中数字2的值,而数字2此时的值是0。 图片PvW状课网-少儿编程在线网课平台
完整程序:PvW状课网-少儿编程在线网课平台
Scratch3.0编程与数学:求最大公因数(3辗转相除法)PvW状课网-少儿编程在线网课平台
来源: Silence学习坊
上一篇:Scratch3.0编程与数学:求最大公因数(2短除法) 下一篇:返回列表