《程序设计艺术与方法》课程实验报告 本文关键词：设计艺术，课程，实验，程序，方法
《程序设计艺术与方法》课程实验报告 本文简介：《程序设计艺术与方法》课程实验报告一实验名称STL的熟悉与使用姓名系院专业信息工程系班级物联网一班学号实验日期指导教师成绩一、实验目的和要求1．（1）掌握C++中STL的容器类使用。（2）掌握C++中STL的算法类的使用。二、实验预习内容Vector,list可当作列表使用的数据结构，它们都是动态增
《程序设计艺术与方法》课程实验报告 本文内容：
《程序设计艺术与方法》课程实验报告
一
实验名称
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
using
namespace
std;
vector
myV;
bool
sortup(int
v1,int
v2)
{
return
v1::iterator
it1;
for
(it1=myV.begin();it1!=myV.end();it1++)
{
coutmax)max=(*it1);
cout
#include
//#inclued
using
namespace
std;
typedef
list
lin;
int
value[]={2,4,6,1,8};
void
print(lin
lin::iterator
lit;//定义一个迭代器
for(lit=l.begin();lit!=l.end();lit++)
coutv2;
}
int
main(){
lin
lin2;
lin2.push_front(3);
lin2.push_front(4);
lin2.insert(lin2.begin(),value,value+5);
cout
/*声明常量N存储行和列*/
#define
N
8
#define
NUM
8
/*声明全局变量，h[N][N]控制盘格，H[N][N]控制输出，n[N]存储每一步的纵坐标，count用于计数。/
int
h[N][N],n[N],H[N][N];
int
count=0;
/*声明函数void
tryit(int,int)尝试符合条件的方法*/
void
tryit(int,int);
/*声明函数void
outputArray(int[][N])输出数组*/
void
outputArray(int[][N]);
main()
{
int
x=0,y=0,i,j;
/*初始化为零*/
for(i=0;i=0i=0)
tryit(x-1,n[x-1]+1);
else
tryit(0,0);
}
/*尝试下一格*/
else
tryit(x,y+1);
}
}
}
}
/*定义函数void
outputArray(int[][N])输出数组*/
void
outputArray(int
h[][N])
{
int
i,j;
for(i=0;ica-x)
//如果b中的水大于a中的剩余容积，就把a灌满//
{
y-=ca-x;
x=ca;
printf(“pour
B
A/n“);
}
else
//如果b中的水小于a中的剩余容积，那么把b中的水全加入a//
{
x+=y;
y=0;
printf(“pour
B
A/n“);
}
if(y==cc)
//如果b中的水已经和cc相等，那就结束//
{
break;
}
if(ca==x)
//如果a中的水满了，就把a倒空//
{
x=0;
printf(“empty
A/n“);
}
}
}
else
{
while(1)
{
if(x==0)
{
x=ca;
printf(“fill
A/n“);
}
if(x>cb-y)
//如果a中的水大于b中的剩余容积，就把b灌满//
{
x-=cb-y;
y=cb;
printf(“pour
A
B/n“);
}
else
//如果a中的水小于b中的剩余容积，那么把a中的水全加入b//
{
y+=x;
x=0;
printf(“pour
A
B/n“);
}
if(y==cc)
//如果b中的水已经和cc相等，那就结束//
{
break;
}
if(y==cb)
//如果b中的水满了，就把b倒空//
{
y=0;
printf(“empty
B/n“);
}
}
}
}
printf(“success/n“);
}
return
0;
}
运行截图：
三
实验名称
计算几何算法的实现
姓
名
系院专业
信息工程系
班
级
物联网一班
学
号
实验日期
指导教师
成
绩
一、实验目的和要求
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
)
=
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。代码中函数bool
segment_intersect()用于判断p1、p2构成的线段和p3、p4构成的线段是否相交。可以看出共五种情况两线段是相交的，反之就输出“The
two
are
Not
intersected!”
4.房间最短路问题：
#include
#include
#include
innclude
using
namespace
std;
typedef
pair
POINT;//线段
double
direction(POINT
p,POINT
p1,POINT
p2){
POINT
v1,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;
return
v1.first*v2.second-v1.second*v2.second;}
bool
on_segment(POINT
p,POINT
p1,POINT
p2){
double
min_x=p1.firstp2.first?p1.first:p2.first;
double
min_y=p1.secondp2.second?p1.second:p2.second;
if(p.first>=min_x
if(d==0
if(d=
=0
return
false;
}
void
find_convex_hull(vector
int
k=0;
for(int
i=0;iconvex_hull;
do{
convex_hull.push_back(point[0]);
startPoint=point[0];
point.erase(point.begin());
sort(point.begin(),point.end(),sortByPolorAngle);
if(point[0]==convex_hull[0])break;
point.push_back(convex_hull[convex_hull.size()-1]);
}while(1);
for(int
j=0;j
pv;
double
x,y;
int
i;
cout：“>x>>y;
pv.push_back(make_pair(x,y));
}
cout< find_convex_hull(pv); system(“Pause“); return 0; } 运行截图：