太原理工大学算法设计与分析实验报告.docx

太原理工大学算法设计与分析实验报告.docx

《太原理工大学算法设计与分析实验报告.docx》由会员分享，可在线阅读，更多相关《太原理工大学算法设计与分析实验报告.docx（14页珍藏版）》请在冰点文库上搜索。

太原理工大学算法设计与分析实验报告

本科实验报告

课程名称：

算法设计与分析

实验项目：

分治法合并排序

贪心法作业调度

动态规划法求多段图问题

回溯法求n皇后问题

实验地点：

致远楼B503

专业班级：

学号：

学生姓名：

指导教师：

2017年3月18日

实验1分治法合并排序

一、实验目的

1.掌握合并排序的基本思想

2.掌握合并排序的实现方法

3.学会分析算法的时间复杂度

4.学会用分治法解决实际问题

二、实验内容

随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。

三、实验环境

Window10;惠普笔记本；Devcpp

4、算法描述和程序代码

#include

#include

#include

#include

usingnamespacestd;

#definerandom（x）（rand（）%x）;

inta[10];//合并排序函数。

voidMerge（intleft,intmid,intright）{

intt[11];

inti=left,j=mid+1,k=0;

while（（i<=mid）&&（j<=right））{

if（a[i]<=a[j]）

t[k++]=a[i++];

else

t[k++]=a[j++];

}

while（i<=mid）

t[k++]=a[i++];

while（j<=right）

t[k++]=a[j++];

for（i=0,k=left;k<=right;）

a[k++]=t[i++];

}//分划函数，并且调用合并函数。

voidMergeSort（intleft,intright）{

if（left

intmid=（（left+right）/2）;

MergeSort（left,mid）;

MergeSort（mid+1,right）;

Merge（left,mid,right）;//调用合并函数。

}

}

intmain（）{

inti;

cout<<"排序前的数组为：

";

for（i=0;i<10;i++）{

a[i]=random（100）;//调用random函数，产生10个0-100的随机数。

cout<

}

cout<

MergeSort（0,9）;

cout<<"排序后的数组为：

";

for（i=0;i<10;i++）{

cout<

}

getchar（）;

return0;

}

五、实验结果截图

六、实验总结

通过编写这个程序，我进一步了解了分株算法的思想，在实际运用过程当中，尤其是在算法编写方面相对来说比较简单，实现起来较为容易。

实验2贪心法作业调度

一、实验目的

1.掌握贪心算法的基本思想

2.掌握贪心算法的典型问题求解

3.进一步多级调度的基本思想和算法设计方法

4.学会用贪心法分析和解决实际问题

二、实验内容

设计贪心算法实现作业调度，要求按作业调度顺序输出作业序列。

如已知n=8，效益p=（35, 30, 25, 20, 15, 10, 5, 1），时间期限 d=（4, 2, 4, 5, 6, 4, 5, 7），求该条件下的最大效益。

三、实验环境

Window10;惠普笔记本；Devcpp

四、算法描述和程序代码

#include

usingnamespacestd;

constintWork[8]={45,30,28,25,23,15,10,1};//所有作业按收益从大到小排序

constintmaxTime[8]={4,7,3,2,4,6,7,5};

classHomeWork{

private:

intres[8];

boolflag[8];

intmaxReap;

public:

voiddealWith（）{

//遍历所有作业:

inti;

for（i=0;i<8;i++）{

intTime=maxTime[i]-1;

if（!

flag[Time]）{

//如果最大期限那一天还未安排作业,则将当前作业安排在所允许的最大期限那天

res[Time]=Work[i];

flag[Time]=true;

}

else{

//如果当前作业所允许的最大期限那一天已经安排的其他作业,就向前搜索空位,将该作业安排进去

for（intj=Time-1;j>=0;j--）

if（!

flag[j]）{

res[j]=Work[i];

flag[j]=true;

break;

}

}

}

cout<<"作业完成顺序为:

";

for（i=0;i<7;i++）{

cout<

}

cout<

cout<

";

intj;

for（j=0;j<7;j++）

maxReap+=res[j];

cout<

}

HomeWork（）{

inti;

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

flag[i]=false;

maxReap=0;

}

};

intmain（）{

HomeWorka=HomeWork（）;

a.dealWith（）;

getchar（）;

return0;

}

五、实验结果截图

六、实验总结

通过这个实验让我知道了闫新算法在实际当中的运用，也让我了解到了贪心算法的便捷以及贪心算法的实用性

实验3动态规划法求多段图问题

一、实验目的

1.掌握动态规划算法的基本思想

2.掌握多段图的动态规划算法

3.选择邻接表或邻接矩阵方式来存储图

4.分析算法求解的复杂度

二、实验内容

设G=（V,E）是一个带权有向图，其顶点的集合V被划分成k>2个不相交的子集Vi，1

图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。

求一条s到t的最短路线。

参考课本P124图7-1中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。

三、实验环境

Window10;惠普笔记本；Devcpp

四、算法描述和程序代码

#include

intV[50][50];

inta[50],b[20];

intstatick,n,m;

voidcreateGraph（）

