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

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

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

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

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

# -*- 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))

程序的执行结果：

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

# -*- 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))

程序的执行结果：

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

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

运行结果：

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

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

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

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

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

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数学运算技巧总结》、《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串 *** 作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录 *** 作技巧汇总》

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

您可能感兴趣的文章:Python实现利用最大公约数求三个正整数的最小公倍数示例Python实现的求解最大公约数算法示例使用Python求解最大公约数的实现方法Python实现求最大公约数及判断素数的方法Python基于更相减损术实现求解最大公约数的方法Python编程实现数学运算求一元二次方程的实根算法示例python实现数独算法实例Python实现破解猜数游戏算法示例Python实现的求解最小公倍数算法示例 总结

以上是内存溢出为你收集整理的Python基于辗转相除法求解最大公约数的方法示例全部内容，希望文章能够帮你解决Python基于辗转相除法求解最大公约数的方法示例所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。