《程序设计艺术与方法》课程实验报告.docx

《程序设计艺术与方法》课程实验报告.docx

《《程序设计艺术与方法》课程实验报告.docx》由会员分享，可在线阅读，更多相关《《程序设计艺术与方法》课程实验报告.docx（24页珍藏版）》请在冰点文库上搜索。

《程序设计艺术与方法》课程实验报告

《程序设计艺术与方法》课程实验报告

一

实验名称

STL的熟悉与使用

姓名

系院专业

信息工程系

班级

物联网一班

学号

实验日期

指导教师

成绩

一、实验目的和要求

1．

（1）掌握C++中STL的容器类使用。

（2）掌握C++中STL的算法类的使用。

二、实验预习内容

Vector,list可当作列表使用的数据结构，它们都是动态增长的。

1.vector表示一段连续的内存区域每个元素被顺序储存在这段内存中。

对vector的随即访问效率很高。

但是在任意位置而不是在vector末尾插入元素则效率很低，因为它需要把待插入元素的右边的每个元素都拷贝一遍。

类似的删除任一个而不是vector的最后一个元素效率低。

2list表示非连续的内存区域并通过一对指向首尾元素的指针双向进行遍历在list的任意位置插入和删除元素的效率都很高，指针必须被赋值但不需要用拷贝元素来实现移动，另一方面它对随机访问的支持并不好访问一个元素需要遍历中间的元素，另外每个元素还有俩不能给个指针的额外空间开销。

3泛型算法让编写一般化并可重复使用的算法，其效率与指针对某特定数据类型而设计的算法相同。

泛型即是指具有在多种数据类型上皆可操作的含义，与模板有些相似。

STL巨大而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。

三、实验项目摘要

1.练习vector和list的使用。

定义一个空的vector，元素类型为int，生成10个随机数插入到vector中，用迭代

器遍历vector并输出其中的元素值。

在vector头部插入一个随机数，用迭代器遍历vector

并输出其中的元素值。

用泛型算法find查找某个随机数，如果找到便输出，否则将此数

插入vector尾部。

用泛型算法sort将vector排序，用迭代器遍历vector并输出其中的元

素值。

删除vector尾部的元素，用迭代器遍历vector并输出其中的元素值。

将vector清

空。

定义一个list，并重复上述实验，并注意观察结果

2练习泛型算法的使用。

定义一个vector，元素类型为int，插入10个随机数，使用sort按升序排序，输出

每个元素的值，再按降叙排序，输出每个元素的值。

练习用find查找元素。

用min和

max找出容器中的最小元素个最大元素，并输出。

四、实验结果与分析（源程序及相关说明）

1.练习vector和list的使用：

#include

#include

#include

#include

#include

usingnamespacestd;

vectormyV;

boolsortup（intv1,intv2）

{

returnv1

}

intmain（intargc,char*argv[]）

{

srand（time（NULL））;//随机产生十个数

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

myV.push_back（rand（））;

sort（myV.begin（）,myV.end（）,sortup）;//用sort排序升序

vector:

:

iteratorit1;

for（it1=myV.begin（）;it1!

=myV.end（）;it1++）

{

cout<<（*it1）<

}

cout<

intmin=myV[0];

for（it1=myV.begin（）+1;it1!

=myV.end（）;it1++）

if（（*it1）

cout<<"最小元素为"<

intmax=myV[0];

for（it1=myV.begin（）;it1!

=myV.end（）;it1++）

if（（*it1）>max）max=（*it1）;

cout<<"最大元素为"<

cout<

intvalue=rand（）;

it1=find（myV.begin（）,myV.end（）,value）;

if（（*it1）==value）

cout<<"找到了这个随机数"<

else

cout<<"没有找到这个随机数"<

myV.insert（myV.end（）,value）;//数组中没有随机数,插入尾部

cout<<"插入尾部的随机数为"<

for（it1=myV.begin（）;it1!

=myV.end（）;it1++）

{

cout<<（*it1）<

}

cout<<"\n"<

//随机在vector头部插入一个随机数

intt=rand（）;//定义t;将一个随机数赋给t，插入到数组·头部

myV.insert（myV.begin（）,t）;

cout<<"插入头部的随机数为"<

for（it1=myV.begin（）;it1!

=myV.end（）;it1++）

{

cout<<（*it1）<

}

cout<

//删除尾部元素

myV.pop_back（）;

for（it1=myV.begin（）;it1!

=myV.end（）;it1++）

{

cout<<（*it1）<

}

cout<

myV.clear（）;//清空数组

if（myV.empty（））

{

cout<<"It'sempty!

"<

}

system（"PAUSE"）;//pressanykeytocontinue...

return0;

}

