[[356850]]

編程的本質(zhì)來(lái)源于算法，而算法的本質(zhì)來(lái)源于數(shù)學(xué)，編程只不過(guò)將數(shù)學(xué)題進(jìn)行代碼化?！?--- Runsen」

先問(wèn)你們一個(gè)小學(xué)問(wèn)題：「如何求兩個(gè)整數(shù)的最大公約數(shù)?」

曾經(jīng)見(jiàn)過(guò)不少的算法題，發(fā)現(xiàn)有的并不在數(shù)據(jù)結(jié)構(gòu)和算法大綱中，而是來(lái)源于高中數(shù)學(xué)。

高中數(shù)學(xué)在必修三中，有一個(gè)非常重要的知識(shí)點(diǎn)，叫做「碾轉(zhuǎn)相除法、更相減損術(shù)」。

輾轉(zhuǎn)相除法， 又名歐幾里德算法(Euclidean algorithm)乃求兩個(gè)正整數(shù)之最大公因子的算法。它是已知最古老的算法， 其可追溯至公元前300年前。

在古代，有一個(gè)比較出名的數(shù)學(xué)家，叫做「劉徽」。而更相減損術(shù)是我國(guó)數(shù)學(xué)家劉徽的專著《九章算術(shù)》中記載的.

碾轉(zhuǎn)相除法

輾轉(zhuǎn)相除是求最大公約數(shù)的一種算法。給兩個(gè)數(shù),我們可以把它組成數(shù)對(duì)(a,b)輾轉(zhuǎn)相除法基于如下原理：「兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)的相除余數(shù)的最大公約數(shù)?！?/p>

求a和b的最大公約數(shù)，就用ab中較小的數(shù)去除另一個(gè)數(shù)，這個(gè)時(shí)候會(huì)有一個(gè)余數(shù)，當(dāng)余數(shù)是0的時(shí)候，那個(gè)較小的數(shù)就是最大公約數(shù)。

若余數(shù)不是0，那么我們用這個(gè)余數(shù)來(lái)替換那個(gè)比較大的數(shù)，然后以此類(lèi)推，直到算出最大公約數(shù)。

比如，下面我用碾轉(zhuǎn)相除法求100和24的最大公約數(shù)，很明顯最大公約數(shù)就是25。

100 = 24 * 4  + 4 
24  =  4 * 6  + 0  

很顯然4和6中，那個(gè)較小的數(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中，那個(gè)較小的數(shù)5就是55和120最大公約數(shù)。

算法的流程圖(摘自百度百科)

因此得到設(shè)兩數(shù)為m，n，這里不需要判斷兩數(shù)中誰(shuí)最大。

求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é)束

下面，我們將使用對(duì)碾轉(zhuǎn)相除法進(jì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ì)上是一種遞歸的代碼，把求兩個(gè)大數(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 

下面對(duì)Python代碼進(jìn)行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; 
    } 
} 

下面對(duì)Python代碼進(jìn)行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ù)

我國(guó)早期也有求最大公約數(shù)問(wèn)題的算法，就是更相減損術(shù)。

在《九章算術(shù)》中有更相減損術(shù)求最大公約數(shù)的步驟:可半者半之，不可半者，副置分母子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。

更相減損術(shù)來(lái)源于數(shù)的整除性質(zhì)：即如果兩個(gè)整數(shù)a、b都能被c整除,那么a與b的差也能被C整除。

比如求98和63的最大公約數(shù)。

先看98和63這兩個(gè)數(shù)，因?yàn)?3不是偶數(shù)，所以用大數(shù)減去小數(shù)，得到98-63=35 , 63-35=28 35-28=7 , 28-7=21 , 21-7=14 , 14-7=7 。

「此時(shí)，減數(shù)和差相等7」，所以98和63的最大公約數(shù)是7。

再比如求260和104的最大公約數(shù)。

先看260和104兩個(gè)數(shù)，這兩個(gè)數(shù)都是偶數(shù),所以用2約簡(jiǎn)得130和52。

約簡(jiǎn)之后的130和52也都是偶數(shù)，繼續(xù)用2約簡(jiǎn)得65和26，此時(shí)65不是偶數(shù)，所以用大數(shù)減去小數(shù) 65-26=39 , 39-26=13 , 26-13=13。

此時(shí)，減數(shù)和差相等，再上面約去2個(gè)2, 得到的數(shù)是13，所以260和104的最大公約數(shù)是2×2×13=52。

因此更相減損術(shù)不在如下：

• 如果兩個(gè)整數(shù)都是偶數(shù)，就使用2約簡(jiǎn)，直到兩個(gè)整數(shù)不再都是偶數(shù)，然后執(zhí)行第2步。如果兩個(gè)整數(shù)不都是偶數(shù)，則直接執(zhí)行第2步。
• 用較大的數(shù)減去較小的數(shù)，如果得到的差恰好等于較小的數(shù)，則停止。否則，對(duì)較小的數(shù)和差值重復(fù)這個(gè)過(guò)程。
• 第1步中約掉的若干個(gè)2和第2步中得到的差的乘積為原來(lái)兩個(gè)整數(shù)的最大公約數(shù)。

下面，我們將使用對(duì)更相減損術(shù)進(jìn)行代碼化。

''' 
@Author：Runsen 
@WeChat：RunsenLiu  
@微信公眾號(hào)：Python之王 
@CSDN：https://blog.csdn.net/weixin_44510615 
@Github：https://github.com/MaoliRUNsen 
@Date：2020/12/9 
''' 
def MaxCommDivisor(m, n): 
    # 如果兩個(gè)整數(shù)都是偶數(shù)，就使用2約簡(jiǎn)，需要記錄約簡(jiǎn)次數(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ù)，則停止。否則，對(duì)較小的數(shù)和差值重復(fù)這個(gè)過(guò)程。 
    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)相除法在一千多年前的東方和西方同時(shí)被提出，這說(shuō)明天才的想法總是驚人的相似，人類(lèi)科技文明的進(jìn)程也是同步的，這就是算法之美。

本文已收錄 GitHub: https://github.com/MaoliRUNsen/runsenlearnpy100