课程实验报告

1、程序设计艺术与方法课程实验报告 学号： 姓名：周旋 2015.10.10实验一 STL的熟悉与使用实验名称实验一 STL 的熟悉与使用姓 名周旋系院专业信息工程系班 级计算机14-4班学 号实验日期指导教师徐本柱成 绩一、实验目的和要求1掌握C+中STL的容器类的使用;2掌握C+中STL的算法类的使用.二、实验预习内容1预习ICPC讲义，大致了解STL的相关内容。2了解STL中一些类 vector list类的使用方法3了解泛型算法的使用三、实验项目摘要1练习vector和list的使用2练习泛型算法的使用四、实验结果与分析（源程序及相关说明）以下程序实现了下述几个功能：1 定义一个vecto

2、r，生成十个随机数插入到vector中。2 多次使用迭代器iterator遍历vector，输出完成不同功能的vector元素。3 使用泛型算法find 查找vector中的随机数，如果找到输出该随机数，如果没找到将该随机数插入到vector中。4 使用泛型算法 sort 对vector中的元素进行升序与降序排列，使用迭代器iterator输出。5 使用min, max算法求出vector中的最小值与最大值。6 删除vector 中的尾部元素以及全部元素，输出vector的大小。（注：源代码见下页）#include #include #include #include using namesp

3、ace std;vector vint;int main() int i; for (i=0;i10;i+) int r = rand()%99+0; vint.push_back(r); vector :iterator pit1; for (pit1=vint.begin();pit1!=vint.end();pit1+) cout *pit1 ; cout endl; int temp; temp = rand()%99+0; vector :iterator pit2; pit2 = find (vint.begin(),vint.end(),temp); if (pit2!=vint

4、.end() cout The number has been found ! endl; cout The number is: temp endl; else cout Sorry! The number has not been found! Please try again ! endl; vint.push_back(temp); random_shuffle(vint.begin(),vint.end(); cout The max number is : *max_element(vint.begin(),vint.end() endl; cout The min number

5、is : *min_element(vint.begin(),vint.end() endl; cout 数组升序排列的结果为: endl; vector :iterator pit3; sort (vint.begin(),vint.end(); for (pit3=vint.begin();pit3!=vint.end();pit3+) cout *pit3 ; cout endl; cout 数组降序排列的结果为: endl; vector :iterator pit4; sort (vint.rbegin(),vint.rend(); for (pit4=vint.begin();pi

6、t4!=vint.end();pit4+) cout *pit4 ; cout endl; vint.pop_back(); cout 数组的大小为: vint.size() endl; vint.erase (vint.begin(),vint.end(); cout 数组的大小为: vint.size() endl; return 0;实验二 搜索算法的实现实验名称实验二 搜索算法的实现姓 名周旋系院专业信息工程系班 级计算机14-4班学 号实验日期指导教师徐本柱成 绩一、实验目的和要求1掌握宽度优先搜索算法;2掌握深度优先搜索算法.二、实验预习内容1将书上的走迷宫代码上机运行并检验结果，

7、体会搜索的思想2预习n皇后问题3预习骑士游历问题三、实验项目摘要1n皇后问题： 在一个国际象棋棋盘上放n个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果2骑士游历问题： 在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径3倒水问题： 给定2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出 L 升的水，如果可以，输出步骤，如果不可以，请输出No Solution 。四、实验结果与分析（源程序及相关说明）以下仅列出八皇后问题的源代码：#include #include using namespace std;i

8、nt sum = 0;int upperlimit = 1;void compare(int row,int ld,int rd) if( row!= upperlimit ) int pos=upperlimit&(row|ld|rd); while(pos!=0) int p=pos&-pos; pos-=p; compare(row+p,(ld+p)1); else sum+; int main() int n; cout n; upperlimit = (upperlimitn)-1; compare(0,0,0); cout 问题的解如下: sum endl; return 0;实验

9、三 计算几何算法的实现实验名称实验二 计算几何算法的实现姓 名周旋系院专业信息工程系班 级计算机14-4班学 号实验日期指导教师徐本柱成 绩一、实验目的和要求1. 理解线段的性质、叉积和有向面积。2. 掌握寻找凸包的算法。3. 综合运用计算几何和搜索中的知识求解有关问题。二、实验预习内容1预习ICPC讲义，大致了解计算几何算法的相关内容。2了解实现该算法的中一些使用方法。3会使用该算法解决实际问题。三、实验项目摘要1. 将讲义第三章第三节中的凸包代码上机运行并检验结果。2. 完成讲义第三章的课后习题，上机运行并检验结果。3. 思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一

10、条线段上的端点重合，思考这样的情况怎么办。4. 房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房 间的边界固定在x=0,x=10,y=0 和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0 到18 个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间，输出最短路的长度。下图是个例子：四、实验结果与分析（源程序及相关说明）源代码如下：#include#include#include#includeusing namespace std;typedef pair POINT;double direction(POINT p

11、,POINT p1,POINT p2) POINT v1,v2; v1.first = p2.first-p1.first; v1.second = p2.second-p1.second; 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;

12、 double min_y=p1.secondp2.second?p1.second:p2.second; 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,p2) r

13、eturn 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(po

14、int.begin(),p0); vectorconvex_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.push_back(convex_hullconvex_hull.size()-1); while(1); for(int j=0;jconvex_hull.size();j+) coutconv

15、ex_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;实验四 动态规划算法的实现实验名称实验四 动态规划算法的实现姓 名周旋系院专业信息工程系班 级计算机14-4班学 号实验日期指导教师徐本柱成 绩一、实验目的和要求1理解动态规

16、划的基本思想、动态规划算法的基本步骤 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输入一个矩阵

17、，计算所有的子矩阵中和的最大值。 四、实验结果与分析（源程序及相关说明）源代码如下：#include#includeusing namespace std;int min(int x1,int x2, int x3) if(x2x1) x1=x2; else if(x3x1) x1=x3; return x1;void change(string s1,string s2) int N,i; const char * str=s1.c_str(); const char * tep=s2.c_str(); int bNN; b00=0; for(int i=1;i=s1.length();i+) b0i=i; for(int j=1;j