程序设计艺术与方法课程实验报告.doc

《程序设计艺术与方法课程实验报告.doc》由会员分享，可在线阅读，更多相关《程序设计艺术与方法课程实验报告.doc（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、/程序设计艺术与方法课程实验报告一实验名称 STL 的熟悉与使用姓 名系院专业信息工程 系班 级物联网一 班学 号实验日期指导教师成 绩一、实验目的和要求一、实验目的和要求 1 （1）掌握 C+中 STL 的容器类使用。 （2）掌握 C+中 STL 的算法类的使用。二、实验预习内容二、实验预习内容Vector,list 可当作列表使用的数据结构，它们都是动态增长的。 1.vector 表示一段连续的内存区域每个元素被顺序储存在这段内存中。对 vector 的随即访 问效率很高。但是在任意位置而不是在 vector 末尾插入元素则效率很低，因为它需要把待插 入元素的右边的每个元素都拷贝一遍。类似

2、的删除任一个而不是 vector 的最后一个元素效率 低。 2list 表示非连续的内存区域并通过一对指向首尾元素的指针双向进行遍历在 list 的任意位 置插入和删除元素的效率都很高，指针必须被赋值但不需要用拷贝元素来实现移动，另一方 面它对随机访问的支持并不好访问一个元素需要遍历中间的元素，另外每个元素还有俩不能 给个指针的额外空间开销。 3 泛型算法让编写一般化并可重复使用的算法，其效率与指针对某特定数据类型而设计的算 法相同。泛型即是指具有在多种数据类型上皆可操作的含义，与模板有些相似。STL 巨大而 且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其 中

3、算法是泛型的，不与任何特定数据结构或对象类型系在一起。三、实验项目摘要三、实验项目摘要 1. 练习vector 和list 的使用。 定义一个空的vector，元素类型为int，生成10 个随机数插入到vector 中，用迭代 器遍历vector 并输出其中的元素值。在vector 头部插入一个随机数，用迭代器遍历vector 并输出其中的元素值。用泛型算法find 查找某个随机数，如果找到便输出，否则将此数 插入vector 尾部。用泛型算法sort 将vector 排序，用迭代器遍历vector 并输出其中的元 素值。删除vector 尾部的元素，用迭代器遍历vector 并输出其中的元素

4、值。将vector 清 空。定义一个list，并重复上述实验，并注意观察结果 2 练习泛型算法的使用。 定义一个vector，元素类型为int，插入10 个随机数，使用sort 按升序排序，输出/每个元素的值，再按降叙排序，输出每个元素的值。练习用find 查找元素。用min 和 max 找出容器中的最小元素个最大元素，并输出。四、实验结果与分析（源程序及相关说明）四、实验结果与分析（源程序及相关说明） 1. 练习vector 和list 的使用：#include #include #include#include #include using namespace std;vector myV

5、;bool sortup(int v1,int v2)return v1:iterator it1;for (it1=myV.begin();it1!=myV.end();it1+)coutmax)max=(*it1);cout#include/#incluedusing 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.pu

6、sh_front(3); lin2.push_front(4); lin2.insert(lin2.begin(),value,value+5);cout/*声明常量 N 存储行和列*/#define N 8#define NUM 8/*声明全局变量，hNN控制盘格，HNN控制输出，nN存储每一步的*纵坐标，count 用于计数。*/int hNN,nN,HNN;/int count=0;/*声明函数 void tryit(int,int)尝试符合条件的方法*/void tryit(int,int);/*声明函数 void outputArray(intN)输出数组*/void outputA

7、rray(intN);main()int x=0,y=0,i,j;/*初始化为零*/for(i=0;i=0i=0)tryit(x-1,nx-1+1);elsetryit(0,0);/*尝试下一格*/elsetryit(x,y+1);/*定义函数 void outputArray(intN)输出数组*/void outputArray(int hN)int i,j;for(i=0;ica-x) /如果 b 中的水大于 a 中的剩余容积，就把 a 灌满/y-=ca-x;x=ca;printf(“pour B An“);else /如果 b 中的水小于 a 中的剩余容积，那么把 b 中的水全加入 a

