計算機算法設計與分析課程設計(已修改)
2025-06-23 05:28 本頁面
【正文】 用分治法解決快速排序問題及用動態(tài)規(guī)劃法解決最優(yōu)二叉搜索樹問題及用回溯法解決圖的著色問題 一、 課程設計目的： 《計算機算法設計與分析》這門課程是一門實踐性非常強的課程，要求我們能夠?qū)⑺鶎W的算法應用到實際中，靈活解決實際問題。通過這次課程設計，能夠培養(yǎng)我們獨立思考、綜合分析與動手的能力，并能加深對課堂所學理論和概念的理解，可以訓練我們算法設計的思維和培養(yǎng)算法的分析能力。 二、課程設計內(nèi)容： 分治法： （ 2）快速排序； 動態(tài)規(guī)劃： （ 4）最優(yōu)二叉搜索樹； 回溯法： （ 2）圖的著色。 三、概要設計： ? 分治法 — 快速排序： 分治法的基本思想是將一個規(guī)模為 n的問題分解為 k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。 分治法的條件： （ 1) 該問題的規(guī)模縮小到一定的程度就可以容易地解決； （ 2) 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； （ 3) 利用該問題分解出的子問題的解可以合并為該問題的解； （ 4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。 抽象的講，分治法有兩個重要步驟： （ 1） 將問題拆開； 《計算機算法設計與分析》課程設計報告 2 （ 2）將答案合并； ? 動態(tài)規(guī)劃 — 最優(yōu)二叉搜索樹： 動態(tài)規(guī)劃的基本思想是 將問題分解為若干個小問題，解子問題，然后從子問題得到原問題的解。設計動態(tài)規(guī)劃法的步驟： （ 1） 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征； （ 2）遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）； （ 3）以自底向上的方式計算出最優(yōu)值； （ 4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。 ? 回溯法 — 圖的著色 回溯法的基本思想是確定了解空間的組織結(jié)構(gòu)后，回溯法就是從開始節(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始節(jié)點就成為一個活結(jié)點 ，同時也成為當前的擴展結(jié)點。在當前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的或節(jié)點，并成為當前擴展結(jié)點。如果在當前的擴展結(jié)點處不能再向縱深方向移動，則當前的擴展結(jié)點就成為死結(jié)點。換句話說，這個節(jié)點，這個結(jié)點不再是一個活結(jié)點。此時，應往回（回溯）移動至最近一個活結(jié)點處，并使這個活結(jié)點成為當前的擴展結(jié)點?；厮莘匆赃@種工作方式遞歸的在解空間中搜索，直到找到所要求的解或解空間中以無活結(jié)點為止。 四、詳細設計與實現(xiàn)： ? 分治法 — 快速排序 快速排序是基于分治策略的 另 一個排序算法。 其基本 思想是，對于輸入的子數(shù)組 ? ?rpa : ,按 以下三個步驟進行排序 ： （ 1）、 分解 (divide) 以元素 ??pa 為基準元素將 ? ?rpa : 劃分為三段 ? ?1: ?qpa ， ??qa和， ? ?rqa :1? 使得 ? ?1: ?qpa 中任何一個元素都小于 ??qa ， 而 ? ?rqa :1? 中任何一個元素大于等于 ??qa ，下標 q 在劃分 過程中確定。 （ 2）、 遞歸求解 (conquer) 通過遞歸調(diào)用快速排序算法分別對 ? ?1: ?qpa 和 ? ?rqa :1?進行排序。 （ 3）、 合并 (merge) 由于 ? ?1: ?qpa 和 ? ?rqa :1? 的排序都是在原位置進 行的，所以不必進行任何合并操作就已經(jīng)排好序了。 《計算機算法設計與分析》課程設計報告 3 算法實現(xiàn)題 : 現(xiàn)將數(shù)列 {23 21 34 45 65 76 86 46 30 39 89 20 2 3 8 47 38 54 59 40}進行快速排序。 源程序如下： include iostream using namespace std。 define size 20 int partition(int data[],int p,int r) { int n=data[p],i=p+1,j=r,temp。 //將 n 的元素交換到左邊區(qū)域 //將 n 的元素交換到右邊區(qū)域 while(true) { while(data[i]n) +
畢業(yè)設計相關推薦
鄂ICP備17016276號-1