算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告

1、聲明：此文檔只作為學(xué)習(xí)參考，不得用作它途！ 算法設(shè)計(jì)與分析實(shí)驗(yàn)教學(xué)大綱 實(shí)驗(yàn)學(xué)時(shí)：32 實(shí)驗(yàn)個(gè)數(shù)：7 實(shí)驗(yàn)學(xué)分：1 課程性質(zhì)： 適用專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程 教材及參考書(shū)： 1. 計(jì)算機(jī)算法設(shè)計(jì)與分析，王曉東，北京：電子工業(yè)出版社，2012 2. 算法與數(shù)據(jù)結(jié)構(gòu)，傅清祥等著，北京：電子工業(yè)出版社，2003 3. 計(jì)算機(jī)算法導(dǎo)引設(shè)計(jì)與分析，盧開(kāi)澄著，北京：清華大學(xué)出版社，2001 大綱執(zhí)筆人：劉芳 大綱審定人： 郭濤 一、 實(shí)驗(yàn)課的性質(zhì)與任務(wù) 算法的設(shè)計(jì)與分析是計(jì)算機(jī)科學(xué)的核心問(wèn)題之一，也是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)本科及研究生的一門(mén)重要的專(zhuān)業(yè)基礎(chǔ)課，其內(nèi)容是研究計(jì)算機(jī)領(lǐng)域及其有關(guān)領(lǐng)域中的一些

2、非數(shù)值計(jì)算的常用算法。課程將覆蓋計(jì)算機(jī)軟件實(shí)現(xiàn)中常用的、有代表性的算法，并具有一定的深度和廣度，通過(guò)實(shí)驗(yàn)，使學(xué)生理解并掌握算法設(shè)計(jì)的基本技術(shù)，讓學(xué)生具有針對(duì)所給的問(wèn)題設(shè)計(jì)和實(shí)現(xiàn)高效算法的基本能力。 二、實(shí)驗(yàn)課程目的與要求 計(jì)算機(jī)科學(xué)的一個(gè)核心問(wèn)題是算法理論，本課程介紹非數(shù)值算法設(shè)計(jì)的策略與技 術(shù)，同時(shí)介紹算法的復(fù)雜性的概念通過(guò)對(duì)一些代表性算法的使用達(dá)到了解掌握與運(yùn)用的 目的。 通過(guò)完成課程實(shí)驗(yàn)，使學(xué)生達(dá)到如下要求： 1. 熟悉各種基本常用算法的基本思想、適用范圍，初步掌握算法分析的基本技巧以及如何根據(jù)實(shí)際問(wèn)題設(shè)計(jì)一個(gè)有效的算法。 2. 能對(duì)給定問(wèn)題分析出恰當(dāng)?shù)臄?shù)學(xué)模型，并設(shè)計(jì)出解決方案，將算法

3、用高級(jí)語(yǔ)言 （C，VC+等）編程實(shí)現(xiàn)。 三、實(shí)驗(yàn)項(xiàng)目及內(nèi)容提要 算法設(shè)計(jì)與分析實(shí)驗(yàn)課程 序 實(shí) 實(shí)驗(yàn)名稱(chēng) 學(xué) 必 選 學(xué) 實(shí)驗(yàn)類(lèi)型 內(nèi)容提要 號(hào) 驗(yàn)項(xiàng) 目 編號(hào) 時(shí) 做 做 分 數(shù) 基 本 操 作 驗(yàn) 證 綜合 設(shè) 計(jì) 1 1 算法設(shè)計(jì) 基礎(chǔ) 4 通過(guò)本次實(shí)驗(yàn)，程序 設(shè)計(jì)語(yǔ)言基礎(chǔ)知識(shí)， 熟悉文件操作等 2 2 遞歸與分 治策略及 其應(yīng)用 6 掌握遞歸算法的設(shè) 計(jì)思想，提高應(yīng)用分 治法設(shè)計(jì)算法的技 能 3 3 動(dòng)態(tài)規(guī)劃 及其應(yīng)用 6 掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃 算法的步驟，并編程 實(shí)現(xiàn)有關(guān)算法。 4 4 貪心算法 及其應(yīng)用 6 通過(guò)本次實(shí)驗(yàn)，掌握 設(shè)計(jì)貪心算法的步 驟，并編程實(shí)現(xiàn)有關(guān) 問(wèn)題的求解 54 5

