算法實驗一實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上武漢輕工大學(xué)數(shù)學(xué)與計算機(jī)學(xué)院算法分析實驗報告指導(dǎo)老師： 湯小月 專 業(yè)： 信息管理與信息系統(tǒng) 班 級： 信管1201班 學(xué) 號： 姓 名： 實驗一 分治與遞歸（2學(xué)時）基本題一：基本遞歸算法一、實驗?zāi)康呐c要求1、 熟悉C/C+語言的集成開發(fā)環(huán)境；2、 通過本實驗加深對遞歸過程的理解二、實驗內(nèi)容：掌握遞歸算法的概念和基本思想，分析并掌握“整數(shù)劃分”問題的遞歸算法。三、實驗題任意輸入一個整數(shù)，輸出結(jié)果能夠用遞歸方法實現(xiàn)整數(shù)的劃分。具體程序代碼如下：#include<iostream>using namespace std;int q(int n,int m)

2、/正整數(shù)n的最大加數(shù)m的劃分?jǐn)?shù)if(n<1)|(m<1) return 0; /n，m需>1if(n=1)|(m=1) return 1; /正整數(shù)或者最大加數(shù)=1時，只有一種劃分情況if(n<m) return q(n,n); /最大加數(shù)實際不能大于正整數(shù)本身if(n=m) return q(n,m-1)+1; /遞歸，n的劃分由其q（n，m-1）和n1=n組成return q(n,m-1)+q(n-m,m); /正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1=m-1的劃分組成void main()int n,m;cout<<"請輸入

3、一個整數(shù)n（-1退出）："<<endl;cin>>n;while(n>=1)cout<<"請輸入一個最大加數(shù)m："<<endl;cin>>m;cout<<"正整數(shù)n的最大加數(shù)m的劃分?jǐn)?shù)為"<<q(n,m)<<endl;cout<<"請輸入一個整數(shù)n（-1退出）："<<endl;cin>>n;進(jìn)行編譯如下：運行結(jié)果如下：四、實驗步驟1 理解算法思想和問題要求；2 編程實現(xiàn)題目要求；3 上機(jī)輸

4、入和調(diào)試自己所編的程序；4 驗證分析實驗結(jié)果；5 整理出實驗報告。 基本題二：棋盤覆蓋問題一、實驗?zāi)康呐c要求1、掌握棋盤覆蓋問題的算法；2、初步掌握分治算法二、實驗題：    盤覆蓋問題：在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。三、實驗提示void chessBoard(int tr, int tc, int dr, int dc, int siz

5、e)         if (size = 1) return;      int t = tile+,  / L型骨牌號        s = size/2;  / 分割棋盤      / 覆蓋左上角子棋盤      if (dr < tr + s && dc &l

6、t; tc + s)         / 特殊方格在此棋盤中         chessBoard(tr, tc, dr, dc, s);      else / 此棋盤中無特殊方格         / 用 t 號L型骨牌覆蓋右下角      

7、60;  boardtr + s - 1tc + s - 1 = t;         / 覆蓋其余方格         chessBoard(tr, tc, tr+s-1, tc+s-1, s);      / 覆蓋右上角子棋盤      if (dr < tr + s && dc >= tc +

8、s)         / 特殊方格在此棋盤中         chessBoard(tr, tc+s, dr, dc, s);      else / 此棋盤中無特殊方格         / 用 t 號L型骨牌覆蓋左下角boardtr + s - 1tc + s = t;   &

9、#160;     / 覆蓋其余方格         chessBoard(tr, tc+s, tr+s-1, tc+s, s);        / 覆蓋左下角子棋盤      if (dr >= tr + s && dc < tc + s)       

10、60; / 特殊方格在此棋盤中         chessBoard(tr+s, tc, dr, dc, s);      else / 用 t 號L型骨牌覆蓋右上角         boardtr + stc + s - 1 = t;         / 覆蓋其余方格   &#

11、160;     chessBoard(tr+s, tc, tr+s, tc+s-1, s);      / 覆蓋右下角子棋盤      if (dr >= tr + s && dc >= tc + s)         / 特殊方格在此棋盤中         chess

12、Board(tr+s, tc+s, dr, dc, s);      else / 用 t 號L型骨牌覆蓋左上角         boardtr + stc + s = t;         / 覆蓋其余方格         chessBoard(tr+s, tc+s, tr+s, tc+s, s);

