Python基于递归和非递归算法求两个数最大公约数、最小公倍数示例

2024-04-14 19:22:26

本文实例讲述了Python基于递归和非递归算法求两个数最大公约数、最小公倍数。分享给大家供大家参考，具体如下：

最大公约数和最小公倍数的概念大家都很熟悉了，在这里就不多说了，今天这个是因为做题的时候遇到了所以就写下来作为记录，也希望帮到别人，下面是代码：

#!/usr/bin/env python
#coding:utf-8
from fractions import gcd
#非递归实现
def gcd_test_one(a, b):
  if a!=0 and b!=0:
    if a>b:
      a, b=b, a
    if b%a==0:
      return a
    gcd_list=[]
    for i in range(1,a):
      if b%i==0 and a%i==0:
        gcd_list.append(i)
    return max(gcd_list)
  else:
    print 'Number is wrong!!!'
#递归实现
def gcd_test_two(a, b):
  if a>b:
    a, b=b, a
  if b%a==0:
    return a
  else:
    return gcd_test_two(a,b%a)
#python自带的gcd
def gcd_test_three(a, b):
  return gcd(a,b)
if __name__ == '__main__':
  print gcd_test_one(12,24)
  print gcd_test_one(12,8)
  print gcd_test_one(6,24)
  print gcd_test_one(0,24)
  print '----------------------------------------------------------------------------'
  print gcd_test_two(12,24)
  print gcd_test_two(12,8)
  print gcd_test_two(6,32)
  print '----------------------------------------------------------------------------'
  print gcd_test_three(12,24)
  print gcd_test_three(12,8)

结果如下：

12
4
6
Number is wrong!!!
None
----------------------------------------------------------------------------
12
4
2
----------------------------------------------------------------------------
12
4

PS：这里再为大家推荐一款本站相关在线工具供大家参考：

在线最小公倍数/最大公约数计算工具：
http://tools.jb51.net/jisuanqi/gbs_gys_calc

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

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

python如何求解两数的最大公约数

题目: 给定两个自然数,求这两个数的最大公约数. 分析: 单看题目的话,非常简单,我们可以循环遍历自然数,如果能够整除两个自然数,就把这个数记下来,在这些记录中找到最大的一个. 但是这样做有几个缺点:一是做除法计算量比较大,二是遍历所有自然数完全没有必要.另外,如果能够循环,还是不要递归,因为Python的函数递归最大栈空间是1000(如果我没有记错的话),如果数字大一些,很容易出现爆栈. 所以在这里有两种处理方法: 1.如果较大的自然数除较小的一个自然数,取得余数,较小的自然数和余数的最大公约
Python基于递归算法求最小公倍数和最大公约数示例

本文实例讲述了Python基于递归算法求最小公倍数和最大公约数.分享给大家供大家参考,具体如下: # 最小公倍数 def lcm(a, b, c=1): if a * c % b != 0: return lcm(a, b, c+1) else: return a*c test_cases = [(4, 8), (35, 42), (5, 7), (20, 10)] for case in test_cases: print('lcm of {} is {}'.format(*case, lcm
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实现利用最大公约数求三个正整数的最小公倍数.分享给大家供大家参考,具体如下: 在求解两个数的小公倍数的方法时,假设两个正整数分别为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求解最大公约数的实现方法

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
Python自定义函数实现求两个数最大公约数、最小公倍数示例

本文实例讲述了Python自定义函数实现求两个数最大公约数.最小公倍数.分享给大家供大家参考,具体如下: 1. 求最小公倍数的算法: 最小公倍数 = 两个整数的乘积 / 最大公约数所以我们首先要求出两个整数的最大公约数, 求两个数的最大公约数思路如下: 2. 求最大公约数算法: ① 整数A对整数B进行取整, 余数用整数C来表示举例: C = A % B ② 如果C等于0,则C就是整数A和整数B的最大公约数 ③ 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 1, 2
Python基于更相减损术实现求解最大公约数的方法

本文实例讲述了Python基于更相减损术实现求解最大公约数的方法.分享给大家供大家参考,具体如下: 先从网上摘录一段算法的描述如下: 更相减损法:也叫更相减损术,是出自< 九章算术>的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合. <九章算术>是中国古代的数学专著,其中的"更相减损术"可以用来求两个数的最大公约数,即"可半者半之,不可半者,副置分母.子之数,以少减多,更相减损,求其等也.以等数约之."
Python基于辗转相除法求解最大公约数的方法示例

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

本文实例讲述了Python实现的求解最大公约数算法.分享给大家供大家参考,具体如下: 使用Python求解两个数的最大公约数的时候用到了前面介绍的分解质因式.其实,我写分解质因式程序的时候就是因为发现在实现最大公约数求解的过程中用到了这个功能. 比较令我开心的是之前学的一点Python集合处理功能居然在这个时候也派上了用场,小程序的完成让人感觉比较舒心. 代码实现如下: #!/usr/bin/python from collections import Counter def PrimeNum(
Python基于递归和非递归算法求两个数最大公约数、最小公倍数示例

本文实例讲述了Python基于递归和非递归算法求两个数最大公约数.最小公倍数.分享给大家供大家参考,具体如下: 最大公约数和最小公倍数的概念大家都很熟悉了,在这里就不多说了,今天这个是因为做题的时候遇到了所以就写下来作为记录,也希望帮到别人,下面是代码: #!/usr/bin/env python #coding:utf-8 from fractions import gcd #非递归实现 def gcd_test_one(a, b): if a!=0 and b!=0: if a>b: a,
C++基于递归和非递归算法求二叉树镜像的方法

本文实例讲述了C++基于递归和非递归算法求二叉树镜像的方法.分享给大家供大家参考,具体如下: /*求二叉树镜像 -- 采用递归和非递归方法经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二叉树结点定义*/ typedef st
C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)

本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同.分享给大家供大家参考,具体如下: /*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二
javascript使用递归算法求两个数字组合功能示例

本文实例讲述了javascript使用递归算法求两个数字组合功能.分享给大家供大家参考,具体如下: // 12 ,3,4 两个数字组合最后结果应该是 // 13 // 14 // 23 // 24 // 34 // 这5种用程序怎么算出来 // 是求组合的算法 // var arr = [12, 3, 4]; // var len = arr.length; // var result = []; // for (var i = 0; i < len; i++) { // for (va
C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法.分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <stack> using std::cout; using std::cin; using std::endl; using std::stack; /*二叉树结点定义*/
Python 基于FIR实现Hilbert滤波器求信号包络详解

在通信领域,可以通过希尔伯特变换求解解析信号,进而求解窄带信号的包络. 实现希尔伯特变换有两种方法,一种是对信号做FFT,单后只保留单边频谱,在做IFFT,我们称之为频域方法:另一种是基于FIR根据传递函数设计一个希尔伯特滤波器,我们称之为时域方法. # -*- coding:utf8 -*- # @TIME : 2019/4/11 18:30 # @Author : SuHao # @File : hilberfilter.py import scipy.signal as signal im
Python基于递归实现电话号码映射功能示例

本文实例讲述了Python基于递归实现电话号码映射功能.分享给大家供大家参考,具体如下: 问题电话按键上面的每个数字都对应着几个字母,如果按下一个数字键代表输入一个字母,那么输入一个数字组成的字符串,它所产生的所有的可能的字母串是什么,有多少种思路: 这个是一个递归的问题下面是具体的实现,为了更清晰看懂递归调用的过程,这里打印出来了每一次递归的过程: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城功能:电话号码映射 '

Python基于递归和非递归算法求两个数最大公约数、最小公倍数示例

相关推荐

随机推荐