程序设计艺术与方法

程序设计艺术与方法程序设计艺术与方法程序设计艺术与方法xxx公司程序设计艺术与方法文件编号：文件日期：修订次数：第1.0次更改批准审核制定方案设计，管理制度程序设计艺术与方法实验一STL的熟悉与使用1．实验目的（1）掌握C++中STL的容器类的使用。（2）掌握C++中STL的算法类的使用。2．试验设备硬件环境：PC计算机软件环境：操作系统：Windows2000/WindowsXP/Linux语言环境：Devcpp/gnuc++3．试验内容(1)练习vector和list的使用。定义一个空的vector，元素类型为int，生成10个随机数插入到vector中，用迭代器遍历vector并输出其中的元素值。在vector头部插入一个随机数，用迭代器遍历vector并输出其中的元素值。用泛型算法find查找某个随机数，如果找到便输出，否则将此数插入vector尾部。用泛型算法sort将vector排序，用迭代器遍历vector并输出其中的元素值。删除vector尾部的元素，用迭代器遍历vector并输出其中的元素值。将vector清空。定义一个list，并重复上述实验，并注意观察结果。(2)练习泛型算法的使用。-149定义一个vector，元素类型为int，插入10个随机数，使用sort按升序排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用find查找元素。用min和max找出容器中的小元素个大元素，并输出。源代码：#include<iostream>#include<vector>#include<iomanip>#include<ctime>#include<algorithm>usingnamespacestd;vector<int>myV;boolsortup(intv1,intv2){returnv1<v2;}intmain(intargc,char*argv[]){srand(time(NULL));for(inti=0;i<10;i++)(rand());sort(),(),sortup);vector<int>::iteratorit1;for(it1=();it1!=();it1++){cout<<(*it1)<<setw(6);}cout<<endl;intmin=myV[0]; for(it1=()+1;it1!=();it1++)if((*it1)<min)min=(*it1);cout<<"最小元素为"<<min<<endl;intmax=myV[0];for(it1=();it1!=();it1++)if((*it1)>max)max=(*it1);cout<<"最大元素为"<<max<<endl;cout<<endl;intvalue=rand();it1=find(),(),value);if((*it1)==value)cout<<"找到了这个随机数"<<endl;elsecout<<"没有找到这个随机数"<<endl;(),value);cout<<"插入尾部的随机数为"<<value<<endl;for(it1=();it1!=();it1++){cout<<(*it1)<<setw(6);}cout<<"\n"<<endl;intt=rand();(),t);cout<<"插入头部的随机数为"<<t<<endl;for(it1=();it1!=();it1++){cout<<(*it1)<<setw(6);}cout<<endl;();for(it1=();it1!=();it1++){cout<<(*it1)<<setw(6);}cout<<endl;();if()){cout<<"It'sempty!"<<endl;}system("PAUSE");return0;}运行截图：2练习泛型算法的使用：源代码：#include<list>#include<iostream>实验目的(1)掌握宽度优先搜索算法。(2)掌握深度优先搜索算法。2.试验设备硬件环境：PC计算机软件环境：操作系统：Windows2000/WindowsXP/Linux语言环境：Devcpp/gnuc++3.试验内容(1)将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。(2)八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。思考：将此题推广到N皇后的情况，检验在N比较大的情况下，比方说N=16的时候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。(3)骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。(4)倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升的水，如果可以，输出步骤，如果不可以，请输出NoSolution。（2）八皇后问题源代码：#include<iostream>usingnamespacestd;#include<>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<<"请输入皇后的个数:"; cin>>n; upperlimit=(upperlimit<<n)-1; compare(0,0,0); cout<<"问题的解如下:"<<sum<<endl; return0;}运行截图：

（4）倒水问题源代码：4.倒水问题：#include""intmain(){intca,cb,cc,x,y;while(scanf("%d%d%d",&ca,&cb,&cc)!=EOF){if(cb==cc){printf("fillB\n");}elseif(ca==cc){printf("fillA\n");printf("pourAB\n");}else{x=y=0;if(ca<cc){while(1){if(y==0){y=cb;printf("fillB\n");}if(y>ca-x)实验目的(1)理解线段的性质、叉积和有向面积。(2)掌握寻找凸包的算法。(3)综合运用计算几何和搜索中的知识求解有关问题。2.试验设备硬件环境：PC计算机软件环操作系统：Windows2000/WindowsXP/Linux语言环境：Devcpp/gnuc++3.试验内容(1)将讲义第三章第三节中的凸包代码上机运行并检验结果。(2)完成讲义第三章的课后习题，上机运行并检验结果。(3)思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。(4)房间短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的短路径。房间的边界固定在x=0,x=10,y=0和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0到18个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x位置和两个门的y坐标区间，输出最短路的长度。（4）房间短路问题源代码：#include<iostream>#include<utility>#include<vector>#include<algorithm>usingnamespacestd;typedefpair<double,double>POINT;econd<||point[i].second==&&point[i].first<{p0=point[i];k=i;}}()+k);(),p0);vector<POINT>convex_hull;do{(point[0]);startPoint=point[0];());sort(),(),sortByPolorAngle);if(point[0]==convex_hull[0])break;(convex_hull[()-1]);}while(1);for(intj=0;j<();j++){cout<<convex_hull[j].first<<''<<convex_hull[j].second<<endl;}}intmain(){vector<POINT>pv;doublex,y;inti;cout<<"请输入10个点<x,y>："<<endl;for(i=1;i<=10;i++){cout<<"No."<<i<<':';cin>>x>>y;(make_pair(x,y));}cout<<endl;find_convex_hull(pv);system("Pause");return0;}运行截图：实验四动态规划算法的实现1.实验目的(1)理解动态规划的基本思想、动态规划算法的基本步骤。(2)掌握动态规划算法实际步骤。2.试验设备硬件环境：PC计算机软件环境：操作系统：Windows2000/WindowsXP/Linux语言环境：Devcpp/gnuc++3.试验内容(1)求两个字符串的最长公共子序列。X的一个子序列是相应于X下标序列{1,2,…,m}的一个子序列，求解两个序列的所有子序列中长度大的，例如输入：pear,peach输出：pea。(2)给定两个字符串a和b，现将串a通过变换变为串b，可用的操作为，删除串a中的一个字符；在串a的某个位置插入一个元素；将串a中的某个字母换为另一个字母。对于任意的串a和串b，输出少多少次能够将串变为串b。思考：输出变换的步骤。(3)输入一个矩阵，计算所有的子矩阵中和的大值。例如，输入0-2-7092-62-41-41-180-2输出为：15思考：当矩阵很大时，比如100*100的矩阵，你的程序还能够很快的得出结果吗，如果不能，请思考如何用动态规划的思想解决求两个字符串的最长公共子序列源代码：#include<cstring>#include<iostream>#defineN100usingnamespacestd;.i]与str2[1...j]的最长公共子序列的长度intc[N][N];//flag[i][j]==0为str1[i]==str2[j]//flag[i][j]==1为c[i-1][j]>=s[i][j-1]//flag[i][j]==-1为c[i-1][j]<s[i][j-1]intflag[N][N];//求长度intLCSLength(char*x,char*y){inti,j;//分别取得x,y的长度intm=strlen(x);intn=strlen(y);for(i=1;i<=m;i++)c[i][0]=0;for(i=0;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;flag[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];flag[i][j]=1;}else{c[i][j]=c[i][j-1];flag[i][j]=-1;}