4、 回溯法及 其應(yīng)用 6 通過(guò)本實(shí)驗(yàn)，理解回 溯法的深度搜索策 略，掌握用回溯法解 題的算法框架。 6 6 分支限界 法及其應(yīng) 用 4 通過(guò)本實(shí)驗(yàn)，理解分 支限界法的剪枝搜 索策略，掌握用分支 限界法算法框架 7 7 線(xiàn)性規(guī)劃 問(wèn)題的求 解 4 理解線(xiàn)性規(guī)劃的算 法模型，了解求解線(xiàn) 性規(guī)劃的單純形算 法，學(xué)會(huì)使用 Excel 求解線(xiàn)性規(guī)劃問(wèn)題。 三、實(shí)驗(yàn)內(nèi)容安排： 實(shí)驗(yàn)一 算法設(shè)計(jì)基礎(chǔ) （驗(yàn)證型實(shí)驗(yàn) 4 學(xué)時(shí)） 1.實(shí)驗(yàn)?zāi)康?（1） 鞏固程序設(shè)計(jì)語(yǔ)言基礎(chǔ)知識(shí)，熟悉文件操作等。 （2） 對(duì)給定問(wèn)題，能設(shè)計(jì)算法并編程實(shí)現(xiàn)問(wèn)題的求解，并分析算法的時(shí)間復(fù)雜性。 2.實(shí)驗(yàn)要求 （1） 認(rèn)真填寫(xiě)實(shí)驗(yàn)報(bào)告，附

5、加源代碼（主要代碼）和運(yùn)行記錄； （2） 對(duì)設(shè)計(jì)好的算法，測(cè)試運(yùn)行實(shí)驗(yàn)數(shù)據(jù)，檢查輸出是否正確。并對(duì)算法的時(shí)間和空間復(fù)雜度進(jìn)行分析。 3.實(shí)驗(yàn)內(nèi)容： （1） 統(tǒng)計(jì)數(shù)字問(wèn)題（P8） #include "iostream" #include <stdlib.h> #include <fstream.h> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; int i,n,m; int page;/page 是書(shū)的總頁(yè)

6、數(shù) int number10=0; void main() fin>>page; for (int j=1;j<=page;j+) n=j; while(n) m=n%10; +numberm; n=n/10; for ( i=0;i<=9;i+) fout<<numberi<<endl; fin.close(); fout.close(); return; （2） 字典序問(wèn)題（P8） （3） 最多約數(shù)問(wèn)題（P9） #include "iostream" #include <stdlib.h> #include &

7、lt;fstream.h> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; void main() int a,b,i,j,max; fin>>a>>b; int number100=0;/約數(shù)個(gè)數(shù) for ( i=a;i<=b;i+) for (j=1;j<=i;j+) if( i%j=0) numberi+;/若能被整除則約數(shù)個(gè)數(shù)加 1 for( i=a;i<b;i+) if(numberi>

8、numberi+1) max=numberi; else max=numberi+1; fout<<max<<endl; fin.close(); fout.close(); （4） 最大間隙問(wèn)題（P10） （5） 設(shè)計(jì)算法求解 fibonacci 數(shù)列的第 110 項(xiàng)的值。 （6） 設(shè)計(jì)算法求解盡可能多的完美數(shù)（完全數(shù)） 。 注：至少選擇其中 2 題完成 實(shí)驗(yàn)二 遞歸與分治策略及其應(yīng)用 （驗(yàn)證型、設(shè)計(jì)型實(shí)驗(yàn) 6 學(xué)時(shí)） 1.實(shí)驗(yàn)?zāi)康?（1） 進(jìn)一步掌握遞歸算法的設(shè)計(jì)思想以及遞歸程序的調(diào)試技術(shù)。 （2） 提高應(yīng)用分治法設(shè)計(jì)算法的技能 （3） 理解這樣一個(gè)觀點(diǎn)：分治和遞歸

