实验一 STL 的熟悉不使用 实验名称 实验一 STL 的熟悉不使用 姓名 汪子成 系院与业 信息工程系 班级 计算机 15-1班 学号 20XX216758 实验日期

　指导教师 徐本柱 成绩

　一、实验目的和要求 1．掌握 C++中 STL 的容器类的使用; 2．掌握 C++中 STL 的算法类的使用. 二、实验预习内容 1．预习 ICPC 讲义，大致了解 STL 的相关内容。

　2．了解 STL 中一些类 vectorlist 类的使用方法 3．了解泛型算法的使用 三、实验项目摘要 (1)练习vector和list的使用。定义一个空的vector，元素类型为int，生成10个随机数插入到vector中，用迭代器遍历 vector 并输出其中的元素值。在 vector 头部插入一个随机数，用迭代器遍历vector 并输出其中的元素值。用泛型算法 find 查找某个随机数，如果找到便输出，否则将此数插入 vector 尾部。用泛型算法 sort 将 vector 排序，用迭代器遍历 vector 并输出其中的元素值。删除 vector 尾部的元素，用迭代器遍历 vector 并输出其中的元素值。将 vector 清空。定义一个 list，并重复上述实验，并注意观察结果。

　(2)练习泛型算法的使用。定义一个 vector，元素类型为 int，插入 10 个随机数，使用 sort 按升序排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用 find 查找元素。用 min和 maR 找出容器中的最小元素和最大元素，并输出。

　四、实验结果与分析（源程序及相关说明）

　1.练习vector和list的使用：

　#include<iostream> #include<vector> #include<iomanip> #include<ctime> #include<algorithm> usingnamespacestd; vector<int>mRV; boolsortup(intv1,intv2) { returnv1<v2; } intmain(intargc,charRargv[]) { srand(time(NULL));for(inti=0;i<10;i++) mRV.push_back(rand()); sort(mRV.begin(),mRV.end(),sortup);vector<int>::iteratorit1; for(it1=mRV.begin();it1!=mRV.end();it1++) { cout<<(Rit1)<<setw(6); } cout<<endl; intmin=mRV[0];

　for(it1=mRV.begin()+1;it1!=mRV.end();it1++)

　if((Rit1)<min)min=(Rit1); cout<<"最小元素为"<<min<<endl; intmaR=mRV[0]; for(it1=mRV.begin();it1!=mRV.end();it1++) if((Rit1)>maR)maR=(Rit1); cout<<"最大元素为"<<maR<<endl; cout<<endl; intvalue=rand(); it1=find(mRV.begin(),mRV.end(),value); if((Rit1)==value) cout<<"找到了这个随机数"<<endl; else cout<<"没有找到这个随机数"<<endl; mRV.insert(mRV.end(),value); cout<<"插入尾部的随机数为"<<value<<endl; for(it1=mRV.begin();it1!=mRV.end();it1++) { cout<<(Rit1)<<setw(6); } cout<<"\n"<<endl; intt=rand(); mRV.insert(mRV.begin(),t); cout<<"插入头部的随机数为"<<t<<endl; for(it1=mRV.begin();it1!=mRV.end();it1++) {

　cout<<(Rit1)<<setw(6); } cout<<endl; mRV.pop_back(); for(it1=mRV.begin();it1!=mRV.end();it1++) { cout<<(Rit1)<<setw(6); } cout<<endl; mRV.clear(); if(mRV.emptR()) { cout<<"It"semptR!"<<endl; } sRstem("PAUSE");//pressanRkeRtocontinue... return0; }

　2 练习泛型算法的使用：

　#include<list> #include<iostream> usingnamespacestd; tRpedeflist<int>lin; intvalue[]={1,6,7,8,9}; voidprint(lin&l) { inti; lin::iteratorlit; for(lit=l.begin();lit!=l.end();lit++) cout<<(Rlit)<<""; cout<<endl; } boolsortsp(intv1,intv2) { returnv1>v2; } intmain(){ linlin2; lin2.push_front(3); lin2.push_front(4); lin2.insert(lin2.begin(),value,value+5); cout<<"lin2 内的元素为："; print(lin2);

　lin2.sort(); cout<<"排序后的 lin2:"; print(lin2); lin2.push_front(10); cout<<"在 list 头部插入 10 乊后的结果："; print(lin2); lin2.remove(6); cout<<"删除一个数后的 lin1:"; print(lin2); sRstem("PAUSE"); return0; }

　 实验二搜索算法的实现 实验名称 实验二搜索算法的实现 姓名 汪子成 系院与业 信息工程系 班级 计算机 15-1班 学号 20XX216758 实验日期

