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

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

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

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

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

4、注意观察结果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 v1v2;in

5、t main(int argc,char*argv)srand(time(NULL);/随机产生十个数for(int i=0;i10;i+)myV.push_back(rand();sort(myV.begin(),myV.end(),sortup);/用 sort 排序升序vector:iterator it1;for(it1=myV.begin();it1!=myV.end();it1+)cout(*it1)setw(6);/打印数组coutendl;int min=myV0;for(it1=myV.begin()+1;it1!=myV.end();it1+)if(*it1)min)min

6、=(*it1);cout最小元素为 minmax)max=(*it1);cout最大元素为 maxendl;coutendl;int value=rand();it1=find(myV.begin(),myV.end(),value);if(*it1)=value)cout找到了这个随机数endl;elsecout没有找到这个随机数endl;myV.insert(myV.end(),value);/数组中没有随机数,插入尾部cout插入尾部的随机数为valueendl;for(it1=myV.begin();it1!=myV.end();it1+)cout(*it1)setw(6);coutn

7、endl;/随机在 vector 头部插入一个随机数int t=rand();/定义 t;将一个随机数赋给 t，插入到数组头部myV.insert(myV.begin(),t);cout插入头部的随机数为 tendl;for(it1=myV.begin();it1!=myV.end();it1+)cout(*it1)setw(6);coutendl;/删除尾部元素myV.pop_back();for(it1=myV.begin();it1!=myV.end();it1+)cout(*it1)setw(6);coutendl;myV.clear();/清空数组if(myV.empty()cout

8、 Its empty!endl;system(PAUSE);/press any key to continue.return 0;运行截图：2 练习泛型算法的使用：#include#include/#incluedusing namespace std;typedef list lin;int value=2,4,6,1,8;void print(lin&l)int i;lin:iterator lit;/定义一个迭代器for(lit=l.begin();lit!=l.end();lit+)cout(*lit);/打印 list 中的元素coutv2;int main()lin lin2;l

9、in2.push_front(3);lin2.push_front(4);lin2.insert(lin2.begin(),value,value+5);coutlin2 内的元素为：;print(lin2);lin2.sort();cout排序后的 lin2:;print(lin2);lin2.push_front(10);/在 list 头部插入 10cout在 list 头部插入 10 之后的结果：;print(lin2);lin2.remove(6);cout删除一个数后的 lin1:;print(lin2);system(PAUSE);/press any key to contin

10、eu.return 0;运行截图：二实验名称搜索算法的实验信息工程系物联网一班姓名系院专业班级学号实验日期一、实验目的和要求一、实验目的和要求1掌握宽度优先搜索算法。2掌握深度优先搜索算法。指导教师成绩二、实验预习内容二、实验预习内容1 宽度优先搜索算法：又称广度优搜索。是最简单的图的算法的原形。其属于一种盲搜寻法，目的是系统地展开并检查图中的所有节点，以寻找结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。2 深度优先搜索算法：它的目的是要达到被搜索结构的叶结点。在一个 HTML 文件中，当一个超链被选择后，被连接的HTML 文件将执行深度优先搜索，即在搜索其余的

11、超链走到不能再深入为止，然后返回到某一个 HTML 文件，再继续选择该 HTML 文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。三、实验项目摘要三、实验项目摘要1.将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。2.八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。思考：将此题推广到N 皇后的情况，检验在N 比较大的情况下，比方说N=16 的时候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。3骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出

12、一条符合上述要求的路径。4 倒水问题：给定2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L 升的水，如果可以，输出步骤，如果不可以，请输出 No Solution。四、实验结果与分析（源程序及相关说明）四、实验结果与分析（源程序及相关说明）2，八皇后问题：#include/*声明常量 N 存储行和列*/#define N 8#define NUM 8/*声明全局变量，hNN控制盘格，HNN控制输出，nN存储每一步的*纵坐标，count 用于计数。*/int hNN,nN,HNN;int count=0;/*声明函数 void tryit(int,int)尝试符合条件的方法*/v

13、oid tryit(int,int);/*声明函数 void outputArray(intN)输出数组*/void outputArray(intN);main()int x=0,y=0,i,j;/*初始化为零*/for(i=0;i=N-1;i+)for(j=0;j=N-1;j+)hij=0;tryit(x,y);printf(/其他的布局略n);printf(共有%d 种布局.n,92);return(0);/*定义函数 void tryit(int,int)尝试符合条件的方法*/void tryit(int x,int y)int i,j;if(count=0&x=0&y=N-1&hxy

14、=0)/*对与皇后在同一行、列、斜线上的点作出处理*/for(j=0;j=0&x+j=0&y+j=0&x+j=0&y-j=0&x-j=0&y+j=0&x-j=0&y-j=N-1&hx-jy-j=0)hx-jy-j=x+1;/*对皇后处的点作出标志*/hxy=-x-1;/*完成一种走法作出处理*/if(x=7)/*转换成输出的格式*/for(i=0;i=N-1;i+)for(j=0;j=N-1;j+)if(hij0)Hij=1;elseHij=0;count=count+1;/*输出前几种情况*/if(count=NUM)printf(-布局%d-n,count);outputArray(H);

15、/*对下一种走法，清楚前一次的影响*/for(i=0;i=N-1;i+)for(j=0;j7)/*清楚前一次影响*/for(i=0;i=0)tryit(x-1,nx-1+1);elsefor(j=0;j=N-1;j+)if(hij=x|hij=-x)hij=0;nx=y;tryit(x+1,0);tryit(0,0);/*尝试下一格*/elsetryit(x,y+1);/*定义函数 void outputArray(intN)输出数组*/void outputArray(int hN)运行截图：4.倒水问题：#includestdio.hint main()int ca,cb,cc,x,y;w

16、hile(scanf(%d%d%d,&ca,&cb,&cc)!=EOF)if(cb=cc)printf(fill Bn);else if(ca=cc)printf(fill An);printf(pour A Bn);elsex=y=0;int i,j;for(i=0;i=N-1;i+)for(j=0;j=N-1;j+)printf(%d,hij);printf(n);if(caca-x)/如果 b 中的水大于 a 中的剩余容积，就把 a 灌满/y-=ca-x;x=ca;printf(pour B An);else/如果 b 中的水小于 a 中的剩余容积，那么把 b 中的水全加入 a/x+=y

17、;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 A Bn);if(y=cc)/如果 b

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

