《程序设计艺术与方法》课程实验报告(共25页).doc

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

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

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

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

4、型算法的使用。定义一个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 *ar

5、gv) 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=(*it1);

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

7、6); coutnendl; /随机在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();/清

8、空数组 if(myV.empty() cout Its empty! endl; system(PAUSE); /press any key to continue. return 0;运行截图：2 练习泛型算法的使用：#include#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(

9、*lit) ;/依次打印list中的元素 coutv2; int main()lin lin2; lin2.push_front(3); /单独逐个插入几个数 lin2.push_front(4); lin2.insert(lin2.begin(),value,value+5);coutlin2内的元素为：;print(lin2);lin2.sort();/对链表l1进行从小到大排序 cout排序后的lin2: ;print(lin2);lin2.push_front(10);/在list头部插入10 cout在list头部插入10之后的结果：; print(lin2);lin2.remove

10、(6);cout删除一个数后的lin1:; print(lin2); system(PAUSE);/press any key to contineu. return 0;/List不允许对随机数进行操作运行截图：二实验名称 搜索算法的实验姓 名黄星辰系院专业计算机与信息学院班 级计算机科学与技术122班学 号实验日期指导教师徐本柱成 绩一、实验目的和要求1掌握宽度优先搜索算法。2掌握深度优先搜索算法。二、实验预习内容1宽度优先搜索算法：又称广度优搜索。是最简单的图的算法的原形。其属于一种盲搜寻法，目的是系统地展开并检查图中的所有节点，以寻找结果。换句话说，它并不考虑结果的可能位址，彻底地搜索

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

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

13、N,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+)hij=0;tryit(x,y);printf(/其他的布局略n);printf(共有%d种布局.n,92);return(0);/*定义函数void tryit(int,int)尝试符合条件的方法*/voi

14、d 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;elseHij=0; count=count+1;/*输出前几种情

15、况*/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);else tryit(0,0);/*尝试下一格*/elsetryit(x,y+1);/*定义函数void outputArray(intN)输出数组*/void outputArray(int hN)int i,j;for(i=0;i=N-1;i+)for(j=0;j=N-1;

16、j+)printf(%d ,hij);printf(n);运行截图：3. 骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。#include int board88 = 0; int main(void) int startx, starty; int i, j; printf(输入起始点：); scanf(%d %d, &startx, &starty); if(travel(startx, starty) printf(游历完成！n); else printf(游历失败！n); for(i = 0; i 8; i+) for(j

17、 = 0; j 8; j+) printf(%2d , boardij); putchar(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; / 测试下一步的出路int nexti8 = 0; int nextj8 = 0; / 记录出路的个数int exists8 = 0; int i, j, k, m, l; int tmpi, tmpj; int count, mi

18、n, 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 7 | tmpj 7) continue; / 如果这个方向可走，记录下来if(boardtmpitmpj = 0) nextil = tmpi; nextjl = tmpj; / 可走的方向加一个l+; co

19、unt = 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 + ktmove2k; if(tmpi 0 | tmpj 7 | tmpj 7) continue; if(boardtmpitmpj = 0) existsl+; tmp = exists0;

20、 min = 0; / 从可走的方向中寻找最少出路的方向for(l = 1; l count; l+) if(existsl tmp) tmp = existsl; min = l; / 走最少出路的方向i = nextimin; j = nextjmin; boardij = m; return 1; 运行截图：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(fill

21、 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中的剩余容积，那么把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)

22、; 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中的水已经和cc相等，那就结束/ break; if(y=cb) /如果b中的水满了，就把b倒空/ y=0; printf(empty Bn); printf(successn); return 0;运行截图：三实验名称 计算几何算法的实现姓 名黄星辰系院专业计算机与信息学院班 级计算机科学与技术122

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

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

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

26、 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 说明 p2 一定在 p3p4上。所以判断p1p2跨立Q1Q2的依据是：( p1 p3 ) ( p4 p3 ) * ( p4 p3 ) ( p2p3 ) = 0。同理判断Q1Q2跨立P1P2的依据是：( p3 - p1 ) ( p2 - p1 ) * ( p2 - p1

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

28、st; 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.first?p1.first:p2.first; double min_y=p1.secondp2.second?p1.second:p2.second; if(p.first=min_x&

29、p.first= min_y&p.second=max_y) return true; else return 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,p1,p2)return true; if(d= =0&on_segment(p2,startPoint,p1)return true; return f

30、alse; 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.begin(),p0); vectorconvex_hull; do convex_hull.push_back(point0); startPoint=point0