---

title: 算法導(dǎo)論總復(fù)習(xí)
author: Clint_chan
categories: [ 陳定鋼]
image: assets/images/flag1.jpg
tags: 算法導(dǎo)論復(fù)習(xí),向高分前進(jìn)！

---

目錄

• 一.排序算法
  • 1.選擇排序
    • 1.1原理&圖示
    • 1.2代碼部分
  • 2.插入排序
    • 2.1原理&圖示
    • 2.2代碼部分
  • 3.歸并排序
    • 3.1原理&圖示
    • 3.2代碼部分
  • 4.快速排序
    • 4.1原理&圖示
    • 4.2代碼部分
  • 5.堆排序
    • 5.1原理&圖示
    • 5.2代碼部分
  • 6.計(jì)數(shù)排序
    • 6.1原理&圖示
    • 6.2代碼部分
  • 7.桶排序
    • 7.1原理&圖示
    • 7.2代碼部分
  • 8.基數(shù)排序
    • 8.1原理&圖示
    • 8.2代碼部分
  • 9.希爾排序
    • 9.1原理&圖示
    • 9.2代碼部分
  • 10.排序算法比較
• 二.紅黑樹
  • 1.紅黑樹定義和性質(zhì)
• 三.動(dòng)態(tài)規(guī)劃
  • 1.鋼條問題
  • 2.矩陣鏈問題
  • 3.LCS問題
• 四.貪心算法
• 五.圖算法
• 六.粒子群算法
• 七.遺傳算法與模擬退火
• 考試資料
• 教案
• 參考文獻(xiàn)

一.排序算法

1.選擇排序

1.1原理及圖示

在未排序數(shù)組中找到最小（大）關(guān)鍵詞元素排在已排序序列初始位置，再如此，將選中的元素插入到已排序序列末尾。（類似于數(shù)據(jù)結(jié)構(gòu)的進(jìn)棧操作）
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-BcGWZJJ7-1608866355870)(https://clint-chan.github.io/CDG/assets/images/selectionSort.gif)]

1.2代碼部分

#Python代碼 def selectionSort(arr):for i in range(len(arr) - 1):# 記錄最小數(shù)的索引minIndex = ifor j in range(i + 1, len(arr)):if arr[j] < arr[minIndex]:minIndex = j# i 不是最小數(shù)時(shí)，將 i 和最小數(shù)進(jìn)行交換if i != minIndex:arr[i], arr[minIndex] = arr[minIndex], arr[i]return arr

2.插入排序

2.1原理及圖示

將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列，依次讀取未排序序列中的元素，并插入到已排序序列合理位置。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-QUPM9WxK-1608866355874)(https://www.runoob.com/wp-content/uploads/2019/03/insertionSort.gif)]

2.2代碼部分

# Python代碼 def insertionSort(arr):for i in range(len(arr)):preIndex = i-1current = arr[i]while preIndex >= 0 and arr[preIndex] > current:arr[preIndex+1] = arr[preIndex]preIndex-=1arr[preIndex+1] = currentreturn arr

3.歸并排序

3.1原理及圖示

需要申請(qǐng)內(nèi)存空間，采用遞歸函數(shù)，依次二分，直至只剩一個(gè)元素，再依次合并。（最底層合并是1合1等于2，倒數(shù)第二層是2合2=4）
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-H68KPxkA-1608866355876)(https://www.runoob.com/wp-content/uploads/2019/03/mergeSort.gif)]

3.2代碼部分

# Python代碼 def mergeSort(arr):import mathif(len(arr)<2):return arrmiddle = math.floor(len(arr)/2)left, right = arr[0:middle], arr[middle:]return merge(mergeSort(left), mergeSort(right))def merge(left,right):result = []while left and right:if left[0] <= right[0]:result.append(left.pop(0))else:result.append(right.pop(0));while left:result.append(left.pop(0))while right:result.append(right.pop(0));return result

4.快速排序

4.1原理及圖示

從序列中挑選一個(gè)基準(zhǔn)值作為分割標(biāo)準(zhǔn)，然后再已分割的兩個(gè)序列繼續(xù)分割，再…分割，最后遞歸地（recursive）合并。如果還不明白請(qǐng)參考更多資料，考試可能要考。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-TQFhCVOA-1608866355882)(https://www.runoob.com/wp-content/uploads/2019/03/quickSort.gif)]

4.2代碼部分

#快速排序Python代碼 def quickSort(arr, left=None, right=None):left = 0 if not isinstance(left,(int, float)) else leftright = len(arr)-1 if not isinstance(right,(int, float)) else rightif left < right:partitionIndex = partition(arr, left, right)quickSort(arr, left, partitionIndex-1)quickSort(arr, partitionIndex+1, right)return arrdef partition(arr, left, right):pivot = leftindex = pivot+1i = indexwhile i <= right:if arr[i] < arr[pivot]:swap(arr, i, index)index+=1i+=1swap(arr,pivot,index-1)return index-1def swap(arr, i, j):arr[i], arr[j] = arr[j], arr[i]

5.堆排序

5.1原理及圖示

首先構(gòu)建樹結(jié)構(gòu)，隨后構(gòu)建極大（小）堆，然后將最后節(jié)點(diǎn)與根節(jié)點(diǎn)交換，并將該根節(jié)點(diǎn)依次取出。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-JlpVMDHc-1608866355890)(https://www.runoob.com/wp-content/uploads/2019/03/heapSort.gif)]

---

本次期末考試如無特別說明，高度深度從0開始記。

樹的高度為根節(jié)點(diǎn)的高度；某節(jié)點(diǎn)的高度等于該節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑（邊數(shù)）；節(jié)點(diǎn)的深度是根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)所經(jīng)歷的邊的個(gè)數(shù)。
構(gòu)建極大堆時(shí)間復(fù)雜度:O(lgn)

