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

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

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

3、疋义一个空的vector，兀素类型为int,生成10个随机数插入到vector中，用迭代器遍历vector并输出其中的兀素值。在 vector头部插入一个随机数，用迭代器遍历vector并输出其中的元素值。用泛型算法find查找某个随机数，如果找到便输出，否则将此数插入vector尾部。用泛型算法sort将vector排序，用迭代器遍历 vector并输出其中的元 素值。删除vector尾部的兀素，用迭代器遍历vector并输出其中的兀素值。将vector清空。定义一个list，并重复上述实验，并注意观察结果2练习泛型算法的使用。疋义一个vector，兀素类型为int,插入10个随机数，使用s

4、ort按升序排序，输出 每个元素的值，再按降叙排序，输出每个元素的值。练习用find查找元素。用min和max找出容器中的最小元素个最大元素，并输出。四、实验结果与分析(源程序及相关说明)1.练习vector和list的使用：#i nclude #in elude #in cludevioma nip#in clude#i nclude using n amespace std;vector myV;bool sortup(i nt v1,i nt v2)retur n v1v2;int main (i nt argc, char *argv)sran d(time(NULL); /随机产生十

5、个数for (i nt i=0;i10;i+)myV.push_back(ra nd();sort(myV.begi n(),myV.e nd(),sortup); /用sort排序升序vector:iterator it1;for (it仁myV.begi n();it1!=myV.e nd();it1+)8山(51)$6上可(6)； /打印数组coute ndl;int min=m yV0;for (it仁myV.begi n()+1;it1!=myV.e nd();it1+)if(*it1)mi n)mi n=(*it1);coutmax)max=(*it1);coutvv 最大元素为v

6、vmaxvvendl;coute ndl;int value=ra nd();it1=fi nd(myV.begi n(),myV.e nd(),value);if(*it1)=value)cout找到了这个随机数endl ;elsecoutvv没有找到这个随机数endl;myV.insert(myV.end(),value); /数组中没有随机数,插入尾部coutvv插入尾部的随机数为vvaluevvendl;for (it仁myV.begi n();it1!=myV.e nd();it1+)coutv(*it1)vsetw(6);coutne ndl;/ 随机在vector头部插入一个随机

7、数int t=rand();定义t;将一个随机数赋给t，插入到数组头部myV.i nsert(myV.beg in( ),t);coutvv插入头部的随机数为vtvendl;for (it1=myV.begi n();it1!=myV.e nd();it1+)coutvv(*it1)vvsetw(6);coutvve ndl;/删除尾部元素myV.pop_back ();for (it1=myV.begi n();it1!=myV.e nd();it1+)coutvv(*it1)vvsetw(6);coutvve ndl;myV.clear();清空数组if(myV.empty()cout I

8、ts empty! en dl;system(PAUSE); /press any key to continu e. return 0;运行截图： C-Un mafu俚字没计言术与右法匚 ppi26657665 10324 10504 11852 16831 17508 18450 21882 26816最小元素为丈丸吕最大元素为2G816没有找到这个随机数插入尾部的随机数为2旳朋256576&5 10324 10504 11852 16831 17508 18450 21882 26816 28066幡入头部的隔机数为M躯4492 25657665 10324 10504 11852 16

9、834 17508 18450 21S82 26816 280564492 2b6o 7665 10324 105D4 11852 16834 17508 1SS4qO 21貂2 26816 11 s emptv!请按任意僮吳续*rT 1 =|r2练习泛型算法的使用：#i nclude#in clude #i nclued using n amespace std; typedef list lin;in t value=2,4,6,1,8;void prin t(lin &l)int i;lin:iterator lit;/定义一个迭代器for(lit=l.beg in ();lit!=l.

10、e nd();lit+) coutv(*lit)vv2;int mai n()lin lin2;lin 2.push_fro nt(3);lin 2.push_fro nt(4);lin 2.i nsert(li n2.beg in( ),value,value+5);coutli n2 内的元素为：;prin t(li n2);lin 2.sort();cout排序后的 lin2:;prin t(li n2);lin2.push_front(1O);在 list 头部插入 10cout在list头部插入10之后的结果：; prin t(li n2);lin 2.remove(6);cout删