9、經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)中。 2.實(shí)驗(yàn)要求 （1） 認(rèn)真填寫(xiě)實(shí)驗(yàn)報(bào)告，附加源代碼（主要代碼）和運(yùn)行記錄； （2） 對(duì)設(shè)計(jì)好的算法，要分析算法的時(shí)間和空間復(fù)雜度。 3.實(shí)驗(yàn)內(nèi)容： （1） 設(shè)計(jì)算法求解整數(shù)的劃分問(wèn)題，對(duì)給定的整數(shù)，輸出劃分?jǐn)?shù)。 （P14）并思考如何實(shí)現(xiàn)輸出每個(gè)具體的劃分。 #include "iostream" #include <stdlib.h> using namespace std; int q(int m,int n) if (n<1)|(m<1) return 0; if (n=1)|(m=1)return 1; if (m&

10、lt;n) return q(m,m); if (m=n) return q(m,n-1)+1; return q(m,n-1)+q(m-n,n); void main() int n,m; cout<<"分別輸入 m 和 n 的值(m 為被劃分?jǐn)?shù)，n 為最大加數(shù))"<<endl; cin>>m>>n; cout<<"劃分?jǐn)?shù)為："<<endl; cout<<q(m,n)<<endl; system("pause"); （2） 設(shè)計(jì)算法求解

11、n 個(gè)互異元素的全排列的算法并編程實(shí)現(xiàn)（P13），并在此基礎(chǔ)上修改程序，使其能解決有重復(fù)元素的排列問(wèn)題（P41算法實(shí)現(xiàn)題 2-5）。 #include "iostream" #include <stdlib.h> #include <fstream.h> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; int count=0; int check(char list,int k ,int m ) /判斷是否

12、互異，重復(fù)返回 0 if( m > k) for(int i = k ; i< m ; i+) if( listi = listm ) return 0 ; return 1 ; inline void swap(char &a,char &b) char temp; temp=a;a=b;b=temp; void perm(char list,int k,int m) /依次交換第一個(gè)元素進(jìn)行排序 if(k=m) /只剩下一個(gè)元素 count+; for(int i=0;i<=m;i+) fout<<listi<<" &qu

