Python基于更相减损术实现求解最大公约数的方法

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

先从网上摘录一段算法的描述如下：

更相减损法：也叫 更相减损术，是出自《 九章算术》的一种求最大公约数的算法，它原本是为 约分而设计的，但它适用于任何需要求最大公约数的场合。

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

看完上面的描述，我的第一反应是这个描述是不是有问题？从普适性来说的话，应该是有问题的。举例来说，如果我求解4和4的最大公约数，可半者半之之后，结果肯定错了！后面的算法也不能够进行！

不管怎么说，先实现一下上面的算法描述：

# -*- coding:utf-8 -*-
#! python2
def MaxCommDivisor(m,n):
  # even process
  while m % 2 == 0 and n % 2 == 0:
    m = m / 2
    n = n / 2
  # exchange order when needed
  if m < n:
    m,n = n,m
  # calculate the max comm divisor
  while m - n != n:
    diff = m - n
    if diff > n:
      m = diff
    else:
      m = n
      n = diff
  return n
print(MaxCommDivisor(55,120))
print(MaxCommDivisor(55,77))
print(MaxCommDivisor(32,64))
print(MaxCommDivisor(16,128))

运行结果：

不用说，上面程序执行错误百出。那么该如何更正呢？

首先，除的2最终都应该再算回去！这样，程序修改如下：

def MaxCommDivisor(m,n):
  com_factor = 1
  if m == n:
    return n
  else:
    # process for even number
    while m % 2 == 0 and n % 2 == 0:
      m = int(m / 2)
      n = int(n / 2)
      com_factor *= 2
    if m < n:
      m,n = n,m
    diff = m - n
    while n != diff:
      m = diff
      if m < n:
        m,n = n,m
      diff = m - n
    return n * com_factor
print(MaxCommDivisor(55,120))
print(MaxCommDivisor(55,77))
print(MaxCommDivisor(32,64))
print(MaxCommDivisor(16,128))

通过修改，上面程序执行结果如下

虽说这段程序写出来看着有点怪怪的，但是总体的算法还是实现了。与辗转相除等算法相比，这个在循环的层级上有一定的概率会减小。特别是最后的两组测试数字对儿，这种情况下的效果要好一些。但是，总体上的算法的效率，现在我还不能够给个准确的衡量。

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基于辗转相除法求解最大公约数的方法示例
赞 (0)

