《程序设计艺术与方法》课程实验报告.doc

《程序设计艺术与方法》课程实验报告
一
实验名称
STL的熟悉与使用
姓 名

系院专业
信息工程系
班 级
物联网一班
学 号

实验日期

指导教师

成 绩

一、实验目的和要求
1．（1）掌握C++中STL的容器类使用。（2）掌握C++中STL的算法类的使用。

二、实验预习内容
Vector,list可当作列表使用的数据结构，它们都是动态增长的。
1.vector表示一段连续的内存区域每个元素被顺序储存在这段内存中。对vector的随即访问效率很高。但是在任意位置而不是在vector末尾插入元素则效率很低，因为它需要把待插入元素的右边的每个元素都拷贝一遍。类似的删除任一个而不是vector的最后一个元素效率低。
2list表示非连续的内存区域并通过一对指向首尾元素的指针双向进行遍历在list的任意位置插入和删除元素的效率都很高，指针必须被赋值但不需要用拷贝元素来实现移动，另一方面它对随机访问的支持并不好访问一个元素需要遍历中间的元素，另外每个元素还有俩不能给个指针的额外空间开销。
3泛型算法让编写一般化并可重复使用的算法，其效率与指针对某特定数据类型而设计的算法相同。泛型即是指具有在多种数据类型上皆可操作的含义，与模板有些相似。STL巨大而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。
三、实验项目摘要
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 和
max 找出容器中的最小元素个最大元素，并输出。
四、实验结果与分析（源程序及相关说明）
1. 练习vector 和list 的使用：
#include <iostream>
#include <vector>
#include<iomanip>
#include<ctime>
#include <algorithm>
using namespace std;
vector<int> myV;
bool sortup(int v1,int v2)
{
return v1<v2;
}
int main(int argc, char *argv[])
{
srand(time(NULL)); //随机产生十个数
for (int i=0;i<10;i++)
myV.push_back(rand());
sort(myV.begin(),myV.end(),sortup); //用sort排序升序
vector<int>::iterator it1;
for (it1=myV.begin();it1!=myV.end();it1++)
{
cout<<(*it1)<<setw(6); //打印数组
}
cout<<endl;
int min=myV[0];
for (it1=myV.begin()+1;it1!=myV.end();it1++)
if((*it1)<min)min=(*it1);
cout<<"最小元素为" <<min<<endl;
int max=myV[0];
for (it1=myV.begin();it1!=myV.end();it1++)
if((*it1)>max)max=(*it1);
cout<<"最大元素为" <<max<<endl;
cout<<endl;
int value=rand();
it1=find(myV.begin(),myV.end(),value);
if((*it1)==value)
cout<<"找到了这个随机数"<<endl ;
else
cout<<"没有找到这个随机数"<<endl;
myV.insert(myV.end(),value); //数组中没有随机数,插入尾部
cout<<"插入尾部的随机数为"<<value<<endl;
for (it1=myV.begin();it1!=myV.end();it1++)
{
cout<<(*it1)<<setw(6);
}
cout<<"\n"<<endl;
//随机在vector头部插入一个随机数
int t=rand();//定义t;将一个随机数赋给t，插入到数组·头部
myV.insert(myV.begin(),t);
cout<<"插入头部的随机数为" <<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(myV.empty())
{
cout << "It's empty!" << endl;
}
system("PAUSE"); //press any key to continue...
return 0;
}

运行截图：

2 练习泛型算法的使用：
#include<list>
#include<iostream>
//#inclued<algorithm>
using namespace std;
typedef list<int> lin;
int value[]={2,4,6,1,8};
void print(lin &l)
{
int i;
lin::iterator lit;//定义一个迭代器
for(lit=l.begin();lit!=l.end();lit++)
cout<<(*lit)<<" ";//打印list中的元素
cout<<endl;
}
bool sortsp(int v1,int v2)//升序排序算法
{
return v1>v2;
}

int main(){
lin lin2;
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);//在list头部插入10
cout<<"在list头部插入10之后的结果：";
print(lin2);
lin2.remove(6);
cout<<"删除一个数后的lin1:";
print(lin2);
system("PAUSE");//press any key to contineu...
return 0;
}
运行截图：

二
实验名称
搜索算法的实验
姓 名