{

inti,j,t,s;

printf（"请输入结点数：

"）;

scanf（"%d",&n）;

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

for（j=0;j<=n;j++）

V[i][j]=0;//初始化V[i][j]=0,表示两结点没有边相连

printf（"输入图的层数：

"）;

scanf（"%d",&k）;

printf（"请输入每层的结点数的最大编号：

"）;

a[0]=0;

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

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

printf（"请输入边数：

"）;

scanf（"%d",&m）;

printf（"请输入结点之间的关系（如：

结点i和结点j的距离为s，则输入i,j,s）\n"）;

for（t=1;t<=m;t++）

{

scanf（"%d%d%d",&i,&j,&s）;

V[i][j]=s;

}

}

intBackward（）//向后求解法

{

inti,j,t,r;

for（i=a[1]+1;i<=a[2];i++）//把第二层每个结点i与第一层结点s的边距赋值给V[i][i]

V[i][i]=V[1][i];

for（r=2;r

for（i=a[r-1]+1;i<=a[r];i++）//遍历第r层的每个结点i与第（r+1）层结点j之间的边距,选择此刻最优解

for（j=a[r]+1;j<=a[r+1];j++）

{

if（V[i][j]!

=0&&V[j][j]==0）//第一次把此刻路径长度赋给V[j][j]

V[j][j]=V[i][i]+V[i][j];

elseif（V[i][j]!

=0&&V[j][j]!

=0）

{

if（（V[i][i]+V[i][j]）

V[j][j]=V[i][i]+V[i][j];

}

}

j=-1;

b[4]=0;

for（r=k-1;r>=2;r--）

for（i=a[r]+1;i<=a[r+1];i++）

{

if（b[r]==j）

break;

for（j=a[r-1]+1;j<=a[r];j++）

if（（V[i][i]-V[j][i]）==V[j][j]）

{

b[r]=j;

break;

}

}

returnV[n][n];

}

intForward（）//向前求解法

{

inti,j,t,r;

for（i=a[k-2]+1;i<=a[k-1];i++）//把第二层每个结点i与第一层结点s的边距赋值给V[i][i]

V[i][i]=V[i][a[k]];

for（r=k-1;r>1;r--）//向前逐层求解

for（j=a[r-1]+1;j<=a[r];j++）//遍历第r层的每个结点i与第（r-1）层结点j之间的边距,选择此刻最优解

for（i=a[r-2]+1;i<=a[r-1];i++）

{

if（V[i][j]!

=0&&V[i][i]==0）//第一次把此刻路径长度赋给V[j][j]

V[i][i]=V[j][j]+V[i][j];

elseif（V[i][j]!

=0&&V[i][i]!

=0）

{

if（（V[j][j]+V[i][j]）

V[i][i]=V[j][j]+V[i][j];

}

}

for（r=2;r<=k-1;r++）

for（i=a[r-2]+1;i<=a[r-1];i++）

{

for（j=a[r-1]+1;j<=a[r];j++）

if（（V[i][i]-V[i][j]）==V[j][j]）

{

b[r]=j;

break;

}

i=j;

r++;

}

returnV[1][1];

}

intmain（）

{

inti,j,r,sp;

createGraph（）;

b[1]=1;

b[k]=n;

//sp=Forward（）;

sp=Backward（）;

printf（"最短路径长度为：

%d\n",sp）;

printf（"最短路径为：

"）;

printf（"%d",b[1]）;

for（i=2;i<=k;i++）

printf（"->%d",b[i]）;

return0;

}

五、实验结果截图

6、实验总结

这个实验让我从中懂得了动态规划算法的核心，更加收敛的运用动态规划算法秋节各类问题，但动态规划算法最重要的还是方程的选择，这个在实际运用中相当重要。

实验4回溯法求n皇后问题

一、实验目的

1.掌握回溯算法的基本思想

2.通过n皇后问题求解熟悉回溯法

3.使用蒙特卡洛方法分析算法的复杂度

二、实验内容

要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击”。

两个皇后位于棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。

现在要找出使得棋盘上8个皇后互不攻击的布局。

三、实验环境

Window10;惠普笔记本；Devcpp

四、算法描述和程序代码

#include

#include

usingnamespacestd;

#defineN8

intres[100][8];

intcountRes=0;

boolPlace（intk,inti,int*x）{

for（intj=0;j

if（x[j]==i||abs（x[j]-i）==abs（j-k））

returnfalse;

returntrue;

}

voidNQueen（intk,intn,int*x）{

for（inti=0;i

if（Place（k,i,x））{

x[k]=i;

if（k==n-1）{

for（i=0;i

res[countRes][i]=x[i];

cout<

}

countRes++;

cout<

}else{

NQueen（k+1,n,x）;

}

}

}

voidNQueen（intn,int*x）{

NQueen（0,n,x）;

}

intmain（）{

intx[N];

for（inti=0;i

*（x+i）=-10;

NQueen（N,x）;

cout<

charshow;

cout<<"是否显示图示?

（Y/N）"<

cin>>show;

if（show=='Y'||show=='y'）{

for（intn=0;n

cout<<"第"<

"<

for（inti=0;i

for（intj=0;j

if（res[n][i]==j）

cout<<"Q"<<"\t";

else

cout<<"*"<<"\t";

}

cout<

}

}

}

return0;

}

五、实验结果截图

六、实验总结

在n皇后问题中可以看出回溯算法求出的是这个问题的所有解，而不是单纯地求出了这个问题所产生的最优解，这样对于我们在实际运用方面十分实用。