课程实验报告

课程实验报告

课程实验报告

PAGE

PAGE #

实验一 STL的熟悉与使用

实验名称

实验一 STL的熟悉与使用

姓 名

汪子成 系院专业

信息工程系

班级计算机15-1班

学号

2015216758

实验日期

指导教师

徐本柱

成绩

一、实验目的和要求

.掌握C++中STL的容器类的使用；

.掌握C++中STL的算法类的使用.

二、实验预习内容

1.预习ICPC讲义，大致了解 STL的相关内容。

.了解STL中一些类 vector list类的使用方法

.了解泛型算法的使用

三、实验项目摘要

练习vector和list的使用。疋义一个空的vector，兀素类型为int,生成10个随机数插入到 vector

中，用迭代器遍历 vector并输出其中的元素值。在 vector头部插入一个随机数，用迭代器遍历

vector并输出其中的元素值。用泛型算法 find查找某个随机数，如果找到便输出，否则将此数

插入vector尾部。用泛型算法 sort将vector排序，用迭代器遍历 vector并输出其中的兀素值。

　删除vector尾部的兀素，用迭代器遍历 vector并输出其中的兀素值。将 vector清空。疋义一个

list，并重复上述实验，并注意观祭结果。

练习泛型算法的使用。定义一个 vector，元素类型为int,插入10个随机数，使用 sort按升序

排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用find查找元素。用min和 max找出容器中的最小元素和最大元素，并输出。

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

1.练习vector和list的使用：

#i nclude <iostream>

#in elude <vector>

#in cludevioma nip>

#in clude<ctime>

#i nclude <algorithm>

using n amespace std;

vector <int> myV;

bool sortup(i nt v1,i nt v2)

{

retur n v1<v2;

}

int main (i nt argc, char *argv[])

{

srand(time(NULL)); for (int i=0;i<10;i++)

myV.push_back(ra nd());

sort(myV.beg in (),myV.e nd(),sortup); vector<in t>::iterator it1;

for (it1=myV .begi n();it1!=myV .en d();it1++)

{

8山<<(51)<<$6上可(6)；

}

cout<<e ndl;

int mi n=m yV[0];

for (it1=myV .begi n()+1;it1!=myV .en d();it1++)

if((*it1)<mi n)mi n=(*it1);

cout<<"最小元素为"wminwendl;

int max=myV[0];

for (it1=myV .begi n();it1!=myV .en d();it1++)

if((*it1)>max)max=(*it1);

coutw"最大元素为"wmaxwendl;

cout?e ndl;

int value=ra nd();

it1=find(myV .begin(),myV.end(),value); if((*it1)==value)

cout?"找到了这个随机数"<<endl ;

else

coutvv"没有找到这个随机数"<<endl;

myV.i nsert(myV.e nd(),value);

coutvv"插入尾部的随机数为"vvvaluevvendl; for (it1=myV .begi n();it1!=myV .en d();it1++) {

8山<<(*让1)<<$6上可(6)；

}

cout<<"\n"<<e ndl;

int t=ra nd();

myV.i nsert(myV.begi n(),t);

coutvv"插入头部的随机数为"vv^vendl; for (it1=myV .begi n();it1!=myV .en d();it1++) {

coutvv(*it1)vvsetw(6);

}

coutvve ndl;

myV.pop_back ();

for (it1=myV .begi n();it1!=myV .en d();it1++)

{

coutvv(*it1)vvsetw(6);

}

coutvve ndl;

myV.clear();

if(myV .empty())

{

cout << "It's empty!" << en dl;

}

system("PAUSE"); //press any key to con ti nu e... return 0;

祐入头却的随机数为202800280 1635 2765 461720280 1635

祐入头却的随机数为20280

0280 1635 2765 4617

20280 1635 2765 4617

111s empty!

请按任意键继绞..?.

il

为21435

635 2765 4617 4889

635 2765 4617 48 ?91635曰 —

635 2765 4617 48 ?9

1635

曰 —w ] I

甌夫兀素752801&

4S89 6289 13975 1476? 190?6 23408 28016 214354889 6289 13975 14767 19076 23488 2801662?9 13975 14767 1907&

4S89 6289 13975 1476? 190?6 23408 28016 21435

4889 6289 13975 14767 19076 23488 28016

