我们上学的时候都求过最大公约数,大概是小学 5 年级问题,但是我们好像没有在哪个计算器上直接找到求最大公约数的按键,有时候两个数字很大, 求起来还是挺麻烦的,但如果借助电脑这件事就容易了,今天我们一起在电脑上用小学一年级同学也会使用的Scratch软件编程帮我们实现自动求最大公约数的功能。
先回顾一下求最大公约数的数学逻辑。求最大公约数是数学中的一个经典问题,数学家们想出来很多种方法,其中最早的一种方法叫辗转相除法,出现在距今 2300 多年前的古希腊数学家欧几里得所著的《几何原本》一书中,所以也被称为欧几里得算法,它是目前仍然在使用的算法之一。下面我们就一起来看一下这个算法。
题目:A、B有最大公约数K,并且A > B,已知A, B来求K。
用辗转相除法求K的过程:
举两个例子:
1. 12和9两个数求最大公约数。
2. 5767和4453两个数求最大公约数。
说白了辗转相除法求最大公约数就是:不断求两数相除的余数,用除数代替被除数,余数代替除数,直到余数为0,此刻的除数就是最大公约数。
知道辗转相除法的原理,程序就很容易编出来了(如下图),比单纯学数学好的地方是,不管多大的数,会编程序的同学随时都可以求着玩,分分钟出答案。
其实用辗转相除法不但可以求最大公约数,只要稍微变化一下,还可以将10进制转化成2进制。后面我们会继续写文章来看看这个神奇的辗转相除法如何对进制进行转化。
,