算法設(shè)計與分析期末試題_考試版

1、經(jīng)常采用的算法主要有迭代法、分而 治之法、貪婪法、動態(tài)規(guī)劃法、回溯 法、分支限界法()、用計算機求解問題的步驟：、問題分析、數(shù)學模型建立、算法設(shè) 計與選擇、算法指標、算法分析、算 法實現(xiàn)、程序調(diào)試、結(jié)果整理文檔編 制、算法定義：算法是指在解決問題時, 按照某種機械步驟一定可以得到問題 結(jié)果的處理過程、算法的三要素、操作、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)算法具有以下個屬性：有窮性：一個算法必須總是在執(zhí)行 有窮步之后結(jié)束，且每一步都在有窮 時間內(nèi)完成。確定性：算法中每一條指令必須有 確切的含義。不存在二義性。只有一 個入口和一個出口可行性：一個算法是可行的就是算 法描述的操作是可以通過已經(jīng)實現(xiàn)的 基本運算執(zhí)行有

2、限次來實現(xiàn)的。輸入：一個算法有零個或多個輸入, 這些輸入取自于某個特定對象的集 合。輸出：一個算法有一個或多個輸出， 這些輸出同輸入有著某些特定關(guān)系的 量。算法設(shè)計的質(zhì)量指標：正確性：算法應(yīng)滿足具體問題的 需求；可讀性：算法應(yīng)該好讀，以有利 于讀者對程序的理解；健壯性：算法應(yīng)具有容錯處理， 當輸入為非法數(shù)據(jù)時，算法應(yīng)對其作 出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出 結(jié)果。效率與存儲量需求：效率指的是 算法執(zhí)行的時間；存儲量需求指算法 執(zhí)行過程中所需要的最大存儲空間。 一般這兩者與問題的規(guī)模有關(guān)。迭代法基本思想：迭代法也稱“輾轉(zhuǎn)法”，是 一種不斷用變量的舊值遞推出新值的 解決問題的方法。解題步驟：、確定

3、迭代模型。根據(jù)問題 描述，分析得出前一個(或幾個)值 與其下一個值的迭代關(guān)系數(shù)學模型。、建立迭代關(guān)系式。迭代關(guān)系式就 是一個直接或間接地不斷由舊值遞推 出新值的表達式，存儲新值的變量稱 為迭代變量、對迭代過程進行控制。確定在什 么時候結(jié)束迭代過程，這是編寫迭代 程序必須考慮的問題。不能讓迭代過 程無休止地重復執(zhí)行下去。迭代過程 的控制通常可分為兩種情況：一種是 所需的迭代次數(shù)是個確定的值，可以 計算出來；另一種是所需的迭代次數(shù) 無法確定。對于前一種情況，可以構(gòu) 建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代 過程的控制；對于后一種情況，需要 進一步分析出用來結(jié)束迭代過程的條 件。編寫計算斐波那契()數(shù)列的第

4、項函 數(shù)()0寫成遞歸函數(shù)有：()();();(>)()();一個飼養(yǎng)場引進一只剛出生的新品種 兔子，這種兔子從出生的下一個月開 始，每月新生一只兔子，新生的兔子 也如此繁殖。如果所有的兔子都不死 去，問到第個月時，該飼養(yǎng)場共有兔子多少只？();(<);();分而治之法、基本思想將一個難以直接解決的大問題，分割 成一些規(guī)模較小的相同問題，以便各 個擊破，分而治之。分治法所能解決的問題一般具有以下幾個特征：()該問題的規(guī)?？s小到一定 的程度就可以容易地解決；()該問題可以分解為若干個 規(guī)模較小的相同問題，即該問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì)；()利用該問題分解出的子問題的解可以合并為該問題的

5、解；貪婪法基本思想：以逐步的局部最優(yōu)，達到【問題】背包問題問題描述：有不同價值、不同 重量的物品件，求從這件物品中選取 一部分物品的選擇方案，使選中物品<>()叩叩；("輸入背包容量，物品種類:");("");(<)("輸入物品的重量和價值:");("");口；(<)("");j;()該問題所分解出的各個子 問題是相互獨立的，即子問題之間不 包含公共的子子問題。、分治法的基本步驟()分解：將原問題分解為若干 個規(guī)模較小，相互獨立，與原問題形 式相同的子問題；()解決：若子

6、問題規(guī)模較小而 容易被解決則直接解，否則遞歸地解 各個子問題；()合并：將各個子問題的解合 并為原問題的解。最終的全局最優(yōu)。無后效性的總重量不超過指定的限制重量，但 選中物品的價值之和最大。(<);(<)(>);口；口；(< <);();(<)("");動態(tài)規(guī)劃 基本思想：把求解的問題分成許多階 段或多個子問題，然后按順序求解各 個子問題。前一個子問題的解為后一 個子問題的求解提供了有用的信息。 在求解任何一子問題時，列出各種可 能的局部解，通過決策保留那些有可 能達到最優(yōu)的局部解，丟棄其他局部 解，依次解決各子問題，最后一個子 問題就是

7、問題的解?；静襟E()劃分階段：按照問題的時間或空 問特征，把問題分為若干個階段。注 意這若干個階段一定要是有序的或者 是可排序的(即無后向性)，否則問題 就無法用動態(tài)規(guī)劃求解。()選擇狀態(tài)：將問題發(fā)展到各個階 段時所處于的各種客觀情況用不同的 狀態(tài)表示出來。當然，狀態(tài)的選擇要 滿足無后效性。()確定決策并寫出狀態(tài)轉(zhuǎn)移方程： 之所以把這兩步放在一起，是因為決 策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài) 轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策 來導出本階段的狀態(tài)。所以，如果我 們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫 出來了。但事實上，我們常常是反過 來做，根據(jù)相鄰兩段的各狀態(tài)之間的 關(guān)系來確定決策?；厮莘ɑ舅枷耄喊凑丈疃葍?yōu)先策略，從 根結(jié)點出發(fā)搜索解空間。算法搜索至 解空間的任一結(jié)點時總是先判斷該結(jié) 點是否問題的約束條件。如果滿足進 入該子樹，繼續(xù)按深度優(yōu)先的策略搜 索。否則，不去搜索以該結(jié)點為根的 子樹，而是逐層向其祖先結(jié)點回溯。 其實回溯法就是對隱式圖的深度優(yōu)先 搜索算法基本步驟：1、確定問題的解空間：應(yīng)用回溯法 時，首先應(yīng)明確定義問題的解的空 問。問題的解空間應(yīng)至少包含問題 的一個解。2、確定結(jié)點的擴展規(guī)則3、搜索解空間：從開始結(jié)點出發(fā)，以 深度優(yōu)先的方式搜索整個解空間。【問