西安郵電大學(xué)《算法設(shè)計與分析》課內(nèi)上機實驗題目及其解答

1、西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院算法設(shè)計與分析算法設(shè)計與分析上機題目解答上機題目解答西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院算法設(shè)計與分析算法設(shè)計與分析上機存在的問題上機存在的問題（1）上機準(zhǔn)備工作不足；）上機準(zhǔn)備工作不足；（2）程序設(shè)計風(fēng)格不夠好；）程序設(shè)計風(fēng)格不夠好；（3）測試用例設(shè)計不夠全面；）測試用例設(shè)計不夠全面；（4）上機報告撰寫不夠認(rèn)真；）上機報告撰寫不夠認(rèn)真；（5）上機報告排版不夠規(guī)范。）上機報告排版不夠規(guī)范。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院算法設(shè)計與分析算法設(shè)計與分析遞歸與分治策略遞歸與分治策略西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院遞歸與分治策

2、略遞歸與分治策略基本題基本題 1：用分治法查找數(shù)組元素的最大值和用分治法查找數(shù)組元素的最大值和最小值。最小值。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院遞歸與分治策略遞歸與分治策略【問題分析問題分析】（1）數(shù)組的生成）數(shù)組的生成：許多同學(xué)采用固定數(shù)組固定數(shù)組的做法，實際上采用隨機數(shù)組隨機數(shù)組是一個比較好的做法，一是可以生成隨機數(shù)字，便于測試代碼；二是相對于固定長度數(shù)組可以很方便地生成任意長度的數(shù)組。如下：西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院遞歸與分治策略遞歸與分治策略（2）算法分析）算法分析：給同學(xué)們的資料上面的算法如下所示：算法中“假定 n 是 2 的指數(shù)倍”，實際算法中可以不局限

3、于此。許多同學(xué)都正確地實現(xiàn)了任意長度數(shù)組的最值計算分治算法。算法的偽代碼如下（并非唯一算法）算法的偽代碼如下（并非唯一算法）：西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院遞歸與分治策略遞歸與分治策略西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院遞歸與分治策略遞歸與分治策略（3）小結(jié)）小結(jié)：大部分同學(xué)均能夠正確編寫程序，但存在一些問題，需要繼續(xù)努力。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院遞歸與分治策略遞歸與分治策略基本題基本題 2：眾數(shù)問題（眾數(shù)問題（課本課本 P39 算法實現(xiàn)題算法實現(xiàn)題 2的的 2-1 題題）。）。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院遞歸與分治策略遞歸與分治策略西

4、安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院遞歸與分治策略遞歸與分治策略西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院遞歸與分治策略遞歸與分治策略【問題分析問題分析】（1）算法）算法：可以用很直觀的思路來求解“眾數(shù)”問題，即通過掃描輸入文件中的各個數(shù)據(jù)，如果是新數(shù)據(jù)則建立“記錄”；否則針對老數(shù)據(jù)累加其出現(xiàn)頻度。最后統(tǒng)計出現(xiàn)頻度最高的“數(shù)據(jù)”即為“眾數(shù)眾數(shù)”，該頻度的值為“重數(shù)重數(shù)”。由于上述算法中涉及到“查找”，因此一種做法是先將讀入的全部數(shù)據(jù)排序，之后按照上述思路逐個分析、處理。大部分同學(xué)都能正確求解此問題，采用的排序算法有“快速排序快速排序”和“合并排序合并排序”（均體均體現(xiàn)了現(xiàn)了“分治法分治

5、法”思想思想）；數(shù)據(jù)結(jié)構(gòu)有結(jié)構(gòu)體結(jié)構(gòu)體或者二維數(shù)組二維數(shù)組，用來保存出現(xiàn)的數(shù)據(jù)及其頻度。這些都是正確的做法。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院遞歸與分治策略遞歸與分治策略（2）小結(jié)）小結(jié)：和“數(shù)組求最值”問題相同。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院算法設(shè)計與分析算法設(shè)計與分析動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院基本題基本題 1：編輯距離問題（編輯距離問題（第第 4 版教材版教材P79 3-2題題）。動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃【問題分析問題分析

6、】（1）算法原理分析）算法原理分析西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃（2）小結(jié)）小結(jié)：經(jīng)過查閱資料和分析，大部分同學(xué)都能理解算法并編寫出正確的程序，有些同

