课程实验报告讲解

1、实验一 STL的熟悉与使用实验名称实验一 STL的熟悉与使用姓名汪子成系院专业信息工程系班级计算机15-1班学号2015216758实验日期指导教师徐本柱成绩一、实验目的和要求1 .掌握C+中STL的容器类的使用；2 .掌握C+中STL的算法类的使用.二、实验预习内容1.预习ICPC讲义，大致了解 STL的相关内容。2 .了解STL中一些类 vector list类的使用方法3 .了解泛型算法的使用三、实验项目摘要(1) 练习vector和list的使用。疋义一个空的vector，兀素类型为int,生成10个随机数插入到 vector中，用迭代器遍历vector并输出其中的元素值。在vecto

2、r头部插入一个随机数，用迭代器遍历vector并输出其中的元素值。用泛型算法find查找某个随机数，如果找到便输出，否则将此数插入vector尾部。用泛型算法 sort将vector排序，用迭代器遍历 vector并输出其中的兀素值。 删除vector尾部的兀素，用迭代器遍历vector并输出其中的兀素值。将vector清空。疋义一个list，并重复上述实验，并注意观祭结果。(2) 练习泛型算法的使用。定义一个vector，元素类型为int,插入10个随机数，使用 sort按升序排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用find查找元素。用min和 max找出容器中的最小元

3、素和最大元素，并输出。四、实验结果与分析(源程序及相关说明)1.练习vector和list的使用：#i nclude #in elude #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 (int i=0;i10;i+)myV.push_back(ra nd();sort(myV.beg in (),myV.e nd(),

4、sortup);vector:iterator it1;for (it1=myV .begi n();it1!=myV .en d();it1+)8山(51)$6上可(6)；coute ndl;int mi n=m yV0;for (it1=myV .begi n()+1;it1!=myV .en d();it1+)if(*it1)mi n)mi n=(*it1);coutmax)max=(*it1);coutw最大元素为wmaxwendl;coute ndl;int value=ra nd();it1=find(myV .begin(),myV.end(),value); if(*it1)=

