算法實驗一實驗報告

武漢輕工大學數(shù)學與計算機學院算法分析試驗匯報指導老師：湯小月專業(yè)：信息管理與信息系統(tǒng)班級：信管1201班學號：姓名：試驗一分治與遞歸（2課時）基本題一：基本遞歸算法一、試驗?zāi)繕伺c要求熟悉C/C++語言集成開發(fā)環(huán)境；經(jīng)過本試驗加深對遞歸過程了解二、試驗內(nèi)容：掌握遞歸算法概念和基本思想，分析并掌握“整數(shù)劃分”問題遞歸算法。三、試驗題任意輸入一個整數(shù)，輸出結(jié)果能夠用遞歸方法實現(xiàn)整數(shù)劃分。詳細程序代碼以下：#include<iostream>usingnamespacestd;intq(intn,intm)//正整數(shù)n最大加數(shù)m劃分數(shù){ if((n<1)||(m<1))return0;//n，m需>1 if((n==1)||(m==1))return1;//正整數(shù)或者最大加數(shù)=1時，只有一個劃分情況 if(n<m)returnq(n,n);//最大加數(shù)實際不能大于正整數(shù)本身 if(n==m)returnq(n,m-1)+1;//遞歸，n劃分由其q（n，m-1）和n1=n組成 returnq(n,m-1)+q(n-m,m);//正整數(shù)n最大加數(shù)n1小于m劃分由n1=m劃分和n1=m-1劃分組成}voidmain(){ intn,m; cout<<"請輸入一個整數(shù)n（-1退出）："<<endl; cin>>n; while(n>=1) { cout<<"請輸入一個最大加數(shù)m："<<endl; cin>>m; cout<<"正整數(shù)n最大加數(shù)m劃分數(shù)為"<<q(n,m)<<endl; cout<<"請輸入一個整數(shù)n（-1退出）："<<endl; cin>>n; }}進行編譯以下：運行結(jié)果以下：四、試驗步驟了解算法思想和問題要求；編程實現(xiàn)題目要求；上機輸入和調(diào)試自己所編程序；驗證分析試驗結(jié)果；整理出試驗匯報。

基本題二：棋盤覆蓋問題一、試驗?zāi)繕伺c要求1、掌握棋盤覆蓋問題算法；2、初步掌握分治算法二、試驗題：

盤覆蓋問題：在一個2k×2k個方格組成棋盤中，恰有一個方格與其它方格不一樣，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示4種不一樣形態(tài)L型骨牌覆蓋給定特殊棋盤上除特殊方格以外全部方格，且任何2個L型骨牌不得重合覆蓋。三、試驗提醒voidchessBoard(inttr,inttc,intdr,intdc,intsize)