13、0;  編寫程序代碼如下:#include <iostream> using namespace std; int board6565,tile; /* tile 為紙片編號*/ void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌號 s = size/2; / 分割棋盤 / 覆蓋左上角子棋盤 if (dr < tr + s && dc < tc + s) / 特殊方格在此棋盤中 chessBoa

14、rd(tr, tc, dr, dc, s); else / 此棋盤中無特殊方格 / 用 t 號L型骨牌覆蓋右下角 boardtr + s - 1tc + s - 1 = t; / 覆蓋其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆蓋右上角子棋盤 if (dr < tr + s && dc >= tc + s) / 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤中無特殊方格 / 用 t 號L型骨牌覆蓋左下角 boardtr + s - 1tc + s = t;

15、/ 覆蓋其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆蓋左下角子棋盤 if (dr >= tr + s && dc < tc + s) / 特殊方格在此棋盤中 chessBoard(tr+s, tc, dr, dc, s); else / 用 t 號L型骨牌覆蓋右上角 boardtr + stc + s - 1 = t; / 覆蓋其余方格 chessBoard(tr+s, tc, tr+s, tc+s-1, s); / 覆蓋右下角子棋盤 if (dr >= tr + s && dc >= t

16、c + s) / 特殊方格在此棋盤中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 號L型骨牌覆蓋左上角 boardtr + stc + s = t; / 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); /輸出最終的結(jié)果void result(int b65,int n) int i,j; for(i=1;i<=n;i+) for(j=1;j<=n;j+) cout<<bij<<" " cout<<endl; int main() int

17、 size,dr,dc; cout<<"選擇輸入4種不同形態(tài)的L型骨牌中的一種(4/8/16/64): "<<endl;cin>>size;cout<<"請輸入特殊的塊的位置(x,y): "<<endl;cin>>dr>>dc;cout<<"結(jié)果如下："<<endl; boarddrdc=-1; tile+; chessBoard(1,1,dr,dc,size); result(board,size); 運行調(diào)試結(jié)果如下:試運行

18、結(jié)果如下: 提高題一：二分搜索一、實驗?zāi)康呐c要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、實驗題1、設(shè)a0:n-1是一個已排好序的數(shù)組。請改寫二分搜索算法，使得當(dāng)搜索元素x不在數(shù)組中時，返回小于x的最大元素的位置I和大于x的最小元素位置j。當(dāng)搜索元素在數(shù)組中時，I和j相同，均為x在數(shù)組中的位置。2、設(shè)有n個不同的整數(shù)排好序后存放于t0:n-1中，若存在一個下標(biāo)I，0in，使得ti=i，設(shè)計一個有效的算法找到這個下標(biāo)。要求算法在最壞的情況下的計算時間為O（logn）。三、實驗提示1、用I，j做參數(shù)，且采用傳遞引用或指針的形式帶回值。bool BinarySearch(int a,

19、int n,int x,int& i,int& j)    int left=0;    int right=n-1;    while(left<right)           int mid=(left+right)/2;        if(x=amid)      

20、           i=j=mid;           return true;               if(x>amid)           left=mid+1;  &

21、#160;    else           right=mid-1;2        i=right;    j=left;    return false;int SearchTag(int a,int n,int x)    int left=0;    int right=n-1;

22、0;   while(left<right)           int mid=(left+right)/2;        if(x=amid) return mid;        if(x>amid)           right=mid-1; &

23、#160;     else           left=mid+1;        return -1;實驗題1代碼編寫如下:#include<iostream> using namespace std; void BubbleSort(int* pData,int Count) /冒泡排序的函數(shù)，pData中從0位置處存了Count個數(shù)，該函數(shù)將數(shù)組中元素排序 int iTemp; for

24、(int i=1;i<Count;i+) for(int j=Count-1;j>=i;j-) if(pDataj<pDataj-1) iTemp = pDataj-1; pDataj-1 = pDataj; pDataj = iTemp; bool BinarySearch(int a,int n,int x,int& i,int& j) /數(shù)組a大小為n，數(shù)組中存放了已經(jīng)排好序（升序）的數(shù)列 int left=0; int right=n-1; int mid=0; while(left<right) mid=(left+right)/2; if(x

25、=amid) i=j=mid; return true; if(x>amid) left=mid+1; else right=mid-1; i=right; j=left; return false; int SearchTag(int a,int n,int x) int left=0; int right=n-1; while(left<right) int mid=(left+right)/2; if(x=amid) return mid; if(x>amid) right=mid-1; else left=mid+1; return -1; int main() in