---

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-6WvsGyb0-1608866355892)(https://clint-chan.github.io/CDG/assets/images/heap-sort.png)]

5.2代碼部分

#堆排序 Python代碼 def buildMaxHeap(arr):import mathfor i in range(math.floor(len(arr)/2),-1,-1):heapify(arr,i)def heapify(arr, i):left = 2*i+1right = 2*i+2largest = iif left < arrLen and arr[left] > arr[largest]:largest = leftif right < arrLen and arr[right] > arr[largest]:largest = rightif largest != i:swap(arr, i, largest)heapify(arr, largest)def swap(arr, i, j):arr[i], arr[j] = arr[j], arr[i]def heapSort(arr):global arrLenarrLen = len(arr)buildMaxHeap(arr)for i in range(len(arr)-1,0,-1):swap(arr,0,i)arrLen -=1heapify(arr, 0)return arr

6.計(jì)數(shù)排序

6.1原理及圖示

原理的話看圖很好理解；

• （1）找出待排序的數(shù)組中最大和最小的元素
• （2）統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
• （3）對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）
• （4）反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1

---

6.2代碼部分

#計(jì)數(shù)排序Python代碼 def countingSort(arr, maxValue):bucketLen = maxValue+1bucket = [0]*bucketLensortedIndex =0arrLen = len(arr)for i in range(arrLen):if not bucket[arr[i]]:bucket[arr[i]]=0bucket[arr[i]]+=1for j in range(bucketLen):while bucket[j]>0:arr[sortedIndex] = jsortedIndex+=1bucket[j]-=1return arr

7.桶排序

桶排序是計(jì)數(shù)排序的升級(jí)版（將離散數(shù)值升級(jí)為連續(xù)區(qū)間）。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。為了使桶排序更加高效，我們需要做到這兩點(diǎn)：

• 在額外空間充足的情況下，盡量增大桶的數(shù)量
• 使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)均勻的分配到 K 個(gè)桶中
• 同時(shí)，對(duì)于桶中元素的排序，選擇何種比較排序算法對(duì)于性能的影響至關(guān)重要。
  理想情況：當(dāng)輸入的數(shù)據(jù)可以均勻的分配到每一個(gè)桶中。
  最壞情況：所有數(shù)據(jù)分入一個(gè)桶中。

7.1原理及圖示

7.2代碼部分

