程序设计艺术与方法

1、程序设计艺术与方法实验一STL得熟悉与使用1 .实验目得(1)掌握C+4STL得容器类得使用。(2)掌握C+中STL得算法类得使用。2 .试验设备硬件环境:PC计算机软件环境:操作系统:Windows2000/WindowsXP/Linux语言环境:Devcpp/gnuc+3 .试验内容(1)练习vector与list得使用。定义一个空得vector,元素类型为int,生成10个随机数插入到vector中,用迭代器遍历vector并输出其中得元素值。在vector头部插入一个随机数,用迭代器遍历vector并输出其中得元素值。用泛型算法find查找某个随机数,如果找到便输出,否则将此数插入ve

2、ctor尾部。用泛型算法sort将vector排序,用迭代器遍历vector并输出其中得元素值。删除vector尾部得元素,用迭代器遍历vector并输出其中得元素值。将vector清空。定义一个list,并重复上述实验，并注意观察结果。(2)练习泛型算法得使用。149定义一个vector,元素类型为int,插入10个随机数，使用sort按升序排序，输出每个元素得值,再按降叙排序,输出每个元素得值。练习用find查找元素。用min与max找出容器中得小元素个大元素,并输出。源代码:#include<iostream>#include<vector>#include<

3、;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+)myV、push_back(rand);sort(myV、begin,myV、end,sortup);vector<int>:iteratorit1;for(it1=myV、begin;i

4、t1!=myV、end;it1+)cout<<(*it1)<<setw(6);cout<<endl;intmin=myV0;for(it1=myV>begin+1;it1!=myV>end;it1+)coutvv”最小元素为"«min«endl;intmax=myV0;for(it1=myV>begin;it1!=myV>end;it1+)>max)max=(*it1);coutvv”最大元素为"«max«endl;cout«endl;intvalue=ran

5、d;it1=find(myV>begin,myV>end,value);if(*it1)=value)coutvv”找到了这个随机数"«endl;elsecoutvv”没有找到这个随机数"«endl;myV>insert(myV>end,value);coutvv”插入尾部得随机数为"«value«endl;for(it1=myV>begin;it1!=myV>end;it1+)(cout«(*it1)«setw(6);)cout«"n"&

6、#171;endl;intt=rand;myV>insert(myV>begin,t);coutvv”插入头部得随机数为"«t«endl;for(it1=myV>begin;it1!=myV>end;it1+)(cout«(*it1)«setw(6);)cout«endl;myV>pop_back;for(it1=myV>begin;it1!=myV>end;it1+)(cout«(*it1)«setw(6);)cout«endl;myV>clear;if(

7、myV>empty)(cout«"It'sempty!"«endl;)system("PAUSE");return0;)运行截图：X:USERSDELLDESKTOPVCC+WC6.06REENMYPROJECTSDODebuLG09225692401B46912615141121963!?239792752B"£45最小区系为1函*最大兀素为3184G瞬臃嬲一L0f225692431046012615141121563?23979275203184B28055幡人头部的随机数为una1L1132lf

8、r09225692431046g1261514113196392397927520918452805S111321AR922fi9243i£M4H12A1S14tl219E392”内2K2031A4SIt1ooftptyt请按任意幽续.2练习泛型算法得使用源代码：#include<list>#include<iostream>/#inclued<algorithm>usingnamespacestd;typedeflist<int>lin;intvalue=1,2,3,4,5;voidprint(lin&l)inti;lin:i

9、teratorlit;for(lit=l、begin;lit!=l、end;lit+)cout<<(*lit)<<""cout<<endl;boolsortsp(intv1,intv2)returnv1>v2;intmainlinlin2;lin2、push_front(3);lin2、push_front(4);lin2、insert(lin2、begin,value,value+5);cout<<"lin2内得元素为：”；print(lin2);lin2、sort;cout<<"排序后