13、ot; fout<<endl; else /還有多個(gè)元素，遞歸產(chǎn)生排列 for(int i=k;i<=m;i+) if(check(list,k,i) swap(listk,listi); perm(list,k+1,m); swap(listk,listi); return; void main() char number100; int i=0,n=0; /n 是總個(gè)數(shù) fin>>number; /number 數(shù)組為待排元素 while(numberi != '0') n+; i+; perm(number,0,n-1); fout<&

14、lt;count; fin.close(); fout.close(); system("pause"); （3） 設(shè)計(jì)算法求解棋盤(pán)的覆蓋問(wèn)題，并編程實(shí)現(xiàn)（P20）。 （4） 設(shè)計(jì)一個(gè)求解 Gray 碼的分治策略，并編程實(shí)現(xiàn)（P39 算法分析題 2-14）。 （5） 設(shè)計(jì)求解半數(shù)集問(wèn)題的算法，并編程實(shí)現(xiàn)。（P40算法實(shí)現(xiàn)題 2-3） （6） 設(shè)計(jì)求解整數(shù)因子分解問(wèn)題的算法，并編程實(shí)現(xiàn)。 （P43 算法實(shí)現(xiàn)題 2-11） #include "iostream" #include <stdlib.h> #include <fstream.h

15、> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; void main() int number,result; int count=1; fin>>number;/輸入整數(shù) for(int i=2;i<number;i+) if(number%i=0) result=number/i; /result 是因子 for(int i=2;i<=result;i+) if(result%i=0) count+; fout&l

16、t;<count; fin.close(); fout.close(); （7） 設(shè)計(jì)求解雙色 hanoi 問(wèn)題的算法，并編程實(shí)現(xiàn)。 （P43 算法實(shí)現(xiàn)題 2-11） 注：至少選擇其中 3 題完成 實(shí)驗(yàn)三 動(dòng)態(tài)規(guī)劃及其應(yīng)用 （驗(yàn)證型、設(shè)計(jì)型實(shí)驗(yàn) 6 學(xué)時(shí)） 1.目的要求 （1） 理解動(dòng)態(tài)規(guī)劃算法的概念和基本要素，并能和分治法進(jìn)行比較。 （2） 掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟，并編程實(shí)現(xiàn)有關(guān)算法。 （3） 理解這樣一個(gè)觀點(diǎn)：同樣的問(wèn)題可以用不同的方法解決，一個(gè)好的算法是反復(fù)努力和重新修正的結(jié)果。 （4） 對(duì)設(shè)計(jì)好的算法，要分析算法的時(shí)間和空間復(fù)雜度。 2.實(shí)驗(yàn)內(nèi)容 （1） 編程實(shí)現(xiàn)矩陣連乘問(wèn)題

17、的求解。 （P47） （2） 分別采用分治法和動(dòng)態(tài)規(guī)劃法求解實(shí)現(xiàn)最大子段和問(wèn)題，并編程實(shí)現(xiàn)。（P54） #include "iostream" #include <stdlib.h> using namespace std; int MaxSubSum(int *a,int left,int right) /最大子段和 分治法 int sum=0; if(left=right) sum=aleft>0 ? aleft :0; else int center=(left+right)/2; int leftsum=MaxSubSum(a,left,cente

18、r); int rightsum=MaxSubSum(a,center+1,right); int s1=0; int lefts=0; for(int i=center;i>=left;i-) lefts+=ai; if(lefts>s1) s1=lefts; int s2=0; int rights=0; for( i=center+1;i<right;i+) rights+=ai; if(right>s2)s2=rights; sum=s1+s2; if(sum<leftsum)sum=leftsum; if(sum<rightsum)sum=righ

19、tsum; return sum; int MaxSumDongtai(int n,int *a) /最大子段和 動(dòng)態(tài)規(guī)劃法 /n 表示前 n 個(gè)數(shù)字 int sum=0,b=0; for(int i=1;i<=n;i+) if(b>0) b+=ai; else b=ai; if(b>sum) sum=b; return sum; void main() int a=0,1,2,3,4,5,6,7; int n; cout<<MaxSubSum(a,0,7)<<endl; cout<<MaxSumDongtai(7,a)<<en

20、dl; return; （3） 編程實(shí)現(xiàn)最長(zhǎng)公共子序列(LCS)問(wèn)題的求解。 （P52） （4） 編程實(shí)現(xiàn) 01 背包問(wèn)題的求解。 （P71） #include <stdlib.h> #include "iostream" #include <stdio.h> using namespace std; #define max(a,b) (a) > (b) ? (a) : (b) /max(a,b) a,b 中的最大值 #define min(a,b) (a) < (b) ? (a) : (b) /min(a,b) a,b 中的最小值 te

21、mplate <typename Type> void Knapsack(Type* v, int *w, int c, int n, Type *m) /遞歸初始條件 /v 價(jià)值,w 重量,c 容量,n 件數(shù),m 價(jià)值數(shù) int jMax = min(wn - 1, c); for (int j=0; j<=jMax; j+) /背包的重量 mnj = 0; for (j=wn; j<=c; j+) /背包的價(jià)值 mnj = vn; /m(i,j) 背包容量為 j，可選擇物品為 i,i+1n 時(shí) 0-1 背包的最優(yōu)值 for (int i=n-1; i>1; i

22、-) jMax = min(wi - 1, c); for (int j=0; j<=jMax; j+) mij = mi+1j; for (j=wi; j<=c; j+) mij = max(mi+1j, mi+1j-wi+vi); m1c = m2c; if (c >= w1) m1c = max(m1c, m2c-w1+v1); cout<<m1c<<endl; template <typename Type> void TraceBack(Type *m, int *w, int c, int n, int* x) /物品裝入 xi