#桶排序Python代碼 def bucketSort(nums):#選擇一個(gè)最大的數(shù)max_num = max(nums)# 創(chuàng)建一個(gè)元素全是0的列表, 當(dāng)做桶bucket = [0]*(max_num+1)# 把所有元素放入桶中, 即把對(duì)應(yīng)元素個(gè)數(shù)加一for i in nums:print(f"{bucket=}")bucket[i] += 1# 存儲(chǔ)排序好的元素sort_nums = []print(f"{bucket=}")for j in range(len(bucket)):n = bucket[j]if n != 0:for _ in range(n):print(f"{sort_nums=}{j=}")sort_nums.append(j)return sort_numsnums = [5,6,3,2,1,65,2,0,8,0,9] print("測(cè)試結(jié)果:") print(bucketSort(nums))

8.基數(shù)排序

8.1原理及圖示

基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。

• 基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序
  • 基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶；
  • 計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值；
  • 桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值；

---

8.2代碼部分

#基數(shù)排序Python代碼 def radix_sort(s):"""基數(shù)排序"""i = 0 # 記錄當(dāng)前正在排拿一位，最低位為1max_num = max(s) # 最大值j = len(str(max_num)) # 記錄最大值的位數(shù)while i < j:bucket_list =[[] for _ in range(10)] #初始化桶數(shù)組for x in s:bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶數(shù)組print(bucket_list)s.clear()for x in bucket_list: # 放回原序列for y in x:s.append(y)i += 1if __name__ == '__main__':a = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,23424]radix_sort(a)print(a)

9.希爾排序

9.1原理及圖示

基本思想：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄"基本有序"時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

由基本思想可以得出希爾排序也就是升級(jí)版的插入排序，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

---

9.2代碼部分

#Python代碼 def shellSort(arr):import mathgap=1while(gap < len(arr)/3):gap = gap*3+1while gap > 0:for i in range(gap,len(arr)):temp = arr[i]j = i-gapwhile j >=0 and arr[j] > temp:arr[j+gap]=arr[j]j-=gaparr[j+gap] = tempgap = math.floor(gap/3)return arr

10.排序算法比較

Congretulations! 恭喜你已經(jīng)復(fù)習(xí)完了排序算法，下面咱們來比較這些算法吧！

• 穩(wěn)定性：有隨機(jī)性的都統(tǒng)一為不穩(wěn)定，其余為穩(wěn)定。
• 空間復(fù)雜度：精通流程就可以聯(lián)想到。
• 時(shí)間復(fù)雜度：需要熟讀（偽）代碼并了解數(shù)學(xué)推導(dǎo)
• In-place & Out-place：需不需要開辟輔助空間

---

二.紅黑樹

1.紅黑樹定義和性質(zhì)

紅黑樹是一種含有紅黑結(jié)點(diǎn)并能自平衡的二叉查找樹。它必須滿足下面性質(zhì)：

• 性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。
• 性質(zhì)2：根節(jié)點(diǎn)是黑色。
• 性質(zhì)3：每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。
• 性質(zhì)4：每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色。
• 性質(zhì)5：任意一結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)。
  • 性質(zhì)5.1：如果一個(gè)結(jié)點(diǎn)存在黑子結(jié)點(diǎn)，那么該結(jié)點(diǎn)肯定有兩個(gè)子結(jié)點(diǎn)

---

一顆簡(jiǎn)單的紅黑樹：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-GcfvauQy-1608866355905)(https://clint-chan.github.io/CDG/assets/images/紅黑樹1.png)]

紅黑樹能自平衡，它靠的是什么？三種操作：左旋、右旋和變色。

• 左旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))，其右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，右子結(jié)點(diǎn)的左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的右子結(jié)點(diǎn)，左子結(jié)點(diǎn)保持不變。如圖3。
• 右旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))，其左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，左子結(jié)點(diǎn)的右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的左子結(jié)點(diǎn)，右子結(jié)點(diǎn)保持不變。
• 變色：結(jié)點(diǎn)的顏色由紅變黑或由黑變紅。

---

插入和刪除相對(duì)復(fù)雜，需要仔細(xì)學(xué)習(xí)教案和參考資料。

• 插入：插入一共有八種情景；

• 刪除：刪除簡(jiǎn)化后仍有九種情景。

點(diǎn)擊這里回到目錄