系院专业
信息工程系
班 级
物联网一班
学 号

实验日期

指导教师

成 绩

一、实验目的和要求
1．掌握宽度优先搜索算法。
2．掌握深度优先搜索算法。
二、实验预习内容
1宽度优先搜索算法：又称广度优搜索。是最简单的图的算法的原形。其属于一种盲搜寻法，目的是系统地展开并检查图中的所有节点，以寻找结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。
2深度优先搜索算法：它的目的是要达到被搜索结构的叶结点。在一个HTML文件中，当一个超链被选择后，被连接的HTML文件将执行深度优先搜索，即在搜索其余的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。

三、实验项目摘要
1.将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。
2 .八皇后问题：
在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有
的布棋方法。上机运行并检验结果。
思考：将此题推广到N 皇后的情况，检验在N 比较大的情况下，比方说N=16 的时
候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。
3骑士游历问题：
在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，
输出一条符合上述要求的路径。
4 倒水问题：
给定2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L 升
的水，如果可以，输出步骤，如果不可以，请输出No Solution。
四、实验结果与分析（源程序及相关说明）
2，八皇后问题：
#include <stdio.h>
/*声明常量N存储行和列*/
#define N 8
#define NUM 8
/*声明全局变量，h[N][N]控制盘格，H[N][N]控制输出，n[N]存储每一步的
*纵坐标，count用于计数。
*/
int h[N][N],n[N],H[N][N];
int count=0;
/*声明函数void tryit(int,int)尝试符合条件的方法*/
void tryit(int,int);
/*声明函数void outputArray(int[][N])输出数组*/
void outputArray(int[][N]);
main()
{
int x=0,y=0,i,j;
/*初始化为零*/
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
h[i][j]=0;
}
tryit(x,y);
printf("//其他的布局略\n");
printf("共有%d种布局.\n",92);
return(0);
}

/*定义函数void tryit(int,int)尝试符合条件的方法*/
void tryit(int x,int y)
{
int i,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(x>=0&&x<=N-1&&y>=0&&y<=N-1&&h[x][y]==0)
{
/*对与皇后在同一行、列、斜线上的点作出处理*/
for(j=0;j<=7;j++)
{
if(h[x][j]==0)
h[x][j]=x+1;
if(h[j][y]==0)
h[j][y]=x+1;
if(x+j>=0&&x+j<=N-1&&y+j>=0&&y+j<=N-1&&h[x+j][y+j]==0)
h[x+j][y+j]=x+1;
if(x+j>=0&&x+j<=N-1&&y-j>=0&&y-j<=N-1&&h[x+j][y-j]==0)
h[x+j][y-j]=x+1;
if(x-j>=0&&x-j<=N-1&&y+j>=0&&y+j<=N-1&&h[x-j][y+j]==0)
h[x-j][y+j]=x+1;
if(x-j>=0&&x-j<=N-1&&y-j>=0&&y-j<=N-1&&h[x-j][y-j]==0)
h[x-j][y-j]=x+1;
}
/*对皇后处的点作出标志*/
h[x][y]=-x-1;
/*完成一种走法作出处理*/
if(x==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);
outputArray(H);
}
/*对下一种走法，清楚前一次的影响*/
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
{
if(h[i][j]==x||h[i][j]==-x||h[i][j]==-x-1)
h[i][j]=0;
}
}
/*递归，尝试另一种方法*/
tryit(x-1,n[x-1]+1);
}
/*未走完一次，继续下一行*/
else
{
n[x]=y;
tryit(x+1,0);
}
}
else
{
/*此路不通时，返回上一行，尝试下一种方法*/
if(y>7)
{
/*清楚前一次影响*/
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
{
if(h[i][j]==x||h[i][j]==-x)
h[i][j]=0;
}
}
/*分情况递归*/
if(x-1>=0)
tryit(x-1,n[x-1]+1);
else
tryit(0,0);
}
/*尝试下一格*/
else
tryit(x,y+1);
}
}
}
}

/*定义函数void outputArray(int[][N])输出数组*/
void outputArray(int h[][N])
{
int i,j;
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
printf("%d ",h[i][j]);
printf("\n");
}
}
运行截图：

