本文实例讲述了Python基于辗转相除法求解最大公约数的方法。分享给大家供大家参考，具体如下：
之前总结过一次高德纳TAOCP中的最大公约数求解，其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数。
这个题目我最初的理解理解错了，自然也没有做出标准答案。现在按照标准答案的解答写一下相应的代码实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
# -*- coding:utf-8 -*-#! python2def MaxCommDivisor(m,n): while m * n != 0: m = m % n if m == 0: return n else: n = n % m if n == 0: return mprint(MaxCommDivisor(55,120)) |
程序的执行结果：
交换一下两个数字的位置，代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
# -*- coding:utf-8 -*-#! python2def MaxCommDivisor(m,n): while m * n != 0: m = m % n if m == 0: return n else: n = n % m if n == 0: return mprint(MaxCommDivisor(120,55)) |
程序的执行结果：
题目提示中提到了会降低效率，通过上面的代码来看，效率的损失应该是在除法以及判断上。在此，把之前算法的代码拿过来对比一下：
|
1
2
3
4
5
6
7
8
|
def CommDevisor(m,n): r = m % n while r != 0: m = n n = r r = m % n return nprint(CommDevisor(120,25)) |
运行结果：
新算法在循环中，多了一个除法以及比较操作。其实，比较的效率还是不错的，但是除法的运算会导致效率的降低。
希望本文所述对大家Python程序设计有所帮助。
原文链接：https://blog.csdn.net/grey_csdn/article/details/77414949