23、為 1，反之為 0；背包容量 c 減少當(dāng)前裝入物品的重量 for (int i=1; i<n; i+) if(mic = mi+1c) xi = 0; else xi = 1; c -= wi; xn = (mnc)? 1:0; void main(int argc, char* argv) int n = 6,c = 20,x7; /n 個(gè)物品，用 x7來(lái)記錄每個(gè)物品是否裝入，c 背包容量 int w7 = -2, 5, 10, 9, 5, 2, 1; /每個(gè)物品的重量 int v7 = -1, 6, 3, -4, 4, 6, 0; /每個(gè)物品的價(jià)值 int *ppm = new in

24、t*n+1; for (int i=0; i<n+1; i+) ppmi = new intc+1; Knapsack<int>(v, w, c, n, ppm); TraceBack<int>(ppm, w, c, n, x); for ( i=1; i<=n; i+) cout<<xi; return; （5） 設(shè)計(jì)一個(gè) O(n2)時(shí)間的算法，找出由 n 個(gè)數(shù)組成的序列的最長(zhǎng)單調(diào)遞增子序列。（P87 算法分析題 3-1） （6） 設(shè)計(jì)算法求解獨(dú)立任務(wù)最優(yōu)調(diào)度問(wèn)題，并編程實(shí)現(xiàn)。 （P79算法實(shí)現(xiàn)題 3-1） （7） 設(shè)計(jì)算法求解石子合并問(wèn)題編程

25、實(shí)現(xiàn)。（P79 實(shí)現(xiàn)題 3-3） （8） 設(shè)計(jì)算法求解數(shù)字三角形問(wèn)題，并編程實(shí)現(xiàn)。 （P80題 3-4） #include <stdio.h> void main() int a100100; int i,j,n; printf("輸入行數(shù)：") ; scanf("%d",&n) ; for(i = 1 ; i <= n ; i + ) printf("輸入第%d 行數(shù)：n",i); for( j =1 ;j <= i; j+) scanf("%d",&aij ) ; for

26、(i = n-1;i>0;i-) for(j = i;j>0;j-) aij += ai+1j+1 > ai+1j?ai+1j+1 : ai+1j; /aij選 ai+1j+1,ai+1j中最大的 printf("最大路徑和是：%dn",a11 ) ; return; （9） 設(shè)計(jì)算法求解最小 m 段和問(wèn)題，并編程實(shí)現(xiàn)。 （P81題 3-8） （10） 設(shè)計(jì)算法求解最少費(fèi)用購(gòu)物問(wèn)題，并編程實(shí)現(xiàn)。（P88 算法實(shí)現(xiàn)題 3-14） 注：至少選擇其中 3 題完成。 3.主要儀器設(shè)備及軟件 （1） PC 機(jī) （2） TC、VC+、Java 等任一編程語(yǔ)言 實(shí)驗(yàn)四

27、貪心算法及其應(yīng)用 （驗(yàn)證型、設(shè)計(jì)型實(shí)驗(yàn) 6 學(xué)時(shí)） 1.目的要求： （1） 理解貪心算法的概念和基本要素； （2） 掌握設(shè)計(jì)貪心算法的步驟，并編程實(shí)現(xiàn)有關(guān)問(wèn)題的求解。 2.實(shí)驗(yàn)內(nèi)容： （1） 編程實(shí)現(xiàn)活動(dòng)安排問(wèn)題的求解。 （P91） void sort(int f,int n) /結(jié)束時(shí)間 f排序 int temp; for(int i=1;i<n;i+) for(int j=0;j<i;j+) if(fj>fj+1) /結(jié)束時(shí)間按從早到晚排序 temp=fj; fj=fj+1; fj+1=temp; cout<<"排序結(jié)果："<<

28、endl; for(int i=0;i<n;i+) cout<<fi<<" " int greedySelector(int s, int f, bool A) /活動(dòng)安排算法 int n=s.length-1,j=1,count=1; A1=true; for(int i=2;i<=n;i+) if(si>=fj) /若下一活動(dòng)開(kāi)始時(shí)間晚于上一活動(dòng)，則下一活動(dòng)可安排，活動(dòng)數(shù)count 加 1 Ai=true; j=i; count+; else Ai=false; return count; （2） 設(shè)計(jì)算法求解會(huì)場(chǎng)安排問(wèn)題，并編

