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

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

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

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

4、插入10个随机数，使用sort按升字排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用find查找元素。用min与max找出容器中的最小元素个最大元素,并输出。四、实验结果与分析(源程序及相关说明)1、 练习vector与list的使用：#include<iostream>#include<vector>#include<iomanip>#include<ctime>#include<algorithm>usingnamespacestd;vector<int>myV;boolsortup(intv1,intv

5、2)returnv1<v2;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<int>:iteratorit1;for(it1=myV、begin();it1!=myV、end();it1+)cout<<(*it1)<<setw(6);打印数组cout<<endl;intmin=myV0;for(it1

6、=myV、begin()+1;it1!=myV、end();it1+)if(*it1)<min)min=(*it1);cout<<"最小元素为"<<min<<endl;intmax=myV0;for(it1=myV、begin();it1!=myV、end();it1+)if(*it1)>max)max=(*it1);cout<<"最大元素为"<<max<<endl;cout<<endl;intvalue=rand();it1=find(myV、begin()

7、,myV、end(),value);if(*it1)=value)cout<<"找到了这个随机数"<<endl;elsecout<<"没有找到这个随机数"<<endl;myV、insert(myV、end(),value);/数组中没有随机数，插入尾部cout<<”插入尾部的随机数为"<<value<<endl;for(it1=myV、begin();it1!=myV、end();it1+)cout<<(*it1)<<setw(6);co

8、ut<<"n"<<endl;/随机在vector头部插入一个随机数intt=rand();/定义t;将一个随机数赋给t,插入到数组头部myV、insert(myV、begin(),t);cout<<"插入头部的随机数为"<<t<<endl;for(it1=myV、begin();it1!=myV、end();it1+)cout<<(*it1)<<setw(6);cout<<endl;/删除尾部元素myV、popback();for(it1=myV、begin(

9、);it1!=myV、end();it1+)cout<<(*it1)<<setw(6);cout<<endl;myV、clear();/清空数组if(myV、empty()cout<<"It'sempty!"<<endl;system("PAUSE");/pressanykeytocontinue、return0;运行截图：产:erAriminstraTcr匚Wsttup'程序费艺方;去帛匚卜whuq%匚ppi25657665103241050411852168341750818

10、4502188226816最小元素为2#三最大元素为25816没有找到这个随机数插入尾部的随机数为2805625657665103241050411852168311750818450218822681628066情人头部的随机数为449244922565766510324105041185216834175081845021882268162805644M2b6口766口10324lOdlM11B52168341750S1弘口021822681611?semptvl请按任意建维续一.2练习泛型算法的使用：#include<list>#include<iostream>

11、/#inclued<algohthm>usingnamespacestd;typedeflist<int>lin;intvalue=2,4,6,1,8;voidprint(lin&l)inti;lin:iteratorlit;/定义一个迭代器for(lit=l、begin();lit!=l、end();lit+)cout<<(*lit)<<""/打印list中的元素cout<<endl;boolsortsp(intv1,intv2)/升序排序算法returnv1>v2;intmain()linlin2

12、;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头部插入10cout<<"在list头部插入10之后的结果:"print(lin2);lin2、remove(6);cout<<"删除一个

13、数后的lin1:"print(lin2);system("PAUSE");pressanykeytocontineu、return0;运行截图:实验名称搜索算法的实验姓名u信息工程"亚物联网一沁口系院专业化班级,学号系班实验日期指导教师成绩一、实验目的与要求1 .掌握宽度优先搜索算法。2 .掌握深度优先搜索算法。二、实验预习内容1 宽度优先搜索算法:又称广度优搜索。就是最简单的图的算法的原形。其属于一种盲搜寻法目的就是系统地展开并检查图中的所有节点,以寻找结果。换句话说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。2 深度优先搜索算法:

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

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

16、;/*声明函数voidtryit(int,int)尝试符合条件的方法*/voidtryit(int,int);/*声明函数voidoutputArray(intN)输出数组*/voidoutputArray(intN);程序设计艺术与方法课程实验报告main()intx=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);/*定义函数voidtryi

17、t(int,int)尝试符合条件的方法*/voidtryit(intx,inty)inti,j;if(count<=NUM)/*重复时跳出递归*/if(H00=1&&H14=1&&H27=1&&H35=1&&H42=1&&H56=1&&H61=1&&H73=1)&&count!=1)elseif(x>=0&&x<=N-1&&y>=0&&y<=N-1&&hxy=0)/*对与皇后

18、在同一行、列、斜线上的点作出处理*/for(j=0;j<=7;j+)if(hxj=0)hxj=x+1;if(hjy=0)hjy=x+i；if(x+j>=0&&x+j<=N-1&&y+j>=0&&y+j<=N-1&&hx+jy+j=0)hx+jy+j=x+1;if(x+j>=0&&x+j<=N-1&&y-j>=0&&y-j<=N-1&&hx+jy-j=0)hx+jy-j=x+1;if(x-j>=0&&a

19、mp;x-j<=N-1&&y+j>=0&&y+j<=N-1&&hx-jy+j=0)hx-jy+j=x+1;if(x-j>=0&&x-j<=N-1&&y-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(hij&

20、lt;0)Hij=1;elseHij=0;)count=count+1;/*输出前几种情况*/if(count<=NUM)(printf("布局%dn",count);outputArray(H);/*对下一种走法,清楚前一次的影响*/for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)if(hij=x|hij=-x|hij=-x-1)hij=0;/*递归,尝试另一种方法*/tryit(x-1,nx-1+1);/*未走完一次,继续下一行*/elsenx=y;tryit(x+1,0);else/*此路不通时,返回上一行,尝试下一种方法*/

