加载中…求最大公约数（两种方法）
(2022-03-14 19:39:48)| 分类： 研究-学习 |
求最大公约数，很早就听说过辗转相除法。今天在学习迭代法时，看到了另一种方法：
if a>b:
a=a-b
else:
b=b-a
if a
a,b=b,a
a=a-b
a,b=b,a %
b
a=int(input("第一个数："))
b=int(input("第一个数："))
while a!=b:
print(a)
----------------
a=int(input("第一个数："))
b=int(input("第一个数："))
while a!=b:
print(a)
即如果两个数不相等，就一直采用大数减小数的方法，直到两个数相等时，这个数就是最大公约数。
这跟我之前了解到的辗转相除法好像不一样，网上查询后，得知确实不是。
辗转相除法， 又名欧几里德算法（Euclidean
algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
a=int(input("第一个数："))
b=int(input("第一个数："))
while b>0:
print(a)
喜欢
0
赠金笔