相关推荐

  • python使用分治法实现求解最大值的方法

    本文实例讲述了python使用分治法实现求解最大值的方法.分享给大家供大家参考.具体分析如下: 题目: 给定一个顺序表,编写一个求出其最大值和最小值的分治算法. 分析: 由于顺序表的结构没有给出,作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义,数据随机生成.我们知道如果数组大小为 1 则可以直接给出结果,如果大小为 2则一次比较即可得出结果,于是我们找到求解该问题的子问题即: 数组大小 <= 2.到此我们就可以进行分治运算了,只要求解的问题数组长度比 2 大就继续分治,否则求解子问题

  • python求解水仙花数的方法

    本文实例讲述了python求解水仙花数的方法.分享给大家供大家参考.具体如下: 一个N位的十进制正整数,如果它的每个位上的数字的N次方的和等于这个数本身,则称其为花朵数. #!/usr/bin/python def get_flower(n, ofile): D_pow=[pow(i,n) for i in range(0,10)] V_min=1*pow(10,n-1) V_max=sum((9*pow(10,x) for x in range(0,n))) T_count=0 print D

  • python实现求解列表中元素的排列和组合问题

    求解列表中元素的排列和组合问题这个问题之前就遇到过几次没有太留意,最近在做题的时候遇上挺多的排列组合问题的,想来有必要温习一下了,今天花点时间写一下,之前都是手工写的,后来知道可以直接使用python的内置模块就可以完成这个工作了,今天就使用python的itertools模块来完成这个工作,一共解决四个问题: 1.生成排列,列表中元素不允许重复出现 2.生成排列,列表中元素可以重复出现 3.生成组合,不限元素个数,列表中元素不允许重复出现 4.生成组合,不限元素个数,列表中元素可以重复出现 因

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

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

    本文实例讲述了Python基于辗转相除法求解最大公约数的方法.分享给大家供大家参考,具体如下: 之前总结过一次高德纳TAOCP中的最大公约数求解,其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数. 这个题目我最初的理解理解错了,自然也没有做出标准答案.现在按照标准答案的解答写一下相应的代码实现: # -*- coding:utf-8 -*- #! python2 def MaxCommDivisor(m,n): while m * n != 0: m = m % n if m == 0

  • Python实现求最大公约数及判断素数的方法

    本文实例讲述了Python实现求最大公约数及判断素数的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python def showMaxFactor(num): count = num / 2 while count > 1: if num % count == 0: print 'largest factor of %d is %d' % (num, count) break #break跳出时会跳出下面的else语句 count -= 1 else: prin

  • Python线性方程组求解运算示例

    Python线性方程组求解运算示例

    本文实例讲述了Python线性方程组求解运算.分享给大家供大家参考,具体如下: 求解线性方程组比较简单,只需要用到一个函数(scipy.linalg.solve)就可以了.比如我们要求以下方程的解,这是一个非齐次线性方程组: 3x_1 + x_2 - 2x_3 = 5 x_1 - x_2 + 4x_3 = -2 2x_1 + 3x_3 = 2.5 代码如下: # coding=utf-8 import numpy as np from scipy.linalg import solve a =

  • Python实现利用最大公约数求三个正整数的最小公倍数示例

    本文实例讲述了Python实现利用最大公约数求三个正整数的最小公倍数.分享给大家供大家参考,具体如下: 在求解两个数的小公倍数的方法时,假设两个正整数分别为a.b的最小公倍数为d,最大公约数为c.存在这样的关系d=a*b/c.通过这个关系式,我们可以快速的求出三个正整数的最小公倍数. def divisor(a,b): c = a%b while c>0: a=b b=c c=a%b return b x1 = input("input1:") x2 = input("

  • Python实现简单求解给定整数的质因数算法示例

    本文实例讲述了Python实现简单求解给定整数的质因数算法.分享给大家供大家参考,具体如下: 接着做题遇到求解质因数分解的问题,思想很简单,就是需要遍历从1到该整数本身,并且判断当数字为质数时加入列表最后输出即可,求解这样的一个正整数的质因数分解,关键在于理解,每次得到一个质因数之后需要更新整数为:原始整数除以这个质因数的值,循环直至原始整数的值小于2终止,输出结果即可,实现如下: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒

  • Python求解平方根的方法

    本文实例讲述了Python求解平方根的方法.分享给大家供大家参考.具体如下: 主要通过SICP的内容改写而来.基于newton method求解平方根.代码如下: #!/usr/bin/python def sqrt_iter(guess,x): if(good_enough(guess, x)): print guess else: sqrt_iter(improve(guess, x),x) def improve(guess, x): return average(guess, x/gue

  • Python实现高效求解素数代码实例

    素数是编程中经常需要用到的. 作为学习Python的示例,下面是一个高效求解一个范围内的素数的程序,不需要使用除法或者求模运算. #coding:utf-8 #设置python文件的编码为utf-8,这样就可以写入中文注释 def primeRange(n): myArray=[1 for x in range(n+1)] ##列表解析,生成长度为(n+1)的列表,每个数值都为1 myArray[0]=0 myArray[1]=0 startPos=2 while startPos <= n:

  • 使用Python求解最大公约数的实现方法

    1. 欧几里德算法 欧几里德算法又称辗转相除法, 用于计算两个整数a, b的最大公约数.其计算原理依赖于下面的定理: 定理: gcd(a, b) = gcd(b, a mod b) 证明:   a可以表示成a = kb + r, 则r = a mod b   假设d是a, b的一个公约数, 则有  d|a, d|b, 而r = a - kb, 因此d|r.   因此,d是(b, a mod b)的公约数.   加上d是(b,a mod b)的公约数,则d|b, d|r, 但是a = kb + r

随机推荐