29、程實(shí)現(xiàn)。（P108，算法實(shí)現(xiàn)題 4-1）。 （3） 編程實(shí)現(xiàn)最優(yōu)裝載問(wèn)題的求解。 （P95） #include "iostream.h" void sort(int *w,int *t,int n) /按照 weight 的升序進(jìn)行排序 t for(int i=0;i <=n;i+) int minweight=w0;/最小值 for(int j=i;j <=n;j+) int temp=j; for(int k=i;k <=j;k+) if(wk <wtemp) minweight=wk; temp=k; tj=temp; void loadlin

30、g(int x,int w,int c,int n) int *t=new intn+1;/指向物品的序號(hào) sort(w,t,n); for(int i=1;i <=n;i+) xi=0; for(i=1;i<=n&&wti<=c;i+) xti=1; c-=wi; cout<<"輸出所裝載的物品序列號(hào)以及它的重量為：" <<ti<<" "<<wi<<endl; void main() int n,c; cout<<"請(qǐng)輸入要裝載物品的數(shù)量

31、"<<endl; cin>>n; int *w=new intn+1;/指向物品的重量 int *x=new intn+1; for(int i=1;i <=n;i+) xi=0; cout<<"請(qǐng)輸入該所能夠裝載的最大重量："<<endl; cin>>c; cout<<"請(qǐng)輸入裝載的物品的重量"<<endl; for( i=1;i<n+1;i+) cin>>wi; loadling(x,w,c,n); return; （4） 編程實(shí)現(xiàn)背

32、包問(wèn)題的求解。 （P94） void Sort(int n,float v,float w) /按單位價(jià)值為物品排序 float l = v/w+v%w; void bubblesort(sqlist &l) /冒泡排序 int lastexchangeindex; int i,j; RcdType temp20; i=l.length; while(i>1) lastexchangeindex=1; for(j=1;j<l.length;j+) if(l.rj+1.key<l.rj.key) tempj=l.rj; l.rj=l.rj+1; l.rj+1=tempj

33、; lastexchangeindex=j; i=lastexchangeindex; void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; float c = M; for(i = 1;i <= n;i+) xi = 0; /初始化 xi for(i = 1;i <= n;i+) if(wi>c) break; xi = 1; c-=wi; if(i<=n) xi = c/wi; return; （5） 編程實(shí)現(xiàn)多機(jī)調(diào)度問(wèn)題的求解。 （P106） （6） 設(shè)計(jì)算法求解汽車(chē)加油問(wèn)

34、題，并編程實(shí)現(xiàn)。（P111，算法實(shí)現(xiàn)題 49）； #include <stdio.h> void greedy(int d,int n,int k) int num = 0; /加油次數(shù) for(int i = 0;i <= k;i+) /若加油站距離大于最大行駛距離，則無(wú)解 if(di > n) printf("No Solutionn"); return; int s = 0; for(i = 0;i <=k;i+) /若下站與下下站距離之和大于最大行駛數(shù)，則加油，反之不加 s += di; if(s > n) num+; s = d

35、i; printf("%dn",num); void main() int i,n,k,d1000; /最多行駛 n 千米，k 個(gè)加油站，每個(gè)加油站距離 d; printf("請(qǐng)輸入汽車(chē)加滿(mǎn)油最大行駛距離n"); scanf("%d",&n); printf("請(qǐng)輸入加油站個(gè)數(shù)n"); scanf("%d",&k); printf("請(qǐng)依次輸入每個(gè)加油站距上一站距離n"); for(i = 0;i <= k;i+) scanf("%d"

36、;,&di); greedy(d,n,k); return; （7） 設(shè)計(jì)算法求解刪數(shù)問(wèn)題，并編程實(shí)現(xiàn)。（P112，算法實(shí)現(xiàn)題 4-11）； （8） 設(shè)計(jì)算法求解數(shù)列級(jí)差問(wèn)題，并編程實(shí)現(xiàn)。 注：至少選擇其中 3 題完成。 3.主要儀器設(shè)備及軟件 （1） PC 機(jī) （2） TC、VC+、Java 等任一編程語(yǔ)言 實(shí)驗(yàn)五 回溯法及其應(yīng)用 （驗(yàn)證型、設(shè)計(jì)型實(shí)驗(yàn) 6 學(xué)時(shí)） 1.目的要求： （1） 理解回溯法的深度搜索策略，掌握用回溯法解題的算法框架； （2） 掌握設(shè)計(jì)回溯算法的基本技巧和實(shí)際問(wèn)題的分析求解。 2.實(shí)驗(yàn)內(nèi)容： （1） 設(shè)計(jì)算法從前 m 個(gè)大寫(xiě)字母(m26)種取出 n 個(gè)字母的所

