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