7、學(xué)還有不同的思路，有些同學(xué)將“編輯距離”視為一個對象，采用 OOP 的方法編寫程序，這些都是值得鼓勵的。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃基本題基本題 2：數(shù)字三角形問題（數(shù)字三角形問題（第第 4 版教材版教材P80 3-4題題）。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃【問題分析問題分析】（1）算法原理分析）算法原理分析根據(jù)題目描述，如下圖所示，可以將數(shù)字三角形轉(zhuǎn)化為右邊的形式。這樣可以用下三角矩陣下三角矩陣來儲存各個數(shù)字。西安

8、郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃（A）最優(yōu)子結(jié)構(gòu)）最優(yōu)子結(jié)構(gòu)：從下往上看從下往上看，“最底層到底最底層到底 n - 1 層層”的最優(yōu)解包含“最最底層到底底層到底 n 層層”的最優(yōu)解。（B）重疊子問題）重疊子問題：要求從最底層到從最底層到 n 層的解層的解需求從最低層到從最低層到 n - 1 層的解層的解。本題可用動態(tài)規(guī)劃方法求解本題可用動態(tài)規(guī)劃方法求解。令 TriArray 表示數(shù)字三角形轉(zhuǎn)換成的二維矩陣，ResArray i j 為結(jié)果數(shù)組，表示第表示第 i 層第層第 j 個數(shù)字到最低端的最優(yōu)解個數(shù)字到最低端的最優(yōu)解。則有遞推式：ResArray i - 1 j =

9、max ( TriArray i - 1 j + ResArray i j ), ( TriArray i - 1 j + ResArray i j + 1 西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃算法偽代碼算法偽代碼西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃（2）小結(jié)）小結(jié)：本題目相對于“編輯距離”題目而言更為直觀，容易思考。絕大多數(shù)同學(xué)都能正確求解。但很多同學(xué)未從“動態(tài)規(guī)劃動態(tài)規(guī)劃”的角度來思考本問題，這是不滿足題目要求的。另外測試用例不夠全面是存在的普遍問題，許多同學(xué)僅僅測試了題目給定的一個例子。事實上，題目要求數(shù)字三題目要求數(shù)字三角形的行數(shù)角形的行

10、數(shù) n 滿足條件滿足條件 1 = n = 100，而且所有數(shù)字在，而且所有數(shù)字在 0 99 之間之間。因此設(shè)計測試用例時應(yīng)該考慮上述條件，最好用“隨機數(shù)隨機數(shù)”設(shè)計方法設(shè)計方法來自動設(shè)計測試用例并自動測試（比如在同一個程序中設(shè)計一個循環(huán)，自動生成若比如在同一個程序中設(shè)計一個循環(huán)，自動生成若干個測試?yán)硬⒆詣訙y試，最后輸出所有結(jié)果供分析干個測試?yán)硬⒆詣訙y試，最后輸出所有結(jié)果供分析）。上機時發(fā)現(xiàn)的另外一個問題是有些同學(xué)編寫的程序中采用字符方式從文本文件中讀取數(shù)字采用字符方式從文本文件中讀取數(shù)字西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃三角形的數(shù)字三角形的數(shù)字，如果這個數(shù)字大于或

11、等于 10（2 位位），就會造成錯誤。這需要修改程序。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃基本題基本題 3：最大最大 k 乘積問題（乘積問題（第第 4 版教材版教材P83 3-13題題）。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃【問題分析問題分析】（1）算法原理分析）算法原理分析先通過若干個簡單例子來觀察規(guī)律，摸索思路先通過若干個簡單例子來觀察規(guī)律，摸索思路。例如十進制整數(shù) 1234 劃分為 3 段可有如下情形：1 2 34 = 681 23 4 = 9212 3 4 = 144西安郵電大學(xué)

12、計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃算法偽代碼算法偽代碼西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院動態(tài)規(guī)劃動態(tài)規(guī)劃（2）小結(jié)）小結(jié)：本題目相對容易思考，但不少同學(xué)未能做出結(jié)果。測試用例不夠全面是存在的普遍問題。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院算法設(shè)計與分析算法設(shè)計與分析貪心算法貪心算法西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院貪心算法貪心算法基本題基本題 1：程序存儲問題（程序存儲問題（第

13、第 4 版教材版教材 P110 4-5題題）。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院貪心算法貪心算法西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院貪心算法貪心算法【問題分析問題分析】（1）算法原理分析）算法原理分析本題目較為簡單，先對程序長度進行排序，然后用循環(huán)累加排序后的程序長度，并計數(shù)程序個數(shù)。算法偽代碼算法偽代碼略略西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院貪心算法貪心算法（2）小結(jié)）小結(jié)：本題目比較容易，同學(xué)們基本都做出了結(jié)果。但是測試用例不夠全面仍然是老問題。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院貪心算法貪心算法基本題基本題 2：最優(yōu)分解問題（最優(yōu)分解問題（第第 4 版教