37、有排列（組合），并編程實(shí)現(xiàn)。 （2） 設(shè)計(jì)算法求解子集合問(wèn)題，并編程實(shí)現(xiàn)。 （P151，算法實(shí)現(xiàn)題 5-1） （3） 設(shè)計(jì)算法求解工作分配問(wèn)題，并編程實(shí)現(xiàn)。（P156，算法實(shí)現(xiàn)題 5-13） （4） 設(shè)計(jì)算法實(shí)現(xiàn) 01 背包問(wèn)題，并編程實(shí)現(xiàn)。（P159，算法實(shí)現(xiàn)題 5-22） （關(guān)鍵代碼） /*0-1 背包改進(jìn)算法*/ int bestp;/最優(yōu)結(jié)果 /*限界函數(shù)*/ int bound(int i,int cw,int cp) cw+=xi*wi; cp+=xi*pi; int cleft=c-cw; int b=cp; for(int j=i+1;j<=n&&wj&l

38、t;=cleft;j+) b+=pj; cleft-=wj; if(j<n) b+=pj*(cleft)/wj; return b; bool check(int i,int cw,int cp) if(cw+xi*wi>c)|(bound(i,cw,cp)<bestp) return false; else return true; void output(int i) cout<<i; /*功能函數(shù)*/ void tryload(int i;int cw;int cp) /cw 當(dāng)前背包容量,cp 當(dāng)前背包價(jià)值 if(i>n) /輸出一個(gè)可行解 outp

