Python <演演算法思想集結>之初窺基礎演演算法

1. 前言

資料結構和演演算法是程式的 2 大基礎結構，如果說資料是程式的汽油，演演算法則就是程式的發動機。

什麼是資料結構？

指資料在計算機中的儲存方式，資料的儲存方式會影響到獲取資料的便利性。

現實生活中，如果把春夏秋冬的衣物全部堆放在一起，當需要某一季節的衣服時，尋找起來是困難的。

如果分門別類、有條理地存放，則尋找起來會方便很多。

同理，編寫程式時，如果對程式所依賴的資料有條理、易於查詢的方式進行儲存，則在處理資料時，可以提升程式的整體效能。

資料結構準確說是一個空間管理概念，同樣的資料使用不同的資料結構時，對程式會有空間度上的影響。

什麼是演演算法？

理解演演算法，可以從 2 個角度：

• 廣義角度： 演演算法是指處理資料時，使用的解決思路。只要能達到資料處理目的，任一解決思路都可認為是演演算法，也就是說程式中無處不演演算法。
• 狹義角度： 對各種解決問題的經驗和思路進行總結、歸納，形成演演算法體系或演演算法思想。

研究演演算法的意義：

• 條條道路通羅馬，解決同一個問題的方案往往不只一種，所以，需要在諸多的方案中選擇最佳的一種，這便是研究演演算法的意義之一。
• 系統化演演算法理論，以此讓演演算法成為一門獨立的體系，當解決問題時，可以遵循問題的特徵快速找到特定的演演算法方案。

本文主要是從狹義角度聊聊常見的幾種演演算法。

2. 常見演演算法思想

2.1 窮舉演演算法思想

窮舉演演算法也稱為列舉演演算法或暴力演演算法，是一種原始演演算法。

什麼是原始演演算法?

要了解原始演演算法的概念，就需要理解計算機的思維模式。

計算機本質是一臺無意識、無經驗、無知識積累的冰冷機器，它僅有基本的運算能力和判斷能力。當然它還有一個人類無法比擬的強項，運算速度非常快。

人類思維和計算機思維的區別

比如，請找出數列[1,2,3,4,5]中哪 2 個數位相加等於 5。人類思維是直觀性學習思維，可以直接給出答案，計算機不行。

計算機採用的是基本運算加判斷的方案。先把1和2相加然後判斷，如果不是，繼續 把1和 3相加再判斷……

這種思維我們稱為窮舉思維或暴力思維。

nums = [1, 2, 3, 4, 5]
for i in range(len(nums)):
    for j in range(len(nums)):
        if nums[i] != nums[j] and nums[i] + nums[j] == 5:
            print(nums[i], nums[j])

當數列中的數位很少的時候，人類的思維有優勢，當資料量很大的時候，計算機雖然採用的是笨拙的窮舉思維，但是，因處理速度快，反而要遠遠快於人類計算出來。

本質上講，計算機是無思維的，或者說計算機只會窮舉，所以說，演演算法的本質都是引導性的。

什麼是引導性？

就是你問它，它搖頭或點頭，你根據它的點頭或搖頭，繼續問，它繼續點頭或搖頭，直到得到你想到的答案。

窮法演演算法的思想：在一個指定的資料範圍之內，通過不停地判斷直到查詢到正確的答案。

可以用 2 句話概括：無迴圈無程式，無條件無邏輯。

現根據窮舉演演算法的思路解決一個數學中常見的猜數位題目。

如下圖，每一箇中文漢字表示一個數位，請找出每一個漢字所對應的數位。

窮舉流程：

• 確定數位範圍： 如果要讓整個表示式有意義，則我和程字所對應的數位不能是 0。所以我和程字的數位範圍應該是 1~9之間，其它的數位範圍可以是 0~9之間。
• 初始每一個漢字所對應的數位， 然後套用表示式進行計算，如果計算結果符合要求，則宣佈查詢到，否則，更改每一個漢字所對應的數位。

編寫實現：

# 為 我很愛程式設計 中的每一個漢字初始數位起始邊界
wo = 1
hen = 0
ai = 0
bian = 1
chen = 1
count = 0
result = 0
for wo in range(1, 10):
    for hen in range(0, 10):
        for ai in range(0, 10):
            for bian in range(0, 10):
                for chen in range(1, 10):
                    result = chen * pow(10, 5) + chen * pow(10, 4) + chen * pow(10, 3) + chen * pow(10, 2) + chen * pow(
                        10, 1) + chen
                    num1 = wo * pow(10, 4) + hen * pow(10, 3) + ai * pow(10, 2) + bian * pow(10, 1) + chen
                    count += 1
                    if num1 * wo == result:
                        print(wo, hen, ai, bian, chen)
                        print("次數：",count)
                        break