　指导教师 徐本柱 成绩

　一、实验目的和要求 1．掌握宽度优先搜索算法; 2．掌握深度优先搜索算法.

　二、实验预习内容 1．预习 ICPC 讲义中的搜索的内容 2.了解什么是深度优先搜索和广度优先搜索。

　三、实验项目摘要 1.将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。

　2.八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后乊间丌相互攻击，求出所有的布棋方法。上机运行并检验结果。

　3.骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍丏仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。

　4.倒水问题：给定 2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出 L 升 的水，如果可以，输出步骤，如果丌可以，请输出 NoSolution

　四、实验结果与分析（源程序及相关说明）

　2，八皇后问题：

　#include<stdio.h> #defineN8 #defineNUM8 inth[N][N],n[N],H[N][N]; intcount=0; voidtrRit(int,int); voidoutputArraR(int[][N]); main() {

　intR=0,R=0,i,j;

　for(i=0;i<=N-1;i++)

　{

　 for(j=0;j<=N-1;j++)

　h[i][j]=0;

　}

　trRit(R,R);

　printf("......\n");

　printf("共有%d 种布局.\n",92);

　return(0); } voidtrRit(intR,intR) {

　inti,j;

　 if(count<=NUM)

　{

　if((H[0][0]==1&&H[1][4]==1&&H[2][7]==1&&H[3][5]==1&&H[4][2]==1&&H[5][6]==1&&H[6][1]==1&&H[7][3]==1)&&count!=1)

　{}

　else

　{

　 if(R>=0&&R<=N-1&&R>=0&&R<=N-1&&h[R][R]==0)

　 {

　for(j=0;j<=7;j++)

　{

　 if(h[R][j]==0)

　h[R][j]=R+1;

　 if(h[j][R]==0)

　 h[j][R]=R+1;

　 if(R+j>=0&&R+j<=N-1&&R+j>=0&&R+j<=N-1&&h[R+j][R+j]==0)

　h[R+j][R+j]=R+1;

　 if(R+j>=0&&R+j<=N-1&&R-j>=0&&R-j<=N-1&&h[R+j][R-j]==0)

　h[R+j][R-j]=R+1;

　 if(R-j>=0&&R-j<=N-1&&R+j>=0&&R+j<=N-1&&h[R-j][R+j]==0)

　 h[R-j][R+j]=R+1;

　 if(R-j>=0&&R-j<=N-1&&R-j>=0&&R-j<=N-1&&h[R-j][R-j]==0)

　h[R-j][R-j]=R+1;

　 }

　h[R][R]=-R-1;

　if(R==7)

　{

　 for(i=0;i<=N-1;i++)

　 {

　for(j=0;j<=N-1;j++)

　{

　 if(h[i][j]<0)

　H[i][j]=1;

　 else

　H[i][j]=0;

　}

　 }

　count=count+1;

　 if(count<=NUM)

　 {

　printf("------布局%d------\n",count);

　 outputArraR(H);

　 } for(i=0;i<=N-1;i++)

　 {

　for(j=0;j<=N-1;j++)

　{

　 if(h[i][j]==R||h[i][j]==-R||h[i][j]==-R-1)

　 h[i][j]=0;

　}

　 }

　 trRit(R-1,n[R-1]+1);

　}

　 else

　{

　 n[R]=R;

　trRit(R+1,0);

　}

　 }

　 else

　 {

　if(R>7)

　{

　 for(i=0;i<=N-1;i++)

　 {

　for(j=0;j<=N-1;j++)

　{

　 if(h[i][j]==R||h[i][j]==-R)

　h[i][j]=0;

　}

　 }

　 if(R-1>=0)

　 trRit(R-1,n[R-1]+1);

　else

　trRit(0,0);

　}

　else

　 trRit(R,R+1);

　 }

　}

　} } voidoutputArraR(inth[][N]) {

　inti,j;

　for(i=0;i<=N-1;i++)

　{

　 for(j=0;j<=N-1;j++)

　printf("%d",h[i][j]);

　 printf("\n");

　} }

　 3.骑士游历问题：

　#include<stdio.h> intboard[8][8]={0}; inttravel(intR,intR) { intktmove1[8]={-2,-1,1,2,2,1,-1,-2}; intktmove2[8]={1,2,2,1,-1,-2,-2,-1}; intneRti[8]={0}; intneRtj[8]={0}; inteRists[8]={0}; inti,j,k,m,l; inttmpi,tmpj; intcount,min,tmp;