4.倒水问题：
#include"stdio.h"
int main()
{
int ca,cb,cc,x,y;
while(scanf("%d%d%d",&ca,&cb,&cc)!=EOF)
{
if(cb==cc)
{ printf("fill B\n");
}
else if(ca==cc)
{
printf("fill A\n");
printf("pour A B\n");
}
else
{
x=y=0;
if(ca<cc)
{
while(1)
{ if(y==0)
{
y=cb;
printf("fill B\n");
}
if(y>ca-x) //如果b中的水大于a中的剩余容积，就把a灌满//
{
y-=ca-x;
x=ca;
printf("pour B A\n");
}
else //如果b中的水小于a中的剩余容积，那么把b中的水全加入a//
{
x+=y;
y=0;
printf("pour B A\n");
}
if(y==cc) //如果b中的水已经和cc相等，那就结束//
{
break;
}
if(ca==x) //如果a中的水满了，就把a倒空//
{
x=0;
printf("empty A\n");
}
}
}
else
{
while(1)
{
if(x==0)
{
x=ca;
printf("fill A\n");
}
if(x>cb-y) //如果a中的水大于b中的剩余容积，就把b灌满//
{
x-=cb-y;
y=cb;
printf("pour A B\n");
}
else //如果a中的水小于b中的剩余容积，那么把a中的水全加入b//
{
y+=x;
x=0;
printf("pour A B\n");
}
if(y==cc) //如果b中的水已经和cc相等，那就结束//
{
break;
}
if(y==cb) //如果b中的水满了，就把b倒空//
{
y=0;
printf("empty B\n");
}
}
}
}
printf("success\n");
}
return 0;
}
运行截图：

三
实验名称
计算几何算法的实现
姓 名

系院专业
信息工程系
班 级
物联网一班
学 号

实验日期

指导教师

成 绩