{

if(size==1)return;

intt=tile++,

//L型骨牌號

s=size/2;

//分割棋盤

//覆蓋左上角子棋盤

if(dr<tr+s&&dc<tc+s)

//特殊方格在此棋盤中

chessBoard(tr,tc,dr,dc,s);

else{//此棋盤中無特殊方格

//用t號L型骨牌覆蓋右下角

board[tr+s-1][tc+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型骨牌覆蓋左下角board[tr+s-1][tc+s]=t;

//覆蓋其余方格

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型骨牌覆蓋右上角

board[tr+s][tc+s-1]=t;

//覆蓋其余方格

chessBoard(tr+s,tc,tr+s,tc+s-1,s);}

//覆蓋右下角子棋盤

if(dr>=tr+s&&dc>=tc+s)

//特殊方格在此棋盤中

chessBoard(tr+s,tc+s,dr,dc,s);

else{//用t號L型骨牌覆蓋左上角

board[tr+s][tc+s]=t;

//覆蓋其余方格

chessBoard(tr+s,tc+s,tr+s,tc+s,s);}

}編寫程序代碼以下:#include<iostream>usingnamespacestd;intboard[65][65],tile;/*tile為紙片編號*/voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌號s=size/2;//分割棋盤//覆蓋左上角子棋盤if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盤中chessBoard(tr,tc,dr,dc,s);else{//此棋盤中無特殊方格//用t號L型骨牌覆蓋右下角board[tr+s-1][tc+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型骨牌覆蓋左下角board[tr+s-1][tc+s]=t;//覆蓋其余方格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型骨牌覆蓋右上角board[tr+s][tc+s-1]=t;//覆蓋其余方格chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆蓋右下角子棋盤if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盤中chessBoard(tr+s,tc+s,dr,dc,s);else{//用t號L型骨牌覆蓋左上角board[tr+s][tc+s]=t;//覆蓋其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}//輸出最終結(jié)果voidresult(intb[][65],intn){inti,j;for(i=1;i<=n;i++) {for(j=1;j<=n;j++) cout<<b[i][j]<<""; cout<<endl;}}intmain(){intsize,dr,dc; cout<<"選擇輸入4種不一樣形態(tài)L型骨牌中一個(4/8/16/64):"<<endl; cin>>size; cout<<"請輸入特殊塊位置(x,y):"<<endl; cin>>dr>>dc; cout<<"結(jié)果以下："<<endl;board[dr][dc]=-1;tile++;chessBoard(1,1,dr,dc,size);result(board,size);}運行調(diào)試結(jié)果以下:試運行結(jié)果以下:

提升題一：二分搜索一、試驗?zāi)繕伺c要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、試驗題1、設(shè)a[0:n-1]是一個已排好序數(shù)組。請改寫二分搜索算法，使得當搜索元素x不在數(shù)組中時，返回小于x最大元素位置I和大于x最小元素位置j。當搜索元素在數(shù)組中時，I和j相同，均為x在數(shù)組中位置。2、設(shè)有n個不一樣整數(shù)排好序后存放于t[0:n-1]中，若存在一個下標I，0≤i＜n，使得t[i]=i，設(shè)計一個有效算法找到這個下標。要求算法在最壞情況下計算時間為O（logn）。三、試驗提醒1、用I，j做參數(shù)，且采取傳遞引用或指針形式帶回值。boolBinarySearch(inta[],intn,intx,int&i,int&j){

intleft=0;

intright=n-1;

while(left<right)

{

intmid=(left+right)/2;

if(x==a[mid])

{

i=j=mid;

returntrue;

}

if(x>a[mid])

left=mid+1;

else

right=mid-1;2

}

i=right;

j=left;

returnfalse;}intSearchTag(inta[],intn,intx){

intleft=0;

intright=n-1;

while(left<right)

{

intmid=(left+right)/2;

if(x==a[mid])returnmid;

if(x>a[mid])

right=mid-1;

else

left=mid+1;

}

return-1;}試驗題1代碼編寫以下:#include<iostream>usingnamespacestd;voidBubbleSort(int*pData,intCount)//冒泡排序函數(shù)，pData中從0位置處存了Count個數(shù)，該函數(shù)將數(shù)組中元素排序{intiTemp;for(inti=1;i<Count;i++){for(intj=Count-1;j>=i;j--) {if(pData[j]<pData[j-1]) {iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp; } }}}boolBinarySearch(inta[],intn,intx,int&i,int&j)//數(shù)組a大小為n，數(shù)組中存放了已經(jīng)排好序（升序）數(shù)列{intleft=0;intright=n-1;intmid=0;while(left<right){mid=(left+right)/2;if(x==a[mid]) {i=j=mid;returntrue; }if(x>a[mid])left=mid+1;elseright=mid-1;}i=right;j=left;returnfalse;}intSearchTag(inta[],intn,intx){intleft=0;intright=n-1;while(left<right){intmid=(left+right)/2;if(x==a[mid])returnmid;if(x>a[mid])right=mid-1;elseleft=mid+1;}return-1;}intmain(){inta[100];cout<<"請輸入數(shù)組中數(shù)個數(shù)，小于100:";intnum=0;cin>>num;cout<<"請輸入數(shù)組中數(shù)："<<endl;for(inti=0;i<num;i++)cin>>a[i];//下面將數(shù)組a排成升序BubbleSort(a,num);cout<<"下面輸出排序后數(shù)組："<<endl;for(i=0;i<num;i++)printf("%4d",a[i]);cout<<endl;cout<<"請輸入要查找數(shù):";intx=0;cin>>x;intj=0;if(BinarySearch(a,num,x,i,j))cout<<"找到了，位置為"<<i<<endl;elsecout<<"沒找到,小于該數(shù)最大元素位置為"<<i<<"大于該數(shù)最小元素位置為"<<j<<"（第一個元素位置為0）"<<endl;return0;}試運行調(diào)試結(jié)果以下:運行結(jié)果以下列圖所表示:試驗題2編寫代碼以下:#include<iostream>usingnamespacestd;/*依照題目中隱含要求，現(xiàn)在將問題進行簡化，假設(shè)數(shù)組中存放數(shù)全部為整數(shù)*/voidBubbleSort(int*pData,intCount)//冒泡排序函數(shù)，pData中從0位置處存了Count個數(shù)，該函數(shù)將數(shù)組中元素排升序{intiTemp;for(inti=1;i<Count;i++){for(intj=Count-1;j>=i;j--) {if(pData[j]<pData[j-1]) {iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp; } }}}boolBinaryFind_iei(inta[],intn,int&i)//數(shù)組a大小為n，數(shù)組中存放了已經(jīng)排好序（升序）數(shù)列{intleft=0;intright=n-1;intmid=0;while(left<right){mid=(left+right)/2;if(mid==a[mid]){i=mid;returntrue;//找到了}elseif(mid>a[mid])left=mid;elseright=mid;}returnfalse;}intmain(){inta[100];cout<<"請輸入數(shù)組中數(shù)個數(shù)，小于100:";intnum=0;cin>>num;cout<<"請輸入數(shù)組中數(shù)："<<endl;for(intii=0;ii<num;ii++)cin>>a[ii];//下面將數(shù)組a排成升序BubbleSort(a,num);cout<<"下面輸出排序后數(shù)組："<<endl;for(inti=0;i<num;i++)printf("%4d",a[i]);cout<<endl;intj=0;if(BinaryFind_iei(a,num,j))cout<<"找到了，位置為"<<j<<endl;elsecout<<"不存在符合第i個位置等于i元素。"<<endl;return0;}試運行調(diào)試結(jié)果以下:運行結(jié)果以下:結(jié)果分析：利用分治策略求解時，所需時間取決于分解后子問題個數(shù)、子問題規(guī)模大小等素，而二分法，因為其劃分簡單和均勻特點，是經(jīng)常采取一個有效方法，比如二分法檢索。