2练习泛型算法的使用：

#i nclude<list>

#in clude<iostream> using n amespace std; typedef list<i nt> lin;

in t value[]={1,6,7,8,9};

void prin t(lin &l)

{

int i;

lin::iterator lit;

for(lit=l.beg in ();lit!=l.e nd();lit++) cout<<(*lit)<<"";

cout?e ndl;

}

bool sortsp(i nt v1,i nt v2)

{

retur n v1>v2;

}

int mai n(){

lin lin2;

lin 2.push_fro nt(3);

lin 2.push_fro nt(4);

lin 2.i nsert(li n2.beg in( ),value,value+5);

cout?"lin2内的元素为：";

prin t(li n2);

lin 2.sort();

cout?"排序后的 lin2:";

prin t(li n2);

lin 2.push_fro nt(1O);

cout?"在list头部插入10之后的结果：";

prin t(li n2);

lin 2.remove(6);

cout?"删除一个数后的lin 1:";

prin t(li n2);

system("PAUSE");

return 0;

}

■ C:\Users\VIC 8OSS\Documen

内的元素为：1？ 8 9 4 3

排序看的lin2： 1 3 4 6 7 9 9

1±list头部插入10之后的结果；10 1346789

删睁一个1101=10 1 3 4 7 8 9

碾任*礙镁….

实验二 搜索算法的实现

实验名称

实验二搜索算法的实现

姓 名

汪子成 系院专业

信息工程系

班 级计算机15-1班

学 号

2015216758

实验日期

指导教师

徐本柱

成 绩

一、实验目的和要求

?掌握宽度优先搜索算法；

.掌握深度优先搜索算法.

二、实验预习内容

预习ICPC讲义中的搜索的内容

了解什么是深度优先搜索和广度优先搜索。

三、实验项目摘要

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

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

3.骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶

点，输出一条符合上述要求的路径。

4?倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出 L升

的水，如果可以，输出步骤，如果不可以，请输出 No Solution

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

2,八皇后问题：

#i nclude <stdio.h>

#defi ne N 8

#defi ne NUM 8

int h[N][N] ,n[ N],H[N][N];

int coun t=0;

void tryit(i nt, int);

void outputArray(i nt[][N]);

mai n()

{

int x=O,y=O,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(i nt x,i nt y)

{

int i,j;

if(cou nt<=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)&&coun t!=1)

{}

else

{

if(x>=0&& x<=N-1 &&y>=0&&y<=N-1 &&h[x][y]==O)

{

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

{

if(h[x][j]==O)

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

if(h[j][y]==O)

h[j][y]=x+1;

if(x+j>=0&& x+jv=N-1 &&y+j>=0&&y+j<=N-1 &&h[x+j][y+j]==O) 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;

}

}

coun t=co un t+1;

if(cou nt<=NUM)

{

printf("——布局 %d——\n",cou nt);

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]=O；

}

}

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][i]==x||h[i][i]==-x)

h[i][j]=O；

}

}

if(x-1>=0)

tryit(x-1, n[x-1]+1);

else

tryit(O,O);

}

else

tryit(x,y+1);

}

}

}

}

void outputArray(i nt h[][N])

{

int i,j;

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

{

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

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

prin tf("\n");

}

}

丄 0 @ kl 0 0 6

9 8 1 3 0 8 Q

布局2

0 0 0 0 0 6 0

0 0 0 10 0 0

布局3

0 0 6 0 0 0 6

0 3 0 0 0 10

3.骑士游历问题：

#i nclude <stdio.h>

int board[8][8] = {0};

int travel( int x, int y)

{

int ktmove1[8] = {-2, -1,1,2, 2,1, -1, -2}; int ktmove2[8] = {1,2, 2, 1, -1, -2, -2, -1}; int nexti[8] = {0};

int nextj[8] = {0};

int exists[8] = {0};

int i, j, k, m, l;

int tmpi, tmpj;

int count, min, tmp;

i = x;

i = v;

board[i][j] = 1;

for(m = 2; m <= 64; m++) {

for(l = 0; l < 8; l++)

exists[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) con ti nue;

if(board[tmpi][tmpj] == 0) {

n exti[l] = tmpi;

n extj[l] = tmpj;

l++;

}

}

count = l;

if(co unt == 0) {

return 0;

}

else if(co unt == 1) {

min = 0;

}

else {

for(l = 0; l < count; l++) {

for(k = 0; k < 8; k++) {

tmpi = n exti[l] + ktmove1[k];

tmpj = n extj[l] + ktmove2[k];

if(tmpi < 0 || tmpj < 0 ||

tmpi > 7 || tmpj > 7) {

con ti nue;

}

if(board[tmpi][tmpj] == 0)

exists[l]++;

}

}

tmp = exists[0];

min = 0;

for(l = 1; l < count; l++) {

if(exists[l] < tmp) {

tmp = exists[l];

min = l;

}

}

}

i = n exti[ min];

j = n extj[mi n];

board[i][j] = m;

}

