從高中碾轉相除法、更相減損術算法談起
編程的本質來源于算法，而算法的本質來源于數學，編程只不過將數學題進行代碼化?！?--- Runsen」
先問你們一個小學問題：「如何求兩個整數的最大公約數?」
曾經見過不少的算法題，發現有的并不在數據結構和算法大綱中，而是來源于高中數學。
高中數學在必修三中，有一個非常重要的知識點，叫做「碾轉相除法、更相減損術」。
輾轉相除法， 又名歐幾里德算法(Euclidean algorithm)乃求兩個正整數之最大公因子的算法。它是已知最古老的算法， 其可追溯至公元前300年前。
在古代，有一個比較出名的數學家，叫做「劉徽」。而更相減損術是我國數學家劉徽的專著《九章算術》中記載的.
碾轉相除法
輾轉相除是求最大公約數的一種算法。給兩個數,我們可以把它組成數對(a,b)輾轉相除法基于如下原理：「兩個整數的最大公約數等于其中較小的數和兩數的相除余數的最大公約數?！?/p>
求a和b的最大公約數，就用ab中較小的數去除另一個數，這個時候會有一個余數，當余數是0的時候，那個較小的數就是最大公約數。
若余數不是0，那么我們用這個余數來替換那個比較大的數，然后以此類推，直到算出最大公約數。
比如，下面我用碾轉相除法求100和24的最大公約數，很明顯最大公約數就是25。
- 100 = 24 * 4 + 4
- 24 = 4 * 6 + 0
很顯然4和6中，那個較小的數4就是100和24最大公約數。
下面用碾轉相除法求55和120的最大公約數，很明顯最大公約數就是5。
- 55 = 120 * 0 + 55
- 120 = 55 * 2 + 10
- 55 = 10 * 5 + 5
很顯然10和5中，那個較小的數5就是55和120最大公約數。
算法的流程圖(摘自百度百科)
因此得到設兩數為m，n，這里不需要判斷兩數中誰最大。
求m，n兩數的最大公約數的步驟為：
用m除以n，m%n=r(r>=0)。如果r=0，則min(m,n)。
如果r≠0，用n除以r，依此循環，直到r=0結束
下面，我們將使用對碾轉相除法進行代碼化。
- def gcd(a, b):
- # 如果b是0，退出循環
- while b:
- # 循環賦值
- a, b = b, a%b
- return a
- print(gcd(100,25)) #25
輾轉相除法本質上是一種遞歸的代碼，把求兩個大數的公約數gcd(a,b)轉化為 求其中較小的數和兩數的相除余數的最大公約數gcd(b,a%b)，直至b為0，則返回a為求得的最大公約數gcd(gcd(a,b), 0)。
因此可以得到：gcd(a,b) = gcd(b,a%b) = gcd(gcd(a,b), 0)
- def gcd(a, b):
- return gcd(b, a % b) if b != 0 else a
- print(gcd(55,120)) #5
下面對Python代碼進行Java的代碼轉化
- /**
- * @author Runsen
- * @date 2020/12/9 13:18
- */
- public class Gcd {
- public static void main(String[] args) {
- int gcd = gcd(91, 49);
- System.out.println(gcd);
- }
- private static int gcd(int a, int b) {
- while(b != 0) {
- int temp = a % b;
- a = b;
- b = temp;
- }
- return a;
- }
- }
下面對Python代碼進行JavaScript的代碼轉化。
- function gcd(a, b){
- while(b != 0){
- temp = a % b;
- a = b;
- b = temp;
- };
- return a;
- }
- console.log((gcd(55,120))) #5
更相減損術
我國早期也有求最大公約數問題的算法，就是更相減損術。
在《九章算術》中有更相減損術求最大公約數的步驟:可半者半之，不可半者，副置分母子之數，以少減多，更相減損，求其等也，以等數約之。
更相減損術來源于數的整除性質：即如果兩個整數a、b都能被c整除,那么a與b的差也能被C整除。
比如求98和63的最大公約數。
先看98和63這兩個數，因為63不是偶數，所以用大數減去小數，得到98-63=35 , 63-35=28 35-28=7 , 28-7=21 , 21-7=14 , 14-7=7 。
「此時，減數和差相等7」，所以98和63的最大公約數是7。
再比如求260和104的最大公約數。
先看260和104兩個數，這兩個數都是偶數,所以用2約簡得130和52。
約簡之后的130和52也都是偶數，繼續用2約簡得65和26，此時65不是偶數，所以用大數減去小數 65-26=39 , 39-26=13 , 26-13=13。
此時，減數和差相等，再上面約去2個2, 得到的數是13，所以260和104的最大公約數是2×2×13=52。
因此更相減損術不在如下：
- 如果兩個整數都是偶數，就使用2約簡，直到兩個整數不再都是偶數，然后執行第2步。如果兩個整數不都是偶數，則直接執行第2步。
- 用較大的數減去較小的數，如果得到的差恰好等于較小的數，則停止。否則，對較小的數和差值重復這個過程。
- 第1步中約掉的若干個2和第2步中得到的差的乘積為原來兩個整數的最大公約數。
下面，我們將使用對更相減損術進行代碼化。
- '''
- @Author：Runsen
- @WeChat：RunsenLiu
- @微信公眾號：Python之王
- @CSDN：https://blog.csdn.net/weixin_44510615
- @Github：https://github.com/MaoliRUNsen
- @Date：2020/12/9
- '''
- def MaxCommDivisor(m, n):
- # 如果兩個整數都是偶數，就使用2約簡，需要記錄約簡次數
- index = 1
- while m % 2 == 0 and n % 2 == 0:
- m = m / 2
- n = n / 2
- index = index * 2
- # 用較大的數減去較小的數，因此需要判斷m和n的大小，確保m是最大的。
- if m < n:
- m, n = n, m
- # 用較大的數減去較小的數，如果得到的差恰好等于較小的數，則停止。否則，對較小的數和差值重復這個過程。
- while m - n != n:
- diff = m - n
- if diff > n:
- m = diff
- else:
- m = n
- n = diff
- return n * index
- print(MaxCommDivisor(24, 12)) #12
更相減損術和輾轉相除法在一千多年前的東方和西方同時被提出，這說明天才的想法總是驚人的相似，人類科技文明的進程也是同步的，這就是算法之美。
本文已收錄 GitHub: https://github.com/MaoliRUNsen/runsenlearnpy100