10、得lin2:"print(lin2);lin2、push_front(10);cout<<"在list头部插入10之后得结果：”;print(lin2);lin2、remove(6);cout<<"删除一个数后得linl:"print(lin2);system("PAUSE");return0;运行截图：x琲序后的Mn2t133344E江工也共、部插入好之后的结果：1012334d&实验二搜索算法得实现1、实验目得（1）掌握宽度优先搜索算法。（2）掌握深度优先搜索算法。2、试验设备硬件环境：PC计算机软

11、件环境：操作系统：Windows2000/WindowsXP/Linux语言环境：Devcpp/gnuc+3、试验内容（1）将书上得走迷宫代码上机运行并检验结果，并注意体会搜索得思想。（2）八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有得布棋方法。上机运行并检验结果。思考:将此题推广到N皇后得情况，检验在N比较大得情况下，比方说N=16得时候,您得程序能否快速得求出结果，如果不能，思考有什么方法能够优化算法。（3）骑士游历问题：在国际棋盘上使一个骑士遍历所有得格子一遍且仅一遍，对于任意给定得顶点，输出一条符合上述要求得路径。（4）倒水问题：给定2个没有刻度

12、容器，对于任意给定得容积，求出如何只用两个瓶装出L开得水，如果可以，输出步骤,如果不可以,请输出NoSolution。(2)八皇后问题源代码:#include<iostream>usingnamespacestd;#include<math、h>intsum=0;intupperlimit=1;voidpare(introw,intld,intrd)if(row!=upperlimit)intpos=upperlimit&(row|ld|rd);while(pos!=0)intp=pos&pos;pos=p;pare(row+p,(ld+p)<&l

13、t;1,(rd+p)>>1);elsesum+;intmainintn;cout<<”请输入皇后得个数：”；cin>>n;upperlimit=(upperlimit<<n)1;pare(0,0,0);cout<<"问题得解如下:"<<sum<<endl;return0;运行截图:(4)倒水问题源代码:4、倒水问题:#include"stdio、h"intmainintca,cb,cc,x,y;while(scanf("%d%d%d",&ca,

14、&cb,&cc)!=EOF)if(cb=cc)printf("fillBn");elseif(ca=cc)printf("fillAn");printf("pourABn");elsex=y=0;if(ca<cc)while(1)if(y=0)y=cb;printf("fillBn");if(y>cax)/如果b中得水大于a中得剩余容积,就把a灌满/y=cax;x=ca;printf("pourBAn");else/如b中得水小于a中得剩余容积,那么把b中得水全加入a