　i=R; j=R; board[i][j]=1; for(m=2;m<=64;m++){ for(l=0;l<8;l++) eRists[l]=0; l=0; for(k=0;k<8;k++){ tmpi=i+ktmove1[k]; tmpj=j+ktmove2[k]; if(tmpi<0||tmpj<0||tmpi>7||tmpj>7) continue; if(board[tmpi][tmpj]==0){ neRti[l]=tmpi; neRtj[l]=tmpj; l++; } } count=l; if(count==0){ return0; } elseif(count==1){ min=0; }

　else{ for(l=0;l<count;l++){ for(k=0;k<8;k++){ tmpi=neRti[l]+ktmove1[k]; tmpj=neRtj[l]+ktmove2[k]; if(tmpi<0||tmpj<0|| tmpi>7||tmpj>7){ continue; } if(board[tmpi][tmpj]==0) eRists[l]++; } } tmp=eRists[0]; min=0; for(l=1;l<count;l++){ if(eRists[l]<tmp){ tmp=eRists[l]; min=l; } } } i=neRti[min]; j=neRtj[min]; board[i][j]=m;

　} return1; } intmain() { intstartR,startR; inti,j; printf("输入起始点：");scanf("%d%d",&startR,&startR); if(travel(startR,startR)){ printf("游历完成！\n"); } else{ printf("游历失败！\n"); } for(i=0;i<8;i++){ for(j=0;j<8;j++){ printf("%2d",board[i][j]); } putchar("\n"); } return0; }

　实验三计算几何算法的实现 实验名称 实验二计算几何算法的实现 姓名 汪子成 系院与业 信息工程系 班级 计算机 15-1班 学号 20XX216758 实验日期

　指导教师 徐本柱 成绩

　一、实验目的和要求 1.理解线段的性质、叉积和有向面积。

　2.掌握寻找凸包的算法。

　3.综合运用计算几何和搜索中的知识求解有关问题。

　二、实验预习内容 1．预习 ICPC 讲义，大致了解计算几何算法的相关内容。

　2．了解实现该算法的中一些使用方法。

　3．会使用该算法解决实际问题。

　三、实验项目摘要 1.将讲义第三章第三节中的凸包代码上机运行并检验结果。

　2.完成讲义第三章的课后习题，上机运行并检验结果。

　3.思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能不另一条线段上的端点重合，思考这样的情况怎么办。

　4.房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在 R=0,R=10,R=0 和 R=10。起点和重点固定在(0,5)和(10,5)。房间里还有 0 到18 个墙，每个墙有两个门。输入给定的墙的个数，每个墙的 R 位置和两个门的 R 坐标区间，输出最短路的长度。下图是个例子：

　四、实验结果与分析（源程序及相关说明）

　3.思考：

　用跨立方法。线段相交满足丏只需满足如下两个条件就可以了：1 两条线段相互跨立；2一条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若p1p2 跨立 p3p4，则矢量(p1–p3)和(p2-p1)位于矢量(p4–p3)的两侧，即(p1–p3）×(p4-p3)R(p2–p3)×(p4–p3)<0。上式可改写成(p1–p3)×(p4-p3)R(p4–p3)×(p2–p3)>0。当(p1–p3)×(p4–p3)=0 时，说明(p1–p3)和(p4–p3)共线，但是因为已经通过快速排斥试验，所以 p1 一定在线段 p3p4 上；同理，(p4–p3)×(p2–p3)=0 说明 p2 一定在 p3p4 上。所以判断 p1p2 跨立 Q1Q2 的依据是：(p1–p3)×(p4–p3)R(p4–p3)×(p2–p3)>=0。同理判断 Q1Q2 跨立 P1P2 的依据是：(p3-p1)×(p2-p1)R(p2-p1)×(p4-p1)>=0。代码中凼数 boolsegment_intersect()用于判断 p1、p2 构成的线段和 p3、p4 构成的线段是否相交。可以看出共五种情况两线段是相交的，反乊就输出“ThetwoareNotintersected!” 4.房间最短路问题：

　#include<iostream> #include<utilitR>

　#include<vector> #include<algorithm> usingnamespacestd; tRpedefpair<double,double>POINT; 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.firstRv2.second-v1.secondRv2.second;} boolon_segment(POINTp,POINTp1,POINTp2){ doublemin_R=p1.first<p2.first?p1.first:p2.first; doublemaR_R=p1.first>p2.first?p1.first:p2.first; doublemin_R=p1.second<p2.second?p1.second:p2.second; doublemaR_R=p1.second>p2.second?p1.second:p2.second; if(p.first>=min_R&&p.first<maR_R&&p.second>=min_R&&p.second<=maR_R) returntrue; else returnfalse; } POINTstartPoint; boolsortBRPolorAngle(constPOINT&p1,constPOINT&p2) { doubled=direction(startPoint,p1,p2);

　if(d<0)returntrue; if(d>0)returnfalse; if(d==0&&on_segment(startPoint,p1,p2))returntrue; if(d==0&&on_segment(p2,startPoint,p1))returntrue; returnfalse; } voidfind_conveR_hull(vector<POINT>&point) { POINTp0=point[0]; intk=0; for(inti=0;i<point.size();i++) { if(point[i].second<p0.second|| point[i].second==p0.second&&point[i].first<p0.first){ p0=point[i]; k=i;} } point.erase(point.begin()+k); point.insert(point.begin(),p0); vector<POINT>conveR_hull; do{ conveR_hull.push_back(point[0]); startPoint=point[0]; point.erase(point.begin()); sort(point.begin(),point.end(),sortBRPolorAngle);

　if(point[0]==conveR_hull[0])break; point.push_back(conveR_hull[conveR_hull.size()-1]); }while(1); for(intj=0;j<conveR_hull.size();j++){ cout<<conveR_hull[j].first<<""<<conveR_hull[j].second<<endl; }} intmain(){ vector<POINT>pv; doubleR,R; inti; cout<<"请输入 10 个点<R,R>："<<endl; for(i=1;i<=10;i++){ cout<<"No."<<i<<":"; cin>>R>>R; pv.push_back(make_pair(R,R)); } cout<<endl;find_conveR_hull(pv); sRstem("Pause"); return0; }

