课程实验报告

课程实验报告1程序设计艺术与方法课程实验报告学号：2014217155姓名：周旋2015.10.10课程实验报告2实验一STL的熟悉与使用实验名称实验一STL的熟悉与使用姓名周旋系院专业信息工程系班级计算机14-4班学号2014217155实验日期指导教师徐本柱成绩一、实验目的和要求1．掌握C++中STL的容器类的使用;2．掌握C++中STL的算法类的使用.二、实验预习内容1．预习ICPC讲义，大致了解STL的相关内容。2．了解STL中一些类vectorlist类的使用方法3．了解泛型算法的使用三、实验项目摘要1．练习vector和list的使用2．练习泛型算法的使用四、实验结果与分析（源程序及相关说明）以下程序实现了下述几个功能：1．定义一个vector，生成十个随机数插入到vector中。2．多次使用迭代器iterator遍历vector，输出完成不同功能的vector元素。3．使用泛型算法find查找vector中的随机数，如果找到输出该随机数，如果没找到将该随机数插入到vector中。4．使用泛型算法sort对vector中的元素进行升序与降序排列，使用迭代器iterator输出。5．使用min,max算法求出vector中的最小值与最大值。6．删除vector中的尾部元素以及全部元素，输出vector的大小。（注：源代码见下页）课程实验报告3#includeiostream#includevector#includecstdlib#includealgorithmusingnamespacestd;vectorintvint;intmain(){inti;for(i=0;i10;i++){intr=rand()%99+0;vint.push_back(r);}vectorint::iteratorpit1;for(pit1=vint.begin();pit1!=vint.end();pit1++){cout*pit1;}coutendl;inttemp;temp=rand()%99+0;vectorint::iteratorpit2;pit2=find(vint.begin(),vint.end(),temp);if(pit2!=vint.end()){coutThenumberhasbeenfound!endl;coutThenumberis:tempendl;}else{coutSorry!Thenumberhasnotbeenfound!Pleasetryagain!endl;vint.push_back(temp);}random_shuffle(vint.begin(),vint.end());coutThemaxnumberis:*max_element(vint.begin(),vint.end())endl;coutTheminnumberis:*min_element(vint.begin(),vint.end())endl;cout数组升序排列的结果为:endl;vectorint::iteratorpit3;sort(vint.begin(),vint.end());for(pit3=vint.begin();pit3!=vint.end();pit3++){课程实验报告4cout*pit3;}coutendl;cout数组降序排列的结果为:endl;vectorint::iteratorpit4;sort(vint.rbegin(),vint.rend());for(pit4=vint.begin();pit4!=vint.end();pit4++){cout*pit4;}coutendl;vint.pop_back();cout数组的大小为:vint.size()endl;vint.erase(vint.begin(),vint.end());cout数组的大小为:vint.size()endl;return0;}实验二搜索算法的实现课程实验报告5实验名称实验二搜索算法的实现姓名周旋系院专业信息工程系班级计算机14-4班学号2014217155实验日期指导教师徐本柱成绩一、实验目的和要求1．掌握宽度优先搜索算法;2．掌握深度优先搜索算法.二、实验预习内容1．将书上的走迷宫代码上机运行并检验结果，体会搜索的思想2．预习n皇后问题3．预习骑士游历问题三、实验项目摘要1．n皇后问题：在一个国际象棋棋盘上放n个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果2．骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径3．倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升的水，如果可以，输出步骤，如果不可以，请输出NoSolution。课程实验报告6四、实验结果与分析（源程序及相关说明）以下仅列出八皇后问题的源代码：#includeiostream#includemath.husingnamespacestd;intsum=0;intupperlimit=1;voidcompare(introw,intld,intrd){if(row!=upperlimit){intpos=upperlimit&~(row|ld|rd);while(pos!=0){intp=pos&-pos;pos-=p;compare(row+p,(ld+p)1,(rd+p)1);}}else{sum++;}}intmain(){intn;cout请输入皇后的个数:;cinn;upperlimit=(upperlimitn)-1;compare(0,0,0);cout问题的解如下:sumendl;return0;}课程实验报告7实验三计算几何算法的实现实验名称实验二计算几何算法的实现姓名周旋系院专业信息工程系班级计算机14-4班学号2014217155实验日期指导教师徐本柱成绩一、实验目的和要求1.理解线段的性质、叉积和有向面积。2.掌握寻找凸包的算法。3.综合运用计算几何和搜索中的知识求解有关问题。二、实验预习内容1．预习ICPC讲义，大致了解计算几何算法的相关内容。2．了解实现该算法的中一些使用方法。3．会使用该算法解决实际问题。三、实验项目摘要1.将讲义第三章第三节中的凸包代码上机运行并检验结果。2.完成讲义第三章的课后习题，上机运行并检验结果。3.思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。4.房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在x=0,x=10,y=0和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0到18个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x位置和两个门的y坐标区间，输出最短路的长度。下图是个例子：课程实验报告8四、实验结果与分析（源程序及相关说明）源代码如下：#includeiostream#includeutility#includevector#includealgorithmusingnamespacestd;typedefpairdouble,doublePOINT;doubledirection(POINTp,POINTp1,POINTp2){POINTv1,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);}boolon_segment(POINTp,POINTp1,POINTp2){doublemin_x=p1.firstp2.first?p1.first:p2.first;doublemax_x=p1.firstp2.first?p1.first:p2.first;doublemin_y=p1.secondp2.second?p1.second:p2.second;doublemax_y=p1.secondp2.second?p1.second:p2.second;if(p.first=min_x&&p.firstmax_x&&p.second=min_y&&p.second=max_y)returntrue;elsereturnfalse;}POINTstartPoint;boolsortByPolorAngle(constPOINT&p1,constPOINT&p2){doubled=direction(startPoint,p1,p2);if(d0)returntrue;if(d0)returnfalse;if(d==0&&on_segment(startPoint,p1,p2))returntrue;if(d==0&&on_segment(p2,startPoint,p1))returntrue;returnfalse;课程实验报告9}voidfind_convex_hull(vectorPOINT&point){POINTp0=point[0];intk=0;for(inti=0;ipoint.size();i++){if(point[i].secondp0.second||point[i].second==p0.second&&point[i].firstp0.first){p0=point[i];k=i;}}point.erase(point.begin()+k);point.insert(point.begin(),p0);vectorPOINTconvex_hull;do{convex_hull.push_back(point[0]);startPoint=point[0];point.erase(point.begin());sort(point.begin(),point.end(),sortByPolorAngle);if(point[0]==convex_hull[0])break;point.push_back(convex_hull[convex_hull.size()-1]);}while(1);for(intj=0;jconvex_hull.size();j++){coutconvex_hull[j].first''convex_hull[j].secondendl;}}intmain(){vectorPOINTpv;doublex,y;inti;cout请输入10个点x,y：endl;for(i=1;i=10;i++){coutNo.i':';cinxy;pv.push_back(make_pair(x,y));}coutendl;课程实验报告10find_convex_hull(pv);system(Pause);return0;}课程实验报告11实验四动态规划算法的实现实验名称实验四动态规划算法的实现姓名周旋系院专业信息工程系班级计算机14-4班学号2014217155实验日期指导教师徐本柱成绩一、实验目的和要求1．理解动态规划的基本思想、动态规划算法的基本步骤2．掌握动态规划算法实际步骤二、实验预习内容1．动态规划算法的基本要素2．最长公共子序列3．矩阵连乘问题三、实验项目摘要1.求两个字符串的最长公共子序列。-151-X的一个子序列是相应于X下标序列{1,2,…,m}的一个子序列，求解两个序列的所有