11、除一个数后的lin 1:;prin t(li n2);system(PAUSE);/press any key to con ti neu. return 0;运行截图:实验名称姓 名实验日期一、实验目的和要求1掌握宽度优先搜索算法。2.掌握深度优先搜索算法。搜索算法的实验系院专业信息工程系班级物:网一学班指导教师二、实验预习内容1 宽度优先搜索算法：又称广度优搜索。是最简单的图的算法的原形。其属于一种盲搜寻法， 目的是系统地展开并检查图中的所有节点， 以寻找结果。 换句话说， 它并不考虑结果的可能位 址，彻底地搜索整张图，直到找到结果为止。2深度优先搜索算法：它的目的是要达到被搜索结构的叶结

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

13、能够优化算法。 3骑士游历问题： 在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点， 输出一条符合上述要求的路径。4 倒水问题：给定 2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L 升的水，如果可以，输出步骤，如果不可以，请输出 No Solution 。四、实验结果与分析(源程序及相关说明)2，八皇后问题：#include /*声明常量N存储行和列*/#define N 8#define NUM 8/*声明全局变量，hNN控制盘格，HNN控制输出，nN存储每一步的 * 纵坐标， count 用于计数。*/int hNN,nN,HNN;int count=

14、0;/* 声明函数 void tryit(int,int) 尝试符合条件的方法 */void 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)尝试符合条件的方法 */v

