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

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个随机数，使用sor

4、t按升序排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用find查找元素。用min和max找出容器中的最小元素个最大元素，并输出。四、实验结果与分析（源程序及相关说明）1.练习vector和list的使用：#i nclude #in clude #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)srand(time(NULL);/随机产生十个数for

5、 (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+)coutv(*it1)vsetw(6);/打印数组coute ndl;int mi n=m yV0;for (it仁myV.begi n()+1;it1!=myV.e nd();it1+)if(*it1)max)max=(*it1);coutvv 最大元素为vvmaxvvendl;coute nd

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

7、t;将一个随机数赋给t，插入到数组头部myV.i nsert(myV.begi n(),t);cout插入头部的随机数为tendl;for (it仁myV.begi n();it1!=myV.e nd();it1+)coutv(*it1)vsetw(6);coute ndl;/删除尾部元素myV.pop_back ();for (it仁myV.begi n();it1!=myV.e nd();it1+)coutv(*it1)vsetw(6);coute ndl;myV.clear(); 清空数组if(myV.empty()cout Its empty! en dl;system(PAUSE);

8、 /press any key to con ti nu e. return 0;运行截图:2练习泛型算法的使用：#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.e nd();lit+) coutv(*lit)vv2;int mai n()lin lin2;lin 2.push_fro nt(3);lin 2.pu

9、sh_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删除一个数后的lin 1:; prin t(li n2);system(PAUSE);/press any key to con ti neu. retur

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

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

12、积，求出如何只用两个瓶装出L升的水，如果可以，输出步骤，如果不可以，请输出No Solution 。四、实验结果与分析（源程序及相关说明）2，八皇后问题：#i nclude /*声明常量N存储行和列*/#defi ne N 8#defi ne NUM 8/*声明全局变量，hNN控制盘格，HNN控制输出，nN存储每一步的*纵坐标，count用于计数。*/int hNN ,n N,HNN;int coun t=0;/*声明函数void tryit(int,int)尝试符合条件的方法*/void tryit(i nt, int);/* 声明函数 void outputArray(intN) 输出数组

13、 */void outputArray(i ntN);mai n()int x=O,y=O,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(i nt x,i nt y)int i,j;if(cou nt=0& x=0&yv=N-1 &hxy=0) /*对与皇后在同一行、列、斜线上的点作出处理*/ for(j=0;jv=7;j+)

14、if(hxj=0) hxj=x+1;if(hjy=0)hjy=x+1;if(x+j=0& x+j=0&y+j=0& x+jv=N-1 &y-j=0&y-jv=N-1 &hx+jy-j=O)hx+jy-j=x+1;if(x-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；coun t=co un t+1;/

15、*输出前几种情况*/if(cou nt=NUM)printf(布局 %dn,cou nt);outputArray(H);/*对下一种走法，清楚前一次的影响*/for(i=0;i7)/*清楚前一次影响*/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(i nt hN)int i,j;for(i=0;i=N-1;i+)for(j=0;jv=N-1;j+)prin

16、 tf(%d ,hij);prin tf(n);运行截图:4.倒水问题：#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);prin tf(pour A Bn);elsex=y=O;if(caca-x)/如果b中的水大于a中的剩余容积，就把a灌满/y-=ca-x;x=ca;printf(pour B An);else/如果b中的水小于a中的剩余容积，那么把b中的水全加入

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

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

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

20、。3思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况。4房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在x=0,x=10,y=0 和y=10。起点和重点固定在（0,5）和（10,5）。房间里还有0到18个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x位置和两个门的y坐标区间，输出最短路的长度4.房间最短路问题：#in clude#in clude#in cludeinn cludeusing n amespace std;typedef pair POINT;/ 线段double direc

21、tion(POINT p,POINT p1,POINT p2)POINT v1,v2;v1.first=p2.first-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

22、.first;double min _y=p1.sec on dp2.sec on d?p1.sec on d:p2.sec ond; if(p.first=min_x&p.first=min_y&p.sec on d=max_y)return true;elsereturn false;POINT startPoi nt;bool sortByPolorA ngle(co nst POINT & p1,co nst POINT & p2) double d=directi on( startPo in t,p1,p2);if(d0)return false;if(d=0&on _segme

23、nt(startPo in t,p1,p2)retur n true;if(d= =0&on_segment(p2,startPoint,p1)return true;return false;void find_con vex_hull(vector& poi nt)POINT pO=poi ntO;int k=0;for(int i=0;ipoint.size();i+)if(po in ti.secon dvpO.secon d|poi nti.sec on d=p0.sec ond&poi nti.firstp0.first) p0=poi nti;k=i;poi nt.erase(p

24、oi nt.begi n()+k);poin t.i nsert(po in t.begi n() ,p0); vectorco nvex_hull;docon vex_hull.push_back(po in t0);startPoi nt=poi nt0;poin t.erase(po in t.beg in();sort(poi nt.beg in( ),poi nt.e nd(),sortByPolorA ngle);if(po in t0=c on vex_hull0)break;poi nt.push_back(co nv ex_hullc on vex_hull.size()-1);while(1);for(i nt j=O;jcon vex_hull.size();j+)coutc onv ex_hullj.first c on vex_hullj.sec on de ndl;int mai n()vector pv;double x,