课程实验报告

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

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

3、gt;#include <vector>#include <cstdlib>#include <algorithm>using namespace std;vector <int> vint;int main() int i; for (i=0;i<10;i+) int r = rand()%99+0; vint.push_back(r); vector <int>:iterator pit1; for (pit1=vint.begin();pit1!=vint.end();pit1+) cout << *pit1

4、<<" " cout << endl; int temp; temp = rand()%99+0; vector <int>:iterator pit2; pit2 = find (vint.begin(),vint.end(),temp); if (pit2!=vint.end() cout <<"The number has been found !"<< endl; cout <<"The number is: "<< temp <<

5、 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 m

6、in number is : "<< *min_element(vint.begin(),vint.end() << endl; cout <<"数组升序排列的结果为: "<< endl; vector <int>:iterator pit3; sort (vint.begin(),vint.end(); for (pit3=vint.begin();pit3!=vint.end();pit3+) cout << *pit3 <<" " cout <<

7、; endl; cout <<"数组降序排列的结果为: "<< endl; vector <int>:iterator pit4; sort (vint.rbegin(),vint.rend(); for (pit4=vint.begin();pit4!=vint.end();pit4+) cout << *pit4 <<" " cout << endl; vint.pop_back(); cout <<"数组的大小为: "<< vint.

8、size() << endl; vint.erase (vint.begin(),vint.end(); cout <<"数组的大小为: "<< vint.size() << endl; return 0;实验二 搜索算法的实现实验名称实验二 搜索算法的实现姓 名周旋系院专业信息工程系班 级计算机14-4班学 号2014217155实验日期指导教师徐本柱成 绩一、实验目的和要求1掌握宽度优先搜索算法;2掌握深度优先搜索算法.二、实验预习内容1将书上的走迷宫代码上机运行并检验结果，体会搜索的思想2预习n皇后问题3预习骑士游历问题

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

10、 std;int 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,(rd+p)>>1); else sum+; int main() int n; cout<<"请输入皇后的个数:" cin >> n;

11、upperlimit = (upperlimit<<n)-1; compare(0,0,0); cout << "问题的解如下:" << sum << endl; return 0;实验三 计算几何算法的实现实验名称实验二 计算几何算法的实现姓 名周旋系院专业信息工程系班 级计算机14-4班学 号2014217155实验日期指导教师徐本柱成 绩一、实验目的和要求1. 理解线段的性质、叉积和有向面积。2. 掌握寻找凸包的算法。3. 综合运用计算几何和搜索中的知识求解有关问题。二、实验预习内容1预习ICPC讲义，大致了解计算几何算

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

13、，输出最短路的长度。下图是个例子：四、实验结果与分析（源程序及相关说明）源代码如下：#include<iostream>#include<utility>#include<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.se

14、cond-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.first<p2.first?p1.first:p2.first; double max_x=p1.first>p2.first?p1.first:p2.first; double min_y=p1.second

15、<p2.second?p1.second:p2.second; double max_y=p1.second>p2.second?p1.second:p2.second; if(p.first>=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 &a

16、mp;p2) double d=direction(startPoint,p1,p2); if(d<0) return true; if(d>0) 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) POINT p0=point0; int k=0

17、; for(int i=0;i<point.size();i+) if(pointi.second<p0.second| pointi.second=p0.second&&pointi.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

18、(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;j<convex_hull.size();j+) cout<<convex_hullj.first<<' '<<convex_hullj.second<<endl; int main() vec

19、tor<POINT> pv; double x,y; int i; cout<<"请输入10个点<x,y>："<<endl; for(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

20、0;实验四 动态规划算法的实现实验名称实验四 动态规划算法的实现姓 名周旋系院专业信息工程系班 级计算机14-4班学 号2014217155实验日期指导教师徐本柱成 绩一、实验目的和要求1理解动态规划的基本思想、动态规划算法的基本步骤 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输入一个矩阵，计算所有的子矩阵中和的最大值。 四、实验结果与分析（源程序及相关说明）源代码如下：#include<iostream>#include<string>using namespace