'''
輸出結果
7 9 3 6 5
次數： 62429
'''

上述程式碼為典型的窮舉演演算法，程式碼中新增了一個計數器，用來統計最終計算多少次，僅為了觀察。

窮舉演演算法的結構有一個較大的特點，往往會出現迴圈語法結構層層巢狀。

在此基礎上思考，是否存在優化方案，可以減少迴圈次數。

題目中還有一個隱式條件，我很愛程式設計中的每一個漢字所對應的數位不能相同。可以把這條件加入到上述程式碼中。

# 為 我很愛程式設計 中的每一個漢字初始數位起始邊界
wo = 1
hen = 0
ai = 0
bian = 1
chen = 1
count = 0
result = 0
for wo in range(1, 10):
    for hen in range(0, 10):
        if hen == wo:
            continue
        for ai in range(0, 10):
            if ai == hen or ai == wo:
                continue
            for bian in range(0, 10):
                if bian == ai or bian == hen or bian == wo:
                    continue
                for chen in range(1, 10):
                    if chen == bian or chen == ai or chen == hen or chen == wo:
                        continue
                    result = chen * pow(10, 5) + chen * pow(10, 4) + chen * pow(10, 3) + chen * pow(10, 2) + chen * pow(
                        10, 1) + chen
                    num1 = wo * pow(10, 4) + hen * pow(10, 3) + ai * pow(10, 2) + bian * pow(10, 1) + chen
                    count += 1
                    if num1 * wo == result:
                        print(wo, hen, ai, bian, chen)
                        print("次數：", count)
                        break
 '''
 輸出結果：
 7 9 3 6 5
 次數： 18666
 '''

從 2 次程式碼的執行結果可知，迴圈次數減少了 62429-18666=43763次。雖然減少了迴圈次數，因沒有從本質上改變演演算法結構，所以說還是最原始的窮舉演演算法思路。

2.2 遞推演演算法思想

計算機的思維本質是窮舉。但是，人的思維是知識性、探索性思維，可以在解決問題時，發現問題中的規律，並通過計算機語言告訴計算機，這樣可以在計算時繞過一些不必要的計算。

研究演演算法的本質就是通過發現資料間的規律、減少窮舉的次數。

什麼是遞推演演算法？

簡單講，不斷地利用已知資訊推匯出最終結果。顯然，已知資訊和最終結果資料之間一定要存在某些內在聯絡或規律。

遞推演演算法又分為順推法和逆推法。

• 順推法： 從已知條件出發，逐步推算出所需要的結果。

• 逆推法： 從已知的結果出發，用迭代式逐步推算出問題開始，逆推法的本質就是逆向思維。

這裡通過 2 個案例分別介紹順推法和逆推法。

斐波拉契數列

數列 [1,1,2,3,5,8,13,21,34,55,……]就是一個符合斐波拉契關係的數列。

斐波拉契數列特點：

• 數列中的第 1、2 位置的數位是 1 ，這是已知資訊。
• 從第 3 個位置開始，其值為前面 2 個數位相加的結果。 知道了第 3 個位置的值，也將知道第 4 個位值，依此類推，可以求解出任何位置的數位。

num1 = 1
num2 = 1
for i in range(12):
    # 推匯出第 3 個位置的數位
    num3 = num1 + num2
    print(num3, end="\t")
    # 為計算後續資料做準備
    num1 = num2
    num2 = num3

求解斐波拉契數列的方案就是典型的順推思維。

如有數列[1,4,10,22,46……]，分析數列中前面幾個數位的規律，輸出數列的前 20 個數位。分析後可發現第 1 個位置的數位 1是已知資訊，從第 2 個位置開始，其值和前一個值符合2*x+2的線性規律，所以也可以遞推演演算法求解。

猴子吃桃

有一隻猴子，第 1 天摘了若干桃子，吃了桃子的一半後又吃了一個，第 2 天也是吃了桃子一半後再吃了一個……如此類推，到第 10 天時，還剩餘 1 只桃子。請問猴子第 1 天摘了多少隻桃子。

分析：

• 第 10 天還剩餘 1 只桃子，可以看成是已知資訊，已知資訊屬於結果資訊。

