【青少年编程】求最大公约数的辗转相除法

「青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），公众号后台回复【Scratch】或【Python】，即可进入。如果加入了之前的社群不需要重复加入。

我们将有关编程题目的教学视频已经发布到抖音号21252972100，小马老师上，大家可以关注一下。

故事情境：最近在学绳子算术的小星星非常苦恼，他常常在想，如果有一款程序能实现根据输入的两根绳子长度，可以把两根长绳截成长度相等的小段后，直接求出一共可以截成多少段，每段最长多少米就好了。小猫知道后，决定设计一个程序帮助小星星走出绳子算术的困境。

（1）保留舞台默认白色背景及小猫角色，将小猫角色调整到舞台上合适的位置；

（2）建立名为“绳子”的列表用于存储数据。

舞台效果如下图所示。

（1）点击绿旗，询问“输入绳子长度”并等待；

（2）将输入的绳子长度保存到列表“绳子”后，小猫分别说两根绳子的长度3秒；

（3）根据输入的两根绳子长度，设计算法实现：把两根长绳截成长度相等的小段。求出一共可以截成多少段，每段最长多少米；

（4）计算完成后，小猫分别说“一共可以截成多少段，每段最长多少米。”3秒。

假设有两个数 x x x和 y y y，存在一个最大公约数 z = ( x , y ) z=(x,y) z=(x,y)，即 x x x和 y y y都有公因数 z z z，那么 x x x一定能被 z z z整除， y y y也一定能被 z z z整除，所以 x x x和 y y y的线性组合 m x + n y mx+ny mx+ny也一定能被 z z z整除。（ m m m和 n n n可取任意整数）

对于辗转相除法来说，思路就是：

若 x > y x > y x>y，设 x / y = n , x % y = c x/y = n, x % y = c x/y=n,x%y=c，则 x x x能表示成 x = n y + c x = ny + c x=ny+c的形式，将 n y ny ny移到左边就是 x − n y = c x - ny = c x−ny=c，由于一般形式的 m x + n y mx + ny mx+ny能被z整除，所以等号左边的 x − n y x - ny x−ny（作为 m x + n y mx + ny mx+ny的一个特例）就能被 z z z整除，即 x x x除 y y y的余数 c c c也能被 z z z整除。

脚本编写：

参考文献：

• https://blog.csdn.net/hello_woo/article/details/79293235
• https://blog.csdn.net/qq_41575507/article/details/90752742
• https://zhuanlan.zhihu.com/p/338809271