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

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告目錄實(shí)驗(yàn)一：遞歸與分治1 二分查找 歸并排序 快速排序?qū)嶒?yàn)二：回溯算法8 01背包實(shí)驗(yàn)三：動(dòng)態(tài)規(guī)劃12 矩陣連乘最少乘法數(shù)實(shí)驗(yàn)一：遞歸與分治一、實(shí)驗(yàn)?zāi)康睦斫膺f歸算法的思想和遞歸程序的執(zhí)行過程，并能熟練編寫遞歸程序。掌握分治算法的思想，對(duì)給定的問題能設(shè)計(jì)出分治算法予以解決。二、實(shí)驗(yàn)內(nèi)容1 二分查找在對(duì)線性表的操作中，經(jīng)常需要查找某一個(gè)元素在線性表中的位置。此問題的輸入是待查元素x和線性表L，輸出為x在L中的位置或者x不在L中的信息。2 合并排序3 快速排序?qū)Ρ緦?shí)驗(yàn)中的問題，設(shè)計(jì)出算法并編程實(shí)現(xiàn)。實(shí)驗(yàn)總結(jié)及思考3、 實(shí)驗(yàn)過程1. 二分查找算法：BinSearch(aArray

2、0,1n-1,key) low<-0; right<-n-1; while low<=right do m<-(low+(right-low)/2; if key>aArraymid l<-mid+1; if key<aArraymid r<-mid-1; if key=aArraymid return mid; 代碼：#include <iostream>using namespace std;void Binary(int aArray,int key,int length) /二分查找 int mid,low,high; mid

3、=low=0; high=length-1; while(low<=high) mid = low + (high - low)/2); /使用 (low + high) / 2 會(huì)有整數(shù)溢出的問題 if(low<0|high>=length|high - low=0) cout<<"元素不存在，查找失敗"<<endl; if(key>aArraymid) /key在右邊 low=mid+1; else if(key<aArraymid) /key在左邊 high=mid-1; else cout<<&quo

4、t;查找成功，元素的位置是:"<<mid<<endl; break; int main()int length = 0;int key = 0;cout<<"請(qǐng)輸入數(shù)組的長度："<<endl; cin >> length;int* aArray = new intlength;cout<<"請(qǐng)輸入數(shù)組："<<endl; for (int i = 0; i < length; i+)cin >> aArrayi;cout<<"

5、;請(qǐng)輸入待查找的數(shù)字：" <<endl;cin >> key;Binary(aArray,key,length);delete aArray; /釋放空間 return 0;二分查找的平均時(shí)間復(fù)雜度為O(logn)最壞情況下的時(shí)間復(fù)雜度O(n)運(yùn)行截圖：2. 合并排序基本操作如下: （1）分解:將n 個(gè)元素分成各含n/2 個(gè)元素的子序列 （2）解決:用合并排序法對(duì)兩個(gè)子序列遞歸地排序 （3）合并:合并兩個(gè)已排好序的子序列得到排序結(jié)果 在對(duì)子序列排序時(shí)，其長度為1 時(shí)遞歸結(jié)束。單個(gè)元素被視為是已排好序的。算法：MergeSort(A0n-1)if n>1

6、copy A0n/2-1toB0n/2-1 copy An/2n-1toC0n/2-1 MergeSort(B0n/2-1) MergeSort(C0n/2-1) Merge(B,C,A)Merge(B0p-1,C0q-1,A0P+q-1)i<-0;j<-0;k<-0while i<p and j<q do if Bi<=Cj Ak<-Bi;i<-i+1; else Ak<-Cj;j<-j+1; k<-k+1; if i=p copyCjq-1toAkp+q-1 elsecopyBiq-1toAkp+q-1代碼：#include

7、<iostream>using namespace std;void Merge(int *a, int p, int q, int r)/把數(shù)組a分成L，R，再排序合并成a int n1 = q-p+1;int n2 = r-q;int *L = new intn1+1;int *R = new intn2+1;int i, j, k;for (i=0; i<n1; i+)Li = ap+i;for (j=0; j<n2; j+)Rj = aq+j+1;Ln1 = 10000000;Rn2 = 10000000;for (i=0,j=0,k=p;k<=r;k+)