21、if(y>7)/*清楚前一次影响*/for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)程序设计艺术与方法课程实验报告if(hij=x|hij=-x)hij=0;/*分情况递归*/if(x-1>=0)tryit(x-1,nx-1+1);elsetryit(0,0);/*尝试下一格*/elsetryit(x,y+1);/*定义函数voidoutputArray(intN)输出数组*/voidoutputArray(inthN)inti,j;for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)printf("%d

22、",hij);printf("n");运行截图:"C-,U?Adminstrjtcr一五二"匚聚隹序爰+艺本与万.法DehugCppi.ex="000000010000010000010000701000。000000100000000010000100001D00000000000G010000010000100000布局801000000000001001DOOOOOO0000001000010000000000010010000000001000。其隹的布局略共有92种布局.?ressanvkevtocontinue*dI4、倒

23、水问题：#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");程序设计艺术与方法课程实验报告elsex=y=0;if(ca<cc)while(1)if(y=0)y=cb;printf("

24、;fillBn");if(y>ca-x)/如b中的水大于a中的剩余容积,就把a灌满/y-=ca-x;x=ca;printf("pourBAn");else/如b中的水小于a中的剩余容积,那么把b中的水全加入a/x+=y;y=0;printf("pourBAn");if(y=cc)/如果b中的水已经与cc相等，那就结束break;if(ca=x)/如果a中的水满了，就把a倒空x=0;printf("emptyAn");elsewhile(1)if(x=0)x=ca;printf("fillAn");i

25、f(x>cb-y)/如a中的水大于b中的剩余容积,就把b灌满/x-=cb-y;y=cb;printf("pourABn");else/如a中的水小于b中的剩余容积,那么把a中的水全加入b/y+=x;x=0;printf("pourABn");if(y=cc)/如果b中的水已经与cc相等，那就结束break;程序设计艺术与方法课程实验报告if(y=cb)/如果b中的水满了，就把b倒空y=0;printf("emptyB'n");printf("successn");return0;运行截图：实验名称计算

26、几何算法的实现姓名系院专业信息工程系班级物联网一班学号实验日期指导教师成绩一、实验目的与要求1 .理解线段的性质、叉积与有向面积。2 .掌握寻找凸包的算法。3 .综合运用计算几何与搜索中的知识求解有关问题。二、实验预习内容凸包：就是一组点集中的子集，这一子集形成的凸多边形可以将点集中所有的点都围住，并且这一凸边形的面积就是最小的。一种寻找凸包的算法：打包法首先，我们找出点集中最卜方的点，如果这样的点不止一个，就选用最左边的点（如P0）。显然，这个点（P0）就是凸包子集中的一个点。可以设想在P0处拴了一根皮筋的一端，另一端放在与P0成水平位置的右侧。现在,将皮筋，沿逆时针方向转动，首先会碰到P1

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

28、短路径。房间的边界固定在x=0,x=10,y=0与y=10。起点与重点固定在（0,5）与（10,5）。房间里还有0到18个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x位置与两个门的y坐标区间，输出最短路的长度四、实验结果与分析(源程序及相关说明)3、思考：用跨立方法，跨立的含义就是：如果一条线段的一个端点在一条直线的一边，另一个端点在这条直线的另一端，我们就说这条线段跨立在这条直线上。线段相交满足且只需满足如下两个条件就可以了：1两条线段相互跨立；2条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若p1p2跨立p3P4，则矢量(pl-p3)与(p2-pl)位于矢

29、量(p4-p3)的两侧，即(pl-p3)X(p4-p3)*(p2-p3)义(p4-p3)<0o上式可改写成(pl-p3)义(p4-p3)*(p4-p3)义(p2-p3)>0o当(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)X(

30、p4-pl)>=0o代码中函数boolsegment_intersect(用于判断pl、p2构成的线段与p3、p4构成的线段就是否相交。可以瞧出共五种情况访线段就是*目交而，反之就输出“ThetwoareNotintersected!4、房间最短路问题：#include<iostream>#include<utility>#include<vector>innclude<algorithm>usingnamespacestd;typedefpair<double,double>POINT;/线段doubledirection(P

31、OINTp,POINTp1,POINTp2)POINTv1,v2;v1、first=p2、first-p1、first;v1、second=p2second-p«first;v2、first=p1、first-p、first;v2、second=p1second-psecond;returnv1、first*v2、second-v1、second*v2、second;boolon_segment(POINTp,POINTp1,POINTp2)doublemin_x=p1、first<p2、first?p1、first:p2、first;max_x=p1、first>p2、

32、first?p1、first:p2、first;doublemin_y=p1、second<p2second?p1second:p2second;doublemax_y=p1、second>p2second?p1second:p2second;if(p、first>=minx&&p、first<maxx&&p、second>=min_y&&p、second<=max_y)returntrue;elsereturnfalse;POINTstartPoint;boolsortByPolorAngle(constPOINT&p1,constPOINT&p2)doubled=direction(startPoint,p1,p2);if(d<0)returntrue;if