[Python3 练习] 008 欧几里德算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[Python3 练习] 008 欧几里德算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1687字,纯文字阅读大概需要3分钟。
内容图文
题目:写个“欧几里德算法”的小程序
(1) 描述
- 我知识浅薄,一开始被“欧几里德”的大名唬住了,去搜了一下才知道这就是高中时学过的“辗转相除法”
- 辗转相除法的用处
- 求两个正整数的最大公约数
- 示例
- a = 30,b = 18,求 a 与 b 的最大公约数
- a % b = 12 => a = 18, b = 12
- a % b = 6 => a = 12, b = 6
- a % b = 0 => 此时的 b 即为原来两数的最大公约数
- a = 30,b = 18,求 a 与 b 的最大公约数
- 总结
- 大的数 num1 对小的数 num2 取余
- 把 num2 的值赋给 num1,把余数赋给 num2,再进行上一步操作,直到余数为 0
- 余数为 0 的那个式子中的 num2 即为最大公约数
(2) 证明
- 方法来自互联网
1) 证明方法1
设 num1,num2,m,r,d 均为自然数
不妨设 num1 > num2,d 为两个数的任意一个公约数;m 表示倍数,r 表示余数
num1 = m * num2 + r
=> r = num1 - m * num2
等式两边同除以 d,得 r/d = (num1 - m * num2)/d = num1/d - m * num2/d
因为 d 为 num1,num2 的公约数,且 m 为自然数
所以 r/d 也是自然数
=> d 必是 r 的约数
=> 求 num1 与 num2 的最大公约数,可以转为求 num2 与 r 的最大公约数
2) 证明方法2
令 d 为 num1,num2 的最大公约数
取 num1 的某一个约数 m1,num2 的某一个约数 m2,使得 num1 = m1 * d,num2 = m2 * d —— (1)
不妨设 r = num1 % num2 = num1 - m * num2 —— (2)
将 (1) 代入 (2),得 r = m1 * d - m * (m2 * d) = (m1 - m * m2) * d
=> d 也是余数 r 的约数
若 (m1 - m * m2) 与 m2 不互质
不妨设 (m1 - m * m2) = k1 * d‘,m2 = k2 * d‘,(d‘>1)
m1 = m * m2 + k1 * d‘ = m * (k2 * d‘) + k1 * d‘ = (m * k2 + k1) * d‘
=> num1 = m1 * d = [(m * k2 + k1) * d‘] * d = (m * k2 + k1) * (d‘ * d)
? num2 = m2 * d = (k2 * d‘) * d = k2 * (d‘ * d)
=> num1 与 num2 有公约数 (d‘ * d)
因为 d‘ > 1,d >= 1
所以 (d‘ * d) > d
=> 与题设矛盾
=> (m1 - m * m2) 与 m2 互质
=> d 也是 num2 与 r 的最大公约数
(3) 要求
- 写出“欧几里德算法”的程序,起名为 gcd()
- gcd 为 Greatest Common Divisor(最大公约数) 的缩写
(3) 程序
1) 代码
# 解法1
def gcd(num1, num2): # 不需要规定 x > y,就算 x < y,取一次余就换回来了
while num2 != 0:
t = num1 % num2
num1 = num2
num2 = t
return num1
# 解法2 更贴近算法的描述
def gcd(num1, num2):
while num1:
num1, num2 = num2 % num1, num1
return num2
2) 运行情况
>>> print(gcd(16, 36))
4
原文:https://www.cnblogs.com/yorkyu/p/10367428.html
内容总结
以上是互联网集市为您收集整理的[Python3 练习] 008 欧几里德算法全部内容,希望文章能够帮你解决[Python3 练习] 008 欧几里德算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。