运行截图：

2练习泛型算法的使用：

#include

#include

//#inclued

usingnamespacestd;

typedeflistlin;

intvalue[]={2,4,6,1,8};

voidprint（lin&l）

{

inti;

lin:

:

iteratorlit;//定义一个迭代器

for（lit=l.begin（）;lit!

=l.end（）;lit++）

cout<<（*lit）<<"";//打印list中的元素

cout<

}

boolsortsp（intv1,intv2）//升序排序算法

{

returnv1>v2;

}

intmain（）{

linlin2;

lin2.push_front（3）;

lin2.push_front（4）;

lin2.insert（lin2.begin（）,value,value+5）;

cout<<"lin2内的元素为：

";

print（lin2）;

lin2.sort（）;

cout<<"排序后的lin2:

";

print（lin2）;

lin2.push_front（10）;//在list头部插入10

cout<<"在list头部插入10之后的结果：

";

print（lin2）;

lin2.remove（6）;

cout<<"删除一个数后的lin1:

";

print（lin2）;

system（"PAUSE"）;//pressanykeytocontineu...

return0;

}

运行截图：

二

实验名称

搜索算法的实验

姓名

系院专业

信息工程系

班级

物联网一班

学号

实验日期

指导教师

成绩

一、实验目的和要求

1．掌握宽度优先搜索算法。

2．掌握深度优先搜索算法。

二、实验预习内容

1宽度优先搜索算法：

又称广度优搜索。

是最简单的图的算法的原形。

其属于一种盲搜寻法，目的是系统地展开并检查图中的所有节点，以寻找结果。

换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。

2深度优先搜索算法：

它的目的是要达到被搜索结构的叶结点。

在一个HTML文件中，当一个超链被选择后，被连接的HTML文件将执行深度优先搜索，即在搜索其余的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。

当不再有其他超链可选择时，说明搜索已经结束。

三、实验项目摘要

1.将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。

2.八皇后问题：

在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有

的布棋方法。

上机运行并检验结果。

思考：

将此题推广到N皇后的情况，检验在N比较大的情况下，比方说N=16的时

候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。

3骑士游历问题：

在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，

输出一条符合上述要求的路径。

4倒水问题：

给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升

的水，如果可以，输出步骤，如果不可以，请输出NoSolution。

四、实验结果与分析（源程序及相关说明）

2，八皇后问题：

#include

/*声明常量N存储行和列*/

#defineN8

#defineNUM8

/*声明全局变量，h[N][N]控制盘格，H[N][N]控制输出，n[N]存储每一步的

*纵坐标，count用于计数。

*/

inth[N][N],n[N],H[N][N];

intcount=0;

/*声明函数voidtryit（int,int）尝试符合条件的方法*/

voidtryit（int,int）;

/*声明函数voidoutputArray（int[][N]）输出数组*/

voidoutputArray（int[][N]）;

main（）

{

intx=0,y=0,i,j;

/*初始化为零*/

for（i=0;i<=N-1;i++）

{

for（j=0;j<=N-1;j++）

h[i][j]=0;

}

tryit（x,y）;

printf（"//其他的布局略\n"）;

printf（"共有%d种布局.\n",92）;

return（0）;

}

/*定义函数voidtryit（int,int）尝试符合条件的方法*/

voidtryit（intx,inty）

