👾前言👾
因为博主最近比较忙所以好久没有进行更新,接下来几天会将基础算法更新完。
大家学习一个算法的时候,首先应该知道它是干啥的,然后理解其思路,最后再上手敲敲
因为算法这东西跟其他的还不一样,必须自己动手,否则看似自己会了，实际上差之千里。
刚开始看这两个名字你可能会觉得灰常的高大上,不明所以
其实GCD就是我们日常说到的最大公因数,LCM是我们日常说到的最小公倍数
你可能会问?为什么这么简单的题你还要将他拿出来说说呢？请带着疑问我们往下看。
🍁前置知识🍁
求最大公因数我们有两种方法：
辗转相除法(来自西方)：辗转相除，直到余数为0,得到的除数就是最大公因数
更相减损术(来自中国老祖宗)：更相减损，直到结果为0,得到的减数与被减数就是最大公因数
求最小公倍数的方法:
利用性质：a*b=gcd(a,b)*lcm(a,b)
🤺练习🤺
两个数的最大公因数
# 辗转相除法 def gcd(a,b): if a<b: a,b=b,a temp=b while temp: temp=a%b a=b b=temp return a print(gcd(30,901)) # 更相减损术 def gcd(a,b): if a<b: a,b=b,a temp=b while a!=b: temp=a-b if temp>b: a=temp else: a=b b=temp return a print(gcd(300,100))
两个数最大公倍数自己想想如何实现。
多个数的最大公因数
def gcd(a,b): if a<b: a,b=b,a temp=b while temp: temp=a%b a=b b=temp return a def lsgcd(ls): n=len(ls) if n==1: return n elif n==2: return gcd(ls[0],ls[1]) return gcd(lsgcd(ls[:n//2]),lsgcd(ls[n//2:])) print(gcd(2,3)) print(lsgcd([15,6,9,21]))
多个数的最大公倍数
def lcm(a,b): ta=a tb=b if a<b: a,b=b,a temp=b while temp: temp=a%b a=b b=temp return (ta*tb)//a def lslcm(ls): n=len(ls) if n==1: return n elif n==2: return lcm(ls[0],ls[1]) return lcm(lslcm(ls[:n//2]),lslcm(ls[n//2:])) print(lcm(2,3)) print(lslcm([15,6,9,21])) print(lslcm([1,2,3,4]))
