python用递归方式实现最大公约数_Pyhton递归与欧几里得算法求最大公约数-程序员宅基地

技术标签: python用递归方式实现最大公约数  

题目要求:

使用递归编写一个函数,利用欧几里得算法求最大公约数,例如 gcd(x, y) 返回值为参数 x 和参数 y 的最大公约数。欧几里得算法:

欧几里德算法又称辗转相除法,是指用于计算两个正整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。欧几里德算法是用来求两个正整数最大公约数的算法。是由古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法。

扩展欧几里德算法可用于RSA加密等领域。

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法,是这样进行的:1997 = 3 * 615 + 152

615 = 4 * 152 + 7

7 = 1 * 5 + 2

5 = 2 * 2 +1

2 = 2 * 1 + 0

当被加的数为 0 时,就得出了 1997 和 615 的最大公约数 1。

计算证明:

其计算原理依赖于下面的定理:

定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数(Greatest Common Divisor)缩写为GCD。

gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)证法一:

a可以表示成a = kb + r(a,b,k,r皆为正整数,且r

假设d是a,b的一个公约数,记作d|a,d|b,即a和b都可以被d整除。

而r = a - kb,两边同时除以d,r/d=a/d-kb/d=m,由等式右边可知m为整数,因此d|r

因此d也是b,a mod b的公约数

假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数。

进而d|a.因此d也是a,b的公约数

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。证法二

第一步:令c=gcd(a,b),则设a=mc,b=nc

第二步:可知r =a-kb=mc-knc=(m-kn)c

第三步:根据第二步结果可知c也是r的因数

第四步:可以断定m-kn与n互素【否则,可设m-kn=xd,n=yd,(d>1),则m=kn+xd=kyd+xd=(ky+x)d,则a=mc=(ky+x)dc,b=nc=ycd,故a与b最大公约数≥cd,而非c,与前面结论矛盾】

从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r),得证

注意:两种方法是有区别的。Python递归:def gcd (x,y):

if y:

return gcd(y,x%y)

else:

return x

print(gcd(4,6))

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_40001025/article/details/110067512

智能推荐

repost:ubuntu16.04 耍帅快捷键_怎样用终端耍帅-程序员宅基地

文章浏览阅读202次。ubuntu16.04 耍帅快捷键https://blog.csdn.net/xiaoqu001/article/details/78721772 关于Firfox的:Ctrl + t : 新建标签(Tab)Ctrl + w : 关闭当前标签(Tab)Alt + F4 : 关闭当前窗口(也就是关闭了所有Tab)Ctrl + Shift + w : 关闭当前窗口(与Alt + ..._怎样用终端耍帅

UnityEffects(3)之闪电链_unity 闪电链-程序员宅基地

文章浏览阅读1.6w次,点赞14次,收藏48次。今天来分享一下Untiy中实现闪电链的方法,实际在项目中使用,效果不错。国际惯例:工程放在:https://github.com/aceyan/UnityEffects 使用unity5.4场景是Scene/(3)ChainLightning 使用了unity的lineRender来模拟闪电的效果: 主要功能都在UVChainLightning这个脚_unity 闪电链

USB口 2.4G 无线串口 兼容NRF24L01P 通讯 模块使用说明_2.4g串口模块怎么调试参数-程序员宅基地

文章浏览阅读1.1w次,点赞4次,收藏25次。USB口 2.4G 无线串口 兼容NRF24L01P 通讯 模块使用说明_2.4g串口模块怎么调试参数

学生-课程数据库—初识sql语句(04)(注释版)_数据库学生课程语句-程序员宅基地

