课程实验报告汇总17686.pdf

《课程实验报告汇总17686.pdf》由会员分享，可在线阅读，更多相关《课程实验报告汇总17686.pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 个随机数

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

3、rt 按升序排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用 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;i10;i+)

4、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/24 coutendl;int value=rand();i

5、t1=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);cout插入头部的随机数为 tendl;for(it1=myV.begin();it1!=myV.e

6、nd();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 练习泛型算法的使用：#include#include using namespace std;typedef list lin;int value=1,6

7、,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(lin2);lin2.sort();cout排序后的 lin2:;print(lin2);lin2.push_front(10);cout在 list 头部插入

8、10 之后的结果：;print(lin2);lin2.remove(6);cout删除一个数后的 lin1:;print(lin2);system(PAUSE);return 0;实验二 搜索算法的实现 .6/24 实验名称 实验二 搜索算法的实现 姓 名 汪子成 系院专业 信息工程系 班 级 计算机15-1班 学 号 2015216758 实验日期 指导教师 徐本柱 成 绩 一、实验目的和要求 1掌握宽度优先搜索算法;2掌握深度优先搜索算法.二、实验预习容 1预习 ICPC 讲义中的搜索的容 2.了解什么是深度优先搜索和广度优先搜索。三、实验项目摘要 1.将书上的走迷宫代码上机运行并检验结果

9、，并注意体会搜索的思想。2.八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。3.骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。4.倒水问题：给定 2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出 L 升 的水，如果可以，输出步骤，如果不可以，请输出 No Solution .7/24 四、实验结果与分析（源程序与相关说明）2，八皇后问题：#include#define N 8#define NUM 8 int hNN,nN,HNN;int coun

10、t=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&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

11、=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(count=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

12、=N-1;i+)for(j=0;j=N-1;j+)printf(%d,hij);printf(n);.11/24 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 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=6

13、4;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=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

14、|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 startx,starty;int i,j;printf(输入起始点：);scanf(%d%d,&startx,&starty);if(travel(startx,starty)printf(游历完成！n);else printf(

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

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

17、：.16/24 四、实验结果与分析（源程序与相关说明）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 p3)共线，但是因为已经通过快速排斥试验，所以 p1 一定在线段 p3p4 上；同理，(p4 p3)(p2 p3)=0 说明 p2 一定在 p3p4 上。所

18、以判断 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#include#include#include using namespace std;typedef pair

19、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 p1,POINT p2)double min_x=p1.firstp2.first?p1.first:p

20、2.first;double min_y=p1.secondp2.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(startPoint,p1,

21、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.begin()+k);point.insert(point.begi

22、n(),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(int j=0;jconvex_hull.size();j+)coutconvex_hullj.fi

23、rst 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 实验四 动态规划算法的实现 实验名称 实验四 动态规划算法的实现 姓 名 汪子成 系院专业 信息工程系 班 级 计算机15-1班 学 号 2015216758 实验日期 指导教师 徐本柱

24、成 绩 一、实验目的和要求 1理解动态规划的基本思想、动态规划算法的基本步骤 2掌握动态规划算法实际步骤 二、实验预习容 1动态规划算法的基本要素 2最长公共子序列 3矩阵连乘问题 .21/24 三、实验项目摘要(1)求两个字符串的最长公共子序列。-151-X 的一个子序列是相应于 X 下标序列1,2,m的一个子序列，求解两个序列的所有子序列中长度最大的，例如输入：pear,peach 输出：pea。(2)给定两个字符串 a 和 b，现将串 a 通过变换变为串 b，可用的操作为，删除串a 中的一 个字符；在串 a 的某个位置插入一个元素；将串 a 中的某个字母换为另一个字母。对于任意的串 a

25、和串 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 a100

26、100;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;tep=0;for(i=1;is1.size();i+)for(j=1;js2.size();j+)if(s1i=s2j)aij=ai-1j-1+1;if(maxaij).22/24 max=aij;tep=i;if(max=0)cout没有公共子序列!;else cout两个字符串的最长公共子序列为:;for(i=t

27、ep-max+1;i=tep;i+)couts1i;coutendl;int main()string s1,s2;cout请输入两个字符串:endl;couts1;couts2;longest(s1,s2);coutendl;return 0;(2)给定两个字符串a和b，现将串a通过变换变为串b#include#include using namespace std;int min(int x1,int x2,int x3).23/24 if(x2x1)x1=x2;else if(x3x1)x1=x3;return x1;void change(string s1,string s2)con

28、st char*str=s1.c_str();const char*tep=s2.c_str();int b100100;b00=0;for(int i=1;i=s1.length();i+)b0i=i;for(int j=1;j=s2.length();j+)bj0=j;for(i=1;i=s2.length();i+)for(int m=1;m=s1.length();m+)if(tepi-1=strm-1)bim=bi-1m-1;else bim=1+min(bi-1m-1,bi-1m,bim-1);cout将a变为b需要bs2.length()s1.length()步！endl;int main()string s1,s2;cout s1;cout s2;change(s1,s2);coutendl;return 0;.24/24