15、oid tryit(int x,int y)int i,j;if(count=0&x=0&y=N-1&hxy=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; else Hij=0;count=co

16、unt+1;/* 输出前几种情况 */if(count=NUM)printf( 布局 %d n,count);outputArray(H);/* 对下一种走法，清楚前一次的影响 */for(i=0;i=N-1;i+)for(j=0;j7)/* 清楚前一次影响 */for(i=0;i=N-1;i+)for(j=0;j=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;

17、i=N-1;i+)for(j=0;j=N-1;j+)printf(%d ,hij); printf(n);运行截图：*C-UersAdminstratcr：程字;Srf艺术与方法2Vh(yDebug(Zf：pl mxm布局100000000000100000000001I)000010000100000000000100100000000010000-布局210000000()0000100000000010010000000000010000100000100000000001000-布局3100000000000001000010000000001000000000101000000()0

18、00100000100000布局41 1nnnnnAn4.倒水问题：#i ncludestdio.hint mai n()int ca,cb,cc,x,y;while(sca nf(%d%d%d,&ca,&cb,&cc)!=EOF)if(cb=cc) prin tf(fill Bn);else if(ca=cc)prin tf(fill An);printf(pour A Bn);else x=y=0; if(caca-x)/ 如果 b 中的水大于 a 中的剩余容积，就把 a 灌满 / y-=ca-x; x=ca; printf(pour B An);else/如果b中的水小于a中的剩余容积，

19、那么把b中的水全加入a/x+=y;y=0;printf(pour B An);if(y=cc)/如果b中的水已经和cc相等，那就结束/ break;if(ca=x)/ 如果 a 中的水满了，就把 a 倒空/x=0; printf(empty An);else while(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)

20、;if(y=cc)/如果b中的水已经和cc相等，那就结束/break;if(y=cb)/如果b中的水满了，就把b倒空/y=0;printf(empty Bn);prin tf(successn);return 0;运行截图：I (ZLk erEXadmi n -trafa rl二电咛 kt=p 程宇：St十兰 术与方法 2訪 iD?bugi匚 ppi _Fw-=r,pour A E fill Apour A Bfil Apour A B-umpty BDour A Bsuccess实验名称计算几何算法的实现姓名系院专业信息工程 系班级物联网一 班学号实验日期指导教师成绩一、实验目的和要求1理解

21、线段的性质、叉积和有向面积。2 掌握寻找凸包的算法。3综合运用计算几何和搜索中的知识求解有关问题。二、实验预习内容凸包：是一组点集中的子集， 这一子集形成的凸多边形可以将点集中所有的点都围住，并且这一凸边形的面积是取小的。一种寻找凸包的算法：打包法首先，我们找出点集中最下方的点，如果这样的点不止一个，就选用最左边的点（如P0）。显然，这个点（P0）是凸包子集中的一个点。可以设想在P0处拴了一根皮筋的一端，另一端放在和 P0成水平位置的右侧。现在，将皮筋，沿逆时针方向转动，首先会 碰到P1，这样就找到了另一个凸包子集中的点。以P1为中心，做和P0 一样的事，会发现，我们将碰到P3，又一个凸包的点

22、。我们可以一直这样做下去，直到再一次遇到P0,凸包就被找出来了。具体而言，在第一次找到P0点之后，以P0为每个矢量的起点，其它的点为矢量的终点，来比较任意两个矢量的转角，就可以对余下的点进行按极角排序三、实验项目摘要1将讲义第三章第三节中的凸包代码上机运行并检验结果。2完成讲义第三章的课后习题，上机运行并检验结果。3思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的 端点重合，思考这样的情况。4房间最短路冋题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在x=0,x=10,y=0和y=10。起点和重点固定在（0,5）和（10,5）。房

23、间里还有0到18个 墙，每个墙有两个门。输入给疋的墙的个数，每个墙的x位置和两个门的y坐标区间，输出最短路的长度四、实验结果与分析(源程序及相关说明)3.思考：用跨立方法，跨立的含义是：如果一条线段的一个端点在一条直线的一边，另一个端 点在这条直线的另一端，我们就说这条线段跨立在这条直线上。线段相交满足且只需 满足如下两个条件就可以了：1两条线段相互跨立；2 一条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若p1p2跨立p3p4，贝U矢量(pl - p3 )和(p2 - pl ) 位于矢量(p4 - p3 )的两侧，即(pl - p3) X ( p4- p3 ) *

24、 ( p2 - p3 ) X ( p4 - p3 ) 0 。当(pl - p3 ) X ( p4 - p3 ) = 0 时，说明(pl - p3 )和(p4 - p3 )共线，但是因为已经通过快速排斥试验，所以pl 一定在线段p3p4上；同理，(p4 - p3 ) X (p2 - p3 ) = 0 说明p2 一定在p3p4 上。所以判断 p1p2 跨立 Q1Q2的依据是：(pl - p3 ) X ( p4 - p3 ) * ( p4 - p3 ) X ( p2 - p3 ) = 0。同理判断 Q1Q2跨立 P1P2的依据是：(p3 - pl ) X ( p2 -pl ) * ( p2 - pl

25、 ) X ( p4 - pl ) = 0 。代码中函数 bool segment_intersect() 用于判断p1、p2构成的线段和p3、p4构成的线段是否相交。可以看出共五种情况两 线段是相交的，反之就输出“ The two are Not in tersected! ” 4.房间最短路问题：#in clude#in clude#in cludeinn cludeusing n amespace std;typedef pair POINT;/ 线段double direction(POINT p,POINT p1,POINT p2)POINT v1,v2;v1.first=p2.fir

26、st-p1.first;v1.sec on d=p2.sec on d-p1.first;v2.first=p1.first-p.first;v2.sec on d=p1.sec on d-p.sec ond;return v1.first*v2.sec on d-v1.sec on d*v2.sec on d;bool on_segme nt(POINT p,POINT p1,POINT p2)double min _x=p1.firstp2.first?p1.first:p2.first;double min y=p1.secondp2.sec on d?p1.sec on d:p2.sec ond; if(p.first=min_x&p.first= min_y&p.seco nd=max_y) return true;elsereturn false;POINT startPoi nt;bool sortByPolorAngle(const POINT &p1,const POINT &p2) double d=directio n(startPoi nt,p1,p2);if(d0)return false;if(