网络编程
位置：首页>> 网络编程>> Python编程>> Python基于辗转相除法求解最大公约数的方法示例

Python基于辗转相除法求解最大公约数的方法示例

作者：grey_csdn　　发布时间：2023-08-24 19:47:35　

标签：Python,最大公约数

本文实例讲述了Python基于辗转相除法求解最大公约数的方法。分享给大家供大家参考，具体如下：

之前总结过一次高德纳TAOCP中的最大公约数求解，其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数。

这个题目我最初的理解理解错了，自然也没有做出标准答案。现在按照标准答案的解答写一下相应的代码实现：


# -*- coding:utf-8 -*-
#! python2
def MaxCommDivisor(m,n):
 while m * n != 0:
   m = m ％ n
   if m == 0:
     return n
   else:
     n = n ％ m
     if n == 0:
       return m
print(MaxCommDivisor(55,120))

程序的执行结果：

Python基于辗转相除法求解最大公约数的方法示例

交换一下两个数字的位置，代码如下：


# -*- coding:utf-8 -*-
#! python2
def MaxCommDivisor(m,n):
 while m * n != 0:
   m = m ％ n
   if m == 0:
     return n
   else:
     n = n ％ m
     if n == 0:
       return m
print(MaxCommDivisor(120,55))

程序的执行结果：

Python基于辗转相除法求解最大公约数的方法示例

题目提示中提到了会降低效率，通过上面的代码来看，效率的损失应该是在除法以及判断上。在此，把之前算法的代码拿过来对比一下：


def CommDevisor(m,n):
 r = m ％ n
 while r != 0:
   m = n
   n = r
   r = m ％ n
 return n
print(CommDevisor(120,25))

运行结果：

Python基于辗转相除法求解最大公约数的方法示例

新算法在循环中，多了一个除法以及比较操作。其实，比较的效率还是不错的，但是除法的运算会导致效率的降低。

PS：这里再为大家推荐几款计算工具供大家进一步参考借鉴：

在线一元函数（方程）求解计算工具：
http://tools.jb51.net/jisuanqi/equ_jisuanqi

科学计算器在线使用_高级计算器在线计算：
http://tools.jb51.net/jisuanqi/jsqkexue

在线计算器_标准计算器：
http://tools.jb51.net/jisuanqi/jsq

希望本文所述对大家Python程序设计有所帮助。

来源：https://blog.csdn.net/grey_csdn/article/details/77414949

0
投稿

猜你喜欢

手机版 网络编程 asp之家 www.aspxhome.com