39、ut(i); else for(int j=1;j>=0;j-) xi=j; if(check(i,cw,cp) cw+=xi*wi; cp+=xi*pi; tryload(i+1,cw,cp); cw-=xi*wi; cp-=xi*pi; /*主函數(shù)*/ void main() tryload(1,0,0); （5） 設(shè)計(jì)算法求解旅行售貨員問(wèn)題，并編程實(shí)現(xiàn)。 （P139） 關(guān)鍵代碼 #include "iostream.h" #include "stdlib.h" #define noedge 10000 int n,*bestx,*a,best

40、c; /頂點(diǎn)數(shù),最優(yōu)解，G 的鄰接矩陣，最優(yōu)值 /*主函數(shù)*/ void main() getdata(); bestc=noedge; for(int i=1;i<=n;i+) bestxi = xi = i; traveling(2,0); cout<<bestc; for(int i=1;i<=n;i+) cout<<bestxi; /*約束、限界函數(shù)*/ bool check(int i,int cc) if(axi-1xi != noedge && cc+axi-1xi < bestc) return true; else r

41、eturn false; /*功能函數(shù)*/ bool traveling(int i;int cc) if(i>n) else for(int j=i;j<=n;j+) swap(xi,xj); if(check(i,cc) cc+=axi-1xi; traveling(i+1,cc); cc-=axi-1xi; swap(xi,xj); if(axn1!=noedge) for(int k=1;k<=n;k+) cout<<xk; cc+=axnx1; cour<<cc; （6） 設(shè)計(jì)算法求解 n 后問(wèn)題，并編程實(shí)現(xiàn)。（P129） #include

42、"stdio.h" #include "stdlib.h" #include "math.h" #include "iostream" using namespace std; int n;/皇后個(gè)數(shù) int *x; int count=0; bool check(int i) for(int k=1;k<i;k+) if(xk=xi)|fabs(xk-xi)=fabs(k-i) return false; else return true; void output(int i) cout<<i;

43、 int queue(int i) if(i>n) output(i); return 0; else for(int j=1;j<=n;j+) xi=j; if(check(i) i+; count+; return queue(i+1); void main() cout<<"請(qǐng)輸入皇后個(gè)數(shù)："<<endl; cin>>n; x=new intn+1; queue(1); cout<<"可行方案有"<<count<<"種"<<endl;

44、 （7） 設(shè)計(jì)算法完成圖的 m 著色問(wèn)題，并編程實(shí)現(xiàn)。 （P137） 關(guān)鍵代碼 #include "iostream.h" #include "stdlib.h" void main() getdata(); count=0; trycolor(1); cout<<endl<<" " void trycolor(int i) if(i>n) output(); else for(int j=1;j<=m;j+) xi = j; if(check(i) trycolor(i+1); bool chec

45、k(int i) for(int k=1;k<=i+1;i+) if(aki) = 1 && (xk = xi) return false; return true; （8） 設(shè)計(jì)算法用 L 形覆蓋一個(gè)正方塊組成的正方形，要求不重不漏(若邊長(zhǎng)不剛好，還需要挖掉 1 塊)。 （9） 設(shè)計(jì)算法求解最佳調(diào)度問(wèn)題，并編程實(shí)現(xiàn)。（P156，算法實(shí)現(xiàn)題 5-15） （11） 設(shè)計(jì)算法求解無(wú)優(yōu)先級(jí)運(yùn)算問(wèn)題，并編程實(shí)現(xiàn)。（P156，算法實(shí)現(xiàn)題 5-16） 注：至少選擇其中 3 題完成。 3.主要儀器設(shè)備及軟件 （1） PC 機(jī) （2） TC、VC+、Java 等任一編程語(yǔ)言 實(shí)驗(yàn)六 分支

46、限界法及其應(yīng)用 （ 驗(yàn)證型、設(shè)計(jì)型實(shí)驗(yàn) 4 學(xué)時(shí)） 1.目的要求 （1） 理解分支限界法的基本思想和剪枝搜索策略； （2） 掌握設(shè)計(jì)分支限界法的基本技巧和實(shí)際問(wèn)題的分析求解。 2.實(shí)驗(yàn)內(nèi)容： （1） 編程實(shí)現(xiàn) 0/1 背包問(wèn)題的隊(duì)列式/優(yōu)先隊(duì)列式分支限界算法； （2） 編程實(shí)現(xiàn)隊(duì)列式/優(yōu)先隊(duì)列式分支限界算法求解旅行商問(wèn)題的求解。 #include <stdio.h> template<class Type> class Traveling friend void main(void); public: Type BBTSP(int v); private: int n;

47、 /圖 G 的頂點(diǎn)數(shù) Type *a, /圖 G 的鄰接矩陣 NoEdge, /圖 G 的無(wú)邊標(biāo)志 cc, /當(dāng)前費(fèi)用 bestc; /當(dāng)前最小費(fèi)用 ; template<class Type> class MinHeapNode friend Traveling<Type> public: operator Type()const return lcost; private: Type lcost, /子樹(shù)費(fèi)用的下界 cc, /當(dāng)前費(fèi)用 rcost, /xs:n-1中頂點(diǎn)最小出邊費(fèi)用和 int s, /根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑為 x0:s *x; /需要進(jìn)一步搜索的頂點(diǎn)

48、是 xs+1:n-1 template<class Type> Type Traveling<Type>:BBTSP(int v) /旅行收貨商問(wèn)題的優(yōu)先隊(duì)列式分支限界法 /定義最小堆的容量為 1000 MinHeap<MinHeapNode<Type>>H(1000); Type *MinOut = new Typen+1; /計(jì)算 MinOuti = 頂點(diǎn) i 的最小出邊費(fèi)用 Type MinSum = 0;/最小出邊費(fèi)用和 for(int i=1;i<=n;i+) Type Min = NoEdge; for(int j=1;j<=n;j+) if(aij!=NoEdge && (aij<Mi