中南大学 算法实验报告.docx

中南大学 算法实验报告.docx

《中南大学 算法实验报告.docx》由会员分享，可在线阅读，更多相关《中南大学 算法实验报告.docx（17页珍藏版）》请在冰点文库上搜索。

中南大学算法实验报告

姓名：

学号：

班级：

指导老师：

李敏

算法设计与分析基础

——实验报告

实验一：

递归与分治

[实验目的]

1.理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。

2.掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。

[实验预备]

1.编程实现讲过的例题：

二分搜索、合并排序、快速排序。

2.对本实验中的问题，设计出算法并编程实现。

[实验内容和步骤]

1．二分查找（改进版）

在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。

此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。

实验代码如下：

#include

#include

usingnamespacestd;

#defineN21

voidquick_sort（inta[],intleft,intright）

{

if（left

{

inti=left;

intj=right;

intx=a[i];

while（i

{

while（ix）

j--;

if（i

a[i]=a[j];

i++;

}

while（i

i++;

if（i

a[j]=a[i];

j--;

}

}

a[i]=x;

quick_sort（a,left,i-1）;

quick_sort（a,i+1,right）;

}

}

voidmain（void）

{

inta[N];

inti,n,num;

inttop,bottom,mid;

intflag=1;

intloc=-1;

printf（"你想在多少个数中进行折半查找，请输入（1--20）:

"）;

scanf（"%d",&n）;

while（n<1||n>20）

{

printf（"你输入的数不正确，请重新输入:

\n"）;

printf（"你想在多少个数中进行折半查找，请输入（1--20）:

"）;

scanf（"%d",&n）;

}

printf（"请你输入一个整数a[1]:

"）;

scanf（"%d",&a[1]）;

i=2;

while（i<=n）

{

printf（"请你输入一个整数a[%d]:

",i）;

scanf（"%d",&a[i]）;

i++;

}

printf（"\n输出表列：

"）;

for（i=1;i<=n;i++）

{

printf（"%6d",a[i]）;

}

printf（"\n"）;

quick_sort（a,0,n）;

cout<<"排序后:

";

for（i=1;i<=n;i++）

{

printf（"%6d",a[i]）;

}

printf（"\n"）;

printf（"请你输入要查找的数:

"）;

scanf（"%d",&num）;

flag=1;

top=n;

bottom=1;

mid=（top+bottom）/2;

while（flag）

{

printf（"top=%d,bottom=%d,mid=%d,a[i]=%d\n",top,bottom,mid,mid,a[mid]）;

if（（num>a[top]）||（num

{

loc=-1;

flag=0;

}

elseif（a[mid]==num）

{

loc=mid;

printf（"找到数%6d的新位置%2d\n",num,loc）;

break;

}

elseif（a[mid]>num）

{

top=mid-1;

mid=（top+bottom）/2;

}

elseif（a[mid]

{

bottom=mid+1;

mid=（top+bottom）/2;

}

}

if（loc==-1）

{

printf（"%d这个数在表列中没有找到。

\n",num）;

}

}

实验截图：

查找到元素的情况：

未查找到元素情况：

[实验总结及思考]

普通的二分查找算法要求待查找表为有序表，适用范围不广，于是我对我的实验算法进行了改进，在二分查找算法中插入了快速排序算法，这样就可以对无序表进行指定元素查询。

虽然算法的整体耗时增加了，但大大增加了算法的实用性。

同时，我也从实验过程中收获了不少经验，领悟了不少新知识。

实验二：

动态规划

[实验目的]

1.理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。

2.熟练掌握典型的动态规划问题。

3.掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。

[实验内容]

编程实现讲过的例题：

最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线问题等。

本实验中的问题，设计出算法并编程实现。

[实验步骤]

最长公共子序列问题：

一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。

实验代码如下：

#include

usingnamespacestd;

constintX=100,Y=100;//串的最大长度

charresult[X+1];//用于保存结果

intcount=0;//用于保存公共最长公共子串的个数

intLcs_Length（stringx,stringy,intb[][Y+1],intxlen,intylen）

{

inti=0;

intj=0;

intc[X+1][Y+1];

for（i=0;i<=xlen;i++）

{

c[i][0]=0;

}

for（i=0;i<=ylen;i++）

{

c[0][i]=0;

}

for（i=1;i<=xlen;i++）

{

for（j=1;j<=ylen;j++）

{

if（x[i-1]==y[j-1]）

{

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

b[i][j]=1;

}

else

if（c[i-1][j]>c[i][j-1]）

{

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

b[i][j]=2;

}

else

if（c[i-1][j]

{

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

b[i][j]=3;

}

else

{

c[i][j]=c[i][j-1];//或者c[i][j]=c[i-1][j];

b[i][j]=4;

}

}

}

cout<<"计算最优值效果图如下所示：

"<

for（i=1;i<=xlen;i++）

{

for（j=1;j

{

cout<

}

cout<

}

returnc[xlen][ylen];

}