文章浏览阅读248次。select Sname from Studentwhere Sno in (select Sno from SC where Cno='2' )select Snamefrom Student,SCwhere Student.Sno=SC.Sno and Cno='2' select Sno,Sname,Sdeptfrom Studentwhere Sdept in(select Sdept from Student whe_数据库学生课程语句

debian下安装oracle10G-程序员宅基地

文章浏览阅读102次。闲来无事,计划在公司的服务器搭建DATAGUARD环境,原本有4台服务器,其中两台的linux源比较老了,在安装依赖包的时候总是提示错误,咨询了一下SA,说“这个问题比较麻烦”。于是一台台测试,终于找到一台符合安装要求的机器。环境如下:debian77:/home/oracle# cat /proc/versionLinux version 2.6.26.2-weelaa...

Linux可执行文件制作_pyinstaller: command not found-程序员宅基地

文章浏览阅读900次。Linux可执行文件制作背景测试过程中,需要针对不同的Linux系统、核心服务版本进行验证,各种环境依赖的python版本以及已安装的库存在较大差异,考虑到实际测试需求以及出差现场使用的要求,需要将测试脚本打包为可执行文件,可以最大程度上减少依赖,保障测试程序的可用性和易用性。本文介绍一种利用python的pyinstaller库,将程序打包为可执行文件的方式,脱离自动化工程或复杂的环境配置。后半部分针对一些固有化的实现进行介绍,希望对大家有所帮助。环境配置当前使用的编程语言为python._pyinstaller: command not found

随便推点

linux(内网)通过window 上网_linux用windows的网络-程序员宅基地

文章浏览阅读1.1k次。配置window双网卡 10.32.22.206(能上网) 192.168.100.109 (内网)linux 192.168.100.106——108 内网第一步:开启外网网卡共享功能第二步:内网 网卡IP 会因为 开启共享而改变 修改内网网卡ip第三步:刚开始并没能直接上网修改Linux 网卡配置Dns +网关 (设置成 window 内网网卡ip)然后就ok 了..._linux用windows的网络

Play framework 2.0 -访问SQL数据库-程序员宅基地

文章浏览阅读323次。 #访问Sql数据库 1.配置JDBC连接池 play2.0提供了管理JDBC连接池的插件。你可以安装需要来配置许多数据库。要启用数据库插件,就要在conf/application.conf文件中配置一个连接池。根据约定默认的JDBC数据源,必须调用缺省: # Default database configuration db.default.driver=or..._play2框架显示sql

编译nginx常见错误_error http xslt image filter module-程序员宅基地

文章浏览阅读1.9k次。错误一:configure: error: the HTTP XSLT module requires the libxml2/libxsltyum -y install libxml2 libxml2-devyum -y install libxslt-devel错误二:error: the HTTP image filter module requires the GD library.yum -y install gd gd-devel错误三:error: the GeoIP modul_error http xslt image filter module

Vue - el-table 自定义表头(下拉框或输入框等标签)_vue el-table 动态表头 嵌套循环 相应的下拉框-程序员宅基地

文章浏览阅读3.3k次。Vue - el-table 自定义表头(下拉框或输入框等标签)_vue el-table 动态表头 嵌套循环 相应的下拉框

hdu 5374 Tetris(模拟俄罗斯方块)_线性表实现俄罗斯方块-程序员宅基地

文章浏览阅读1k次。题意: 俄罗斯方块想必大家都玩过,现在题目给出了3种俄罗斯方块。 O形,I形,L形 以及5种操作,w选择,a左移一位,d右移以为,w下移一位,p什么都不做。然后又给出了方块出现的序列,要求按所给出的操作能消除多少行。解析: DRAW数组表示已(x,y)(x,y)为左下角,能在图上画出的形状。 然后模拟每个每个方块,直到当前方块不能动位置,在二维数组中标记方块,然后接下来选_线性表实现俄罗斯方块

IDEA中Ctrl+Shift+f快捷键无效的解决方式_idea ctrl+alt+shift失效-程序员宅基地

文章浏览阅读6.1w次,点赞43次,收藏14次。某天突然发现idea非常重要的快捷键ctrl+shift+f无效了,网上搜了很多都说是qq快捷键冲突,但是找了下qq快捷键却没有解决,现在给大家一个解决快捷键冲突的思路:1、查看QQ快捷键-->在QQ的设置里面选择热键-->设置热键看看是否有冲突,如果有,干掉它(或者退出qq看快捷键是否可用,如果可用就是qq的毛病,否则查找其他);2、对我而言就是输入法的问题,不管你用的是搜狗输入法还是百_idea ctrl+alt+shift失效

推荐文章

热门文章

相关标签