一文洞悉python必备50种算法50个与数学有关的Python编程

导读点击头像，可查看合集《50个与数学有关的Python编程》介绍很多青少年在初学编程时，不知道如何练习。算法太高深难懂；应用嘛，内容又太多太杂。笔者认为，与数....

点击头像，可查看合集

《50个与数学有关的Python编程》介绍

很多青少年在初学编程时，不知道如何练习。算法太高深难懂；应用嘛，内容又太多太杂。笔者认为，与数学有关的编程是再合适不过的。

适合谁？

热爱编程的青少年，或者刚步入编程的小白。创作完成后，会提供源码下载。

内容包括：

50个与数学有关的Python编程之思维导图

上一篇（余数）

<<<正文开始>>>第2节 最大公约数和最小公倍数

最大公约数和最小公倍数是小学的内容。两个分数相加时，就会用到它。如

先求6和4的最小公倍数，加好之后，再求分子分母的最大公约数。

题1 笨方法

笨方法就是找出两个数最大值和最小值，从最大值递增，直至找到最小公倍数；从最小值递减，直至找到最大公约数。

N = eval(input("请输入第一个正整数:"))M = eval(input("请输入第二个正整数:"))#if-else找最大值与最小值if M > N: max = M min = Nelse: max = N min = M #三元运算获得最大值与最小值min = M if N > M else Nmax = N if N > M else M#也可以用元组来找最大值与最小值(min, max) = (N, M) if N < M else (M, N)while True: if max % M == 0 and max % N == 0: break max = max 1 while True: if M % min == 0 and N % min == 0: break min = min - 1 print(max,min)

题2 九章算法

笨方法之所以笨，在于适合计算机，并不适合人。而古代是没有计算机的。因此《九章算术》给出了一个适合人的比较实用的算法。《九章算术》是中国古代最重要的数学著作。中国古代的数学讲究的就是实用。

1. M和N，大数减掉小小数。
2. 比较差与小数，再用大数减掉小数，直至为相等。相等的数就为最大公约数。

如：输入14和6。14-6=8 →8-6=2→6-2=4→4-2=2→2-2=0；2就为最大公约数。最小公倍数为14×6÷2=42。

N = eval(input("请输入第一个正整数:"))M = eval(input("请输入第二个正整数:"))(min,max) = (M,N) if N > M else (N,M)while True: max = max - min (min, max) = (min, max) if max > min else (max, min) if min == 0: breakprint(f"最大公约数是{max}")print(f"最小公倍数是{int(N*M/max)}")

题3 欧几里得算法

欧几里得是古希腊时代伟大的数学家，其所著的《几何原本》是平面几何的基础。因此我们在中学所学的几何也叫“欧几里得几何”，简称“欧氏几何”

1. M和N，且M>N。令 R = M mod N。注意R一定会小于N。（%求余是编程里的符合，实际数学用mod）
2. 继续求余，即 N mod R，直至余数为0。此时除数就是最大公约数。

如：输入14和6。14 mod 6=2→6 mod 2=0；2就为最大公约数。最小公倍数为14×6÷2=42。

N = eval(input("请输入第一个正整数:"))M = eval(input("请输入第二个正整数:"))(min,max) = (M,N) if N > M else (N,M)while True: max = max % min #大数对小数的求余 if max == 0: break (max, min) = (min, max) #余数一定会小于除数， #所以直接调换，不用判断 print(f"最大公约数是{min}")print(f"最小公倍数是{int(N*M/min)}")

两种算法谁更优秀呢？我恐怕要说是欧几里得的算法了。从上面14和6的案例来看，欧氏算法的次数要少很多——也就是循环少了很多。

题4 欧几里得算法的递归写法

在很多编程比赛中，递归是免不了的。欧氏算法的递归往往是一道开胃小菜，因此我们在此编一下。

N = eval(input("请输入第一个正整数:"))M = eval(input("请输入第二个正整数:"))#gcd是 Greatest Common Divisor 的缩写def gcd(max,min): max = max % min if max == 0: return min else: return gcd(min,max)(min,max) = (M,N) if N > M else (N,M)result = gcd(max,min)print(f"最大公约数是{result}")print(f"最小公倍数是{int(N*M/result)}")

递归算法与非递归算法，没有优劣之分。它们循环的次数是一样的。本人比较反感用多个方法求解一个问题，但做编程练习时，多思考是一件非常好的事情。

有兴趣的朋友，可以将九章算法改成递归形式。

点个关注

上一篇（余数）