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

拼搏现实的明天。 2022-09-16 03:51 210阅读 0赞

> 「青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），公众号后台回复【Scratch】或【Python】，即可进入。如果加入了之前的社群不需要重复加入。
> 
> 我们将有关编程题目的教学视频已经发布到抖音号**21252972100，小马老师**上，大家可以关注一下。

# 绳子算法 #

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

## 1. 准备工作 ##

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

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

舞台效果如下图所示。

![e8f6526a50d540a191aad7e262658f67.png][]

## 2. 功能实现 ##

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

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

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

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

## 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整除。

脚本编写：

![5e055c03095f49f78646f51eb7d27d3d.png][]

参考文献：

*  https://blog.csdn.net/hello\_woo/article/details/79293235
 *  https://blog.csdn.net/qq\_41575507/article/details/90752742
 *  https://zhuanlan.zhihu.com/p/338809271

[e8f6526a50d540a191aad7e262658f67.png]: /images/20220828/f9c10ae6686f408aaedeb51468394874.png
[5e055c03095f49f78646f51eb7d27d3d.png]: /images/20220828/7140c1e7d8fe4566afe53bc790db7370.png