程序设计艺术与方法

程序设计艺术与方法实验一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找出容器中的小元素个大元素，并输出。源代码：#includeiostream#includevector#includeiomanip#includectime#includealgorithmusingnamespacestd;vectorintmyV;boolsortup(intv1,intv2){returnv1v2;}intmain(intargc,char*argv[]){srand(time(NULL));for(inti=0;i10;i++)myV.push_back(rand());sort(myV.begin(),myV.end(),sortup);vectorint::iteratorit1;for(it1=myV.begin();it1!=myV.end();it1++){cout(*it1)setw(6);}coutendl;intmin=myV[0];for(it1=myV.begin()+1;it1!=myV.end();it1++)if((*it1)min)min=(*it1);cout最小元素为minendl;intmax=myV[0];for(it1=myV.begin();it1!=myV.end();it1++)if((*it1)max)max=(*it1);cout最大元素为maxendl;coutendl;intvalue=rand();it1=find(myV.begin(),myV.end(),value);if((*it1)==value)cout找到了这个随机数endl;elsecout没有找到这个随机数endl;myV.insert(myV.end(),value);cout插入尾部的随机数为valueendl;for(it1=myV.begin();it1!=myV.end();it1++){cout(*it1)setw(6);}cout\nendl;intt=rand();myV.insert(myV.begin(),t);cout插入头部的随机数为tendl;for(it1=myV.begin();it1!=myV.end();it1++){cout(*it1)setw(6);}coutendl;myV.pop_back();for(it1=myV.begin();it1!=myV.end();it1++){cout(*it1)setw(6);}coutendl;myV.clear();if(myV.empty()){coutIt'sempty!endl;}system(PAUSE);return0;}运行截图：2练习泛型算法的使用：源代码：#includelist#includeiostream//#incluedalgorithmusingnamespacestd;typedeflistintlin;intvalue[]={1,2,3,4,5};voidprint(lin&l){inti;lin::iteratorlit;for(lit=l.begin();lit!=l.end();lit++)cout(*lit);coutendl;}boolsortsp(intv1,intv2){returnv1v2;}intmain(){linlin2;lin2.push_front(3);lin2.push_front(4);lin2.insert(lin2.begin(),value,value+5);coutlin2内的元素为：;print(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);return0;}运行截图：实验二搜索算法的实现1.实验目的(1)掌握宽度优先搜索算法。(2)掌握深度优先搜索算法。2.试验设备硬件环境：PC计算机软件环境：操作系统：Windows2000/WindowsXP/Linux语言环境：Devcpp/gnuc++3.试验内容(1)将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。(2)八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。思考：将此题推广到N皇后的情况，检验在N比较大的情况下，比方说N=16的时候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。(3)骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。(4)倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升的水，如果可以，输出步骤，如果不可以，请输出NoSolution。（2）八皇后问题源代码：#includeiostreamusingnamespacestd;#includemath.hintsum=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;}运行截图：（4）倒水问题源代码：4.倒水问题：#includestdio.hintmain(){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(cacc){while(1){if(y==0){y=cb;printf(fillB\n);}if(yca-x)//如果b中的水大于a中的剩余容积，就把a灌满//{y-=ca-x;x=ca;printf(pourBA\n);}else//如果b中的水小于a中的剩余容积，那么把b中的水全加入a//{x+=y;y=0;printf(pourBA\n);}if(y==cc)//如果b中的水已经和cc相等，那就结束//{break;}if(ca==x)//如果a中的水满了，就把a倒空//{x=0;printf(emptyA\n);}}}else{while(1){if(x==0){x=ca;printf(fillA\n);}if(xcb-y)//如果a中的水大于b中的剩余容积，就把b灌满//{x-=cb-y;y=cb;printf(pourAB\n);}else//如果a中的水小于b中的剩余容积，那么把a中的水全加入b//{y+=x;x=0;printf(pourAB\n);}if(y==cc)//如果b中的水已经和cc相等，那就结束//{break;}if(y==cb)//如果b中的水满了，就把b倒空//{y=0;printf(emptyB\n);}}}}printf(success\n);}return0;}运行截图:实验三计算几何算法的实现1.实验目的(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）房间短路问题源代码：#includeiostream#includeutility#includevector#includealgorithmusingnamespacestd;typedefpairdouble,doublePOINT;//线段doubledirection(POINTp,POINTp1,POINTp2){POINTv1,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;returnv1.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(start