提升題二：用分治法實現(xiàn)元素選擇一、試驗要求與目標1、了解分治法基本思想，掌握遞歸程序編寫方法；2、使用分治法編程，求解線形序列中第k小元素。二、試驗內(nèi)容給定線形序列集中n個元素和一個整數(shù)k，1≤k≤n，輸出這n個元素中第k小元素值及其位置。簡述該算法原理、步驟。對該算法與直接排序查找進行比較。編寫并調(diào)試程序。測試要求：元素個數(shù)不少于100；分三種情況：k=1、k=n和k=中位數(shù)。編寫程序代碼以下所表示：#include<stdlib.h>#include<time.h>#include<stdio.h>#include<malloc.h>intpartition(inta[],intp,intr){intz=p,x=r+1;inty=a[p];intt;while(1){while(a[++z]<y&&z<r);//空循環(huán)，不符合條件時向下執(zhí)行while(a[--x]>y);if(z>=x)break;t=a[z];a[z]=a[x];a[x]=t;}a[p]=a[x];a[x]=y;returnx;}voidquicksort(inta[],intp,intr){intq;if(p<r){q=partition(a,p,r);quicksort(a,p,q-1);quicksort(a,q+1,r);}}intmain(){for(;;){intk,*a,*b,n,i,d,s;printf("請輸入數(shù)組個數(shù):");scanf("%d",&n);printf("\n");a=(int*)malloc(sizeof(int)*n);//給數(shù)組a分配空間srand((unsigned)time(NULL));b=(int*)malloc(sizeof(int)*n);//給數(shù)組b分配空間srand((