• 求解第 1 天的桃子總量，需求解的是開始問題。

可以使用逆推演演算法，也就是我們經常講的逆向思維解決猴子吃桃問題。

找出資料之間的關係：

• 第 10 有 1 個桃子，第 10 天的這 1 個桃子是取第 9 天桃子的一半減一個剩餘的。
• 前一天的桃子除以 2 減 1 等於後 1 天的桃子，或者說，前 1 天的桃子等於（後 1 天的桃子加 1）乘以 2。

有了數列之間的關係，編碼就很容易了。

# 第 10 天的桃子數，也是已知條件
num = 1
for i in range(9):
    # 向第 1 天推進
    num = (num + 1) * 2
print(num)

類似的問題還有很多：

如猜年齡問題。

有 5 個小孩子，問第 1 個小孩子的年齡是多少？他說他是第 2 個小孩子的年齡加 2 歲。

問第 2 個小孩子的年齡時，他說他是第3個小孩子的年齡加2歲。

問第3個小孩子的年齡時，他說他是第 4個小孩子年齡加2 歲。

問第 4 個小孩子年齡時，他說他是第 5 個小孩子的年齡加2 歲。

問第 5個小孩子的年齡時，他說他的年齡是 6歲，求解每一個小孩子的年齡。

這個問題也是典型的逆推問題。第 5 個小孩子的年齡是已知的，而且知道與前一個小孩子年齡的關係前一個小孩子的年齡=後一個小孩子年齡+2。滿足數學上的線性函數關係。

一層層回推就能計算出第 1 個小孩子的年齡是：14歲。

age = 6
for i in range(4, 0, -1):
    age = age + 2
    print("第{0}個小孩子的年齡是{1}".format(i,age))
 '''
輸出結果
第4個小孩子的年齡是8
第3個小孩子的年齡是10
第2個小孩子的年齡是12
第1個小孩子的年齡是14
 '''

上述問題雖然簡單，但能精確地描述遞推演演算法的思想。

2.3 遞迴演演算法

具體解決問題時，總是一種演演算法借鑑另一種演演算法，或一個演演算法中融入另一種演演算法。演演算法之間互相交織、迭代而誕生出新的演演算法。

前文所說，窮舉才是計算機的本質，其它演演算法無非是通過分析問題、發現規律、減少演演算法的實施過程中的次數。

什麼是遞迴演演算法？

通過不停呼叫函數本身從而達到解決問題的目地。

如現實生活中經常會遇到的問題，我要找到小王的電話號碼，可以幫助理解遞迴過程。

想知道朋友小王的電話號碼，先找到朋友小李，小李說他也沒有，但是他會幫問問小張,小張說他也沒有，他會問問小胡，小胡說他知道。

這裡麵包括 2 條線。

• 遞進線： 我-（問）->小李-(問)->小張-（問）->小胡(結果)。
• 回溯線： 小胡-(結果)->小張-(結果)->小李-(結果)->我。

遞迴演演算法的特點：

• 通過遞進線尋求幫助。遞推線的最終必須有能得到幫助的時候（如最後小胡知道小王的電話號碼），否則會成為死結。表現在編碼實施過程中需要有呼叫終止的時候。
• 通過回溯線求解出原始問題。

前面的斐波拉契數列也可以使用遞迴演演算法解決。比如說，想知道在第 12 位置的數位是多少。

• 遞進線：求數列第 12位置的值，求助於第 11位置的值，然後再求助於第 10的值， 一至求助到第 1,2位置。
• 回溯線：通過回溯求解出原始問題。

def fb(pos):
    if pos == 1 or pos == 2:
        # 求助的終點
        return 1
    # 求助
    return fb(pos - 1) + fb(pos - 2)
res = fb(12)
print(res)

求解年齡的問題也可以使用遞迴演演算法實現。

def get_age(number):
    if number == 5:
        return 6
    return get_age(number + 1) + 2
print(get_age(1))

遞迴演演算法可以用於 2 類問題的求解：

• 替代迴圈語法結構。一個函數就是一個邏輯實現的封裝，反覆呼叫自己，則可認為重複執行相同邏輯。

  遞迴比迴圈的效能低下。能使用循壞解決的問題就不要使用遞迴。

• 一個看似複雜的問題，其實最終答案歸結到一個小問題上，如求階乘、斐波拉契之類的問題。

  遞迴更多應用於此型別問題的求解。

