《《程序设计艺术与方法》课程实验报告..docx》由会员分享，可在线阅读，更多相关《《程序设计艺术与方法》课程实验报告..docx（24页珍藏版）》请在三一文库上搜索。
1、程序设计艺术与方法课程实验报告实验名称STL的熟悉与使用姓 名系院专业计算机与 信息学院班级计算机科 学与技术 122 班学 号2012211643实验日期指导教师徐本柱成 绩一、实验目的和要求1. (1)掌握C+中STL的容器类使用。(2)掌握C+中STL的算法类的使用。二、实验预习内容Vector,list可当作列表使用的数据结构，它们都是动态增长的。1.vector表7L段连续的内存区域母个兀素被顺序储存在这段内仔中。对vector的随即访问效率很高。但是在任意位置而不是在 vector末尾插入兀素则效率很低，因为它需要把待插入兀素 的右边的每个兀素都拷贝一遍。类似的删除任一个而不是ve
2、ctor的最舟-个兀素效率低。2list表示非连续的内存区域并通过一对指向首尾元素的指针双向进行遍历在list的任意位置插入和删除兀素的效率都很高，指针必须被赋值但不需要用拷贝兀素来实现移动，另一方面它对随机访问的支持并不好访问一个元素需要遍历中间的元素，另外每个元素还有俩不能给个指针的额外空间开销。3泛型算法让编写一般化并可重复使用的算法，其效率与指针对某特定数据类型而设计的算法相同。泛型即是指具有在多种数据类型上皆可操作的含义，与模板有些相似。STL巨大而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。
3、三、实验项目摘要1.练习vector和list的使用。te义一个空的vector,兀素类型为int,生成10个随机数插入到vector中，用迭代器遍历vector并输出其中的九素值。在 vector头部插入一个随机数，用迭代器遍历vector并输出其中的元素值。用泛型算法find查找某个随机数，如果找到便输出，否则将此数插入vector尾部。用泛型算法sort将vector排序，用迭代器遍历 vector并输出其中的元 素值。删除vector尾部的兀素，用迭代器遍历 vector并输出其中的兀素值。将 vector清 空。定义一个list,并重复上述实验，并注意观察结果2练习泛型算法的使用。t
4、e义一个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;int main(int argc, char *argv口)srand(time(NU
5、LL);/随机产生十个数for (int i=0;i10;i+)myV.push_back(rand();sort(myV.begin(),myV.end(),sortup); 用 sort 排序升序vector二iterato门t1;for (it1=myV .begin();it1!=myV .end();it1+)coutv(*it1)vsetw(6); 打印数组coutendl;int min=myV0;for (it1=myV .begin()+1;it1!=myV .end();it1+)if(*it1)min)min=(*it1);cout最小元素为minmax)max=(*it
6、1);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);coutnendl;/随机在vector头部插入一个随机数in
7、t 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 Its empty! endl;system(
8、PAUSE); /press any key to continue. return 0;运行截图：7&78 11589 13582 128? 13?081G925194212143421940小石左方 大元素为319431G2251942131L05售人头部的随机数为“好7t79 11S88 13&82 12997 12909 1G225 19421 21434 ?居姬 31940 14859 5486 7t7B 115S8 15582 L3897 139酮 162四 9421 21434 3150G 2?40 Rt，* cnptyt青按任意错也续.一2练习泛型算法的使用：#include#
9、include/#incluedusing namespace std;typedef list lin;int value=1,6,7,8,9; 定义一个数组 value 并赋值 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;lin2.push_front(3); /单独逐个插入几个数lin2.push_front(4);lin2.insert(lin2.begi
10、n(),value,value+5);coutlin2内的元素为：;print(lin2);lin2.sort();/对链表11进行从小到大排序cout排序后的 1in2:;print(1in2);1in2.push_front(10);/在 list 头部插入 10cout在list头部插入10之后的结果：;print(lin2);lin2.remove(6);cout删除一个数后的lin1:;print(lin2);system(PAUSE);press any key to contineu return 0;/List不允许对随机数进行操作运行截图：Wn2I -“口 ： 6。安全.克器
11、下舞1 M i 匚rs oft Vi ual、tudioM y Proj百咆元索为,后的 lin2* 13 4 6 7 6 9睢1迤1:头部插入1Z之后的结果；18 1 3 4 fc 7 8 9IlinlstB 13 4 7 8 9实验名称搜索算法的实验姓 名黄星辰系院专业计算机与 信息学院班级计算机科 学与技术122 班学号2012211643实验日期指导教师徐本柱成绩一、实验目的和要求1 .掌握宽度优先搜索算法。2 .掌握深度优先搜索算法。二、实验预习内容1宽度优先搜索算法：又称广度优搜索。是最简单的图的算法的原形。其属于一种盲搜寻法，目的是系统地展开并检查图中的所有节点，以寻找结果。换句
12、话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。2深度优先搜索算法：它的目的是要达到被搜索结构的叶结点。在一个HTML文件中，当一个超链被选择后，被连接的 HTML文件将执行深度优先搜索，即在搜索其余的超链走到不能再 深入为止，然后返回到某一个HTML文件，再继续选择该 HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。三、实验项目摘要1 .将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。2 .八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。思考：将此题推广到 N皇后的情况，
13、检验在 N比较大的情况下，比方说 N=16的时 候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。3骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。4倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升的水，如果可以，输出步骤，如果不可以，请输出 No Solution。四、实验结果与分析(源程序及相关说明)2,八皇后问题:#include /*声明常量N存储行和列*/# define N 8# define NUM 8/*声明全局变量，hNN控制盘格，HNN控制输出，nN存储每一步的
14、# 纵坐标，count用于计数。# /int hNN,nN,HNN;int count=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+)h皿=0；tryit(x,y);printf(/其他的布局略n);printf(共有 d 种布局.n”,92);return(0);/*定义函数voi
15、d tryit(int,int)尝试符合条件的方法*/void tryit(int x,int y)int i,j;if(count=0&x=0&y=N-1&hxy=0)/*对与皇后在同一行、歹h斜线上的点作出处理*/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=
16、1;elseHij=0;)count=count+1;/*输出前几种情况*/if(count=NUM) printf(布局 dn,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,
17、j;for(i=0;i=N-1;i+)for(j=0;j=N-1;j+)printf(%d ,hij);printf(n);运行截图:一布局T-出炉自住1中内修 00080001 6008010a3 0 0 Q 0 1 Q 61003008 60010099布局260086091 03100009 RDB修01000009布局33 .骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点, 输出一条符合上述要求的路径。#include int board88 = 0;int main(void) int startx, starty;int i, j；printf(
18、输入起始点:);scanf(%d %d, &startx, &starty);if(travel(startx, starty) printf(游历完成！ n);else printf(游历失败！ n);for(i = 0; i 8; i+) for(j = 0； j 8; j+) printf(%2d , boardjputchar(n);return 0;int travel(int x, int y)int ktmove18 = -2, -1, 1,2, 2, 1, -1, -2; / 对应骑士可走的八个方向int ktmove28 = 1,2, 2, 1, -1, -2, -2, -1
19、; / 测试下一步的出路int nexti8 = 0;int nextj8 = 0; / 记录出路的个数int exists8 = 0;int i, j, k, m, l;int tmpi, tmpj;int count, min, tmp;i = x;j = y;boardij = 1;for(m = 2; m = 64; m+) for(l = 0; l 8; l+)existsl = 0;l = 0;/试探八个方向for(k = 0; k 8; k+) tmpi = i + ktmove1k;tmpj = j + ktmove2k; /如果是边界了，不可走if(tmpi 0 | tmpj
20、 7 | tmpj 7)continue; /如果这个方向可走，记录下来if(boardtmpitmpj = 0) nextil = tmpi;nextjl = tmpj; /可走的方向加一个 l+;count = l; /如果可走的方向为0个，返回 if(count = 0) return 0;else if(count = 1) /只有一个可走的方向/所以直接是最少出路的方向min = 0; else /找出下一个位置的出路数for(l = 0; l count; l+) for(k = 0; k 8; k+) tmpi = nextil + ktmove1k;tmpj = nextjl
21、+ ktmove2k;if(tmpi 0 | tmpj 7 | tmpj 7) continue;if(boardtmpitmpj = 0) existsl+;tmp = exists0;min = 0; /从可走的方向中寻找最少出路的方向 for(l = 1; l count; l+) if(existsl tmp) tmp = existsl;min = l;/走最少出路的方向i = nextimin;j = nextjmin;board皿=m;return 1;运行截图：1 162722318475626 2321745741915 2825622148555824 3530456063
22、20529 14bl3449445?5436 31384164536y13 483350118435232 3712394251107Ppess an9 key to continue*川4 .倒水问题：#includestdio.hint main()int ca,cb,cc,x,y;while(scanf(%d%d%d,&ca,&cb,&cc)!=EOF) if(cb=cc)printf(fill Bn);else if(ca=cc)printf(削 An);printf(pourA Bn); elsex=y=0;if(caca-x)/如果b中的水大于a中的剩余容积，就把a灌满y-=ca-
23、x;x=ca;printf(pour B An); else/如果b中的水小于a中的剩余容积，那么把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);elsewhile(1)if(x=0)x=ca;printf(fill An);if(xcb-y)/如果a中的水大于b中的剩余容积，就把b灌满x-=cb-y;y=cb;printf(pourA Bn); else/如果a中的水小于b中的剩余容积，那么把a中的水全加入b/ y
24、+=x；x=0;printf(pourA Bn);if(y=cc)/如果b中的水已经和cc相等，那就结束break;if(y=cb)/如果b中的水满了，就把b倒空y=0;printf(empty Bn);printf(successn);return 0;运行截图：斐全定r高器大帽MicFosnft Visual EtudioMProjectsypuD&bugijpu.eatewfc 7 5 fill A VDUF ft B fill A puur A B empty It jiour A B success 7 9 8 rm B pour* B A enpt A puur B 由 pll D
25、 pour B A enpt5 A pom? B 俞 ini d pour B A empty 妹 pour B A fill B I)Dur B A success实验名称计算几何算法的实现姓 名黄星辰系院专业计算机与 信息学院班级计算机科 学与技术 122 班学 号2012211643实验日期指导教师徐本柱成 绩一、实验目的和要求1 .理解线段的性质、叉积和后向回积。2 .掌握寻找凸包的算法。3 .综合运用计算几何和搜索中的知识求解有关问题。二、实验预习内容凸包：是一组点集中的子集， 这一子集形成的凸多边形可以将点集中所有的点都围住，并且这一凸边形的面积是最小的。一种寻找凸包的算法：打包法
26、首先，我们找出点集中最下方的点，如果这样的点不止一个，就选用最左边的点(如P0)。显然，这个点(P0)是凸包子集中的一个点。可以设想在 P0处拴了一根 皮筋的一端，另一端放在和 P0成水平位置的右侧。现在，将皮筋，沿逆时针方向转动，首先会 碰到P1,这样就找到了另一个凸包子集中的点。以 P1为中心，做和P0 一样的事，会发现，我 们将碰到P3,又一个凸包的点。我们可以一直这样做下去，直到再一次遇到P0,凸包就被找出来了。具体而言，在第一次找到 P0点之后，以P0为每个矢量的起点，其它的点为矢量的终点， 来比较任意两个矢量的转角，就可以对余下的点进行按极角排序三、实验项目摘要1将讲义第三章第三节
27、中的凸包代码上机运行并检验结果。2完成讲义第三章的课后习题，上机运行并检验结果。3思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的 端点重合，思考这样的情况。4房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在x=0,x=10,y=0和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0到18个 墙，每个墙有两个门。输入给定的墙的个数，每个墙的x位置和两个门的y坐标区间，输出最短路的长度四、实验结果与分析(源程序及相关说明)3 .思考：用跨立方法，跨立的含义是：如果一条线段的一个端点在一条直线的一边，另一个端
28、 点在这条直线的另一端，我们就说这条线段跨立在这条直线上。线段相交满足且只需 满足如下两个条件就可以了：1两条线段相互跨立；2 条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若p1p2跨立p3P4 ,则矢量(p1 - p3 )和(p2 - p1 )位于矢量(p4 - p3 )的两侧，即(p1 -p3) X ( p4- p3 ) * ( p2 -p3 ) X ( p4 - p3 ) 0。当(p1 - p3 ) X ( p4- p3 ) = 0 时，说明(p1 - p3 )和(p4 - p3 ) 共线，但是因为已经通过快速排斥试验， 所以p1 一定在线段p3P4上；同理
29、，(p4 - p3 ) X(p2 - p3 ) = 0说明p2 一定在p3P4上。所以判断p1p2跨立Q1Q2的依据是： (p1 - p3 ) X ( p4 - p3 ) * ( p4 - p3 ) X ( p2-p3 ) = 0。同理判断 Q1Q2 跨立 P1P2的依据是：(p3 - p1 ) X ( p2 - p1 ) * ( p2 - p1 ) X ( p4 - p1 ) = 0。代码中函数 bool segment_intersect(用于判断p1、p2构成的线段和p3、p4构成的线段是否相交。 可以看出共五种情况两覆段是相交而，应之就输出“ The two are Not inter
30、sected!4 .房间最短路问题：#include#include#includeinncludeusing 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.first-p.first;v2.second=p1.second-p.second;return v1.first*v2.second-v1.second*v2.sec
31、ond;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_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
32、=direction(startPoint,p1,p2);if(d0)return false;if(d=0&on_segment(startPoint,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&point
33、i.firstp0.first)p0=pointi;k=i；point.erase(point.begin()+k);point.insert(point.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;运行截图：