8、if (Li<=Rj)ak = Li;i+;elseak = Rj;j+;delete L;delete R;void MergeSort(int *a, int p, int r)/遞歸調(diào)用 if (p<r)int q = (p+r)/2;MergeSort(a, p, q);MergeSort(a, q+1, r);Merge(a, p, q, r); int main()int j = 0;cout<<"請(qǐng)輸入數(shù)組的長度："<<endl; cin >> j;int* aArray = new intj;cout<&

9、lt;"請(qǐng)輸入原始數(shù)組："<<endl; for (int i = 0;i < j;i+)cin >> aArrayi;MergeSort(aArray,0,j-1); cout<<"排序后的數(shù)組："<<endl; for (int i = 0;i < j;i+)cout <<aArrayi<<" "delete aArray;/釋放空間 system("pause");return 0;歸并排序的平均時(shí)間復(fù)雜度：O(logn)運(yùn)行

10、截圖：3. 快速排序 實(shí)現(xiàn)快速排序的分治過程如下: （1）分解:數(shù)組Ap.r被劃分為兩個(gè)(可能空)子數(shù)組Ap.q-1和Aq+1.r, 使得 Ap.q-1中的每個(gè)元素都小于等于 A(q),而且，小于等于 Aq+1.r中的 元素。下標(biāo)q 也在這個(gè)劃分過程中進(jìn)行計(jì)算。 （2）解決:通過遞歸調(diào)用快速排序，對(duì)子數(shù)組Ap.q-1和Aq+1.r排序 （3）合并:因?yàn)閮蓚€(gè)子數(shù)組是就地排序的，將它們的合并不需要操作，整個(gè)數(shù)組 Ap.r已排序。代碼：#include<iostream>using namespace std;void quickSort(int s, int l, int r)if (

11、l<r) int i = l, j = r;int x = sl;/找一個(gè)基準(zhǔn)數(shù)while (i < j) while(i < j && sj>= x) / 從右向左找第一個(gè)小于x的數(shù)j-; if(i < j)si+ = sj;while(i < j && si< x) / 從左向右找第一個(gè)大于等于x的數(shù)i+; if(i < j)sj- = si;si = x;quickSort(s, l, i - 1); / 遞歸調(diào)用quickSort(s, i + 1, r);int main()int j = 0;cout&

12、lt;<"請(qǐng)輸入數(shù)組的長度："<<endl; cin >> j;int* aArray = new intj;cout<<"請(qǐng)輸入原始數(shù)組："<<endl; for (int i = 0;i < j;i+)cin >> aArrayi;quickSort(aArray,0,j-1);cout<<"排序后的數(shù)組："<<endl; for (int i = 0;i < j;i+)cout <<aArrayi<<&q

13、uot; "delete aArray;system("pause");return 0;快排的平均時(shí)間復(fù)雜度O(nlogn)最壞情況下的時(shí)間復(fù)雜度為O（n2)運(yùn)行截圖：實(shí)驗(yàn)二：回溯算法1、 實(shí)驗(yàn)?zāi)康?熟練掌握回溯算法2、 基本思想 回溯法在問題的解空間樹中，按深度優(yōu)先搜索策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹，算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否滿足約束，如果不滿足，則跳過該節(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先節(jié)點(diǎn)搜索，否則，進(jìn)入該子樹，繼續(xù)按照深度優(yōu)先策略搜索。三、實(shí)驗(yàn)內(nèi)容：回溯算法的幾種形式1.用回溯算法搜索子集樹的一般模式void search(int

