Scratch教程

当前位置:小码王 > 学习教程 > Scratch教程

你会用Scratch求公约数吗
导读:通过学习Scratch,孩子们能够学会解决数学中和我们日常生活中的一些简单问题,比如最大公约数问题,你会用Scratch求最大公约数吗?一起跟随南京小码王Scratch培训班老师学习一下。

Scratch是目前比较火热的一款少儿编程工具,但很多孩子没有经过系统学习的话,是无法完全掌握Scratch的功能和用法的。Scratch结合了孩子喜欢的图形、动画、音效、游戏等,为编程增加了更大的乐趣,通过学习Scratch,孩子们能够学会解决数学中和我们日常生活中的一些简单问题,比如非常大公约数问题,你会用Scratch求非常大公约数吗?一起跟随南京小码王Scratch培训班老师学习一下。


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

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

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


一、辗转相除法


辗转相除法的算法步骤是,对于给定的两个正整数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。


辗转相除法的算法用流程图表示。

0.jpg


注:a mod b,即a除以b的余数。


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

1.jpg


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

2.jpg


点击绿旗运行程序,求得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。


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

3.jpg


注:GCD,即非常大公约数。


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

4.jpg


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

5.jpg


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


其实没那么复杂对不对?只要了解了算法和步骤,就能轻松编写出代码和程序,而Scratch中还有完整的代码块,可大大缩减编程难度。如果你对Scratch编程还有什么疑问,或者想获得更多有趣的Scratch教程的话,都可以直接咨询小码王在线老师,也欢迎你来小码王Scratch培训班免费试听课程,感受编程的乐趣。