26、t a100; cout<<"請輸入數(shù)組中數(shù)的個數(shù)，小于100:" int num=0; cin>>num; cout<<"請輸入數(shù)組中的數(shù)："<<endl; for(int i=0;i<num;i+) cin>>ai; /下面將數(shù)組a排成升序 BubbleSort(a,num); cout<<"下面輸出排序后的數(shù)組："<<endl; for(i=0;i<num;i+) printf("%4d",ai); cout<

27、;<endl; cout<<"請輸入要查找的數(shù):" int x=0; cin>>x; int j=0; if(BinarySearch(a,num,x,i,j) cout<<"找到了，位置為"<<i<<endl; else cout<<"沒找到,小于該數(shù)的最大元素位置為"<<i<<"大于該數(shù)的最小元素的位置為"<<j<<"（第一個元素的位置為0）"<<endl

28、; return 0; 試運行調(diào)試結(jié)果如下:運行結(jié)果如下圖所示:實驗題2編寫代碼如下:#include<iostream> using namespace std; /*根據(jù)題目中的隱含要求，現(xiàn)在將問題進(jìn)行簡化，假設(shè)數(shù)組中存放的數(shù)全部為整數(shù)*/ void BubbleSort(int* pData,int Count) /冒泡排序的函數(shù)，pData中從0位置處存了Count個數(shù)， 該函數(shù)將數(shù)組中元素排升序 int iTemp; for(int i=1;i<Count;i+) for(int j=Count-1;j>=i;j-) if(pDataj<pDataj-1

29、) iTemp = pDataj-1; pDataj-1 = pDataj; pDataj = iTemp; bool BinaryFind_iei(int a,int n,int& i) /數(shù)組a大小為n，數(shù)組中存放了已經(jīng)排好序（升序）的數(shù)列 int left=0; int right=n-1; int mid=0; while(left<right) mid=(left+right)/2; if(mid=amid) i=mid; return true; /找到了 else if(mid>amid) left=mid; else right=mid; return fa

30、lse; int main() int a100; cout<<"請輸入數(shù)組中數(shù)的個數(shù)，小于100:" int num=0; cin>>num; cout<<"請輸入數(shù)組中的數(shù)："<<endl; for(int ii=0;ii<num;ii+) cin>>aii; /下面將數(shù)組a排成升序 BubbleSort(a,num); cout<<"下面輸出排序后的數(shù)組："<<endl; for(int i=0;i<num;i+) printf(&q

31、uot;%4d",ai); cout<<endl; int j=0; if(BinaryFind_iei(a,num,j) cout<<"找到了，位置為"<<j<<endl; else cout<<"不存在符合第i個位置等于i的元素。"<<endl; return 0; 試運行調(diào)試結(jié)果如下:運行結(jié)果如下:結(jié)果分析：利用分治策略求解時，所需時間取決于分解后子問題的個數(shù)、子問題的規(guī)模大小等素，而二分法，由于其劃分的簡單和均勻的特點，是經(jīng)常采用的一種有效的方法，例如二分法檢索。&

32、#160;提高題二： 用分治法實現(xiàn)元素選擇一、實驗要求與目的1、了解分治法的基本思想，掌握遞歸程序編寫方法；2、使用分治法編程，求解線形序列中第k小元素。二、實驗內(nèi)容1、 給定線形序列集中n個元素和一個整數(shù)k，1kn，輸出這n個元素中第k小元素的值及其位置。2、 簡述該算法的原理、步驟。對該算法與直接排序查找進(jìn)行比較。3、 編寫并調(diào)試程序。測試要求：元素個數(shù)不少于100；分三種情況：k=1、k=n和k=中位數(shù)。編寫程序代碼如下所示：#include<stdlib.h> #include<time.h> #include<stdio.h>#include<

33、;malloc.h>int partition(int a,int p,int r) int z=p,x=r+1; int y=ap; int t; while(1) while(a+z<y&&z<r);/空循環(huán)，不符合條件時向下執(zhí)行 while(a-x>y); if(z>=x) break; t=az; az=ax; ax=t; ap=ax; ax=y; return x;void quicksort(int a,int p,int r) int q; if(p<r) q=partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); int main() for(;)