课程试验报告

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 <iostream>#in elude <vector>#in cludevioma nip>#in clude<ctime>#i nclude <algorithm>using n amespace std;vector <int> myV;bool sortup(i nt v1,i nt v2)retur n v1<v2;int main (i nt argc, char *argv)srand(t

4、ime(NULL); for (int i=0;i<10;i+)myV.push_back(ra nd();sort(myV.beg in (),myV.e nd(),sortup);vector<in t>:iterator it1;for (it1=myV .begi n();it1!=myV .en d();it1+)8山<<(51)<<$6上可(6)；cout<<e ndl;int mi n=m yV0;for (it1=myV .begi n()+1;it1!=myV .en d();it1+)if(*it1)<mi n)m

5、i n=(*it1);cout<<"最小元素为"wminwendl;int max=myV0;for (it1=myV .begi n();it1!=myV .en d();it1+)if(*it1)>max)max=(*it1);cout<<"最大元素为"wmaxwendl;cout<<e ndl;int value=ra nd();it1=find(myV .begin(),myV.end(),value); if(*it1)=value)cout«"找到了这个随机数"<&

6、lt;endl ;elsecoutvv"没有找到这个随机数"<<endl;myV.i nsert(myV.e nd(),value);coutvv"插入尾部的随机数为"vvvaluevvendl; for (it1=myV .begi n();it1!=myV .en d();it1+) cout<v(*it1)vvsetw(6);cout<<"n"<<e ndl;int t=ra nd();myV.i nsert(myV.begi n(),t);coutvv"插入头部的随机数为&q

7、uot;v<t<vendl; for (it1=myV .begi n();it1!=myV .en d();it1+) cout<v(*it1)v<setw(6);coutvve ndl;myV.pop_back ();for (it1=myV .begi n();it1!=myV .en d();it1+)cout<v(*it1)v<setw(6);coutvve ndl;myV.clear();if(myV .empty()cout vv "It's empty!" vv en dl;system("PAUSE&q

8、uot;); /press any key to con ti nu e. return 0;C：MJsersVIC BO'S'Do匚umaiW侏27&54617 4QB9 G269 13975 14767 107fc 22408 28B1S曇小兀畫为1&翦最尢兀素为2U&LG囂頁找到这个施觇舉常儿尾部的随 021435L6352?&54617 4SS9 G289 19975 147t? 1076 23438 2801G 21435插入头部的随机数为29280Z02S31&352765461?4886289 13975 1476? 1?0

9、76 23408 2801& 21435ZQ2&Q 16352765461749896289 13975 14767 1?076 23408 28016It's： empty*请按任意键继续-2练习泛型算法的使用：#i nclude<list>#in clude<iostream> using n amespace std; typedef list<i nt> lin;in t value=1,6,7,8,9;void prin t(lin &l)int i;lin:iterator lit;for(lit=l.beg in

10、 ();lit!=l.e nd();lit+) cout<<(*lit)<<""cout«e ndl;bool sortsp(i nt v1,i nt v2)retur n v1>v2;int mai n()lin Iin2;lin 2.push_fro nt(3);lin 2.push_fro nt(4);lin 2.i nsert(li n2.beg in( ),value,value+5); cout<<"lin2内的元素为："prin t(li n2);lin 2.sort();cout

11、1;"排序后的 lin2:"prin t(li n2);lin 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;实验二 搜索算法的实现实验名称实验二搜索算法的实现姓名汪子成系院专业信息工程系班级计算机15-1班学号2015216758实验日期指导教师徐本柱成绩一、实验目的和要求1 掌握宽度优先搜索

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

13、结果与分析(源程序及相关说明)2,八皇后问题：#i nclude <stdio.h>#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);v

14、oid tryit(i nt x,i nt y)int i,j;if(cou nt<=NUM)if(H00=1 &&H14=1 &&H27=1 &&H3 5=1 &&H42=1 &&H 56=1&&H 61=1 &&H73=1)&&coun t!=1)elseif(x>=0&& x<=N-1 &&y>=0&&y<=N-1 &&hxy=O)for(j=0;jv=7;j+)if(

15、hxj=O)hxj=x+1;if(hjy=O)hjy=x+1;if(x+j>=0&& x+jv=N-1 &&y+j>=0&&y+j<=N-1 &&hx+jy+j=O) hx+jy+j=x+1;if(x+j>=0&& x+j<=N-1 &&y-j>=0&&y-j<=N-1 &&hx+jy-j=0) hx+jy-j=x+1;if(x-j>=0&& x-j<=N-1 &&y+j>=0

16、&&y+j<=N-1 &&hx-jy+j=0) hx-jy+j=x+1;if(x-j>=0&& x-j<=N-1 &&y-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(hij<0)Hij=1;elseHij=0;coun t=co un t+1;01114= =a(+r lnhvohd04(+±vnh

17、vo上)04FA)七S-L+XWA4-(L+vxc-vx)七 AJ_(+r lnhvohd04(+±lnhvo上)04(H)Ae<lndlnogun8-=5p&nlfe=)匕 £d(lAInNHVluns)七if(x-1>=0)tryit(x-1, nx-1+1);elsetryit(0,0);elsetryit(x,y+1);void outputArray(i nt hN)int i,j;for(i=0;i<=N-1;i+)for(j=0;jv=N-1;j+)prin tf("%d ",hij); prin tf("

18、;n");3.骑士游历问题：#i nclude <stdio.h>int board88 = 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, min, tmp;i = x;j = y;boardii = 1;文档for(m =

19、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 < 0 | tmpi > 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

20、= 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 < 0 | tmpi > 7 | tmpj > 7) con ti nue;if(boardtmpitmpj = 0)existsl+;tmp = exists0;min = 0;for(l = 1; l < count; l+) if(existsl < tmp) tmp

21、= 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) printf("游历完成！ n");else printf("游历失败！ n");for(i = 0; i < 8; i+) f

