229-548128-[专业选修]最大公约数_greatest_common_divisor_gcd.sy.md

show	version	enable_checker
step	1.0	true

最大公约数(greatest common divisor)

回忆

• 函数的拆很容易
  • 但是不能为了拆而拆
  • 故意增加抽象层次
  • 还是要保持简洁
  • 保持高内聚低耦合
• 拆了之后也要能合上去
  • 必要时既有拆开的独立函数
  • 又有针对特定需求合起来的函数
  • 灵活应对
• 天下大势
  • 合久必分
  • 分久必合
• 代码效率和模块复用性不可兼得
• 如何要找到其中的最大公约数
• 什么是最大公约数？🤔

最大公约数

• 最大公约数
  • 也称最大公因数
  • 最大公因子
  • 指两个或多个整数共有约数中最大的一个

• 这个怎么求呢？

代码

• 集合的交集(intersection)
• 确实是可以得出正确答案的
• 还有没有更好的方法呢？

辗转相除法

• 不要翻页
• 尝试把这个算法实现

编码

• 感觉这个优化力度非常大
• 我们去测试一下

测试

• 速度提升了10倍左右哦
• 确实是非常好的算法
• 如果数字变得很大呢？

大数字

• 结果是

• 辗转相除法确实是提高了效率
• 不过也可能有问题

类型错误

• 如果传进来的是一个字符串

强制类型转化

• 如果强制类型转化需要开销
• 如果不管
• 又有可能出问题

• 某站曾经因为lua的gcd函数出问题
• 崩了3个钟头
• 同为动态语言的python瑟瑟发抖
• 口中默念
  • 动态语言一时爽
  • 后期重构火葬场
• 我们先去总结吧

总结

• 这次我们研究了最大公约数
  • gcd(greatest common divisor)
  • 这次合起来的优势比上次还明显
  • 而且大数字的时候效率高得多
• 限于动态语言的缘故
  • 实参的类型是不确定的
    • 可以是整型
    • 也可以是字符串
  • 如果要进行类型转化又有额外的开销
  • 而且还要加上字符try...exception...
• 这两难的局面如何破解呢？🤔
• 我们下次再说👋