python如何求解两数的最大公约数
作者:冬日新雨 发布时间:2021-01-16 07:38:18
标签:python,最大公约数
题目:
给定两个自然数,求这两个数的最大公约数。
分析:
单看题目的话,非常简单,我们可以循环遍历自然数,如果能够整除两个自然数,就把这个数记下来,在这些记录中找到最大的一个。
但是这样做有几个缺点:一是做除法计算量比较大,二是遍历所有自然数完全没有必要。另外,如果能够循环,还是不要递归,因为Python的函数递归最大栈空间是1000(如果我没有记错的话),如果数字大一些,很容易出现爆栈。
所以在这里有两种处理方法:
1、如果较大的自然数除较小的一个自然数,取得余数,较小的自然数和余数的最大公约数就是我们要求的值。
2、如果较大的自然数减去较小的自然数,取得差值,较小的自然数和差值的最大公约数就是我们要求的值。
基于以上两条,我们就可以在根据定义得到的算法的基础上进行改进,但是!减法操作当然比取余要方便很多。而且在计算机里,做位运算的速度要比加减乘除都快,所以,我写了四个算法,具体描述在代码的 __doc__里有注释阐述
代码:
def greatest_common_divisor_1(self, num1, num2):
'''
数值计算寻找最大公约数,给定两个整数,计算其最大公约数,时间复杂度为 o(min(num1,num2)),取余运算复杂度高
'''
gbc = 1
for i in xrange(2, min(num1, num2)+1):
if num2 % i == 0 and num1 % i == 0:
gbc = i
return gbc
def greatest_common_divisor_2(self, num1, num2):
'''
辗转相减法,时间复杂度最差为 o(min(num1,num2)),一般情况下都比这个要好。相减运算要比除法方便很多
'''
while num1 != num2:
if num1 > num2:
num1 = num1 - num2
else:
num2 = num2 - num1
return num1
def greatest_common_divisor_3(self, num1, num2):
'''
求余数法,取模运算比较麻烦,时间复杂度低 o(log max(num1, num2))
'''
while num1 != num2:
if num1 > num2:
if num1 % num2 == 0:
return num2
num1 = num1 % num2
else:
if num2 % num1 == 0:
return num1
num2 = num2 % num1
return num1
def greatest_common_divisor(self, num1, num2):
'''
求两个数的最大公约数
综合取余法和辗转相减法,既能得到较好的时间复杂度,又能避免取余运算,时间复杂度稳定 o(log max(num1,num2))
如果取两个非常大的数的话,前面的方法很容易爆栈、取余困难等等,但是该方法没有问题
a = 999999342353200
b = 777774234
print greatest_common_divisor(a, b)
'''
factor = 1
if num1 < num2:
return greatest_common_divisor_1(num2, num1)
while num1 != num2:
if num1 & 1 is False and num2 & 1 is False: # 均为偶数
num1 = num1 >> 1
num2 = num2 >> 2
factor *= 2
elif num1 & 1 is False and num2 & 1 is True:
num1 = num1 >> 1
elif num1 & 1 is True and num2 & 1 is False:
num2 = num2 >> 1
else:
if num1 > num2:
num1 = num1 - num2
else:
num2 = num2 - num1
return factor*num1
来源:https://blog.csdn.net/dongrixinyu/article/details/78761769
0
投稿
猜你喜欢
- SQL Server有几个版本都在使用中——4.2, 6.0, 6.5, 7.0, 2000,以及2
- Click 是用 Python 写的一个第三方模块,用于快速创建命令行。我们知道,Python 内置了一个 Argparse 的标准库用于创
- 前言:如果正在看文章的你,还不会绘制折线图,请看如何使用matplotlib绘制折线图这篇文章,该文章会仔细而详尽的告诉你绘制折线图的方法。
- 今天我们看看所有的类!由于工作的上的事有点忙!点图!以后讲解这是我编译好了的类的结构图,我们可以用很多软件可以从原板的DLL看到这些内容!当
- Yolov5如何更换BiFPN?第一步:修改common.py将如下代码添加到common.py文件中# BiFPN # 两个特征图add操
- 有的时候需要手里的音频文件变速听,或可能变慢或可能变快这里使用的python进行操作,我的目标是将文件转成2倍速首先需要安装插件pip in
- 相比于time模块,datetime模块的接口则更直观、更容易调用。今天就来讲讲datetime模块。 datetime模块定义了两个常量:
- 1.经典类与新式类在了解Python的类与类型前,需要对Python的经典类(classic classes)与新式类(new-style
- 在python中我们可以使用speech模块让计算机进行语音输出,我们需要使用如下代码安装该模块。对于如何在终端中安装python相应模块,
- 面向过程的程序设计把计算机程序视为一系列的命令集合,即一组函数的顺序执行。为了简化程序设计,面向过程把函数继续切分为子函数,即把大块函数通过
- 1. ASCII 返回与指定的字符对应的十进制数; SQL> select ascii(A) A,ascii(a) a,as
- 本文实例讲述了python获取指定网页上所有超链接的方法。分享给大家供大家参考。具体如下:这段python代码通过urllib2抓取网页,然
- 之前在网上看到有人提问,如何在页面上同步显示服务器的时间,其实实现方法有几种,可能 一般人立马就想到可以使用Ajax每隔一秒去请求服务器,然
- CGArt®2008“贺岁刊”玉鼠闹春,700页再造巅峰本期CGArt杂志信息:下载地址:http://cgart.cgfi
- np.percentilenumpy.percentile(a, q, axis=None, out=None, overwrite_inp
- 我们在设计网站的时候,有的时候需要根据页面元素的属性来制作不同的样式,比如,对于不同的链接类型,显示不同的链接图标。CSS的选择器是个很有用
- 本文给出了几个表单常用的js验证函数,有检查、\等特殊字符的,有检查是否含有空格,检查是否为Email 地址,也有检查是否是小数或负数的,检
- re.search():匹配整个字符串,并返回第一个成功的匹配。如果匹配失败,则返回None pattern: 匹配的规则,str
- 微信入口绑定,微信事件处理,微信API全部操作包含在这些文件中。内容有:微信摇一摇接口/微信多客服接口/微信支付接口/微信红包接口/微信卡券
- Asterisk 是一个开放源代码的软件VoIP PBX系统,我们用Asterisk 搭建企业内部电话系统。Asterisk AMI的Ast