return 1;

}

int mai n()

{

int startx, starty;

int i, j;

printf("输入起始点:");scanf("%d %d", &startx, &starty); if(travel(startx, starty)) { printf("游历完成！ \n");

}

else {

printf("游历失败！ \n");

}

for(i = 0; i < 8; i++) {

for(j = 0; j < 8; j++) {

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

}

putchar('\n');

}

return 0;

}

? C:\Users\VIC BOSS\Docurnents\^p^￡2,€

魏入起粗点；0 1

诱历完成！

TOC \o "1-5" \h \z 4 1 6 21 2S 43 16 19

7 22 3 44 17 28 29 42

2 5 24 27 48 41 18 15

23 B 45 40 25 56 47 30

52 3? 26 61 46 49 14 57

9 64 53 50 55 60 31 34

38 51 62 11 36 33 58 13

B3 10 3? 54 59 12 35 32

E*pocess exited aftei* seconds with return value 0

青按任意键继塚….

实验三 计算几何算法的实现

实验名称

实验一

二计算几何算法的实现

姓 名

汪子成

系院专业

信息工程系

班 级

计算机15-1班

学 号

2015216758

实验日期

指导教师

徐本柱

成 绩

、实验目的和要求

理解线段的性质、叉积和有向面积。

掌握寻找凸包的算法。

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

、实验预习内容

?预习ICPC讲义，大致了解计算几何算法的相关内容。

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

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

、实验项目摘要

将讲义第三章第三节中的凸包代码上机运行并检验结果。

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

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

房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房

间的边界固定在 x=0,x=10,y=0和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0到18个 墙，每个墙有两个门。输入给定的墙的个数，每个墙的 x位置和两个门的y坐标区间，输出最

短路的长度。下图是个例子：

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

3.思考：

用跨立方法。线段相交满足且只需满足如下两个条件就可以了： 1两条线段相互跨立；2 一

条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若

p1p2跨立p3p4，则矢量(pl - p3 )和(p2 - pl )位于矢量(p4 - p3 )的两侧，即(pl - p3) X ( p4- p3 ) * ( p2 - p3 ) X ( p4 - p3 ) < 0。上式可改写成(pl - p3 ) X ( p4- p3 ) * ( p4 - p3 ) X ( p2 - p3) > 0。当(pl - p3 ) X ( p4 - p3 ) = 0 时，说明(pl - p3 )和(p4 - p3 )共线，但是因为已经通过快速排斥试验，所以 pl 一定在线段p3p4