14、m)if(m>n) /遞歸結(jié)束條件 output(); /相應(yīng)的處理(輸出結(jié)果)elseam=0; /設(shè)置狀態(tài)：0表示不要該物品search(m+1); /遞歸搜索：繼續(xù)確定下一個(gè)物品am=1; /設(shè)置狀態(tài)：1表示要該物品search(m+1); /遞歸搜索：繼續(xù)確定下一個(gè)物品2.用回溯算法搜索子集樹的一般模式void search(int m)if(m>n) /遞歸結(jié)束條件 output(); /相應(yīng)的處理(輸出結(jié)果)elsefor(i=m;i<=n;i+)swap(m,i); /交換am和aiif()if(canplace(m) /如果m處可放置search(m+1);

15、/搜索下一層swpa(m,i); /交換am和ai(換回來)四、回溯算法解決0-1背包問題在0 / 1背包問題中，需對(duì)容量為c 的背包進(jìn)行裝載。從n 個(gè)物品中選取裝入背包的物品，每件物品i 的重量為wi ，價(jià)值為pi 。對(duì)于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價(jià)值最高。0代表不裝進(jìn)背包，1代表裝進(jìn)背包，對(duì)樹進(jìn)行深度優(yōu)先搜索，判斷是否為可行解，若為可行解且放進(jìn)去之后最大價(jià)值大于當(dāng)前最大價(jià)值則修改當(dāng)前最大價(jià)值和背包余量。（沒有進(jìn)行減支）代碼：#include <stdio.h>void readdata();void search(int);v

16、oid checkmax();void printresult();int c=35, n=10; /c:背包容量；n：物品數(shù)int w10, v10; /wi、vi:第i件物品的重量和價(jià)值int a10, max; /a數(shù)組存放當(dāng)前解各物品選取情況；max：記錄最大價(jià)值 /ai=0表示不選第i件物品，ai=1表示選第i件物品int main()readdata(); /讀入數(shù)據(jù)search(0); /遞歸搜索printresult();void search(int m)if(m>=n)checkmax(); /檢查當(dāng)前解是否是可行解，若是則把它的價(jià)值與max比較elseam = 1;

17、 /不選第m件物品search(m+1); /遞歸搜索下一件物品am = 0; search(m+1);void checkmax()int i, weight=0, value=0;for(i = 0;i<n;i+)if(ai=1) /如果選取了該物品weight = weight + wi; /累加重量value = value + vi; /累加價(jià)值if(weight<=c) /若為可行解if(value>max) /且價(jià)值大于maxmax = value; /替換maxvoid readdata()int i;for(i=0;i<n;i+)printf(&quo

18、t;請(qǐng)輸入第%d個(gè)物品的重量和價(jià)值n",i+1);scanf("%d %d",&wi,&vi); /讀入第i件物品重量和價(jià)值void printresult()printf("背包可以裝的最大價(jià)值為%d",max); 運(yùn)行截圖：實(shí)驗(yàn)三：動(dòng)態(tài)規(guī)劃一、實(shí)驗(yàn)?zāi)康?理解動(dòng)態(tài)規(guī)劃的基本思想，理解動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題的重疊性質(zhì)。熟練掌握典型的動(dòng)態(tài)規(guī)劃問題。掌握動(dòng)態(tài)規(guī)劃思想分析問題的一般方法，對(duì)較簡(jiǎn)單的問題能正確分析，設(shè)計(jì)出動(dòng)態(tài)規(guī)劃算法，并能快速編程實(shí)現(xiàn)。2、 動(dòng)態(tài)規(guī)劃的基本思想對(duì)于一個(gè)多階段過程問題，是否可以分段

19、實(shí)現(xiàn)最優(yōu)決策，信賴于該問題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)，能否采用動(dòng)態(tài)規(guī)劃的方法，還要看該問題的子問題是否具有重疊性質(zhì)。 最優(yōu)子結(jié)構(gòu)性質(zhì):原問題的最優(yōu)解包含了其子問題的最優(yōu)解 子問題的重疊性質(zhì):每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素動(dòng)態(tài)規(guī)劃一般方法 1.找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征 2.遞歸地定義最優(yōu)值(寫出動(dòng)態(tài)規(guī)劃方程) 3.以自底向上的方式計(jì)算出最優(yōu)值 三、用動(dòng)態(tài)規(guī)劃法計(jì)算矩陣連乘需要的最少乘法次數(shù)在科學(xué)計(jì)算中經(jīng)常要計(jì)算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。若A是一個(gè)p×

20、q的矩陣，B是一個(gè)q×r的矩陣，則其乘積C=AB是一個(gè)p×r的矩陣。由該公式知計(jì)算C=AB總共需要pqr次的數(shù)乘。其標(biāo)準(zhǔn)計(jì)算公式為：現(xiàn)在的問題是，給定n個(gè)矩陣A1,A2,An。其中Ai與Ai+1是可乘的，i=1,2,n-1。要求計(jì)算出這n個(gè)矩陣的連乘積A1A2An。遞歸公式： 代碼：#include<stdio.h>int n; /矩陣個(gè)數(shù)(0100)int p101; /矩陣維數(shù)(n+1) void Matrix_mult() int Arr101101,temp;/(Arr00不用)Arrij存放從矩陣i到矩陣j的最小矩陣乘法數(shù) int i,j,k; int d; /矩陣間隔d for(i=1;i<=n;i+) Arrii=0;/第i個(gè)矩陣到第i個(gè)矩陣乘法數(shù)為0 for(d