三.動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃三要素：（1）問題的階段（2）每個(gè)階段的狀態(tài)（3）相鄰兩個(gè)階段之間的遞推關(guān)系 特點(diǎn)：（1）最優(yōu)化原理（2）無后效性（3）有重疊子問題 關(guān)鍵詞：（1）自底向上（2）填表法（3）寧死不用遞歸 掌握關(guān)鍵： 動(dòng)態(tài)規(guī)劃不是具體算法，它只是一種思想，要深入理解這種思想。（1）以大化小，把大問題化成小問題，而小問題的解已經(jīng)存入在某個(gè)數(shù)據(jù)結(jié)構(gòu)當(dāng)中了，即可以做到調(diào)用。（2）調(diào)用完即可算出當(dāng)前需算的結(jié)果，然后將此結(jié)果當(dāng)做已知，繼續(xù)向頂進(jìn)行。（3）應(yīng)用：a.鋼條切割問題中，以大化小，比如要算長(zhǎng)度d=4的最優(yōu)價(jià)格，先由d=1算起；那么d_4=max（所有已知結(jié)果中最優(yōu)的組合)，即遍歷操作。①分成兩段，第一段為1，那么第二段為3，而d=3時(shí)的最優(yōu)價(jià)格已算出 ，那么①操作就是備選的d_4之一。②...，第一段為2，那么第二段為2，而d=2時(shí)的最優(yōu)價(jià)格也已經(jīng)算出，那么②操作也是備選d_4之一。③...，第一段為3，那么第二段為1，而d=3時(shí)的最優(yōu)價(jià)格也已經(jīng)算出，那么③操作也是備選d_4之一。④...，第一段為4，那么第二段為0，由價(jià)格表直接查出價(jià)格，也是備選d_4之一。⑤選出最好的d_4。b.LCS問題中，采用動(dòng)態(tài)規(guī)劃的具體思想體現(xiàn)在，他每一步都保存了進(jìn)度，比如我算出長(zhǎng)度為4是因?yàn)槲野l(fā)現(xiàn)從長(zhǎng)度為3開始有新的可行路徑，而不是算每一個(gè)長(zhǎng)度都從零開始，但依舊是自底向上。我們也可以由此看出，動(dòng)態(tài)規(guī)劃無論如何怎樣變，以此衍生的各種算法不變的只有自底向頂?shù)倪M(jìn)行計(jì)算操作。

---

1.鋼條切割問題

• ①自頂向下（非多項(xiàng)式級(jí)復(fù)雜度）
• ②帶備忘錄的自頂向下（平方階）
• ③自底向上（平方階）

①自頂向下

#自頂向下 1 def CutRod(p, n): # 函數(shù)返回：切割長(zhǎng)度為 n 的鋼條所得的最大收益 2 if n == 0: 3 return 0 4 q = -1 5 for i in range(1, n+1): 6 q = max(q, p[i] + CutRod(p, n-i)) 7 return q

Core part:Line 5,6.Specific codes go looking up pdf.

②帶備忘錄的自頂向下

#帶備忘錄的自頂向下 1 def MemorizedCutRod(p, n): 2 r=[-1]*(n+1) # 數(shù)組初始化 3 def MemorizedCutRodAux(p, n, r): 4 if r[n] >= 0: 5 return r[n] 6 q = -1 7 if n == 0: 8 q = 0 9 else: 10 for i in range(1, n + 1): 11 q = max(q, p[i] + MemorizedCutRodAux(p, n - i, r)) 12 r[n] = q 13 return q 14 return MemorizedCutRodAux(p, n, r),r

Core part:Line 3,4,5.Specific codes go looking up pdf.

③自底向上

1 def BottomUpCutRod(p, n): 2 r = [0]*(n+1) 3 for i in range(1, n+1): 4 if n == 0: 5 return 0 6 q =0 7 for j in range(1, i+1): 8 q = max(q, p[j]+r[i-j]) 9 r[i] = q 10 return r[n],r

Core part:Line All.Specific codes go looking up pdf.

2.矩陣鏈問題

