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(*case)))
def lcm(a, b):
  for i in range(2, min(a,b)+1):
    if a % i == 0 and b % i == 0:
      return i * lcm(a//i, b//i)
  else:
    return a*b
test_cases = [(4, 8), (5, 7), (24, 16), (35, 42)]
for case in test_cases:
  print('lcm of {} is {}'.format(*case, lcm(*case)))
# 最大公约数
def gcd(a, b):
  if a == b:
    return a
  elif a-b > b:
    return gcd(a-b, b)
  else:
    return gcd(b, a-b)
test_cases = [(35, 14), (88, 66), (5, 4), (20, 10)]
for case in test_cases:
  print('GCD of {} is {}'.format(*case, gcd(*case)))

运行结果：

lcm of 4 & 8 is 8
lcm of 35 & 42 is 210
lcm of 5 & 7 is 35
lcm of 20 & 10 is 20
GCD of 35 & 14 is 7
GCD of 88 & 66 is 22
GCD of 5 & 4 is 1
GCD of 20 & 10 is 10

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

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

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

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

赞 (0)

相关推荐

  • python 递归深度优先搜索与广度优先搜索算法模拟实现

     一.递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! (2)# 写递归的过程 1.写出临界条件 2.找出这一次和上一次关系 3.假设当前函数已经能用,调用自身计算上一次的结果,再求出本次的结果 (3)案例分析:求1+2+3+...+n的数和 # 概述 ''' 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! ''' # 写递归的过程 ''' 1.写出临界条件 2.找出这一次和上一次关系 3.假设

  • Python理解递归的方法总结

    递归 一个函数在执行过程中一次或多次调用其本身便是递归,就像是俄罗斯套娃一样,一个娃娃里包含另一个娃娃. 递归其实是程序设计语言学习过程中很快就会接触到的东西,但有关递归的理解可能还会有一些遗漏,下面对此方面进行更加深入的理解 递归的分类 这里根据递归调用的数量分为线性递归.二路递归与多重递归 线性递归 如果一个递归调用最多开始一个其他递归调用,我们称之为线性递归. 例如: def binary_search(data, target, low, high): """ 二分查

  • python递归全排列实现方法

    本文实例为大家分享了python递归全排列的实现方法,供大家参考,具体内容如下 排列:从n个元素中任取m个元素,并按照一定的顺序进行排列,称为排列: 全排列:当n==m时,称为全排列: 比如:集合{ 1,2,3}的全排列为: { 1 2 3} { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 2 1 } { 3 1 2 } 递归思想: 取出数组中第一个元素放到最后,即a[1]与a[n]交换,然后递归求a[n-1]的全排列 1)如果数组只有一个元素n=1,a={1} 则全排列就是

  • python 列表递归求和、计数、求最大元素的实例

    利用python的递归来执行求和.计数.求最大元素的方法简直溜到爆,这里粘贴一下代码: 列表的递归求和: def sum(list): if list==[]: return 0 return list[0]+sum(list[1:]) 测试: print sum([3,4,2,3]) 列表的递归计数: def countElem(list): if list==[]: return 0 return 1+countElem(list[1:]) 测试: print countElem([3,4,

  • python递归实现快速排序

    快速排序(QuickSort)是对冒泡排序的一种改进: 基本思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序 过程可以递归进行,以此达到整个数据变成有序序列. 一趟快速排序的算法是: 1)设置两个变量i.j,排序开始的时候:i=0,j=N-1: 2)以第一个数组元素作为关键数据,赋值给key,即key=A[0]: 3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key

  • 关于python之字典的嵌套,递归调用方法

    一 字典的嵌套 在机器学习实战决策树部分,生成决策树时用到了字典的嵌套. >>>s1={'no surface':{}} >>>s1['no surfacce'][0]='no' >>>s1 {'no surface':{0:'no'}} >>>s2={'flipper':{}} >>>s2['flipper'][0]='no' >>>s2['flipper'][1]='yes' >>&

  • 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 #coding:utf-8 from fractions import gcd #非递归实现 def gcd_test_one(a, b): if a!=0 and b!=0: if a>b: a,

  • Python基于递归算法实现的汉诺塔与Fibonacci数列示例

    Python基于递归算法实现的汉诺塔与Fibonacci数列示例

    本文实例讲述了Python基于递归算法实现的汉诺塔与Fibonacci数列.分享给大家供大家参考,具体如下: 这里我们通过2个例子,学习python中递归的使用. 1. 找出Fibonacci数列中,下标为 n 的数(下标从0计数) Fibonacci数列的形式是这样的:0,1,1,2,3,5,8,13-- ① 使用while循环,python2代码如下: def fib(n): a,b=0,1 count=0 while count<n: a,b=b,a+b count=count+1 pri

  • Python基于递归算法实现的走迷宫问题

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

  • Python基于React-Dropzone实现上传组件的示例代码

    目录 实例演示 1. axios上传普通文件: 2. 大文件导入: 结语 这次我要讲述的是在React-Flask框架上开发上传组件的技巧.我目前主要以React开发前端,在这个过程中认识到了许多有趣的前端UI框架--React-Bootstrap.Ant Design.Material UI.Bulma等.而比较流行的上传组件也不少,而目前用户比较多的是jQuery-File-Upload和Dropzone,而成长速度快的新晋有Uppy和filepond.比较惋惜的是Fine-Uploader

  • Python基于keras训练实现微笑识别的示例详解

    Python基于keras训练实现微笑识别的示例详解

    目录 一.数据预处理 二.训练模型 创建模型 训练模型 训练结果 三.预测 效果 四.源代码 pretreatment.py train.py predict.py 一.数据预处理 实验数据来自genki4k 提取含有完整人脸的图片 def init_file():     num = 0     bar = tqdm(os.listdir(read_path))     for file_name in bar:         bar.desc = "预处理图片: "      

  • Python基于分水岭算法解决走迷宫游戏示例

    本文实例讲述了Python基于分水岭算法解决走迷宫游戏.分享给大家供大家参考,具体如下: #Solving maze with morphological transformation """ usage:Solving maze with morphological transformation needed module:cv2/numpy/sys ref: 1.http://www.mazegenerator.net/ 2.http://blog.leanote.com

  • Python基于Socket实现的简单聊天程序示例

    Python基于Socket实现的简单聊天程序示例

    本文实例讲述了Python基于Socket实现的简单聊天程序.分享给大家供大家参考,具体如下: 需求:SCIENCE 和MOOD两个人软件专业出身,厌倦了大众化的聊天软件,想着自己开发一款简易的聊天软件,满足他们的个性化需求,又不失"专业水准",Talk is easy, try to code it. 技术:socket,详细可参考前文:Python Socket实现简单TCP Server/client功能 语言:python 尽管socket区分服务器和客户端,但是在聊天程序中两

  • Python基于pygame模块播放MP3的方法示例

    本文实例讲述了Python基于pygame模块播放MP3的方法.分享给大家供大家参考,具体如下: 安装pygame(可参考:安装Python和pygame及相应的环境变量配置) pip安装这个whl文件 装完就直接跑代码啦,很短的 import time import pygame file=r'C:\Users\chan\Desktop\Adele - All I Ask.mp3' pygame.mixer.init() print("播放音乐1") track = pygame.m

  • Python基于ThreadingTCPServer创建多线程代理的方法示例

    本文实例讲述了Python基于ThreadingTCPServer创建多线程代理的方法.分享给大家供大家参考,具体如下: #coding=utf8 from BaseHTTPServer import BaseHTTPRequestHandler from SocketServer import ThreadingTCPServer import gzip from StringIO import StringIO import logging logging.basicConfig(level

随机推荐