8、/x+=y;y=0;printf(“pour B An“);if(y=cc) /如果 b 中的水已经和 cc 相等，那就结束/break; /if(ca=x) /如果 a 中的水满了，就把 a 倒空/x=0;printf(“empty An“);elsewhile(1)if(x=0)x=ca;printf(“fill An“);if(xcb-y) /如果 a 中的水大于 b 中的剩余容积，就把 b 灌满/x-=cb-y;y=cb;printf(“pour A Bn“);else /如果 a 中的水小于 b 中的剩余容积，那么把 a 中的水全加入 b/y+=x;x=0;printf(“pour

9、A Bn“);if(y=cc) /如果 b 中的水已经和 cc 相等，那就结束/break;if(y=cb) /如果 b 中的水满了，就把 b 倒空/y=0;printf(“empty Bn“);printf(“successn“);return 0;运行截图：/三实验名称 计算几何算法的实现姓 名系院专业信息工程 系班 级物联网一 班学 号实验日期指导教师成 绩一、实验目的和要求一、实验目的和要求 1理解线段的性质、叉积和有向面积。 2掌握寻找凸包的算法。 3综合运用计算几何和搜索中的知识求解有关问题。二、实验预习内容二、实验预习内容 凸包：是一组点集中的子集，这一子集形成的凸多边形可以将点

10、集中所有的点都围住，并且 这一凸边形的面积是最小的。 一种寻找凸包的算法：打包法 首先，我们找出点集中最下方的点，如果这样的点不止一个，就选用 最左边的点（如P0）。显然，这个点（P0）是凸包子集中的一个点。可以设想在P0 处拴了一根 皮筋的一端，另一端放在和P0 成水平位置的右侧。现在，将皮筋，沿逆时针方向转动，首先会 碰到P1，这样就找到了另一个凸包子集中的点。以P1 为中心，做和P0 一样的事，会发现，我 们将碰到P3，又一个凸包的点。我们可以一直这样做下去，直到再一次遇到P0，凸包就被找出 来了。具体而言，在第一次找到P0 点之后，以P0 为每个矢量的起点，其它的点为矢量的终点， 来比

11、较任意两个矢量的转角，就可以对余下的点进行按极角排序三、实验项目摘要三、实验项目摘要 1 将讲义第三章第三节中的凸包代码上机运行并检验结果。 2完成讲义第三章的课后习题，上机运行并检验结果。 3思考： 判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的 端点重合，思考这样的情况。 4房间最短路问题： 给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界 固定在x=0,x=10,y=0 和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0 到18 个 墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间， 输出最短

12、路的长度/四、实验结果与分析（源程序及相关说明）四、实验结果与分析（源程序及相关说明）3.思考：用跨立方法，跨立的含义是：如果一条线段的一个端点在一条直线的一边，另一个 端点在这条直线的另一端，我们就说这条线段跨立在这条直线上。线段相交满足且 只需满足如下两个条件就可以了：1 两条线段相互跨立；2 一条线段的一个端点在 另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若 p1p2 跨立 p3p4 ，则矢量 ( p1 p3 ) 和( p2 - p1 )位于矢量( p4 p3 )的两侧，即( p1 p3） ( p4- p3 ) * ( p2 p3 ) ( p4 p3 ) 0。当( p1 p

13、3 ) ( p4p3 ) = 0 时，说明( p1 p3 ) 和 ( p4 p3 )共线，但是因为已经通过快速排斥试验，所以 p1 一定在线段 p3p4 上；同理，( p4 p3 ) (p2 p3 ) = 0 说明 p2 一定在 p3p4 上。所以判断 p1p2 跨立 Q1Q2 的依据是：( p1 p3 ) ( p4 p3 ) * ( p4 p3 ) ( p2p3 ) = 0。同理判断 Q1Q2 跨立 P1P2 的依据是：( p3 - p1 ) ( p2 - p1 ) * ( p2 - p1 ) ( p4 - p1 ) = 0。代码中函数 bool segment_intersect()用于判

14、断 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.

15、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_xif(d=0 if(d= =0 return false; void find_convex_

16、hull(vector int k=0; for(int i=0;iconvex_hull; doconvex_hull.push_back(point0); startPoint=point0; point.erase(point.begin(); sort(point.begin(),point.end(),sortByPolorAngle);if(point0=convex_hull0)break; point.push_back(convex_hullconvex_hull.size()-1); while(1); for(int j=0;j pv; double x,y; int i; cout：“xy;pv.push_back(make_pair(x,y);coutendl; find_convex_hull(pv); system(“Pause“); return 0;运行截图：/