22、or(i = 0; i < 8; i+) printf("%2d ", boardij); putchar('n');return 0;7G2224Pro cess exited afterseconds uiitli return value 0请按任意键f张续.实验三 计算几何算法的实现实验名称实验二计算几何算法的实现姓名汪子成系院专业信息工程系班级计算机15-1班学号2015216758实验日期指导教师徐本柱成绩一、实验目的和要求1. 理解线段的性质、叉积和有向面积。2. 掌握寻找凸包的算法。3. 综合运用计算几何和搜索中的知识求解有关问题。、实

23、验预习内容1 预习ICPC讲义，大致了解计算几何算法的相关内容。2 了解实现该算法的中一些使用方法。3 会使用该算法解决实际问题。、实验项目摘要1. 将讲义第三章第三节中的凸包代码上机运行并检验结果。2. 完成讲义第三章的课后习题，上机运行并检验结果。3思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端 点重合，思考这样的情况怎么办。4.房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在 x=0,x=10,y=0和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0到18个 墙，每个墙有两个门。输入给定的墙的

24、个数，每个墙的x位置和两个门的y坐标区间，输出最短路的长度。下图是个例子：四、实验结果与分析(源程序及相关说明)3.思考：用跨立方法。线段相交满足且只需满足如下两个条件就可以了：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 ) * ( p4 - p3 ) X (

25、p2 - p3) > 0。当(p1 - p3 ) X ( p4 - p3 ) = 0 时，说明(p1 - p3 )和(p4 - p3 )共线，但是因为已经通过快速排斥试验，所以p1 一定在线段p3p4上；同理，(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

26、 - p1 ) >= 0。代 码中函数bool segment_intersect(用于判断p1、p2构成的线段和p3、p4构成的线段是否相 交。可以看出共五种情况两线段是相交的，反之就输出“ The two are Not in tersected”4房间最短路问题：#in clude<iostream>#in clude<utility>#in clude<vector>#i nclude<algorithm>using n amespace std;typedef pair<double,double> POINT;dou

27、ble 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 min _x=p1.first<p2.firs

28、t?p1.first:p2.first;double max_x=p1.first>p2.first?p1.first:p2.first;double min _y=p1.sec on d<p2.sec on d?p1.sec on d:p2.sec ond;double max_y=p1.sec on d>p2.sec on d?p1.sec on d:p2.sec ond;if(p.first>=min_x&&p.first<max_x&&p.seco nd>= min_y&&p.seco nd<=m

29、ax_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(d<0)return true;if(d >0)return false;if(d=0&&on segment(startPoint,p1,p2)return true;if(d= =0&&on _segme nt(p2,star

30、tPoi nt,p1)return true;return false;void find_con vex_hull(vector<POINT >& poi nt)POINT p0=poi nt0;int k=0;for(int i=0;i<point.size();i+)if(po in ti.sec on d<p0.sec on d|poin ti.sec on d=p0.sec；ond&&poin ti.first<p0.first)p0=poi nti;k=i;poi nt.erase(poi nt.begi n()+k);poin

31、 t.i nsert(po in t.begi n() ,p0); vector<POINT>co 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

32、);for(i nt j=0;j<c on vex_hull.size();j+)cout«c onv ex_hullj.first<<' '<<c on vex_hullj.sec on d<<e ndl;int mai n()vector<POINT> pv;double x,y;int i;cout«"请输入 10 个点 <x,y>: "<<endl; for(i=1;i<=10;i+) cout<v"No."v<iv

33、v':'cin> >x>>y;pv.push_back(make_pair(x,y);cout«endl; find_convex_hull(pv);system("Pause");return 0;实验四 动态规划算法的实现实验名称实验四动态规划算法的实现姓名汪子成系院专业信息工程系班级计算机15-1班学号2015216758实验日期指导教师徐本柱成绩一、实验目的和要求1 理解动态规划的基本思想、动态规划算法的基本步骤2 掌握动态规划算法实际步骤、实验预习内容1 动态规划算法的基本要素2 .最长公共子序列3矩阵连乘问题、实

34、验项目摘要(1)求两个字符串的最长公共子序列。-151 - X的一个子序列是相应于 X下标序列1,2,m的一个子序列，求解两个 序列的所有子序列中长度最大的，例如输入：pear, peach输出：pea。(2) 给定两个字符串a和b,现将串a通过变换变为串b,可用的操作为，删除串 a中的一个字符；在串a的某个位置插入一个元素；将串a中的某个字母换为另 一个字母。对于任意的串a和串b,输出最少多少次能够将串变为串 bo思考： 输出变换的步骤。(3) 输入一个矩阵，计算所有的子矩阵中和的最大值。例如，输入0 -2 -7 0 9 2-6 2 -4 1 -4 1 -1 8 0 -2输出为：15思考：当

35、矩阵很大时，比如100*100的矩阵， 你的程序还能够很快的得出结果吗，如果不能，请思考如何用动态规划的思想解决。四、实验结果与分析(源程序及相关说明) 源代码如下：1.求两个字符串的最长公共子序列。#in clude<iostream>#in clude<stri ng>using n amespace std;void longest(string s1,string s2)int max,tep,i,j;int a100100;for(i=0;i<s1.size();i+)for(j=0;j<s2.size();j+)aij=O;for (j=0;j<s2.size();j+)if (s10=s2j)a0j=1;for (i=0;i<s1.size();i+)if (s1i=s20)ai0=1；max=aOO;tep=O;for(i=1;i<s1.size();i+)for(j=1;j<s2.size();j+) if(s1i=s2j) aij=ai-1j-1+1;if(max<aij) max=aij;t