計算機算法復習重點資料教學文案

1、計算機算法復習重點資料n-bit大數相乘算法歸并排序 給定一個數列，將其排序 排序問題的分治法求解 將待排序數列一分為二，每個子數列分別排序 將完成排序的兩個子數列合并 考慮合并兩個排序的數組 和 ，結果存入 中1. xk1. yl1.zkl“o”表示元素與數列連接 一個mergesort算法執(zhí)行實例習題 使用分治大數相乘算法，計算兩個二進制整數10011011和10111010的乘積。要求畫出算法執(zhí)行的問題分解樹。Explore算法 Explore算法 算法執(zhí)行情況 一個節(jié)點上多條邊存在時按字母順序訪問下一節(jié)點。這個樹被稱為深度優(yōu)先搜索樹（DFS樹） 實線表示圖上實際被訪問的邊，每條實線邊代

2、表一個explore調用。實線邊被稱為樹邊。 虛線邊表示圖上沒有被訪問的邊，因為訪問這些邊不會發(fā)現新的節(jié)點。虛線邊被稱為回邊。深度優(yōu)先搜索explore(u)可以訪問所有從u出發(fā)可達的節(jié)點對于沒有訪問過的節(jié)點v，調用explore(v)訪問從v出發(fā)能夠到達的所有節(jié)點，直到圖G上的所有節(jié)點都被訪問過 在以上算法中，每個節(jié)點有兩個關鍵事件： 算法首次訪問到該節(jié)點； 算法完成從該節(jié)點出發(fā)的所有探索，離開該節(jié)點 定義數組pre和post分別記錄節(jié)點的這兩個時間 通過在previsit和postvisit，和一個初始化為1的計數變量clock來實現 算法執(zhí)行實例 算法先后調用explore(A)，exp

3、lore(C)和explore(F)。 算法產生三棵DFS搜索樹，稱為一個DFS森林 節(jié)點上數值分別為該節(jié)點pre和post的值有向圖上深度優(yōu)先搜索-邊的類型 將DFS算法應用到有向圖上，注意在explore中嚴格按照邊的方向訪問節(jié)點。 DFS在有向圖中執(zhí)行示例 對于有向圖DFS產生的搜索樹（森林），一些定義： A是樹的根節(jié)點，是所有節(jié)點的祖先 所有節(jié)點是A的后裔 F、G和H是E的后裔，E是F、G和H的祖先 A是C和B的父節(jié)點、C和B是A的子節(jié)點 將有向圖G上邊集E中的邊對應到DFS森林中，有一些定義： DFS森林中的實線被稱為樹邊，在這條邊上調用explore 一條從節(jié)點到其非子節(jié)點的后裔的

4、邊被稱為前向邊 一條從節(jié)點到其祖先的邊被稱為回邊 兩個非祖先-后裔關系的節(jié)點之間的邊被稱為橫跨邊習題 在下圖中執(zhí)行深度優(yōu)先搜索，如果遇到多個節(jié)點可供選擇的情況，按照節(jié)點字母順序搜索。畫出DFS樹，給出圖上每條邊是樹邊、前向邊、回邊還是橫跨邊，并標出每個節(jié)點的pre和post值。Dijkstra算法 考慮邊有長度的圖，其中每條邊的長度是正數，我們希望計算圖中節(jié)點之間的距離。 優(yōu)先隊列支持以下操作： insert：隊列中加入一個新元素 decreasekey：將隊列中某個元素的鍵值減少 deletemin：返回隊列中具有最小鍵值的元素，并且將該元素從隊列中移除 makequeue：給定一組元素和鍵

5、值，構造一個優(yōu)先隊列 Dijkstra算法 算法執(zhí)行實例：從A出發(fā)，右邊列出所有節(jié)點當前的dist值A到各節(jié)點的最短路徑樹Bellman-Ford算法 一個運行實例在每一輪，可以按照邊長從小到大調用update，邊調用update的順序不唯一習題 在下圖中從節(jié)點S出發(fā)執(zhí)行Bellman-Ford算法 (a) 使用表格描述算法執(zhí)行過程中從S到各節(jié)點的當前最短距離 (b) 畫出最短路徑樹最小生成樹 Kruskal的算法： 將圖G中所有的邊按照權重從小到大排序； 樹T初始化為空，依次挑選不在T中權重最小的，且在T上不產生環(huán)的邊加入T 算法執(zhí)行實例 加入B-C和C-D，但是B-D產生環(huán)，略過， ,BC