Python代碼 p = [30, 35, 15, 5, 10, 20, 25] def matrix_chain_order(p):n = len(p) - 1 # 矩陣個(gè)數(shù)m = [[0 for i in range(n)] for j in range(n)] s = [[0 for i in range(n)] for j in range(n)] # 用來記錄最優(yōu)解的括號(hào)位置for l in range(1, n): # 控制列，從左往右for i in range(l-1, -1, -1): # 控制行,從下往上m[i][l] = float('inf') # 保存要填充格子的最優(yōu)值for k in range(i, l): # 控制分割點(diǎn)q = m[i][k] + m[k+1][l] + p[i]*p[k+1]*p[l+1]if q < m[i][l]:m[i][l] = qs[i][l] = kreturn m, sdef print_option_parens(s, i, j):if i == j:print('A'+str(i+1), end='')else:print('(', end='')print_option_parens(s, i, s[i][j])print_option_parens(s, s[i][j]+1, j)print(')', end='')r, s = matrix_chain_order(p) print_option_parens(s, 0, 5) 計(jì)算次序?qū)τ?jì)算性能的影響：假設(shè)n=3，A1，A2，A3的維數(shù)分別為10×100，100×5，5×50。考察A1×A2×A3需要的數(shù)乘次數(shù)，有以下 兩種計(jì)算方式： （1）（A1×A2）×A3：10×100×5+10×5×50=7500 （2） A1×（A2×A3）：100×5×50+10×100×50=75000通過這個(gè)簡(jiǎn)單的例子足以說明，矩陣的計(jì)算次序?qū)τ?jì)算性能的影響極大。

①所謂標(biāo)量乘法就是進(jìn)行了多少次數(shù)與數(shù)之間的乘法。
②矩陣A 的行列數(shù)分別為i,j ；矩陣B的行列數(shù)分別為k,l,那么要進(jìn)行矩陣乘法A·B需首先需滿足j=k（前列等于后行）.
③我們這邊取標(biāo)量乘法次數(shù)為:count=j*k*l.

其中l(wèi)為第二個(gè)矩陣的列數(shù)代表要做幾次矩陣乘法（每次矩陣乘法進(jìn)行了j*k次標(biāo)量乘法）

④將各數(shù)組的行列值分別儲(chǔ)存在指定的數(shù)據(jù)結(jié)構(gòu)中

3.LCS問題

#Python代碼 import pandas as pd def LCS(s1, s2):size1 = len(s1) + 1size2 = len(s2) + 1# 程序多加一行，一列，方便后面代碼編寫chess = [[["", 0] for j in list(range(size2))] for i in list(range(size1))]for i in list(range(1, size1)):chess[i][0][0] = s1[i - 1]for j in list(range(1, size2)):chess[0][j][0] = s2[j - 1]print("初始化數(shù)據(jù)：")display(pd.DataFrame(chess))for i in list(range(1, size1)): #讓第一行和第一列為0for j in list(range(1, size2)):if s1[i - 1] == s2[j - 1]: #判斷字符是否相等 如果不相等進(jìn)入下一個(gè)判斷條件chess[i][j] = ['↖', chess[i - 1][j - 1][1] + 1]elif chess[i][j - 1][1] > chess[i - 1][j][1]: #因?yàn)槌跏蓟癁?了，所以自底向上的話：幾何上“左邊”必然大于"下方"，所以置‘←’chess[i][j] = ['←', chess[i][j - 1][1]]else:chess[i][j] = ['↑', chess[i - 1][j][1]]print("計(jì)算結(jié)果：")display(pd.DataFrame(chess))i = size1 - 1 #從下往上查找j = size2 - 1s3 = []while i > 0 and j > 0:if chess[i][j][0] == '↖':s3.append(chess[i][0][0])i -= 1j -= 1if chess[i][j][0] == '←':j -= 1if chess[i][j][0] == '↑':i -= 1s3.reverse() #逆序輸出print("最長(zhǎng)公共子序列：%s" % ''.join(s3))LCS("abcde", "asdzbd") # 總之本程序就是由底至頂，由行至列，最后逆序輸出。