　 实验四动态规划算法的实现 实验名称 实验四动态规划算法的实现 姓名 汪子成 系院与业 信息工程系 班级 计算机 15-1班 学号 20XX216758 实验日期

　指导教师 徐本柱 成绩

　一、实验目的和要求 1．理解动态规划的基本思想、动态规划算法的基本步骤 2．掌握动态规划算法实际步骤

　二、实验预习内容 1．动态规划算法的基本要素 2．最长公共子序列 3．矩阵连乘问题

　三、实验项目摘要 (1)求两个字符串的最长公共子序列。

　-151-R 的一个子序列是相应于 R 下标序列{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 思考：当矩阵很大时，比如 100R100的矩阵，你的程序还能够很快的得出结果吗，如果丌能，请思考如何用动态规划的思想解决。

　四、实验结果与分析（源程序及相关说明）

　源代码如下：

　1.求两个字符串的最长公共子序列。

　#include<iostream> #include<string> usingnamespacestd; voidlongest(strings1,strings2) { intmaR,tep,i,j; inta[100][100]; for(i=0;i<s1.size();i++) for(j=0;j<s2.size();j++) a[i][j]=0; for(j=0;j<s2.size();j++) if(s1[0]==s2[j]) a[0][j]=1; for(i=0;i<s1.size();i++) if(s1[i]==s2[0]) a[i][0]=1; maR=a[0][0]; tep=0; for(i=1;i<s1.size();i++) for(j=1;j<s2.size();j++)

　if(s1[i]==s2[j]) { a[i][j]=a[i-1][j-1]+1; if(maR<a[i][j]) { maR=a[i][j]; tep=i; } } if(maR==0) cout<<"没有公共子序列!"; else { cout<<"两个字符串的最长公共子序列为:"; for(i=tep-maR+1;i<=tep;i++) cout<<s1[i]; cout<<endl; } } intmain() { strings1,s2; cout<<"请输入两个字符串:"<<endl; cout<<"一个字符串为:"; cin>>s1; cout<<"另一个字符串为:"; cin>>s2; longest(s1,s2);cout<<endl; return0; }

　 (2)给定两个字符串a和b，现将串a通过变换变为串b #include<iostream> #include<string> usingnamespacestd; intmin(intR1,intR2,intR3) { if(R2<R1) R1=R2; elseif(R3<R1) R1=R3; returnR1; } voidchange(strings1,strings2) { constcharRstr=s1.c_str(); constcharRtep=s2.c_str(); intb[100][100]; b[0][0]=0; for(inti=1;i<=s1.length();i++) b[0][i]=i; for(intj=1;j<=s2.length();j++) b[j][0]=j; for(i=1;i<=s2.length();i++) for(intm=1;m<=s1.length();m++)

　{ if(tep[i-1]==str[m-1]) b[i][m]=b[i-1][m-1]; else b[i][m]=1+min(b[i-1][m-1],b[i-1][m],b[i][m-1]); } cout<<"将a变为b需要"<<b[s2.length()][s1.length()]<<"步！"<<endl; } intmain() { strings1,s2; cout<<"输入字符串a:"; cin>>s1; cout<<"输入字符串b:"; cin>>s2; change(s1,s2); cout<<endl; return0; }

推荐访问:重磅 课程 实验