2019演算法複習

一、填空題：

1、假設某演算法在輸入規模為n時的計算時間為t(n)=3×2n。在某台計算機上實現並完成該演算法的時間為t秒。現有另一台計算機，其執行速度為第一台的64倍，那麼在這台計算機上用同一演算法在t秒內能解決輸入規模為（ n+6 ）的問題。

若上述演算法的計算時間改進為t(n)=n2，其餘條件不變，則在新機器上用t秒事件能解輸入規模為（8n ）的問題；若演算法計算時間進一步改進為t(n)=8新機器可解輸入規模（任意規模）。

2、乙個具有n個圓盤的hanoi塔，至少移動次圓盤才能達到目標狀態。

3、設有n個運動員要進行迴圈賽，現設計乙個滿足以下要求的比賽日程表：①每個選手必須與其他n-1名選手比賽各一次；②每個選手一天至多只能賽一次；③迴圈賽要在最短時間內完成。如果n=2k，迴圈賽最少需要進行天；如果n=2k+1，迴圈賽最少需要進行天。

其中，k為正整數。

4、按分治策略求解棋盤覆蓋問題時，對於如圖1所示的23×23的特殊棋盤，共需要個l型骨牌；並在棋盤上填寫l型骨牌的覆蓋情況。

5、按照漸近階從低到高的順序排列下列表示式：

20n，4n2，logn，3n，2，n2/3，n!，2n。

6、分治法的基本思想是將乙個規模為n的問題分解為與原問題的k個規模較小且的子問題。

7、乙個直接或間接地呼叫自身的演算法稱為它有兩個條件，乙個是要直接或間接地呼叫自身，另乙個是必須有

8、在乙個n×n（n=2k）個方格組成的特殊棋盤中，需要

個l型骨牌完成棋盤覆蓋。

9、動態規劃演算法的主要步驟包括刻畫最優解的性質和結構、遞迴定義最優值、以自底向上的方式計算最優值、根據計算最優值的相關資訊構造最優解，在分析了最優解的性質和結構之後，乙個比較至關重要的步驟是給出最優值的遞迴定義，請給出下面幾個問題的最優值的遞迴定義：

（1）矩陣連乘積問題中，a[i：j]連乘所需的最少乘法次數定義為m[i，j]（1≤i≤j≤n），m[i，j]的初始值定義為0（i=j），則m[i，j]遞迴定義為：

m[i ，j

（2）最長公共子串行問題中，c[i，j]表示序列xi和yj的最長公共子串行的長度，則c[i，j]可遞迴定義為：

10、在使用回溯法考慮求解乙個具體問題時，往往需要設計出約束條件和限界條件。裝載問題的約束條件是限界條件是bestw>cw+r，其中，bestw是當前最優值，cwr

11、0-1揹包問題的回溯法和分支限接法求界中都涉及到活結點的上界函式uprofit的計算問題，它是由兩部分組成，一是該活結點已經獲得的價值之和profit，另乙個則是剩餘未考慮物品的價值上界rprofit，這個值可通過獲得。

二、解答問題

1、解遞迴方程

2、用特徵方程求解下列遞迴方程f(n)的解

3、已知有3個物品：(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10), 揹包的容積m=20，根據0/1揹包動態規劃的遞推式求出最優解。

4、有0-1揹包問題如下：n=6，c=20，p=（11，8，15，18，12，6），w=（5，3，2，10，4，2）。畫出用回溯法或優先佇列式分支限界法求解時的搜尋樹，並指明約束條件、限界條件，若使用優先佇列式分支限界法還需指明優先佇列的優先順序。

5、用貪心演算法求下圖頂點1到其它頂點的的最短路徑。

6、設有6個矩陣a1,a2,a3,a4，a5,a6它們的維數分別是：

用動態規劃方法計算矩陣連乘的最優次數m[i][j]。

7、有如下城市網路圖：試給出用回溯法求解時的搜尋情況。