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

《2022年《程序设计艺术与方法》课程实验报告.pdf》由会员分享，可在线阅读，更多相关《2022年《程序设计艺术与方法》课程实验报告.pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、定义一个 list, 并重复上述实验, 并注意观察结果2 练习泛型算法的使用。定义一个 vector, 元素类型为 int, 插入 10 个随机数 , 使用 sort 按升序排序 , 输出每个元素的值 ,再按降叙排序 , 输出每个元素的值。练习用find 查找元素。用min 与精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告max 找出容器中的最小元素个最大元素, 并输出。四、实验结果与分析(源程序及相关说明) 1

5、、 练习 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(NULL); /随机产生十个数for (int i=0;i10;i+) myV、push_back(rand(); sort(myV、begin(),myV、end(),sortup); /用 sort排序升序vector:itera

6、tor it1; for (it1=myV 、begin();it1!=myV 、end();it1+) cout(*it1)setw(6); /打印数组 coutendl; int min=myV0; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告for (it1=myV 、begin()+1;it1!=myV 、end();it1+) if(*it1)min)min=(*it1); cout最小元素为 min

7、max)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(6); cout

8、nendl; /随机在 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 (); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 22 页 - - - - - -

9、 - - - - 程序设计艺术与方法课程实验报告for (it1=myV 、begin();it1!=myV 、end();it1+) cout(*it1)setw(6); coutendl; myV、clear();/清空数组if(myV 、empty() cout Its empty! endl; system(PAUSE); /press any key to continue 、 、 、return 0; 运行截图 : 2 练习泛型算法的使用:#include #include /#inclued 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名

10、师归纳 - - - - - - - - - -第 4 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告using namespace std; typedef list lin; int value=2,4,6,1,8; 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); lin

11、2、push_front(4); lin2、insert(lin2、begin(),value,value+5); coutlin2 内的元素为 :; print(lin2); lin2、sort(); cout排序后的 lin2: ; print(lin2); lin2、push_front(10);/在 list 头部插入 10 cout在 list 头部插入 10 之后的结果 :; print(lin2); lin2、remove(6); cout删除一个数后的 lin1:; print(lin2); system(PAUSE);/press any key to contineu 、

12、、 、精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告return 0; 运行截图 : 二实验名称搜索算法的实验姓名系院专业信息工程系班级物联网一班学号实验日期指导教师成绩一、实验目的与要求1.掌握宽度优先搜索算法。2.掌握深度优先搜索算法。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 22 页 - - - -

13、- - - - - - 程序设计艺术与方法课程实验报告二、实验预习内容1 宽度优先搜索算法:又称广度优搜索。就是最简单的图的算法的原形。其属于一种盲搜寻法,目的就是系统地展开并检查图中的所有节点,以寻找结果。换句话说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。2 深度优先搜索算法:它的目的就是要达到被搜索结构的叶结点。在一个HTML 文件中 ,当一个超链被选择后,被连接的 HTML 文件将执行深度优先搜索,即在搜索其余的超链走到不能再深入为止 ,然后返回到某一个HTML文件 ,再继续选择该HTML文件中的其她超链。当不再有其她超链可选择时,说明搜索已经结束。三、实验项目摘要

14、1、将书上的走迷宫代码上机运行并检验结果, 并注意体会搜索的思想。2 、八皇后问题 : 在一个国际象棋棋盘上放八个皇后, 使得任何两个皇后之间不相互攻击,求出所有的布棋方法。上机运行并检验结果。思考 : 将此题推广到N 皇后的情况 , 检验在 N 比较大的情况下, 比方说 N=16 的时候, 您的程序能否快速的求出结果, 如果不能 , 思考有什么方法能够优化算法。3骑士游历问题: 在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍, 对于任意给定的顶点, 输出一条符合上述要求的路径。4 倒水问题 : 给定 2 个没有刻度容器, 对于任意给定的容积, 求出如何只用两个瓶装出L 升的水 , 如果可以