{

inti,j;

if（count<=NUM）

{

/*重复时跳出递归*/

if（（H[0][0]==1&&H[1][4]==1&&H[2][7]==1&&H[3][5]==1&&H[4][2]==1&&H[5][6]==1&&H[6][1]==1&&H[7][3]==1）&&count!

=1）

{}

else

{

if（x>=0&&x<=N-1&&y>=0&&y<=N-1&&h[x][y]==0）

{

/*对与皇后在同一行、列、斜线上的点作出处理*/

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

{

if（h[x][j]==0）

h[x][j]=x+1;

if（h[j][y]==0）

h[j][y]=x+1;

if（x+j>=0&&x+j<=N-1&&y+j>=0&&y+j<=N-1&&h[x+j][y+j]==0）

h[x+j][y+j]=x+1;

if（x+j>=0&&x+j<=N-1&&y-j>=0&&y-j<=N-1&&h[x+j][y-j]==0）

h[x+j][y-j]=x+1;

if（x-j>=0&&x-j<=N-1&&y+j>=0&&y+j<=N-1&&h[x-j][y+j]==0）

h[x-j][y+j]=x+1;

if（x-j>=0&&x-j<=N-1&&y-j>=0&&y-j<=N-1&&h[x-j][y-j]==0）

h[x-j][y-j]=x+1;

}

/*对皇后处的点作出标志*/

h[x][y]=-x-1;

/*完成一种走法作出处理*/

if（x==7）

{

/*转换成输出的格式*/

for（i=0;i<=N-1;i++）

{

for（j=0;j<=N-1;j++）

{

if（h[i][j]<0）

H[i][j]=1;

else

H[i][j]=0;

}

}

count=count+1;

/*输出前几种情况*/

if（count<=NUM）

{

printf（"------布局%d------\n",count）;

outputArray（H）;

}

/*对下一种走法，清楚前一次的影响*/

for（i=0;i<=N-1;i++）

{

for（j=0;j<=N-1;j++）

{

if（h[i][j]==x||h[i][j]==-x||h[i][j]==-x-1）

h[i][j]=0;

}

}

/*递归，尝试另一种方法*/

tryit（x-1,n[x-1]+1）;

}

/*未走完一次，继续下一行*/

else

{

n[x]=y;

tryit（x+1,0）;

}

}

else

{

/*此路不通时，返回上一行，尝试下一种方法*/

if（y>7）

{

/*清楚前一次影响*/

for（i=0;i<=N-1;i++）

{

for（j=0;j<=N-1;j++）

{

if（h[i][j]==x||h[i][j]==-x）

h[i][j]=0;

}

}

/*分情况递归*/

if（x-1>=0）

tryit（x-1,n[x-1]+1）;

else

tryit（0,0）;

}

/*尝试下一格*/

else

tryit（x,y+1）;

}

}

}

}

/*定义函数voidoutputArray（int[][N]）输出数组*/

voidoutputArray（inth[][N]）

{

inti,j;

for（i=0;i<=N-1;i++）

{

for（j=0;j<=N-1;j++）

printf（"%d",h[i][j]）;

printf（"\n"）;

}

}

运行截图：

4.倒水问题：

#include"stdio.h"

intmain（）

{

intca,cb,cc,x,y;

while（scanf（"%d%d%d",&ca,&cb,&cc）!

=EOF）

{

if（cb==cc）

{printf（"fillB\n"）;

}

elseif（ca==cc）

{

printf（"fillA\n"）;

printf（"pourAB\n"）;

}

else

{

x=y=0;

if（ca

{

while

（1）

{if（y==0）

{

y=cb;

printf（"fillB\n"）;

}

if（y>ca-x）//如果b中的水大于a中的剩余容积，就把a灌满//

{

y-=ca-x;

x=ca;

printf（"pourBA\n"）;

}

else//如果b中的水小于a中的剩余容积，那么把b中的水全加入a//

{

x+=y;

y=0;

printf（"pourBA\n"）;

}

if（y==cc）//如果b中的水已经和cc相等，那就结束//

{

break;

}

if（ca==x）//如果a中的水满了，就把a倒空//

{

x=0;

printf（"emptyA\n"）;

}

}

}

else

{

while

（1）

{

if（x==0）

{

x=ca;

printf（"fillA\n"）;

}

if（x>cb-y）//如果a中的水大于b中的剩余容积，就把b灌满//

{

x-=cb-y;

y=cb;

printf（"pourAB\n"）;

}

else//如果a中的水小于b中的剩余容积，那么把a中的水全加入b//

{

y+=x;

x=0;

printf（"pourAB\n"）;

}

if（y==cc）//如果b中的水已经和cc相等，那就结束//

{

break;

}

if（y==cb）//如果b中的水满了，就把b倒空//

{

y=0;

printf（"emptyB\n"）;

}

}

}

}

printf（"success\n"）;

}

return0;

}

