【文章內(nèi)容簡介】 left,i,right)。//合并到數(shù)組bCopy(a,b, left,right )。 //復(fù)制到數(shù)組a}} 以下是計(jì)算xm的值的過程int power ( x, m ){//計(jì)算xm的值并返回。y=( 1 )。i=m。While(i 0) y=y*x。 (return y)}四、問答題：問題分析數(shù)學(xué)模型建立算法設(shè)計(jì)與選擇算法指標(biāo)算法分析算法實(shí)現(xiàn)程序調(diào)試結(jié)果整理文檔編制2. 算法定義：算法是指在解決問題時，按照某種機(jī)械步驟一定可以得到問題結(jié)果的處理過程操作控制結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)4. 算法具有以下5個屬性：　　有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成?！　〈_定性：算法中每一條指令必須有確切的含義。不存在二義性。只有一個入口和一個出口　　可行性：一個算法是可行的就是算法描述的操作是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的?！　≥斎耄阂粋€算法有零個或多個輸入，這些輸入取自于某個特定對象的集合。　　輸出：一個算法有一個或多個輸出，這些輸出同輸入有著某些特定關(guān)系的量。5. 算法設(shè)計(jì)的質(zhì)量指標(biāo)：　　正確性：算法應(yīng)滿足具體問題的需求；　　可讀性：算法應(yīng)該好讀，以有利于讀者對程序的理解；　　健壯性：算法應(yīng)具有容錯處理，當(dāng)輸入為非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果?！　⌒逝c存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般這兩者與問題的規(guī)模有關(guān)。經(jīng)常采用的算法主要有迭代法、分治法、貪婪法、動態(tài)規(guī)劃法、回溯法、分支限界法6. 迭代法: 也稱“輾轉(zhuǎn)法”，是一種不斷用變量的舊值遞推出新值的解決問題的方法。，需要做好以下三個方面的工作：　　1)、確定迭代模型。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量?！　?)、建立迭代關(guān)系式。所謂迭代關(guān)系式，指如何從變量的前一個值推出其下一個值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來完成。3)、對迭代過程進(jìn)行控制。在什么時候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數(shù)是個確定的值，可以計(jì)算出來；另一種是所需的迭代次數(shù)無法確定。對于前一種情況，可以構(gòu)建一個固定次數(shù)的循環(huán)來實(shí)現(xiàn)對迭代過程的控制；對于后一種情況，需要進(jìn)一步分析出用來結(jié)束迭代過程的條件。：將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。： （1）該問題的規(guī)?？s小到一定的程度就可以容易地解決； （2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； （3）利用該問題分解出的子問題的解可以合并為該問題的解； （4）該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。 分治法的基本步驟 分治法在每一層遞歸上都有三個步驟： （1）分解：將原問題分解為若干個規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題； （2）解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題； （3）合并：將各個子問題的解合并為原問題的解。11. 動態(tài)規(guī)劃的基本思想前文主要介紹了動態(tài)規(guī)劃的一些理論依據(jù)，我們將前文所說的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動態(tài)規(guī)劃稱為標(biāo)準(zhǔn)動態(tài)規(guī)劃，這種標(biāo)準(zhǔn)動態(tài)規(guī)劃是在研究多階段決策問題時推導(dǎo)出來的，具有嚴(yán)格的數(shù)學(xué)形式，適合用于理論上的分析。在實(shí)際應(yīng)用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。由此可知，動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實(shí)例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解。貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨(dú)立的（即不包含公共的子問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。不足之處：如果當(dāng)前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)（最大或最小）值的解。若存在若干個取最優(yōu)值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同的是，動態(tài)規(guī)劃允許這些子問題不獨(dú)立，（亦即各子問題可包含公共的子問題）也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結(jié)果保存起來，避免每次碰到時都要重復(fù)計(jì)算。因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動態(tài)規(guī)劃法的關(guān)鍵就在于，對于重復(fù)出現(xiàn)的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。1動態(tài)規(guī)劃算法的基本步驟設(shè)計(jì)一個標(biāo)準(zhǔn)的動態(tài)規(guī)劃算法，通?？砂匆韵聨讉€步驟進(jìn)行：（1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的（即無后向性），否則問題就無法用動態(tài)規(guī)劃求解。 （2）選擇狀態(tài)：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。 （3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但事實(shí)上，我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策。 （4）寫出規(guī)劃方程（包括邊界條件）：動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡單的。動態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會非常簡單。根據(jù)動態(tài)規(guī)劃的基本方程可以直接遞歸計(jì)算最優(yōu)值，但是一般將其改為遞推計(jì)算。實(shí)際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計(jì)動態(tài)規(guī)劃，而是按以下幾個步驟進(jìn)行：（1）分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 （2）遞歸地定義最優(yōu)值。 （3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計(jì)算出最優(yōu)值。 （4）根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。 步驟（1）～（3）是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省略，若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟（4）。此時，在步驟（3）中計(jì)算最優(yōu)值時，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速地構(gòu)造出一個最優(yōu)解。總結(jié)：動態(tài)規(guī)劃實(shí)際上就是最優(yōu)化的問題，是指將原問題的大實(shí)例等價于同一最優(yōu)化問題的較小實(shí)例，自底向上的求解最小實(shí)例，并將所求解存放起來，存放的結(jié)果就是為了準(zhǔn)備數(shù)據(jù)。與遞歸相比，遞歸是不斷的調(diào)用子程序求解，是自頂向下的調(diào)用和求解。13. 分治法與動態(tài)規(guī)劃法的相同點(diǎn)是：將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。兩者的不同點(diǎn)是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨(dú)立的。14. 回溯法 回溯法也稱為試探法，該方法首先暫時放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時，就選擇下一個候選解；倘若當(dāng)前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當(dāng)前候選解，尋找下一個候選解的過程稱為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。15. 分支限界法：這是一種用于求解組合優(yōu)化問題的排除非解的搜索算法。類似于回溯法，分枝定界法在搜索解空間時，也經(jīng)常使用樹形結(jié)構(gòu)來組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費(fèi)方法來搜索這些樹。因此，可以很容易比較回溯法與分枝定界法的異同。相對而言，分枝定界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時，回溯法成功的可能性更大。 算法思想：分枝限界（branch and bound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對E節(jié)點(diǎn)的擴(kuò)充方式。每個活節(jié)點(diǎn)有且僅有一次機(jī)會變成E節(jié)點(diǎn)。當(dāng)一個節(jié)點(diǎn)變?yōu)镋節(jié)點(diǎn)時，則生成從該節(jié)點(diǎn)移動一步即可到達(dá)的所有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后從表中選擇一個節(jié)點(diǎn)作為下一個E節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動表為空，擴(kuò)充過程才結(jié)束。 有兩種常用的方法可用來選擇下一個E節(jié)點(diǎn)（雖然也可能存在其他的方法）： 1) 先進(jìn)先出（F I F O） 即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的順序與加入節(jié)點(diǎn)的順序相同，因此活 節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。 2) （優(yōu)先隊(duì)列）最小耗費(fèi)或最大收益法在這種模式中，每個節(jié)點(diǎn)都有一個對應(yīng)的耗費(fèi)或收益。如果查找 一個具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小堆來建立，下一個E節(jié)點(diǎn)就是具有最小耗費(fèi) 的活節(jié)點(diǎn)；如果希望搜索一個具有最大收益的解，則可用最大堆來構(gòu)造活節(jié)點(diǎn)表，下一個 E節(jié)點(diǎn)是具有最大收益的活節(jié)點(diǎn)16. 分支限界法與回溯法的相同點(diǎn)是：都是一種在問題的解空間樹T中搜索問題解的算法。不同點(diǎn)：（1）求解目標(biāo)不同； （2）搜索方式不同； （3）對擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同； （4）存儲空間的要求不同。