19、先，我们找出点集中最下方的点，如果这样的点不止一个，就选用最左边的点（如P0）。显然，这个点（P0）是凸包子集中的一个点。可以设想在P0 处拴了一根皮筋的一端，另一端放在和P0 成水平位置的右侧。现在，将皮筋，沿逆时针方向转动，首先会碰到P1，这样就找到了另一个凸包子集中的点。以P1 为中心，做和P0 一样的事，会发现，我们将碰到P3，又一个凸包的点。我们可以一直这样做下去，直到再一次遇到P0，凸包就被找出来了。具体而言，在第一次找到P0 点之后，以P0 为每个矢量的起点，其它的点为矢量的终点，来比较任意两个矢量的转角，就可以对余下的点进行按极角排序三、实验项目摘要三、实验项目摘要1 将讲义第

20、三章第三节中的凸包代码上机运行并检验结果。2完成讲义第三章的课后习题，上机运行并检验结果。3思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况。4房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在x=0,x=10,y=0 和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0 到18 个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间，输出最短路的长度四、实验结果与分析（源程序及相关说明）四、实验结果与分析（源程序及相关说明）3.思考：用跨立方法，跨立的含义

21、是：如果一条线段的一个端点在一条直线的一边，另一个端点在这条直线的另一端，我们就说这条线段跨立在这条直线上。线段相交满足且只需满足如下两个条件就可以了：1 两条线段相互跨立；2 一条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若p1p2 跨立 p3p4，则矢量(p1 p3)和(p2-p1)位于矢量(p4 p3)的两侧，即(p1 p3）(p4-p3)*(p2 p3)(p4 p3)0。当(p1 p3)(p4p3)=0 时，说明(p1 p3)和(p4 p3)共线，但是因为已经通过快速排斥试验，所以 p1 一定在线段 p3p4 上；同理，(p4 p3)(p2 p3)=0 说

22、明 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()用于判断 p1、p2 构成的线段和 p3、p4 构成的线段是否相交。可以看出共五种情况两线段是相交的，反之就输出“The two are Not intersected!”4.房间最短路问题：#include#include#includeinncludeusing namespace std;type

23、def 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.firs

24、t?p1.first:p2.first;double min_y=p1.secondp2.second?p1.second:p2.second;if(p.first=min_x&p.first=min_y&p.second=max_y)return true;elsereturn false;POINT startPoint;bool sortByPolorAngle(const POINT&p1,const POINT&p2)double d=direction(startPoint,p1,p2);if(d0)return false;if(d=0&on_segment(startPoint

25、,p1,p2)return true;if(d=0&on_segment(p2,startPoint,p1)return true;return false;void find_convex_hull(vector&point)POINT p0=point0;int k=0;for(int i=0;ipoint.size();i+)if(pointi.secondp0.second|pointi.second=p0.second&pointi.firstp0.first)p0=pointi;k=i;point.erase(point.begin()+k);point.insert(point.

26、begin(),p0);vectorconvex_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;jconvex_hull.size();j+)coutconvex_hullj.first convex_hullj.secondendl;int main()vector pv;double x,y;int i;cout请输入 10 个点：endl;for(i=1;i=10;i+)coutNo.ixy;pv.push_back(make_pair(x,y);coutendl;find_convex_hull(pv);system(Pause);return 0;运行截图：