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

算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告||||專業(yè)班級(jí)：學(xué)生姓名：學(xué)號(hào)：第頁(yè)共頁(yè)實(shí)驗(yàn)一基本題一：基本遞歸算法一、實(shí)驗(yàn)?zāi)康呐c要求熟悉C/C++語(yǔ)言的集成開(kāi)發(fā)環(huán)境；通過(guò)本實(shí)驗(yàn)加深對(duì)遞歸過(guò)程的理解二、實(shí)驗(yàn)內(nèi)容：掌握遞歸算法的概念和基本思想，分析并掌握“整數(shù)劃分”問(wèn)題的遞歸算法。三、實(shí)驗(yàn)題任意輸入一個(gè)整數(shù)，輸出結(jié)果能夠用遞歸方法實(shí)現(xiàn)整數(shù)的劃分。四、實(shí)驗(yàn)步驟理解算法思想和問(wèn)題要求；編程實(shí)現(xiàn)題目要求；上機(jī)輸入和調(diào)試自己所編的程序；驗(yàn)證分析實(shí)驗(yàn)結(jié)果；整理出實(shí)驗(yàn)報(bào)告。五、實(shí)驗(yàn)結(jié)果基本題二：棋盤(pán)覆蓋問(wèn)題一、實(shí)驗(yàn)?zāi)康呐c要求1、掌握棋盤(pán)覆蓋問(wèn)題的算法；2、初步掌握分治算法二、實(shí)驗(yàn)題：

盤(pán)覆蓋問(wèn)題：在一個(gè)2k×2k個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤(pán)為一特殊棋盤(pán)。在棋盤(pán)覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤(pán)上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。三、實(shí)驗(yàn)提示voidchessBoard(inttr,inttc,intdr,intdc,intsize)

