课程实验报告汇总（精编版）

1、. . . . 1 / 24 实验一 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 找出容器中的最小元素和最大元素，并输出。. . . . 2 / 24 四、实验结果与分析（源程序与相关说明）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=0;

4、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; . . . . 3 /

5、24 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); coutnendl; int t=rand(); myv.insert(myv.begin(),t); co

6、ut插入头部的随机数为 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() . . . . 4 / 24 cout its empty! endl; system(pause); /press any key to continue. return 0; 2 练习

7、泛型算法的使用：#include #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); coutli

8、n2的元素为： ; print(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; 实验二搜索算法的实现. . . . 6 / 24 实验名称实验二搜索算法的实现姓名汪子成系院专业信息工程系班级计算机 15-1 班学号2015216758 实验日期指导教师徐本柱成绩一、实验目的和要

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

10、出no solution . . . . 7 / 24 四、实验结果与分析（源程序与相关说明）2，八皇后问题：#include #define n 8 #define num 8 int 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(

11、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; else hij=0; . . . . 9 / 24 count=count+1; if(c

12、ount=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); else tryit(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); . . . . 11 / 24 3. 骑士游历问题：#include in

13、t 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; . . . . 12 / 24 boardij = 1; for(m = 2; m = 64; m+) for

14、(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+; 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

15、; k+) tmpi = nextil + ktmove1k; tmpj = nextjl + ktmove2k; if(tmpi 0 | tmpj 7 | tmpj 7) continue; . . . . 13 / 24 if(boardtmpitmpj = 0) existsl+; tmp = exists0; min = 0; for(l = 1; l count; l+) if(existsl tmp) tmp = existsl; min = l; i = nextimin; j = nextjmin; boardij = m; return 1; int main() int s

16、tartx, starty; int i, j; printf(输入起始点： ); scanf(%d %d, &startx, &starty); if(travel(startx, starty) printf(游历完成！ n); else printf(游历失败！ n); . . . . 14 / 24 for(i = 0; i 8; i+) for(j = 0; j 8; j+) printf(%2d , boardij); putchar(n); return 0; 实验三计算几何算法的实现实验名称实验二计算几何算法的实现姓名汪子成系院专业信息工程系班级计算机 15-1

17、 班学号2015216758 实验日期指导教师徐本柱成绩. . . . 15 / 24 一、实验目的和要求1. 理解线段的性质、叉积和有向面积。2. 掌握寻找凸包的算法。3. 综合运用计算几何和搜索中的知识求解有关问题。二、实验预习容1预习 icpc 讲义，大致了解计算几何算法的相关容。2了解实现该算法的中一些使用方法。3会使用该算法解决实际问题。三、实验项目摘要1. 将讲义第三章第三节中的凸包代码上机运行并检验结果。2. 完成讲义第三章的课后习题，上机运行并检验结果。3. 思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。4. 房间

18、最短路问题：给顶一个含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在x=0,x=10,y=0 和 y=10。起点和重点固定在(0,5) 和(10,5) 。房间里还有0 到18 个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间，输出最短路的长度。以下图是个例子：. . . . 16 / 24 四、实验结果与分析（源程序与相关说明）3. 思考：用跨立方法。线段相交满足且只需满足如下两个条件就可以了：1 两条线段相互跨立；2 一条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若p1p2跨立 p3p4 ，则矢量 ( p1 p

19、3 ) 和( p2 - p1 )位于矢量 ( p4 p3 ) 的两侧，即( p1 p3） ( p4- p3 ) * ( p2 p3 ) ( p4 p3 ) 0。当 ( p1 p3 ) ( p4 p3 ) = 0 时，说明 ( p1 p3 ) 和 ( p4 p3 ) 共线，但是因为已经通过快速排斥试验，所以 p1 一定在线段 p3p4 上；同理， ( p4 p3 ) (p2 p3 ) = 0 说明 p2 一定在 p3p4 上。所以判断 p1p2跨立 q1q2 的依据是： ( p1 p3 ) ( p4 p3 ) * ( p4 p3 ) ( p2 p3 ) = 0 。同理判断 q1q2 跨立 p1p

20、2的依据是： ( p3 - p1 ) ( p2 - p1 ) * ( p2 - p1 ) ( p4 - p1 ) = 0。代码中函数bool segment_intersect()用于判断 p1、p2 构成的线段和 p3、p4 构成的线段是否相交。可以看出共五种情况两线段是相交的，反之就输出“the two are not intersected!”4. 房间最短路问题：#include #include #include #include using namespace std; typedef pair point; double direction(point p,point p1,po

21、int 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 p1,point p2) double min_x=p1.firstp2.first?p1.first:p2.first; double min_y=p1.secondp2.

22、second?p1.second:p2.second; . . . . 17 / 24 if(p.first=min_x&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(startpo

23、int,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=pointi; k=i; point.erase(point.be

24、gin()+k); point.insert(point.begin(),p0); vectorconvex_hull; do convex_hull.push_back(point0); . . . . 18 / 24 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); while(1); for

25、(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; . . . . 19 / 24 . . . . 20 / 24 实验四动态规划算法的

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

27、 a 通过变换变为串b，可用的操作为， 删除串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 #include using 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 (s1i=s20) ai0=1; max=a00;