课程实验报告

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 并输出其中的元素值。在

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

3、 和max 找出容器中的最小元素和最大元素，并输出。四、实验结果与分析（源程序及相关说明）1. 练习vector 和list 的使用：#include <iostream>#include <vector>#include<iomanip>#include<ctime> #include <algorithm>using namespace std;vector<int> myV;bool sortup(int v1,int v2)return v1<v2; int main(int argc, char *argv

4、) srand(time(NULL); for (int i=0;i<10;i+) myV.push_back(rand(); sort(myV.begin(),myV.end(),sortup); vector<int>:iterator it1; for (it1=myV.begin();it1!=myV.end();it1+) cout<<(*it1)<<setw(6); cout<<endl; int min=myV0; for (it1=myV.begin()+1;it1!=myV.end();it1+) if(*it1)<

5、min)min=(*it1); cout<<"最小元素为" <<min<<endl; int max=myV0; for (it1=myV.begin();it1!=myV.end();it1+) if(*it1)>max)max=(*it1); cout<<"最大元素为" <<max<<endl; cout<<endl; int value=rand(); it1=find(myV.begin(),myV.end(),value); if(*it1)=value)

6、 cout<<"找到了这个随机数"<<endl ; else cout<<"没有找到这个随机数"<<endl; myV.insert(myV.end(),value); cout<<"插入尾部的随机数为"<<value<<endl; for (it1=myV.begin();it1!=myV.end();it1+) cout<<(*it1)<<setw(6); cout<<"n"<<e

7、ndl; int t=rand(); myV.insert(myV.begin(),t); cout<<"插入头部的随机数为" <<t<<endl; for (it1=myV.begin();it1!=myV.end();it1+) cout<<(*it1)<<setw(6); cout<<endl; myV.pop_back (); for (it1=myV.begin();it1!=myV.end();it1+) cout<<(*it1)<<setw(6); cout<

8、<endl; myV.clear(); if(myV.empty() cout << "It's empty!" << endl; system("PAUSE"); /press any key to continue. return 0;2 练习泛型算法的使用：#include<list>#include<iostream>using namespace std;typedef list<int> lin;int value=1,6,7,8,9; void print(lin &

9、amp;l)int i;lin:iterator lit;for(lit=l.begin();lit!=l.end();lit+)cout<<(*lit)<<" "cout<<endl;bool sortsp(int v1,int v2) return v1>v2; int main()lin lin2; lin2.push_front(3); lin2.push_front(4); lin2.insert(lin2.begin(),value,value+5);cout<<"lin2内的元素为："p