15、 , 输出步骤 , 如果不可以 , 请输出 No Solution 。四、实验结果与分析(源程序及相关说明) 2,八皇后问题 : #include /*声明常量 N 存储行与列 */ #define N 8 #define NUM 8 /*声明全局变量 ,hNN 控制盘格 ,HNN 控制输出 ,nN 存储每一步的*纵坐标 ,count 用于计数。*/ int hNN,nN,HNN; int count=0; /*声明函数 void tryit(int,int) 尝试符合条件的方法 */ void tryit(int,int); /*声明函数 void outputArray(intN) 输出数

16、组 */ void outputArray(intN); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告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); /*定义函数 voi

17、d tryit(int,int) 尝试符合条件的方法 */ void 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+

18、) if(hij0) Hij=1; else Hij=0; count=count+1; /*输出前几种情况 */ if(count=NUM) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告printf(- 布局%d-n,count); outputArray(H); /*对下一种走法 ,清楚前一次的影响 */ for(i=0;i=N-1;i+) for(j=0;j7) /*清楚前一次影响 */ for(i=0;

19、i=N-1;i+) for(j=0;j=0) tryit(x-1,nx-1+1); else tryit(0,0); /*尝试下一格 */ else tryit(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;j+) printf(%d ,hij); printf(n); 运行截图 : 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第

20、 11 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告4、倒水问题 :#includestdi

21、o、h int 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 An); printf(pour A Bn); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告 else x=y=0; if(caca-x) /如果 b中的水大于

22、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倒空/ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 22 页 - - - - - - - - - - 程序设计艺术与

23、方法课程实验报告 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); if(y=cc) /如果 b中的水已经与 cc相等,那就结束 / break; 精品资料 - - - 欢迎下载 - - - - - - - - - - -

24、欢迎下载 名师归纳 - - - - - - - - - -第 16 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告 if(y=cb) /如果 b中的水满了 ,就把 b 倒空/ y=0; printf(empty Bn); printf(successn); return 0; 运行截图 : 三实验名称计算几何算法的实现精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 17 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告姓名系

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

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

27、思考这样的情况。4房间最短路问题: 给顶一个内含阻碍墙的房间, 求解出一条从起点到终点的最最短路径。房间的边界固定在 x=0,x=10,y=0 与y=10。起点与重点固定在(0,5)与 (10,5)。房间里还有0 到18 个墙, 每个墙有两个门。输入给定的墙的个数, 每个墙的 x 位置与两个门的y 坐标区间 , 输出最短路的长度精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 18 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告四、实验结果与分析(源程序及相关说明)

28、 3、思考 : 用跨立方法 ,跨立的含义就是 :如果一条线段的一个端点在一条直线的一边,另一个端点在这条直线的另一端 ,我们就说这条线段跨立在这条直线上。线段相交满足且只需满足如下两个条件就可以了:1 两条线段相互跨立;2 一条线段的一个端点在另一条线段上。如果两线段相交 ,则两线段必然相互跨立对方。若p1p2跨立 p3p4 ,则矢量 ( p1 p3 ) 与( p2 - p1 )位于矢量 ( p4 p3 )的两侧 ,即( p1 p3) ( p4- p3 ) * ( p2 p3 ) ( p4 p3 ) 0。当( p1 p3 ) ( p4p3 ) = 0 时,说明( p1 p3 ) 与 ( p4

29、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 ) ( p4 - p1 ) = 0。代码中函数 bool segment_intersect() 用于判断 p1、p2 构成的线段与 p3、p4构成的线段就是否相交。可以瞧出

30、共五种情况两线段就是相交的,反之就输出“ 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、first; v1、second=p2 、second-p1 、first; v2、first=p1、first-p、first; v2、second=p1 、

31、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&p 、first= 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - -

32、- - - - -第 19 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告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

33、&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&pointi 、firstp0、first) p0=pointi; k=i; point、erase(point 、begin()+k); point、insert(point、begin()

34、,p0); vectorconvex_hull; do convex_hull、push_back(point0); startPoint=point0; point、erase(point 、begin(); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 20 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告sort(point、begin(),point、end(),sortByPolorAngle); if(point0=convex_hull0)break

35、; 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; 运行截图 : 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 21 页，共 22 页 - - - - - - - - - - 程序设计艺术与方法课程实验报告精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 22 页，共 22 页 - - - - - - - - - -