上；同理，(p4 - p3 ) X (p2 - p3 ) = 0说明p2 一定在p3p4上。所以判断p1p2跨立 Q1Q2 的依据是：(pl - p3 ) X ( p4 - p3 ) * ( p4 - p3 ) X ( p2 - p3 ) >= 0。同理判 断 Q1Q2 跨立 P1P2 的依据是：(p3 - pl ) X ( p2 - pl ) * ( p2 - pl ) X ( p4 - pl ) >= 0。代 码中函数bool segment_intersect(用于判断pl、p2构成的线段和p3、p4构成的线段是否相 交。可以看出共五种情况两线段是相交的，反之就输出“ The two are Not in tersected”

4?房间最短路问题：

#in clude<iostream>

#in clude<utility>

#in clude<vector>

#i nclude<algorithm>

using n amespace std;

typedef pair<double,double> POINT;

double direction(POINT p,POINT p1,POINT p2){

POINT v1,v2;

v1.first=p2.first-p1.first;

v1.sec on d=p2.sec on d-p1.first;

v2.first=p1.first-p.first;

v2.sec on d=p1.sec on d-p.sec ond;

return v1.first*v2.sec on d-v1.sec on d*v2.sec on d;}

bool on_segme nt(POINT p,POINT p1,POINT p2){

double min _x=p1.first<p2.first?p1.first:p2.first;

double max_x=p1.first>p2.first?p1.first:p2.first;

double min _y=p1.sec on d<p2.sec on d?p1.sec on d:p2.sec ond;

double max y=p1.second>p2.second?p1.second:p2.second;

if(p.first>=min_x&&p.first<max_x&&p.seco nd>= min_y&&p.seco nd<=max_y)

return true;

else

return false;

}

POINT startPoi nt;

bool sortByPolorA ngle(co nst POINT & p1,co nst POINT & p2)

{

double d=directi on( startPo in t,p1,p2);

if(d<0)return true;

if(d >0)return false;

if(d==0&&on _segme nt(startPo in t,p1,p2))retur n true;

if(d= =0&&on_segment(p2,startPoint,p1))return true;

return false;

}

void find_con vex_hull(vector<POINT >& poi nt)

{

POINT p0=poi nt[0];

int k=0;

for(int i=0;i<point.size();i++)

{

if(po in t[i].sec on d<p0.sec on d||

poin t[i].sec on d==p0.sec；ond&&poin t[i].first<p0.first){

p0=poi nt[i];

k=i;}

}

poi nt.erase(poi nt.begi n()+k);

poin t.i nsert(po in t.begi n() ,p0);

vector<POINT>co nvex_hull;

do{

con vex hull.push back(po in t[0]);

startPoi nt=poi nt[0];

poin t.erase(po in t.beg in());

sort(poi nt.beg in( ),poi nt.e nd(),sortByPolorA ngle);

if(po in t[0]==c on vex_hull[0])break;

poi nt.push_back(co nv ex_hull[c on vex_hull.size()-1]);

}while(1);

for(i nt j=0;j<c on vex_hull.size();j++){

cout?c onv ex_hull[j].first<<' '<<c on vex_hull[j].sec on d<<e ndl;

}}

int mai n(){

vector<POINT> pv;

double x,y;

int i;

cout?"请输入 10 个点 <x,y>: "<<endl;

for(i=1;i<=10;i++){ cout<v"No."v<ivv':';

cin> >x>>y;

pv.push_back(make_pair(x,y));

}

cout?endl; find_convex_hull(pv);

system("Pause");

return 0;

}

实验四 动态规划算法的实现

实验名称

实验四动态规划算法的实现

姓 名

汪子成 系院专业

信息工程系

班 级计算机15-1班

学 号

2015216758

实验日期

指导教师

徐本柱

成 绩

一、实验目的和要求

?理解动态规划的基本思想、动态规划算法的基本步骤

?掌握动态规划算法实际步骤

二、实验预习内容

1 ?动态规划算法的基本要素

2.取长公共子序列

3 ?矩阵连乘问题

、实验项目摘要

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

-151 - X的一个子序列是相应于 X下标序列｛1,2,…,m｝的一个子序列，求解两个 序列的所有子序列中长度最大的，例如输入： pear, peach输出：pea。

给定两个字符串a和b,现将串a通过变换变为串b,可用的操作为，删除串 a中的一个字符；在串a的某个位置插入一个元素；将串a中的某个字母换为另 一个字母。对于任意的串a和串b,输出最少多少次能够将串变为串 bo思考： 输出变换的步骤。

输入一个矩阵，计算所有的子矩阵中和的最大值。 例如，输入0 -2 -7 0 9 2

-6 2 -4 1 -4 1 -1 8 0 -2输出为：15思考：当矩阵很大时，比如100*100的矩阵， 你的程序还能够很快的得出结果吗， 如果不能，请思考如何用动态规划的思想解

决。

四、实验结果与分析(源程序及相关说明) 源代码如下：

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

#in clude<iostream>

#in clude<stri ng>

using n amespace std;

void longest(string s1,string s2)

{

int max,tep,i,j;

int a[100][100];

for(i=0;i<s1.size();i++) for(j=0;j<s2.size();j++) a[i][j]=O;

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;

max=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(max<a[i][j])

{

max=a[i][j];

tep=i;

}

}

if(max==0)

COUtvv"没有公共子序列!"；

else

{

COUtvv"两个字符串的最长公共子序列为 ："；

for(i=tep-max+1;i<=tep;i++)

cout<<s1[i];

coutvve ndl;

}

}