{

if(size==1)return;

intt=tile++,

//L型骨牌號(hào)

s=size/2;

//分割棋盤(pán)

//覆蓋左上角子棋盤(pán)

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

//特殊方格在此棋盤(pán)中

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

else{//此棋盤(pán)中無(wú)特殊方格

//用t號(hào)L型骨牌覆蓋右下角

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

//覆蓋其余方格

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

//覆蓋右上角子棋盤(pán)

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

//特殊方格在此棋盤(pán)中

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

else{//此棋盤(pán)中無(wú)特殊方格

//用t號(hào)L型骨牌覆蓋左下角board[tr+s-1][tc+s]=t;

//覆蓋其余方格

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

//覆蓋左下角子棋盤(pán)

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

//特殊方格在此棋盤(pán)中

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

else{//用t號(hào)L型骨牌覆蓋右上角

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

//覆蓋其余方格

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

//覆蓋右下角子棋盤(pán)

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

//特殊方格在此棋盤(pán)中

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

else{//用t號(hào)L型骨牌覆蓋左上角

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

//覆蓋其余方格

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

}四、實(shí)驗(yàn)結(jié)果提高題一：二分搜索一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、實(shí)驗(yàn)題1、設(shè)a[0:n-1]是一個(gè)已排好序的數(shù)組。請(qǐng)改寫(xiě)二分搜索算法，使得當(dāng)搜索元素x不在數(shù)組中時(shí)，返回小于x的最大元素的位置I和大于x的最大元素位置j。當(dāng)搜索元素在數(shù)組中時(shí)，I和j相同，均為x在數(shù)組中的位置。2、設(shè)有n個(gè)不同的整數(shù)排好序后存放于t[0:n-1]中，若存在一個(gè)下標(biāo)I，0≤i＜n，使得t[i]=i，設(shè)計(jì)一個(gè)有效的算法找到這個(gè)下標(biāo)。要求算法在最壞的情況下的計(jì)算時(shí)間為O（logn）。三、實(shí)驗(yàn)提示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;

}

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;}運(yùn)行結(jié)果

提高題二：用分治法實(shí)現(xiàn)元素選擇一、實(shí)驗(yàn)要求與目的1、了解分治法的基本思想，掌握遞歸程序編寫(xiě)方法；2、使用分治法編程，求解線形序列中第k小元素。二、實(shí)驗(yàn)內(nèi)容給定線形序列集中n個(gè)元素和一個(gè)整數(shù)k，1≤k≤n，輸出這n個(gè)元素中第k小元素的值及其位置。簡(jiǎn)述該算法的原理、步驟。對(duì)該算法與直接排序查找進(jìn)行比較。編寫(xiě)并調(diào)試程序。運(yùn)行結(jié)果實(shí)驗(yàn)二

基本題一：最長(zhǎng)公共子序列問(wèn)題一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉最長(zhǎng)公共子序列問(wèn)題的算法；2、初步掌握動(dòng)態(tài)規(guī)劃算法；二、實(shí)驗(yàn)題

若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對(duì)于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2，3，5，7}。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長(zhǎng)公共子序列。

三、實(shí)驗(yàn)提示include"stdlib.h"#include"string.h"

voidLCSLength(char*x,char*y,intm,intn,int**c,int**b){

inti,j;

for(i=1;i<=m;i++)c[i][0]=0;

for(i=1;i<=n;i++)c[0][i]=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

{

if(x[i]==y[j])

{

c[i][j]=c[i-1][j-1]+1;

b[i][j]=1;

}

elseif(c[i-1][j]>=c[i][j-1])

{

c[i][j]=c[i-1][j];

b[i][j]=2;

}

else

{

c[i][j]=c[i][j-1];

b[i][j]=3;

}

}}voidLCS(inti,intj,char*x,int**b){

if(i==0||j==0)return;

if(b[i][j]==1)

{

LCS(i-1,j-1,x,b);

printf("%c",x[i]);

}

elseif(b[i][j]==2)

LCS(i-1,j,x,b);

elseLCS(i,j-1,x,b);}運(yùn)行結(jié)果基本題二：最大字段和問(wèn)題

一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉最長(zhǎng)最大字段和問(wèn)題的算法；2、進(jìn)一步掌握動(dòng)態(tài)規(guī)劃算法；二、實(shí)驗(yàn)題

若給定n個(gè)整數(shù)組成的序列a1，a2，a3，……an，求該序列形如ai＋ai＋1＋……＋an的最大值。三、實(shí)驗(yàn)提示intMaxSum(intn,int*a,int&besti,int&bestj){

intsum=0;

for(inti=1;i<=n;i++)

for(intj=i;j<=n;j++)

{

intthissum=0;

for(intK=i;k<=j;k++)thissum+=a[k];

if(thissum>sum)

{

sum=thissum;

besti=i;

bestj=j;

}

}

returnsum;

}intMaxSum(intn,int*a,int&besti,int&bestj)

{

intsum=0;

for(inti=1;i<=n;i++)

{

intthissum=0;

for(intj=i;j<=n;j++)

{

thissum+=a[j];

if(thissum>sum)

{

sum=thissum;

besti=i;

bestj=j;

}

}

}

returnsum;}

運(yùn)行結(jié)果提高題一：用動(dòng)態(tài)規(guī)劃法求解0/1背包問(wèn)題一、實(shí)驗(yàn)要求與目的掌握動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的一般特征和步驟。使用動(dòng)態(tài)規(guī)劃法編程，求解0/1背包問(wèn)題。二、實(shí)驗(yàn)內(nèi)容問(wèn)題描述：給定n種物品和一個(gè)背包，物品i的重量是Wi，其價(jià)值為Vi，問(wèn)如何選擇裝入背包的物品，使得裝入背包的物品的總價(jià)值最大？算法描述。程序?qū)崿F(xiàn)；給出實(shí)例測(cè)試結(jié)果。運(yùn)行結(jié)果：實(shí)驗(yàn)三基本題一：多機(jī)調(diào)度問(wèn)題一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉多機(jī)調(diào)度問(wèn)題的算法；2、初步掌握貪心算法；二、實(shí)驗(yàn)題

要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。三、實(shí)驗(yàn)提示1、把作業(yè)按加工所用的時(shí)間從大到小排序2、如果作業(yè)數(shù)目比機(jī)器的數(shù)目少或相等，則直接把作業(yè)分配下去3、

如果作業(yè)數(shù)目比機(jī)器的數(shù)目多，則每臺(tái)機(jī)器上先分配一個(gè)作業(yè)，如下的作業(yè)分配時(shí)，是選那個(gè)表頭上s最小的鏈表加入新作業(yè)。typedefstructJob{

intID;//作業(yè)號(hào)

inttime;//作業(yè)所花費(fèi)的時(shí)間}Job;

typedefstructJobNode//作業(yè)鏈表的節(jié)點(diǎn){

intID;

inttime;

JobNode*next;}JobNode,*pJobNode;

typedefstructHeader

//鏈表的表頭{

ints;

pJobNo