运行截图：

三

实验名称

计算几何算法的实现

姓名

系院专业

信息工程系

班级

物联网一班

学号

实验日期

指导教师

成绩

一、实验目的和要求

1．理解线段的性质、叉积和有向面积。

2．掌握寻找凸包的算法。

3．综合运用计算几何和搜索中的知识求解有关问题。

二、实验预习内容

凸包：

是一组点集中的子集，这一子集形成的凸多边形可以将点集中所有的点都围住，并且这一凸边形的面积是最小的。

一种寻找凸包的算法：

打包法

首先，我们找出点集中最下方的点，如果这样的点不止一个，就选用

最左边的点（如P0）。

显然，这个点（P0）是凸包子集中的一个点。

可以设想在P0处拴了一根

皮筋的一端，另一端放在和P0成水平位置的右侧。

现在，将皮筋，沿逆时针方向转动，首先会

碰到P1，这样就找到了另一个凸包子集中的点。

以P1为中心，做和P0一样的事，会发现，我

们将碰到P3，又一个凸包的点。

我们可以一直这样做下去，直到再一次遇到P0，凸包就被找出

来了。

具体而言，在第一次找到P0点之后，以P0为每个矢量的起点，其它的点为矢量的终点，

来比较任意两个矢量的转角，就可以对余下的点进行按极角排序

三、实验项目摘要

1将讲义第三章第三节中的凸包代码上机运行并检验结果。

2完成讲义第三章的课后习题，上机运行并检验结果。

3思考：

判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的

端点重合，思考这样的情况。

4房间最短路问题：

给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。

房间的边界

固定在x=0,x=10,y=0和y=10。

起点和重点固定在（0,5）和（10,5）。

房间里还有0到18个

墙，每个墙有两个门。

输入给定的墙的个数，每个墙的x位置和两个门的y坐标区间，

输出最短路的长度

四、实验结果与分析（源程序及相关说明）

3.思考：

用跨立方法，跨立的含义是：

如果一条线段的一个端点在一条直线的一边，另一个端点在这条直线的另一端，我们就说这条线段跨立在这条直线上。

线段相交满足且只需满足如下两个条件就可以了：

1两条线段相互跨立；2一条线段的一个端点在另一条线段上。

如果两线段相交，则两线段必然相互跨立对方。

若p1p2跨立p3p4，则矢量（p1–p3）和（p2-p1）位于矢量（p4–p3）的两侧，即（p1–p3）×（p4-p3）*（p2–p3）×（p4–p3）<0。

上式可改写成（p1–p3）×（p4-p3）*（p4–p3）×（p2–p3）>0。

当（p1–p3）×（p4–p3）=0时，说明（p1–p3）和（p4–p3）共线，但是因为已经通过快速排斥试验，所以p1一定在线段p3p4上；同理，（p4–p3）×（p2–p3）=0说明p2一定在p3p4上。

所以判断p1p2跨立Q1Q2的依据是：

（p1–p3）×（p4–p3）*（p4–p3）×（p2–p3）>=0。

同理判断Q1Q2跨立P1P2的依据是：

（p3-p1）×（p2-p1）*（p2-p1）×（p4-p1）>=0。

代码中函数boolsegment_intersect（）用于判断p1、p2构成的线段和p3、p4构成的线段是否相交。

可以看出共五种情况两线段是相交的，反之就输出“ThetwoareNotintersected!

”

4.房间最短路问题：

#include

#include

#include

innclude

usingnamespacestd;

typedefpairPOINT;//线段

doubledirection（POINTp,POINTp1,POINTp2）{

POINTv1,v2;

v1.first=p2.first-p1.first;

v1.second=p2.second-p1.first;

v2.first=p1.first-p.first;

v2.second=p1.second-p.second;

returnv1.first*v2.second-v1.second*v2.second;}

boolon_segment（POINTp,POINTp1,POINTp2）{

doublemin_x=p1.first

p1.first:

p2.first;

max_x=p1.first>p2.first?

p1.first:

p2.first;

doublemin_y=p1.second

p1.second:

p2.second;

doublemax_y=p1.second>p2.second?