Python基于更相减损术实现求解最大公约数的方法
作者:grey_csdn 发布时间:2022-10-31 16:13:24
本文实例讲述了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程序设计有所帮助。
来源:https://blog.csdn.net/grey_csdn/article/details/77416172
猜你喜欢
- 通常在读写文件之前,需要判断文件或目录是否存在,不然某些处理方法可能会使程序出错。所以最好在做任何操作之前,先判断文件是否存在。这里将介绍三
- SQL1: --1、查看表空间的名称及大小 SELECT t.tablespace_name, round(SUM(bytes / (102
- 如何在独立服务器上创建用户?假设独立服务器是intels,我们用ADSI来创建一个用户liyanbing,初始口令定为3625:
- 今天我和中国著名画家"渔人"谈了一个关于"怎样才能设计好"的问题,他给我说了一句话,得益不浅,那句话
- 本文实例讲述了JS+HTML5 canvas绘制验证码。分享给大家供大家参考,具体如下:css样式:<style>body{ &
- 解决2个问题:1.身份证之类的文本数据自动转为科学计数法的问题。2.中文乱码的问题excel从web页面上导出的原理。当我们把这些数据发送到
- 问题描述:最近用jstree遇到一个问题,父节点选中时,被禁用的子节点也会选中如下解决方案:1、 将jstree升级到最新的版本,v3.3.
- 一直在期待这本书,一直希望国内能有一本正视WEB标准,并且全面阐述WEB标准书籍。而这本书是我觉得国内最全面的一本关于WEB标准的书籍,这本
- 本文实例为大家分享了tensorflow实现线性回归的具体代码,供大家参考,具体内容如下一、随机生成1000个点,分布在y=0.1x+0.3
- 本文实例讲述了PHP封装CURL扩展类。分享给大家供大家参考。具体如下:<?php/*** @description: 封装CURL扩
- 数据类型是所有开发语言的基础,JavaScript虽然是一个弱类型的脚本语言,但是在数据类型上也有很多讲究的,看了淘宝UED玉伯的一篇文章,
- python3.6.2环境安装配置图文教程,具体如下一、需要下载的软件》python3.6.2.exe (也可以选择更新的版本) ----
- 译者 | 豌豆花下猫声明 :本文获得原作者授权翻译,转载请保留原文出处,请勿用于商业或非法用途。有许许多多文章写了 Python 中的许多很
- 在遥感应用中,我们经常需要对某一景遥感影像中的全部像元的像素值进行平均值求取——这一操作很好实现,基
- 前言Python是面向对象的程序设计(Object Oriented Programming)。面向对象的程序设计的一条基本原则是:计算机程
- enum 是一组绑定到唯一常数值的符号名称,并且具备可迭代性和可比较性的特性。我们可以使用 enum 创建具有良好定义的标识符,而不是直接使
- 字符串在 Python 中创建字符串对象非常容易。只要将所需的文本放入一对引号中,就完成了一个新字符串的创建(参见清单 1)。如果稍加思考的
- 作者是一名沉迷于Python无法自拔的蛇友,为提高水平,把Python的重点和有趣的实例发在简书上。一、递归是指函数/过程/子程序在运行过程
- 前言一般而言,新的 centos 7.x 中自带的 python 都是 2.x 的版本。对于我们运行 python 软件支持并不友好,所以需
- 本文实例为大家分享了Python实现学生管理系统的具体代码,供大家参考,具体内容如下实现从面向过程到面向对象的过度,通过更改前面的学生管理系