一、实验目的和要求
1．理解线段的性质、叉积和有向面积。
2．掌握寻找凸包的算法。
3．综合运用计算几何和搜索中的知识求解有关问题。
二、实验预习内容
凸包：是一组点集中的子集，这一子集形成的凸多边形可以将点集中所有的点都围住，并且这一凸边形的面积是最小的。
一种寻找凸包的算法：打包法
首先，我们找出点集中最下方的点，如果这样的点不止一个，就选用
最左边的点（如P0）。显然，这个点（P0）是凸包子集中的一个点。可以设想在P0 处拴了一根
皮筋的一端，另一端放在和P0 成水平位置的右侧。现在，将皮筋，沿逆时针方向转动，首先会
碰到P1，这样就找到了另一个凸包子集中的点。以P1 为中心，做和P0 一样的事，会发现，我
们将碰到P3，又一个凸包的点。我们可以一直这样做下去，直到再一次遇到P0，凸包就被找出
来了。具体而言，在第一次找到P0 点之后，以P0 为每个矢量的起点，其它的点为矢量的终点，
来比较任意两个矢量的转角，就可以对余下的点进行按极角排序
三、实验项目摘要
1 将讲义第三章第三节中的凸包代码上机运行并检验结果。
2完成讲义第三章的课后习题，上机运行并检验结果。
3思考：
判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的
端点重合，思考这样的情况。
4房间最短路问题：
给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界
固定在x=0,x=10,y=0 和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0 到18 个
墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间，
输出最短路的长度
四、实验结果与分析（源程序及相关说明）
3.思考：
用跨立方法，跨立的含义是：如果一条线段的一个端点在一条直线的一边，另一个端点在这条直线的另一端，我们就说这条线段跨立在这条直线上。线段相交满足且只需满足如下两个条件就可以了：1 两条线段相互跨立；2 一条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若p1p2跨立p3p4 ，则矢量 ( p1 –p3 ) 和( p2 - p1 )位于矢量( p4 – p3 )的两侧，即( p1 –p3） × ( p4- p3 ) * ( p2 – p3 ) × ( p4 –p3 ) < 0。上式可改写成( p1 – p3 ) × ( p4- p3 ) * ( 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 ) * ( p4 – p3 ) × ( p2–p3 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( p3 - p1 ) × ( p2 - p1 ) * ( p2 - p1 ) × ( p4 - p1 ) >= 0。代码中函数bool segment_intersect()用于判断p1、p2构成的线段和p3、p4构成的线段是否相交。可以看出共五种情况两线段是相交的，反之就输出“The two are Not intersected!”

4.房间最短路问题：
#include<iostream>
#include<utility>
#include<vector>
innclude<algorithm>
using namespace std;
typedef pair<double,double> POINT;//线段
double direction(POINT p,POINT p1,POINT p2){
POINT v1,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;
return v1.first*v2.second-v1.second*v2.second;}
bool on_segment(POINT p,POINT p1,POINT p2){
double min_x=p1.first<p2.first?p1.first:p2.first;
max_x=p1.first>p2.first?p1.first:p2.first;
double min_y=p1.second<p2.second?p1.second:p2.second;
double max_y=p1.second>p2.second?p1.second:p2.second;
if(p.first>=min_x&&p.first<max_x&&p.second>=
min_y&&p.second<=max_y)
return true;
else
return false;}
POINT startPoint;
bool sortByPolorAngle(const POINT &p1,const POINT &p2)
{
double d=direction(startPoint,p1,p2);
if(d<0)return true;
if(d >0)return false;
if(d==0&&on_segment(startPoint,p1,p2))return true;
if(d= =0&&on_segment(p2,startPoint,p1))return true;
return false;
}
void find_convex_hull(vector<POINT>&point)
{
POINT p0=point[0];
int k=0;
for(int i=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>convex_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(int j=0;j<convex_hull.size();j++){
cout<<convex_hull[j].first<<' '<<convex_hull[j].second<<endl;
}}
int main(){
vector<POINT> pv;
double x,y;
int i;
cout<<"请输入10个点<x,y>："<<endl;
for(i=1;i<=10;i++){
cout<<"No."<<i<<':';
cin>>x>>y;
pv.push_back(make_pair(x,y));
}
cout<<endl; find_convex_hull(pv);
system("Pause");
return 0;
}
运行截图：

其中专业理论知识内容包括：保安理论知识、消防业务知识、职业道德、法律常识、保安礼仪、救护知识。作技能训练内容包括：岗位操作指引、勤务技能、消防技能、军事技能。
二．培训的及要求培训目的
安全生产目标责任书
为了进一步落实安全生产责任制，做到“责、权、利”相结合，根据我公司2015年度安全生产目标的内容，现与财务部签订如下安全生产目标：
一、目标值：
1、全年人身死亡事故为零，重伤事故为零，轻伤人数为零。
2、现金安全保管，不发生盗窃事故。
3、每月足额提取安全生产费用，保障安全生产投入资金的到位。
4、安全培训合格率为100%。
二、本单位安全工作上必须做到以下内容：
1、对本单位的安全生产负直接领导责任，必须模范遵守公司的各项安全管理制度，不发布与公司安全管理制度相抵触的指令，严格履行本人的安全职责，确保安全责任制在本单位全面落实，并全力支持安全工作。
2、保证公司各项安全管理制度和管理办法在本单位内全面实施，并自觉接受公司安全部门的监督和管理。
3、在确保安全的前提下组织生产，始终把安全工作放在首位，当“安全与交货期、质量”发生矛盾时，坚持安全第一的原则。
4、参加生产碰头会时，首先汇报本单位的安全生产情况和安全问题落实情况；在安排本单位生产任务时，必须安排安全工作内容，并写入记录。
5、在公司及政府的安全检查中杜绝各类违章现象。
6、组织本部门积极参加安全检查，做到有检查、有整改，记录全。
7、以身作则，不违章指挥、不违章操作。对发现的各类违章现象负有查禁的责任，同时要予以查处。
8、虚心接受员工提出的问题，杜绝不接受或盲目指挥；
9、发生事故，应立即报告主管领导，按照“四不放过”的原则召开事故分析会，提出整改措施和对责任者的处理意见，并填写事故登记表，严禁隐瞒不报或降低对责任者的处罚标准。
10、必须按规定对单位员工进行培训和新员工上岗教育；
11、严格执行公司安全生产十六项禁令，保证本单位所有人员不违章作业。
三、 安全奖惩：
1、对于全年实现安全目标的按照公司生产现场管理规定和工作说明书进行考核奖励；对于未实现安全目标的按照公司规定进行处罚。
2、每月接受主管领导指派人员对安全生产责任状的落