計(jì)算機(jī)算法設(shè)計(jì)與分析課程設(shè)計(jì)(存儲(chǔ)版)
【正文】 int s[20][20],S[20]。 for(i=0。 cout最優(yōu)值即平均步長(zhǎng)為： m[1][n]endl。給定圖 ? ?EVG ,? 和 m種顏色，如果這個(gè)圖不是 m可著色，則給出否定答案；如果這個(gè)圖是 m可著色的，找出所有不同的著色方法 下面根據(jù)回朔法的遞歸描述框架 Backtrack 設(shè)計(jì)圖的 m 著色算法。 《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告 10 在下面的解圖的 m 可著色問題的回溯法中， ??iBacktrack 搜索解空間中第 i 層子樹。 int n。j=n。i=n。 //把 t+1 結(jié)點(diǎn)的顏色換一種 } } } long mColoring(int mm) { m=mm。 for(i=1。 coutendl。 。 mColoring(m)。 cinnm。 if(Ok(t)) { Backtrack(t+1)。 cout 第 sum種解決方案為 ： \n。 //用于存儲(chǔ)當(dāng)前解 long sum。要求： G中每條 邊的 2個(gè)頂點(diǎn)著有不同的顏色。解空間樹的第? ?nii ??1 層中每一結(jié)點(diǎn)都有 m 個(gè)兒子，每個(gè)兒子相應(yīng)于 ??ix 的 m 個(gè)可能的著色之一。求一個(gè)圖的色數(shù) m的問題稱為圖的 m可著色優(yōu)化問題。i++) cinb[i]。i++) cinS[i]。 } } int main() { //主函數(shù) int n,i。 } void print(int i,int j,int s[][20],int S[]) //遞歸輸出結(jié)果 { if(j=i){ 《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告 8 int k=s[i][j]。 if(tm[i][j]) { //以 k為根節(jié)點(diǎn)，左子樹不為空 m[i][j]=t。i=nr。 float t。同理可證 rT 也是一棵最優(yōu)二叉搜索樹。 最優(yōu)子結(jié)構(gòu)性質(zhì)： 二叉搜索樹 T 的一棵含有結(jié)點(diǎn) ji xx ,? 和葉結(jié)點(diǎn) ? ? ? ?11 , ?? jjii xxxx ? 的子樹可以看作是有序集 ? ?ji xx ,? 關(guān)于全集合 ? ?11 , ?? ji xx ? 的一棵二叉搜索樹，其存取概率為以下的條件概率： ? ?jkiwbb ijkk ??? / ? ?jhiwaa ijhh ???? 1/ 《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告 6 式中， njiabbaw jjiiij ???????? ? 1,1 ?。 設(shè)在第 (1)中情形中找到元素 ixx? 的概率為 ib ；在第 (2)種情形中確定 ? ?1, ?? ii xxx 的概率為 ia 。in。 printf(請(qǐng)輸入要排列的數(shù)列： \n)。 } void quick_sort(int data[],int p,int r) { if(p=r) return。 while(data[j]n) j。 四、詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)： ? 分治法 — 快速排序 快速排序是基于分治策略的 另 一個(gè)排序算法。 ? 回溯法 — 圖的著色 回溯法的基本思想是確定了解空間的組織結(jié)構(gòu)后，回溯法就是從開始節(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。用分治法解決快速排序問題及用動(dòng)態(tài)規(guī)劃法解決最優(yōu)二叉搜索樹問題及用回溯法解決圖的著色問題 一、 課程設(shè)計(jì)目的： 《計(jì)算機(jī)算法設(shè)計(jì)與分析》這門課程是一門實(shí)踐性非常強(qiáng)的課程，要求我們能夠?qū)⑺鶎W(xué)的算法應(yīng)用到實(shí)際中，靈活解決實(shí)際問題。設(shè)計(jì)動(dòng)態(tài)規(guī)劃法的步驟： （ 1） 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1