5、value)cout找到了这个随机数endl ;elsecoutvv没有找到这个随机数endl;myV.i nsert(myV.e nd(),value);coutvv插入尾部的随机数为vvvaluevvendl; for (it1=myV .begi n();it1!=myV .en d();it1+) 8山(*让1)$6上可(6)；coutne ndl;int t=ra nd();myV.i nsert(myV.begi n(),t);coutvv插入头部的随机数为vvvendl; for (it1=myV .begi n();it1!=myV .en d();it1+) coutvv(*

6、it1)vvsetw(6);coutvve ndl;myV.pop_back ();for (it1=myV .begi n();it1!=myV .en d();it1+)coutvv(*it1)vvsetw(6);coutvve ndl;myV.clear();if(myV .empty()cout Its empty! en dl;C:ll &ersVIC BOSSDocumentsnp 1 .exe祐入头却的随机数为20280028016352765461720280163527654617111s empty!请按任意键继绞.il为21435635276546174889system

7、(PAUSE); /press any key to con ti nu e. return 0;6352765461748 91635曰w I甌夫兀素752801&13975 14767 19076 23408 28M16629 13975 14767 1907& 23408 2S016 214354S896289 13975 1476? 190?6 23408 28016 2143548896289 13975 14767 19076 23488 280162练习泛型算法的使用：#i nclude#in clude using n amespace std; typedef list li

8、n;in t value=1,6,7,8,9;void prin t(lin &l)int i;lin:iterator lit;for(lit=l.beg in ();lit!=l.e nd();lit+) cout(*lit)v2;int mai n()lin lin2;lin 2.push_fro nt(3);lin 2.push_fro nt(4);lin 2.i nsert(li n2.beg in( ),value,value+5);coutlin2内的元素为：;prin t(li n2);lin 2.sort();cout排序后的 lin2:;prin t(li n2);lin

9、2.push_fro nt(1O);cout在list头部插入10之后的结果：;prin t(li n2);lin 2.remove(6);cout删除一个数后的lin 1:;prin t(li n2);system(PAUSE);return 0;C:UsersVIC 8OSSDocumen内的元素为：1？ 8 9 4 3排序看的lin2： 1 3 4 6 7 9 91list头部插入10之后的结果；10 1346789删睁一个1101=10 1 3 4 7 8 9碾任*礙镁.实验二 搜索算法的实现实验名称实验二搜索算法的实现姓名汪子成系院专业信息工程系班级计算机15-1班学号2015216

10、758实验日期指导教师徐本柱成绩一、实验目的和要求1 掌握宽度优先搜索算法；2 .掌握深度优先搜索算法.二、实验预习内容1. 预习ICPC讲义中的搜索的内容2. 了解什么是深度优先搜索和广度优先搜索。三、实验项目摘要1.将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。2八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出 所有的布棋方法。上机运行并检验结果。3.骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。4倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升的水

11、，如果可以，输出步骤，如果不可以，请输出No Solution四、实验结果与分析(源程序及相关说明)2,八皇后问题：#i nclude #defi ne N 8#defi ne NUM 8int hNN ,n N,HNN;int coun t=0;void tryit(i nt, int);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(i

12、nt x,i nt y)int i,j;if(cou nt=0& x=0&y=0& x+jv=N-1 &y+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;coun t=co un t+1;if(cou nt=NUM)printf(布局 %dn,cou nt);outputArray(H);for(i=0;i=N-1;i+)for(j=0;j7)f

13、or(i=0;i=N-1;i+)for(j=0;j=0)tryit(x-1, nx-1+1);elsetryit(O,O);elsetryit(x,y+1);void outputArray(i nt hN)int i,j;for(i=0;i=N-1;i+)for(j=0;j=N-1;j+)prin tf(%d ,hij);prin tf(n);丄0kl006981308Q布局200000600 0 0 10 0 0布局30 0 6 0 0 0 60 3 0 0 0 103.骑士游历问题：#i nclude int board88 = 0;int travel( int x, int y)in

14、t 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, min, tmp;i = x;i = v;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 + ktmove

15、1k;tmpj = j + ktmove2k;if(tmpi 0 | tmpj 7 | tmpj 7) con ti nue;if(boardtmpitmpj = 0) n extil = tmpi;n extjl = tmpj;l+;count = l;if(co unt = 0) return 0;else if(co unt = 1) min = 0;else for(l = 0; l count; l+) for(k = 0; k 8; k+) tmpi = n extil + ktmove1k;tmpj = n extjl + ktmove2k;if(tmpi 0 | tmpj 7

16、| tmpj 7) con ti nue;if(boardtmpitmpj = 0)existsl+;tmp = exists0;min = 0;for(l = 1; l count; l+) if(existsl tmp) tmp = existsl;min = l;i = n exti min;j = n extjmi n;boardij = m;return 1;int mai n()int startx, starty;int i, j;printf(输入起始点:);scanf(%d %d, &startx, &starty); if(travel(startx, starty) pr

17、intf(游历完成！ n);else printf(游历失败！ n);for(i = 0; i 8; i+) for(j = 0; j 8; j+) printf(%2d , boardij);putchar(n);return 0;C:UsersVIC BOSSDocurnentsp2,魏入起粗点；0 1诱历完成！416212S4316197 22344172829422524274841181523 B45402556473052 3?2661464914579 6453505560313438 51621136335813B3 103?5459123532E*pocess exited

18、aftei*seconds with return value 0青按任意键继塚.实验三 计算几何算法的实现实验名称实验一二计算几何算法的实现姓名汪子成系院专业信息工程系班级计算机15-1班学号2015216758实验日期指导教师徐本柱成绩、实验目的和要求1. 理解线段的性质、叉积和有向面积。2. 掌握寻找凸包的算法。3. 综合运用计算几何和搜索中的知识求解有关问题。、实验预习内容1 预习ICPC讲义，大致了解计算几何算法的相关内容。2 了解实现该算法的中一些使用方法。3 会使用该算法解决实际问题。、实验项目摘要1. 将讲义第三章第三节中的凸包代码上机运行并检验结果。2. 完成讲义第三章的课后

19、习题，上机运行并检验结果。3思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端 点重合，思考这样的情况怎么办。4. 房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在 x=0,x=10,y=0和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0到18个 墙，每个墙有两个门。输入给定的墙的个数，每个墙的x位置和两个门的y坐标区间，输出最短路的长度。下图是个例子：四、实验结果与分析(源程序及相关说明)3.思考：用跨立方法。线段相交满足且只需满足如下两个条件就可以了：1两条线段相互跨立；2 一条线段的一个端点在另

20、一条线段上。如果两线段相交，则两线段必然相互跨立对方。若p1p2跨立p3p4，则矢量(pl - p3 )和(p2 - pl )位于矢量(p4 - p3 )的两侧，即(pl - p3) X ( p4- p3 ) * ( p2 - p3 ) X ( p4 - p3 ) 0。当(pl - p3 ) X ( p4 - p3 ) = 0 时，说明(pl - p3 )和(p4 - p3 )共线，但是因为已经通过快速排斥试验，所以pl 一定在线段p3p4上；同理，(p4 - p3 ) X (p2 - p3 ) = 0说明p2 一定在p3p4上。所以判断p1p2跨立 Q1Q2 的依据是：(pl - p3 )

21、X ( p4 - p3 ) * ( p4 - p3 ) X ( p2 - p3 ) = 0。同理判 断 Q1Q2 跨立 P1P2 的依据是：(p3 - pl ) X ( p2 - pl ) * ( p2 - pl ) X ( p4 - pl ) = 0。代 码中函数bool segment_intersect(用于判断pl、p2构成的线段和p3、p4构成的线段是否相 交。可以看出共五种情况两线段是相交的，反之就输出“The two are Not in tersected”4房间最短路问题：#in clude#in clude#in clude#i ncludeusing n amespace

22、 std;typedef pair POINT;double direction(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

23、 min _x=p1.firstp2.first?p1.first:p2.first;double min _y=p1.sec on dp2.second?p1.second:p2.second;if(p.first=min_x&p.first= min_y&p.seco nd=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)r

24、eturn false;if(d=0&on _segme 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 p0=poi nt0;int k=0;for(int i=0;ipoint.size();i+)if(po in ti.sec on dp0.sec on d|poin ti.sec on d=p0.sec；ond&poin ti.firstp0.first)

25、p0=poi nti;k=i;poi nt.erase(poi 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 e

26、x_hullc on vex_hull.size()-1);while(1);for(i nt j=0;jc on vex_hull.size();j+)coutc onv ex_hullj.first c on vex_hullj.sec on de ndl;int mai n()vector pv;double x,y;int i;cout请输入 10 个点 : endl;for(i=1;i=10;i+) coutvNo.v xy;pv.push_back(make_pair(x,y);coutendl; find_convex_hull(pv);system(Pause);return

27、0;实验四 动态规划算法的实现实验名称实验四动态规划算法的实现姓名汪子成系院专业信息工程系班级计算机15-1班学号2015216758实验日期指导教师徐本柱成绩一、实验目的和要求1 理解动态规划的基本思想、动态规划算法的基本步骤2 掌握动态规划算法实际步骤二、实验预习内容1 动态规划算法的基本要素2.取长公共子序列3 矩阵连乘问题、实验项目摘要(1) 求两个字符串的最长公共子序列。-151 - X的一个子序列是相应于 X下标序列1,2,m的一个子序列，求解两个 序列的所有子序列中长度最大的，例如输入：pear, peach输出：pea。(2) 给定两个字符串a和b,现将串a通过变换变为串b,可

28、用的操作为，删除串 a中的一个字符；在串a的某个位置插入一个元素；将串a中的某个字母换为另 一个字母。对于任意的串a和串b,输出最少多少次能够将串变为串 bo思考： 输出变换的步骤。(3) 输入一个矩阵，计算所有的子矩阵中和的最大值。例如，输入0 -2 -7 0 9 2-6 2 -4 1 -4 1 -1 8 0 -2输出为：15思考：当矩阵很大时，比如100*100的矩阵， 你的程序还能够很快的得出结果吗，如果不能，请思考如何用动态规划的思想解决。四、实验结果与分析(源程序及相关说明) 源代码如下：1.求两个字符串的最长公共子序列。#in clude#in cludeusing n amesp

29、ace std;void longest(string s1,string s2)int max,tep,i,j;int a100100;for(i=0;is1.size();i+) for(j=0;js2.size();j+) aij=O;for (j=0;js2.size();j+)if (s10=s2j)a0j=1;for (i=0;is1.size();i+)if (s1i=s20)ai0=1;max=a00;tep=0;for(i=1;is1.size();i+) for(j=1;js2.size();j+)if(s1i=s2j)aij=ai-1j-1+1;if(maxaij)max=aij;tep=i;if(max=0)COUtvv没有公共子序列!；elseCOUtvv两个字符串的最长公