int mai n()

{

stri ng s1,s2;

COUtvv"请输入两个字符串:"<<endl;

coutvv" —个字符串为："；

cin> >s1;

coutvv"另一个字符串为："；

cin> >s2;

lon gest(s1,s2); coutvve ndl;

return 0;

}

■ C:\U&ers\VIC BOSS\Documents\^：np?2.

请输入两个壬符串：

Process exited af tei* 3.123 seconds with ret urn value 0

青按任意键继续■

(2)给定两个字符串a和b,现将串a通过变换变为串b

#in cludeviostream>

#in cludevstri ng>

using n amespace std;

int min (i nt x1,i nt x2, int x3)

{

if(x2<x1)

x仁 x2;

else if(x3<x1)

x1=x3;

return x1;

}

void cha nge(stri ng s1,stri ng s2)

{

const char * str=s1.c_str();

const char * tep=s2.c_str();

int b[100][100];

b[0][0]=0；

for(i nt i=1;i<=s1 .len gth();i++)

b[0][i]=i;

for(i nt j=1;jv=s2 .len gth();j++)

b[j][0]=j;

for( i=1;i<=s2」en gth(); i++)

for(int m=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+mi n(b[i-1][m-1],b[i-1][m],b[i][m-1]);

}

cout?"将a变为 b需要"<<b[s2.length()][s1.length()]vv "步！ "<<endl;

}

int mai n()

{

stri ng s1,s2;

cout <<"输入字符串a:";

cin >>s1;

cout <<"输入字符串b:";

cin >> s2;

cha nge(s1,s2);

cout?e ndl;

return 0;

}

其中专业理论知识内容包括：保安理论知识、消防业务知识

其中专业理论知识内容包括：保安理论知识、消防业务知识

卫、职业道德、法律常识、保安礼仪、救护知识。作技能训练内容包括：岗位操作指引、勤务技能、消防技能、军事技能。

二?培训的及要求培训目的

安全生产目标责任书

为了进一步落实安全生产责任制，做到“责、权、利”相结合，根据我公司 2015年度安全生产目标的内容，现与 财务部 签订如下安全生产目标:

目标值:

1、全年人身死亡事故为零，重伤事故为零，轻伤人数为零。

2、现金安全保管，不发生盗窃事故。

3、每月足额提取安全生产费用，保障安全生产投入资金的到位。

4、安全培训合格率为 100%。

二、本单位安全工作上必须做到以下内容:

1、对本单位的安全生产负直接领导责任，必须模范遵守公司的各项安全管理制度，不发布与公司安全管理制度相抵触的指令，严格履行本人的安全职责，确保安全责任制在本单位全面落实，并全力支持

安全工作。

2、保证公司各项安全管理制度和管理办法在本单位内全面实施，并自觉接受公司安全部门的监督和管理。

3、在确保安全的前提下组织生产，始终把安全工作放在首位，当“安全与交货期、质量”发生矛盾时，坚持安全第一的原则。

4、参加生产碰头会时，首先汇报本单位的安全生产情况和安全问题落实情况；在安排本单位生产任务时，必须安排安全工作内容，并写入记录。

5、在公司及政府的安全检查中杜绝各类违章现象。

6、组织本部门积极参加安全检查，做到有检查、有整改，记录全。

7、以身作则，不违章指挥、不违章操作。对发现的各类违章现象负有查禁的责任，同时要予以查处。

8、虚心接受员工提出的问题，杜绝不接受或盲目指挥;

9、发生事故，应立即报告主管领导，按照“四不放过”的原则召开事故分析会，提出整改措施和对责任者的处理意见，并填写事故登记表，严禁隐瞒不报或降低对责任者的处罚标准。

10、必须按规定对单位员工进行培训和新员工上岗教育；

11、严格执行公司安全生产十六项禁令，保证本单位所有人员不违章作业。

三、 安全奖惩：

1、对于全年实现安全目标的按照公司生产现场管理规定和工作说明书进行考核奖励；对于未实现安全目标的按照公司规定进行处罚。

2、每月接受主管领导指派人员对安全生产责任状的落