课程试验报告讲解

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 中，

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

3、 输出每个元素的值， 再按降叙排序， 输出每个元素的值。 练习用 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(NULL); for (int i=

4、0;i10;i+) myV.push_back(rand();sort(myV.begin(),myV.end(),sortup); 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);cout 最小元素为 minmax)max=(*it1);cout 最大元素为 maxendl;课程实验报告cout

5、endl; 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;int t=rand(); myV.insert(myV.begin(),t);cout 插入头部

6、的随机数为 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(PAUSE); /press any key to continue. return 0;2 练习泛型算法的使用： #inclu

7、de #include using namespace std; typedef list lin; int value=1,6,7,8,9; void print(lin &l) int i; lin:iterator lit; for(lit=l.begin();lit!=l.end();lit+) cout(*lit) ; coutv2; int main() lin lin2; lin2.push_front(3); lin2.push_front(4); lin2.insert(lin2.begin(),value,value+5); coutlin2 内的元素为： ; print(

8、lin2); lin2.sort();cout 排序后的 lin2: ; print(lin2); lin2.push_front(10);cout 在 list 头部插入 10 之后的结果： ; print(lin2);lin2.remove(6); cout 删除一个数后的 lin1:; print(lin2);system(PAUSE); return 0;实验二 搜索算法的实现课程实验报告实验名称实验二 搜索算法的实现姓名汪子成 系院专业信息工程系班 级 计算机 15-1 班学号2015216758实验日期指导教师徐本柱成绩一、实验目的和要求1掌握宽度优先搜索算法 ;2掌握深度优先搜索

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

10、四、实验结果与分析(源程序及相关说明)2，八皇后问题：#include #define N 8#define NUM 8int hNN,nN,HNN;int count=0;void tryit(int,int);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 x,int y)int i,j;if(count=0&x=0&y=N-1&

11、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;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-

12、1,nx-1+1); else tryit(0,0);elsetryit(x,y+1);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);10课程实验报告3. 骑士游历问题：#include 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 nexti

13、8 = 0;int nextj8 = 0;int exists8 = 0;int i, j, k, m, l;int tmpi, tmpj;int count, min, tmp;i = x;j = y;11课程实验报告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 =

14、 0) nextil = tmpi; nextjl = tmpj;l+; count = l;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;12课程实验报告 if(boardtmpitmpj = 0) existsl+; tmp = exists0;min = 0;

15、for(l = 1; l count; l+) if(existsl tmp) tmp = existsl;min = l; i = nextimin; j = nextjmin; boardij = m; return 1;int main()int startx, starty;int i, j;printf( 输入起始点： ); scanf(%d %d, &startx, &starty); if(travel(startx, starty) printf( 游历完成！ n); else printf( 游历失败！ n);13课程实验报告for(i = 0; i 8; i+) for(j

16、 = 0; j 8; j+) printf(%2d , boardij);putchar(n); return 0;实验三 计算几何算法的实现实验名称实验二 计算几何算法的实现姓名汪子成系院专业信息工程系班级计算机 15-1 班学号2015216758实验日期指导教师徐本柱成绩14课程实验报告、实验目的和要求1. 理解线段的性质、叉积和有向面积。2. 掌握寻找凸包的算法。3. 综合运用计算几何和搜索中的知识求解有关问题。、实验预习内容1预习 ICPC 讲义，大致了解计算几何算法的相关内容。 2了解实现该算法的中一些使用方法。3会使用该算法解决实际问题。、实验项目摘要1. 将讲义第三章第三节中的

17、凸包代码上机运行并检验结果。2. 完成讲义第三章的课后习题，上机运行并检验结果。3. 思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端 点重合，思考这样的情况怎么办。4. 房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房 间的边界固定在 x=0,x=10,y=0 和 y=10。起点和重点固定在 (0,5) 和(10,5)。房间里还有 0 到 18 个 墙，每个墙有两个门。输入给定的墙的个数，每个墙的 x 位置和两个门的 y 坐标区间，输出最 短路的长度。下图是个例子：15课程实验报告四、实验结果与分析(源程序及相关说明)3.思考：

18、 用跨立方法。线段相交满足且只需满足如下两个条件就可以了： 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 p3 )共线，但是因为已经通过快速排斥试验，所以p1 一定在线段 p3p4上；同理， ( p4 p3 ) (p2 p3 ) = 0 说

19、明 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 构成的线段是否相 交。可以看出共五种情况两线段是相交的，反之就输出“ The two are Not intersected!”4.房间最短路问题：#include#incl

20、ude#include#includeusing 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.second;bool on_segment(POINT p,POINT

21、 p1,POINT p2)double min_x=p1.firstp2.first?p1.first:p2.first;double min_y=p1.secondp2.second?p1.second:p2.second;16课程实验报告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=direction(startPoint,p

22、1,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&pointi.firstp0.first) p0=po

23、inti;k=i;point.erase(point.begin()+k); point.insert(point.begin(),p0);vectorconvex_hull;doconvex hull.push back(point0);17课程实验报告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);w

24、hile(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;18课程实验报告19课程实验报告实验四 动态规划算法的实现实验名称实验四 动态规划算法的

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

26、操作为，删除串 a中的一 个字符；在串 a的某个位置插入一个元素； 将串 a 中的某个字母换为另 一个字母。对于任意的串 a 和串 b，输出最少多少次能够将串变为串 b。 思考： 输出变换的步骤。(3) 输入一个矩阵，计算所有的子矩阵中和的最大值。 例如，输入 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 输出为： 15 思考：当矩阵很大时，比如 100*100的矩阵， 你的程序还能够很快的得出结果吗， 如果不能， 请思考如何用动态规划的思想解 决。四、实验结果与分析(源程序及相关说明) 源代码如下：1. 求两个字符串的最长公共子序列。#include#includeusing namespace 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=0;for (j=0;js2.size();j+)if (s10=s2j)a0j=1;for (i=0;is1.size();i+)if (s