計(jì)算機(jī)算法設(shè)計(jì)五大常用算法的分析及實(shí)例(已修改)
2025-07-07 05:16 本頁面
【正文】 摘要算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。其中最常見的五中基本算法是遞歸與分治法、動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界法。本文通過這種算法的分析以及實(shí)例的講解，讓讀者對(duì)算法有更深刻的認(rèn)識(shí)，同時(shí)對(duì)這五種算法有更清楚認(rèn)識(shí)關(guān)鍵詞： 算法， 遞歸與分治法、動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界法 AbstractAlgorithm is thedescription to the problem solving scheme,a set of clear instructions to solve the problem and represents the describe the strategy to solve the problem using the method of system mechanism . That is to say, given some confirm import，the Algorithm will find result In a limited time。If an algorithm is defective or is not suitable for a certain job, it is invalid to execute it. Different algorithms have different need of time or space, and it39。s efficiency are different.There are most mon algorithms: the recursive and divide and conquer、dynamic programming method、greedy algorithm、backtracking、branch and bound to analyze the five algorithms and explain examples, make readers know more about algorithm , and understand the five algorithms more deeply.Keywords: Algorithm, the recursive and divide and conquer, dynamic programming method, greedy algorithm、backtracking, branch and bound method 目錄1. 前言 4 論文背景 42. 算法詳解 5 算法與程序 5 表達(dá)算法的抽象機(jī)制 5 算法復(fù)雜性分析 53．五中常用算法的詳解及實(shí)例 6 遞歸與分治策略 6 遞歸與分治策略基本思想 6 實(shí)例——棋盤覆蓋 7 動(dòng)態(tài)規(guī)劃 8 動(dòng)態(tài)規(guī)劃基本思想 8 動(dòng)態(tài)規(guī)劃算法的基本步驟 9 實(shí)例——矩陣連乘 9 貪心算法 11 貪心算法基本思想 11 貪心算法和動(dòng)態(tài)規(guī)劃的區(qū)別 12 用貪心算法解背包問題的基本步驟： 12 回溯發(fā) 13 回溯法基本思想 13 回溯發(fā)解題基本步驟 13 實(shí)例——01背包問題 14 分支限界法 15 分支限界法思想 15 實(shí)例——裝載問題 16總結(jié) 18參考文獻(xiàn) 18 1. 前言 論文背景 算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。算法中的指令描述的是一個(gè)計(jì)算，當(dāng)其運(yùn)行時(shí)能從一個(gè)初始狀態(tài)和（可能為空的）初始輸入開始，經(jīng)過一系列有限而清晰定義的狀態(tài)，最終產(chǎn)生輸出并停止于一個(gè)終態(tài)。一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)移不一定是確定的。隨機(jī)化算法在內(nèi)的一些算法，包含了一些隨機(jī)輸入。計(jì)算機(jī)的有限資源促使人們關(guān)注程序的執(zhí)行性能，進(jìn)而催生了計(jì)算機(jī)算法這一研究領(lǐng)域。自上世紀(jì)60年代開始至今，已出現(xiàn)了大量解決不同問題的有效算法。由于屬于同一問題類的不同問題之間具有相似性，其解決算法也具有一定的共性，因此產(chǎn)生了一般的算法設(shè)計(jì)技術(shù)，如遞歸技術(shù)、分治、動(dòng)態(tài)規(guī)劃、貪心、圖的遍歷、回溯、分支限界等。掌握算法、分析算法、將算法應(yīng)用到其他領(lǐng)域、創(chuàng)造更高效的算法，是對(duì)每一個(gè)計(jì)算機(jī)學(xué)著的基本要求。本文主要分析五中常用的算法（遞歸與分治法、動(dòng)態(tài)規(guī)劃、貪心算法、回溯發(fā)、分支限界發(fā)），以及對(duì)相應(yīng)算法的實(shí)例詳細(xì)講解。通過對(duì)五中常用算法的單獨(dú)講解、綜合對(duì)比，分析出各種算法的特點(diǎn)以及適用領(lǐng)域，最后列舉相應(yīng)的算法實(shí)例，讓讀者對(duì)這五中常用算法有更深的了解。2. 算法詳解 算法與程序算法：是滿足下述
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1