輸出如圖，這里使用display函數(shù)美觀的將其輸出（國(guó)內(nèi)技術(shù)人員不常用）
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-rqzveATV-1608866355910)(https://clint-chan.github.io/CDG/assets/images/lcs.png)]

要看懂這個(gè)圖，并且要與上述代碼一起看，理解每一步，下面我?guī)Т蠹襾砝斫庖幌逻@個(gè)圖： 1.輸入和處理操作本圖應(yīng)從左至右，從上至下看起；輸出操作反之。 2.輸入：先根據(jù)字符串的長(zhǎng)度確定矩陣的維度(i+1,j+1)，加1的目的是為了實(shí)現(xiàn)一種簡(jiǎn)陋的美觀<i class="fas fa-feather-alt"></i>（如果結(jié)合pandas可以把這個(gè)寫在行列索引里），隨后將第一行列以各字符順序填入，其余行列以(flag,0)初始化，其中flag是指↑，↖，←這三種標(biāo)記。 3.處理：處理操作有兩層for循環(huán)，顯而易見是分別用來控制行列的。先把第一行填滿，再把第二行填滿....直到最后一行（行數(shù)為輸入的第一個(gè)字符串長(zhǎng)度加1），其中每一步都保存上一步的結(jié)果，在這個(gè)算法中體現(xiàn)在長(zhǎng)度上。 從[i,j]=[1,1]看起，根據(jù)判斷條件，a.如果s1[i - 1] == s2[j - 1]，那么填入[↖,chess[i - 1][j - 1][1] + 1]，其中chess[i - 1][j - 1][1] + 1是指矩陣中左上的那一個(gè)元素所儲(chǔ)存的長(zhǎng)度值（儲(chǔ)存在第三維度），再加上1b.如果chess[i][j - 1][1] > chess[i - 1][j][1]，即元素chess[i][j]在矩陣中的左邊元素大于其正上方的元素，則chess[i][j]就為flag值='←'和原長(zhǎng)度，組成的嵌套數(shù)組，即chess[i][j] = ['←', chess[i][j - 1][1]]c.除了上述條件，一切均給chess[i][j]為['↑',原長(zhǎng)度]。d.值得注意的是本處理過程判斷條件的先后一定要注意，肯定是先判斷第一個(gè)if，判斷兩個(gè)子字符是否相等，要不然會(huì)亂套。 4.輸出，從右下至左上開始讀取矩陣元素，最后用reverse函數(shù)逆序輸出。至于為什么要反著來讀，因?yàn)檫@樣容易找到"回去"的路。

點(diǎn)擊這里回到目錄

四.貪心算法

點(diǎn)擊這里回到目錄

---

考試資料

• [1] 排序算法選擇題
• [2] （李蕓老師）算法導(dǎo)論第1次作業(yè)
• [3] （李蕓老師）算法導(dǎo)論第2次作業(yè)
• [4] （李蕓老師）算法導(dǎo)論第3次作業(yè)
• [5] （李蕓老師）2020秋期中測(cè)試題

教案

• [1] 算法基礎(chǔ)知識(shí)
• [2] 函數(shù)的增長(zhǎng)
• [3] 概率分析與隨機(jī)算法
• [4] 分治策略
• [5] 堆排序
• [6] 快速排序
• [7] 線性時(shí)間排序、統(tǒng)計(jì)量
• [8] 基本數(shù)據(jù)結(jié)構(gòu)
• [9] 二叉搜索樹
• [10] 紅黑樹
• [11] 動(dòng)態(tài)規(guī)劃
• [12] 貪心算法
• [13] 基本的圖算法
• [14] 粒子群優(yōu)化算法
• [15] 遺傳算法與模擬退火算法

參考文獻(xiàn)

• [1] 快速排序算法——C/C++
• [2] Python實(shí)現(xiàn)二叉樹遍歷的遞歸和非遞歸算法
• [3] 求遞歸算法時(shí)間復(fù)雜度：遞歸樹
• [4] 主方法求解遞歸式
• [5] 30張圖帶你徹底理解紅黑樹
• [6] 常見的八大排序算法的比較和選擇依據(jù)
• [7] 各種排序算法總結(jié)和比較
• [8] leetcode410:分割數(shù)組的最大值_填表法求解動(dòng)態(tài)規(guī)劃

溫馨提示：用Ctrl+鼠標(biāo)左鍵可以創(chuàng)建新窗口打開鏈接以便流暢體驗(yàn)。

點(diǎn)擊這里回到目錄

總結(jié)

以上是生活随笔為你收集整理的算法导论总复习的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。