14、材版教材 P113 4-15 題題）。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院貪心算法貪心算法西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院貪心算法貪心算法【問題分析問題分析】（1）算法原理分析）算法原理分析對整數(shù)分析可有結(jié)論：若若 a + b = const，則，則 | a b | 越小，越小，a b 越大越大。根據(jù)原問題的描述，需要將正整數(shù)需要將正整數(shù) n 分解為若干互不相同的自然數(shù)的和，同時又要使自然數(shù)的分解為若干互不相同的自然數(shù)的和，同時又要使自然數(shù)的乘積最大乘積最大。當(dāng) n 4 時對 n 的分解的乘積是小于 n 的；當(dāng) n 大于或等于 4 時，n = 1 + ( n 1 ) 因子的

15、乘積也是小于 n 的，所以 n = a + ( n a )，2 a n - 2，可以保證乘積大于 n，即越分解乘積越大。因此可以采用如下貪心策略貪心策略：將將 n 分成從分成從 2 開始的連開始的連續(xù)自然數(shù)的和，如果最后剩下一個數(shù)，將此數(shù)在后項優(yōu)先的方式下均勻地分給前面續(xù)自然數(shù)的和，如果最后剩下一個數(shù)，將此數(shù)在后項優(yōu)先的方式下均勻地分給前面各項各項。該貪心策略首先保證了正整數(shù)所分解出的因子之差的絕對值最小，即該貪心策略首先保證了正整數(shù)所分解出的因子之差的絕對值最小，即 | a b |最小；同時又可以將其分解成盡可能多的因子，且因子的值較大，確保最終所分解最小；同時又可以將其分解成盡可能多的因子

16、，且因子的值較大，確保最終所分解的自然數(shù)的乘積可以取得最大值的自然數(shù)的乘積可以取得最大值。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院貪心算法貪心算法算法偽代碼算法偽代碼西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院貪心算法貪心算法西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院貪心算法貪心算法（2）小結(jié)）小結(jié)：本題目大部分同學(xué)設(shè)計正確，也有部分同學(xué)考慮不夠全面，特別是一些邊界值沒有考慮。測試用例仍然是老問題。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院算法設(shè)計與分析算法設(shè)計與分析回溯法回溯法西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院回溯法回溯法基本題基本題 1：最小重量機器設(shè)計問題（最小重量機器

17、設(shè)計問題（第第 4 版教材版教材 P152 5-3題題）。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院回溯法回溯法西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院回溯法回溯法西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院回溯法回溯法【問題分析問題分析】（1）算法原理分析）算法原理分析算法通過使用回溯來選擇合適的機器使得在總價格不超過 d 時得到的機器重量最小。首先初始化當(dāng)前價格 cp = 0, 當(dāng)前重量 cw = 0。此外還要設(shè)置一個變量 sum 表示選擇機器的總重量，初始化其為每個部件從 1 號供應(yīng)商購買的重量。在循環(huán)選擇 i 號機器時，判斷從 j 號供應(yīng)商購買機器后的價格是否大于總價格，如果不大

18、于則選擇，否則不選，繼續(xù)選擇下一供應(yīng)商進行判斷。在得到一個合適的供應(yīng)商后，繼續(xù)選擇下一機器的供應(yīng)商，從第一個選到最后一個供應(yīng)商。當(dāng)所有機器選擇結(jié)束后，判斷得到的總重量是否比之前的 sum 小，如果小就賦給 sum，然后從這一步開始，回溯到上一機器，選擇下一合適供應(yīng)商，繼續(xù)搜索可行解，直到將整個解空間搜索完畢。這樣，最終得到的 sum 即為最優(yōu)解。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院回溯法回溯法還可以加上一個剪枝條件，即在每次選擇某一機器時，再判斷選擇后的當(dāng)前重量是否已經(jīng)大于之前的 sum，如果大于就沒必要繼續(xù)搜索，因為得到的肯定不是最優(yōu)解。 西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院回溯法回溯法算法偽代碼算法偽代碼西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院回溯法回溯法（2）小結(jié)）小結(jié)：本題目是一道典型的采用回溯法求解的問題，課本上已經(jīng)有通用的求解框架，有很多參考代碼。大部分同學(xué)設(shè)計正確。西安郵電大學(xué)計算機學(xué)院西安郵電大學(xué)計算機學(xué)院回溯法回溯法基本題基本題 2：工作分配問題（工作分配問題（第第 4 版教材版教材 P156