15、/x+=y;y=0;printf("pourBAn");if(y=cc)/如b中得水已经与cc相等,那就结束/break;if(ca=x)如果a中得水满了，就把a倒空x=0;printf("emptyAn");elsewhile(1)if(x=0)x=ca;printf("fillAn");if(x>cby)/果a中得水大于b中得剩余容积,就把b灌满/x=cby;y=cb;printf("pourABn");else/果a中得水小于b中得剩余容积,那么把a中得水全加入b/y+=x;x=0;printf(&qu

16、ot;pourABn");if(y=cc)/果b中得水已经与cc相等,那就结束/break;if(y=cb)/果b中得水满了,就把b倒空/y=0;printf("emptyBn");printf("successn");return0;运行截图:口nC:USERSDELLDESKTCP实验三计算几何算法得实现1、实验目得（1）理解线段得性质、叉积与有向面积。（2）掌握寻找凸包得算法。（3）综合运用计算几何与搜索中彳#知识求解有关问题。2、试验设备硬件环境:PC计算机软件环操作系统:Windows2000/WindowsXP/Linux语言环境：

17、Devcpp/gnuc+&试验内容（1）将讲义第三章第三节中得凸包代码上机运行并检验结果。（2）完成讲义第三章得课后习题，上机运行并检验结果。（3）思考：判线段相交时，如果有个线段得端点在另一条线段上，注意可能与另一条线段上得端点重合，思考这样得情况怎么办。（4）房间短路问题：给顶一个内含阻碍墙得房间，求解出一条从起点到终点得短路径。房间得边界固定在x=0,x=10,y=0与y=10。起点与重点固定在（0,5加（10,5）。房间里还有0至I18个墙，每个墙有两个门。输入给定得墙得个数，每个墙得x位置与两个门得y坐标区间，输出最短路得长度。（4）房间短路问题源代码：#include<

18、;iostream>#include<utility>#include<vector>#include<algorithm>usingnamespacestd;typedefpair<double,double>POINT;/线段doubledirection(POINTp,POINTp1,POINTp2)POINTv1,v2;v1、first=p2、firstp1、first;v1、second=p2、secondp1、first;v2、first=p1、firstp、first;v2、second=p1、secondp、second;r

19、eturnv1、first*v2、secondv1、second*v2、second;boolon_segment(POINTp,POINTp1,POINTp2)doublemin_x=p1、first<p2、first?p1、first:p2、first;doublemax_x=p1、first>p2、first?p1、first:p2、first;doublemin_y=p1、second<p2、second?p1、second:p2、second;doublemax_y=p1、second>p2、second?p1、second:p2、second;if(p、fi

20、rst>=min_x&&p、first<max_x&&p、second>=min_y&&p、second<=max_y)returntrue;elsereturnfalse;POINTstartPoint;boolsortByPolorAngle(constPOINT&p1,constPOINT&p2)doubled=direction(startPoint,p1,p2);if(d<0)returntrue;if(d>0)returnfalse;if(d=0&&on_segmen

21、t(startPoint,p1,p2)returntrue;if(d=0&&on_segment(p2,startPoint,p1)returntrue;returnfalse;voidfind_convex_hull(vector<POINT>&point)POINTp0=point0;intk=0;for(inti=0;i<point、size;i+)if(pointi、second<p0、second|pointi、second=p0、second&&pointi、first<p0、first)p0=pointi;k=

22、i;point、erase(point、begin+k);point、insert(point、begin,p0);vector<POINT>convex_hull;doconvex_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_hul、lsize1);while(1);for(int

23、j=0;j<convex_hull、size;j+)cout<<convex_hullj、first<<''<<convex_hullj、second<<endl;intmainvector<POINT>pv;doublex,y;inti;cout<<”请输入10个点<x,y>:"<<endl;for(i=1;i<=10;i+)cout<<"No、"<<i<<':'cin>>x&

24、gt;>y;pv、push_back(make_pair(x,y);cout<<endl;find_convex_hull(pv);system("Pause");return0;运行截图:"C:USERSDELLDESKT实验四动态规划算法得实现1、实验目得（1）理解动态规划得基本思想、动态规划算法得基本步骤。（2）掌握动态规划算法实际步骤。2、试验设备硬件环境：PC计算机软件环境：操作系统：Windows2000/WindowsXP/Linux语言环境：Devcpp/gnuc+3、试验内容（1）求两个字符串得最长公共子序列。X得一个子序列就是

25、相应于X下标序列1,2,，m得一个子序列，求解两个序列得所有子序列中长度大得例如输入:pear,peach输出:pea。（2）给定两个字符用a与b,现将用a通过变换变为用b,可用得操作为，删除用a中得一个字符;在用a得某个位置插入一个元素；将用a中得某个字母换为另一个字母。对于任意彳4申a与申b,输出少多少次能够将用变为用bo思考:输出变换得步骤。（3）输入一个矩阵，计算所有得子矩阵中与得大值。例如，输入0270926241411802输出为:15思考:当矩阵很大时，比如100*100得矩阵，您得程序还能够很快得得出结果吗，如果不能,请思考如何用动态规划得思想解决（1）求两个字符串得最长公共子序列源代码：#include<cstring>#include<iostream>#defineN100usingnamespacestd;/str1存储字符串x,str2存储字符串ycharstr1N,str2N;/lcs存储最长公共子序列charlcsN;/cij存储stU1、i与str21、j得最长公共子序列得长度intcNN;/flagij=0为str1i=str2j/flagij=1为ci1j