6、 CD BD CFDF EF AD ABCE AC邊的排序： Kruskal算法的實現 使用分離集描述算法的狀態(tài)。每個分離集包含當前獲得連通部件的節(jié)點。如上例中A,B,C和D,E 分離集上實現以下操作 makeset(x)：構造一個僅包含x的單集 find(x)：返回當前x所在的集合 union(x,y)：合并包含x和y的集合為一個集合 完整的Kruskal算法描述 分離集數據結構 使用樹結構表示一個集合。樹可以任意構造。樹上每個節(jié)點代表一個集合元素，每個節(jié)點有一個指針，指向其父節(jié)點。根節(jié)點的指針指向自己。用根節(jié)點代表相應的集合。 樹上每個節(jié)點保存一個數值rank，表示懸掛于該節(jié)點下的子樹的高

7、度。B,EH,C,D,F,G,A 實現makeset和find makeset耗時為O(1)，而find耗時正比于樹的高度 合并兩個集合：將較矮的樹的根節(jié)點直接連到較高的樹的根節(jié)點上function find(x)while x(x): x=(x)return x 操作示例，上標代表節(jié)點的rank 首先執(zhí)行makeset構造單集 執(zhí)行union(A,D)，union(B,E)，union(C,F) 執(zhí)行union(C,G)，union(E,A)Prim算法 使用優(yōu)先隊列，類似Dijkstra 算法執(zhí)行實例習題 考慮下圖 (a) 它的最小生成樹權重（樹上邊權重的總和）是多少?畫出最小生成樹。 (

8、b) 在其上運行Kruskal算法，邊加入MST的順序是怎樣的？有向無環(huán)圖dag上最短路徑問題 dag中所有節(jié)點可以線性排列，這一性質啟發(fā)我們考慮一種新的算法計算dag中兩點間最短路徑 例如：考慮下圖中從S到D的最短路徑 從S到D必須經過B或者C，因此( )min( ) 1,( )3dist Ddist Bdist C 對dag中所有節(jié)點，都存在類似的問題分解關系，如果我們按照下圖dag節(jié)點線性化的順序計算節(jié)點的dist，則在計算每個節(jié)點時，所需要的其它節(jié)點的距離信息已經是已知的了 算法如下最長遞增子序列 給定一個序列的數 定義原序列的子序列為原序列元素的一個子集，且子序列各元素的相對順序不變

9、 。找出給定序列的最長遞增子序列 例如，序列5, 2, 8, 6, 3, 6, 9, 7 的最長遞增子序列是2, 3, 6, 912,na aa1212, 1kiiikaaaiiin且 上圖的有向邊表示元素間的增長關系。如果考慮所有可能添加的有向邊，我們得到下圖 這是一個dag，其中對任意有向邊(i,j)，ij。 令L(j)是終止于元素j的最長遞增子序列的長度，則這個子序列必然包含某條指向j的有向邊(i,j)，使得L(j)=L(i)+1。得到算法如下最大利潤問題 某巧克力工廠生產兩種巧克力，普通巧克力和高級巧克力。工廠每生產一盒普通巧克力，利潤為￥1，每生產一盒高級巧克力，利潤為￥6。每天最多

10、有200盒普通巧克力和300盒高級巧克力的訂單，并且工廠每天生產最多400盒巧克力。工廠希望最大化利潤，應該怎樣安排生產？ 假設工廠每天生產x1盒普通巧克力，x2盒高級巧克力。如何確定它們的取值？ 使用線性規(guī)劃描述問題如下 目標函數： max x1+6x2 限制條件： x1200 x2300 x1+x2400 x1, x20 假設巧克力工廠開發(fā)了一種更高檔的巧克力產品，稱為禮盒巧克力。每生產一盒禮盒巧克力，實現利潤￥13。與上例相同，工廠每天最多生產400盒巧克力，同時，高級巧克力和禮盒巧克力都采用相同的包裝材料，不同的是禮盒巧克力消耗3倍于高級巧克力的包裝材料。工廠每天有600單位的包裝材料。 用x3表示每天生產的禮盒巧克力數量，線性規(guī)劃問題如下maxx1+6x2+13x3x1200, x2300, x1+x2+x3400 x2+3x3600, x1,x2,x30習題 7.2 某種農產品產于A和B兩地，其中A地產量15，B地產量為8。這種產品只在C和D兩個城市銷售，其中C城