10、rint(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班学 号2

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

12、装出L 升的水，如果可以，输出步骤，如果不可以，请输出No Solution四、实验结果与分析（源程序及相关说明）2，八皇后问题：#include <stdio.h>#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("

13、共有%d种布局.n",92);return(0);void tryit(int x,int y)int i,j;if(count<=NUM)if(H00=1&&H14=1&&H27=1&&H35=1&&H42=1&&H56=1&&H61=1&&H73=1)&&count!=1)elseif(x>=0&&x<=N-1&&y>=0&&y<=N-1&&hxy=0)for(

14、j=0;j<=7;j+)if(hxj=0)hxj=x+1;if(hjy=0) hjy=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&&y-j<=N-1&&hx+jy-j=0) hx+jy-j=x+1;if(x-j>=0&&x-j<=N-1&&

15、amp;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&&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; count=count+1;if(count<=NUM)printf(&quo

16、t;-布局%d-n",count); outputArray(H); for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)if(hij=x|hij=-x|hij=-x-1)hij=0;tryit(x-1,nx-1+1); elsenx=y; tryit(x+1,0);elseif(y>7)for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)if(hij=x|hij=-x) hij=0;if(x-1>=0) tryit(x-1,nx-1+1);else tryit(0,0);elsetryit(x,y+1);v

17、oid 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");3. 骑士游历问题：#include <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

18、; int nextj8 = 0; int exists8 = 0; int i, j, k, m, l; int tmpi, tmpj; int count, min, tmp; i = x;j = y; 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 < 0 | tmpi > 7 |

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

20、pj > 7) continue; 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", &

21、;startx, &starty); if(travel(startx, starty) printf("游历完成！n"); else printf("游历失败！n"); for(i = 0; i < 8; i+) for(j = 0; j < 8; j+) printf("%2d ", boardij); putchar('n'); return 0; 实验三 计算几何算法的实现实验名称实验二 计算几何算法的实现姓 名汪子成系院专业信息工程系班 级计算机15-1班学 号2015216758实验日期

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

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

24、- p3 ) * ( p2 p3 ) × ( p4 p3 ) < 0。上式可改写成( p1 p3 ) × ( p4- p3 ) * ( p4 p3 ) × ( p2 p3) > 0。当( p1 p3 ) × ( p4p3 ) = 0 时，说明( p1 p3 ) 和 ( p4 p3 )共线，但是因为已经通过快速排斥试验，所以 p1 一定在线段 p3p4上；同理，( p4 p3 ) ×(p2 p3 ) = 0 说明 p2 一定在 p3p4上。所以判断p1p2跨立Q1Q2的依据是：( p1 p3 ) × ( p4 p3 ) *

25、( 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<iostream> #include<utility> #incl

26、ude<vector> #include<algorithm> using namespace std; typedef pair<double,double> 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.sec

27、ond-v1.second*v2.second; bool on_segment(POINT p,POINT p1,POINT p2) double min_x=p1.first<p2.first?p1.first:p2.first; double max_x=p1.first>p2.first?p1.first:p2.first; double min_y=p1.second<p2.second?p1.second:p2.second; double max_y=p1.second>p2.second?p1.second:p2.second; if(p.first&g

28、t;=min_x&&p.first<max_x&&p.second>= 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(d<0)return true; if(d >0)return false; if(d=0&a

29、mp;&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) POINT p0=point0; int k=0; for(int i=0;i<point.size();i+) if(pointi.second<p0.second| pointi.second=p0.second&&p

30、ointi.first<p0.first) p0=pointi; k=i; point.erase(point.begin()+k); point.insert(point.begin(),p0); vector<POINT>convex_hull; do convex_hull.push_back(point0); startPoint=point0; point.erase(point.begin(); sort(point.begin(),point.end(),sortByPolorAngle); if(point0=convex_hull0)break; point

31、.push_back(convex_hullconvex_hull.size()-1); while(1); for(int j=0;j<convex_hull.size();j+) cout<<convex_hullj.first<<' '<<convex_hullj.second<<endl; int main() vector<POINT> pv; double x,y; int i; cout<<"请输入10个点<x,y>："<<endl; for(

32、i=1;i<=10;i+) cout<<"No."<<i<<':' cin>>x>>y;pv.push_back(make_pair(x,y); cout<<endl; find_convex_hull(pv); system("Pause"); return 0; 实验四 动态规划算法的实现实验名称实验四 动态规划算法的实现姓 名汪子成系院专业信息工程系班 级计算机15-1班学 号2015216758实验日期指导教师徐本柱成 绩一、实验目的和要求1理解动态规划

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

34、输入一个矩阵，计算所有的子矩阵中和的最大值。 例如，输入 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 输出为：15 思考：当矩阵很大时，比如100*100的矩阵，你的程序还能够很快的得出结果吗，如果不能，请思考如何用动态规划的思想解决。 四、实验结果与分析（源程序及相关说明）源代码如下：1.求两个字符串的最长公共子序列。#include<iostream> #include<string> using namespace 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=0; 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=a00; tep=0; for(i=1;i<s1.size();i+) for(j=1;j<s2.size();j+) if(s1i=s2j) aij=ai-1j-1+1; if(max&l