voidDisplay_Lcs（inti,intj,stringx,intb[][Y+1],intcurrent_len,intlcs_max_len）

{

if（i==0||j==0）

{

for（ints=0;s

{

cout<

}

cout<

count++;

return;

}

if（b[i][j]==1）

{

current_len--;

result[current_len]=x[i-1];

Display_Lcs（i-1,j-1,x,b,current_len,lcs_max_len）;

}

else

{

if（b[i][j]==2）

{

Display_Lcs（i-1,j,x,b,current_len,lcs_max_len）;

}

else

{

if（b[i][j]==3）

{

Display_Lcs（i,j-1,x,b,current_len,lcs_max_len）;

}

else

{

Display_Lcs（i,j-1,x,b,current_len,lcs_max_len）;

Display_Lcs（i-1,j,x,b,current_len,lcs_max_len）;

}

}

}

}

intmain（intargc,char*argv[]）

{

stringx="ABCBDAB";

stringy="BDCABA";

intxlen=x.length（）;

intylen=y.length（）;

intb[X+1][Y+1];

intlcs_max_len=Lcs_Length（x,y,b,xlen,ylen）;

cout<

Display_Lcs（xlen,ylen,x,b,lcs_max_len,lcs_max_len）;

cout<<"共有：

"<

return0;

}

实验截图：

[实验总结及思考]

由于有时并不是只有一个最长公共子序列，比如实验所取的两个序列"ABCBDAB"和"BDCABA"，就有3个最长公共子序列。

所以，对初始代码进行了改进，增加一个数组保存结果等。

实验三：

回溯算法

[实验目的]

熟练掌握回溯算法

[实验内容]

回溯算法的几种形式

[实验步骤]

1．8皇后问题

在一个８×８的棋盘里放置８个皇后，要求这8个皇后两两之间互相都不“冲突”。

实验代码如下：

#include

#include

#include

usingnamespacestd;

constintMAX_SIZE=100;

enumflag{blank='X',queen=1};

charChess[MAX_SIZE][MAX_SIZE];//棋盘图

intn;//解决n皇后问题

inttotal;//用于计摆放方式

voidInit（）

{//对棋牌进行初始化

for（inti=0;i

for（intj=0;j

Chess[i][j]=blank;

total=0;//初始时有零中摆放方式

}

boolJudge（intr,intc）

{//判断（r,c）位置是否可放置

inti,j;

for（i=r+1;i

if（Chess[i][c]==queen）

returnfalse;//说明c列上已有一皇后

for（i=c+1;i

if（Chess[r][i]==queen）

returnfalse;//说明r行上已有一皇后

for（i=r+1,j=c+1;（i

if（Chess[i][j]==queen）

returnfalse;//45度斜线上已有一皇后

for（i=r+1,j=c-1;（i=0）;i++,j--）

if（Chess[i][j]==queen）

returnfalse;//135度斜线上已有一皇后

returntrue;//排除四种情况后，说明（r,c）点可放置皇后

}

voidBacktrack（intk,intcnt）

{//回溯算法主程序

if（k<0||cnt==n）//棋牌摆放完毕or以摆满n后

{

if（cnt==n）

{

printf（"No.%d:

\n",++total）;

for（inti=0;i

{

for（intj=0;j

printf（"%c",Chess[i][j]）;

putchar（'\n'）;

}

putchar（'\n'）;

}

}

else

{

intr=k/n,c=k%n;

if（Judge（r,c））

{//可放置一皇后

Chess[r][c]=queen;

Backtrack（k-1,cnt+1）;

Chess[r][c]=blank;

}

Backtrack（k-1,cnt）;

}

}

intmain（）

{

timebt1,t2;

longkk;

cout<<"输入皇后个数:

";

while（cin>>n）

{

Init（）;

ftime（&t1）;

Backtrack（n*n-1,0）;

ftime（&t2）;

cout<<"计算"<

"<

kk=（t2.time-t1.time）*1000+t2.millitm-t1.millitm;

cout<<"本次回溯耗时:

"<

system（"PAUSE"）;

cout<<"输入皇后个数:

";

}

return0;

}

实验截图：

[实验总结及思考]

在算法中加入统计语句和计时语句，可以清晰地看到算法运行情况。

此算法有输入步骤，可以将8皇后问题扩展为n皇后问题。

当然，当n>10时，算法解太多，耗时长，意义不大。