斐波拉契和求年齡的問題即可以使用前文的遞推演演算法思想實現，也可以使用遞迴演演算法實現。說明：

• 解決一個問題不能拘泥一種方案。

• 演演算法與演演算法之間會有重疊、借鑑、融合之處。

  任何語言都提供有遞迴呼叫方式。可以利用遞迴的特點對資料進行處理。

遞迴的底層依賴於棧資料結構，遞迴的具體細節本文不做太多講解，本文意在概括常見演演算法。

在演演算法理論中，回溯本身就是一種演演算法方案，可獨立解決很多實際問題。

回溯法是計算機解題中常用的演演算法，很多問題無法根據某種確定的計演演算法則來求解，但可以利用回溯的技術求解。回溯法是搜尋演演算法中的一種控制策略。

它的基本思想是：從問題的某一種狀態（一般是預設的初始狀態）出發，搜尋從這種狀態出發所能達到的所有「狀態」，當一條路走到「盡頭」的時候，先退幾步，接著從另一種可能的「狀態」出發，繼續搜尋，直到所有的「路徑」都嘗試過。

回溯思路在我們在現實生活中無處不在，對此體現的較具體的就是下棋，還有一個典型的應用就是走迷宮。

因回溯已經內建在遞迴演演算法中，一般需要使用回溯解決的問題，都會用到遞迴。

2.4 分治思想

將一個計算複雜的問題分為若干子問題來進行求解，然後合併各個小問題得到原始問題的最終求解。

分治演演算法的特點：

• 原始問題和分解出來的子問題的問題形式相同，只是資料規模不相同，也就是說無論是原始問題，還是分解後的子問題，都在解決同一個問題。
• 分解出來的子問題具有完全獨立性，子問題是原始問題的縮影。

分治演演算法實時有 2 個過程：

• 分治： 原始問題能分解成若干較小的相同問題，子問題因規模較小，更容易求解到答案。
• 合併： 合併子問題得到原始問題的求解。

因子問題與原始問題相同，一般會使用遞迴演演算法多次迭代。

如二分查詢以及快速排序，都是分治的思想的應用。

二分查詢的具體實現過程，請查閱我的博文：https://blog.51cto.com/gkcode/5250956

快速排序的具體的實現過程，請查閱我的博文：https://blog.51cto.com/gkcode/5195936

2.5 貪婪演演算法思想

貪婪演演算法總是做出在當前看來最好的選擇，並從不整體最優考慮，只是區域性最優秀。雖然貪婪演演算法總是從區域性最優求解，但有時也有可能讓最終求解也是最優的。

貪婪演演算法的特點：

• 不能保證最後的解是最優的。

• 不能用來求最大或最小解問題。

• 只能求滿足某些約束條件的可行解。

貪婪演演算法最典型的案例：找零錢。

問題描述：在超市購物時，收銀員找零錢時，如何使找回零錢的紙幣數最少。

貪婪演演算法的思路是從最大面值的幣種開始，按遞減的順序考慮各種幣種。也就是先儘量用大面值的幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。

這裡的貪心表現在最大可能使用最大金額的幣種。顯然，貪婪演演算法在此問題上是可行的。

編碼實現：

假設人民幣有 100、50、20、10、5、2、1、0.5、0.1幾種面額，且數量無限，找零錢時，請儘量實現找給顧客的零錢所用到的幣種的總數量最少。

# 幣種
bi_zhongs = [100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1]
# 記錄最終結果
dic = {}

# 找霍
lq = 68.9
# 為了便於計算，擴大100倍
lq = lq * 100
for i in range(len(bi_zhongs)):
    if lq >= bi_zhongs[i] * 100:
        # 計算張數
        count = lq // (bi_zhongs[i] * 100)
        dic[bi_zhongs[i]] = int(count)
        # 餘額
        lq = lq % (bi_zhongs[i] * 100)
    if lq == 0:
        break
# 輸出每一種幣種的數量
print(dic)
'''
輸出結果：
{50: 1, 10: 1, 5: 1, 2: 1, 1: 1, 0.5: 1, 0.2: 2}
'''

3. 總結

本文介紹了常見的幾種基礎演演算法 ，除些之外，還有更多演演算法思想。如動態規劃、摸擬思想……限於篇幅原因，本文中即不一一羅列，也不深研演演算法內在細節。

後續會為某些經典演演算法單獨開文，詳細介紹其演演算法的微妙之處。

萬變不離其宗，研究演演算法時即要做到能對各種演演算法獨立分析，又要做到融合貫通。