課程實驗報告匯總（精編版）

1、.實驗一 stl 的熟悉與使用實驗名稱實驗一 stl的熟悉與使用姓名汪子成系院專業(yè)信息工程系班 級計算機 15-1 班學 號2015216758實驗日期指導教師徐本柱成 績一、實驗目的和要求1. 掌握 c+中 stl的容器類的使用;2. 掌握 c+中 stl的算法類的使用.二、實驗預習容1預習 icpc 講義，大致了解stl 的相關容。2了解 stl 中一些類 vector list類的使用方法3了解泛型算法的使用三、實驗項目摘要(1) 練習 vector和 list的使用。定義一個空的vector，元素類型為int，生成 10 個隨機數(shù)插入到 vector中，用迭代器遍歷vector并輸出其

2、中的元素值。在vector頭部插入一個隨機數(shù)， 用迭代器遍歷vector并輸出其中的元素值。用泛型算法find查找某個隨機數(shù)，如果找到便輸 出，否則將此數(shù)插入vector尾部。 用泛型算法sort將 vector排序， 用迭代器遍歷vector并輸出其中的元素值。刪除vector尾部的元素，用迭代器遍歷vector并輸出其中的元素值。將 vector清空。定義一個list，并重復上述實驗，并注意觀察結果。(2) 練習泛型算法的使用。定義一個 vector ，元素類型為 int ，插入 10 個隨機數(shù)，使用 sort 按升序排序， 輸出每個元素的值， 再按降敘排序， 輸出每個元素的值。 練習用

3、find 查找元素。 用 min 和 max 找出容器中的最小元素和最大元素，并輸出。24 / 24四、實驗結果與分析（源程序與相關說明）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

4、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);vector<int>:iterator it1; for (it1=myv.begin();it1!=myv.end();it1+)cout<<(*it1)<<setw(6);cout<<endl;int min=myv0;for (it1=myv.begin()+1;it1!=myv.end();i

5、t1+) if(*it1)<min)min=(*it1);cout<<"最小元素為 " <<min<<endl;int max=myv0;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

6、(*it1)=value)cout<<"找到了這個隨機數(shù) "<<endl ;elsecout<<"沒有找到這個隨機數(shù) "<<endl; myv.insert(myv.end(),value);cout<<"插入尾部的隨機數(shù)為 "<<value<<endl; for (it1=myv.begin();it1!=myv.end();it1+)cout<<(*it1)<<setw(6);cout<<"n"

7、;<<endl;int t=rand(); myv.insert(myv.begin(),t);cout<<"插入頭部的隨機數(shù)為 " <<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&l

8、t;<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> using namespace std; typedef list<int> lin; int value=1,6,7,8,9; void print(lin

9、 &l)int i; lin:iterator lit;for(lit=l.begin();lit!=l.end();lit+)cout<<(*lit)<<" " 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的 元 素 為 ： &

10、quot; print(lin2);lin2.sort();cout<<" 排序后的 lin2: " print(lin2); lin2.push_front(10);cout<<" 在 list頭部插入 10 之后的結果： "print(lin2); lin2.remove(6);cout<<" 刪除一個數(shù)后的lin1:" print(lin2);system("pause"); return 0;實驗二搜索算法的實現(xiàn)實驗名稱實驗二搜索算法的實現(xiàn)姓名汪子成系院專業(yè)信息工程系班級

11、計算機 15-1 班學號2015216758實驗日期指導教師徐本柱成績一、實驗目的和要求1. 掌握寬度優(yōu)先搜索算法;2. 掌握深度優(yōu)先搜索算法.二、實驗預習容1. 預習 icpc 講義中的搜索的容2. 了解什么是深度優(yōu)先搜索和廣度優(yōu)先搜索。三、實驗項目摘要1. 將書上的走迷宮代碼上機運行并檢驗結果，并注意體會搜索的思想。2. 八皇后問題：在一個國際象棋棋盤上放八個皇后，使得任何兩個皇后之間不相互攻擊，求出所有的布棋方法。上機運行并檢驗結果。3. 騎士游歷問題： 在國際棋盤上使一個騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂點，輸出一條符合上述要求的路徑。4. 倒水問題：給定2 個沒有刻度容

12、器，對于任意給定的容積，求出如何只用兩個瓶裝出l 升的水，如果可以，輸出步驟，如果不可以，請輸出no solution四、實驗結果與分析（源程序與相關說明）2，八皇后問題： #include <stdio.h> #define n 8#define num 8int hnn,nn,hnn;int count=0; void tryit(int,int);void outputarray(intn);main()int x=0,y=0,i,j; for(i=0;i<=n-1;i+)for(j=0;j<=n-1;j+) hij=0;tryit(x,y); printf(&q

13、uot;.n");printf("共有%d種布局 .n",92);return(0);void tryit(int x,int y)int i,j; if(count<=num)if(h00=1&&h14=1&&h27=1&&h35=1&&h42=1&&h56= 1&&h61=1&&h73=1)&&count!=1)elseif(x>=0&&x<=n-1&&y>=0&&

14、;y<=n-1&&hxy=0)for(j=0;j<=7;j+)if(hxj=0)hxj=x+1;if(hjy=0)hjy=x+1;if(x+j>=0&&x+j<=n-1&&y+j>=0&&y+j<=n-1&&hx+jy+j=0) hx+jy+j=x+1;if(x+j>=0&&x+j<=n-1&&y-j>=0&&y-j<=n-1&&hx+jy-j=0)hx+jy-j=x+1;if(x-j>

15、=0&&x-j<=n-1&&y+j>=0&&y+j<=n-1&&hx-jy+j=0) hx-jy+j=x+1;if(x-j>=0&&x-j<=n-1&&y-j>=0&&y-j<=n-1&&hx-jy-j=0) hx-jy-j=x+1;hxy=-x-1; if(x=7)for(i=0;i<=n-1;i+)for(j=0;j<=n-1;j+)if(hij<0)hij=1;elsehij=0;count=count

16、+1; if(count<=num)printf("-布局%dn",count);outputarray(h);for(i=0;i<=n-1;i+)for(j=0;j<=n-1;j+)if(hij=x|hij=-x|hij=-x-1) hij=0;elsetryit(x-1,nx-1+1);nx=y;elsetryit(x+1,0);if(y>7)for(i=0;i<=n-1;i+)for(j=0;j<=n-1;j+)if(hij=x|hij=-x)hij=0;tryit(0,0);elseif(x-1>=0)tryit(x-1,n

17、x-1+1); elsetryit(x,y+1);void outputarray(int hn)int i,j;for(i=0;i<=n-1;i+)for(j=0;j<=n-1;j+) printf("%d ",hij);printf("n");3. 騎士游歷問題： #include <stdio.h> int board88 = 0;int travel(int x, int y)int ktmove18 = -2, -1, 1, 2, 2, 1, -1, -2;int ktmove28 = 1, 2, 2, 1, -1, -

18、2, -2, -1;int nexti8 = 0;int nextj8 = 0; int exists8 = 0; int i, j, k, m, l;int tmpi, tmpj;int count, min, tmp; i = x;j = y;boardij = 1;for(m = 2; m <= 64; m+) for(l = 0; l < 8; l+) existsl = 0;l = 0;for(k = 0; k < 8; k+) tmpi = i + ktmove1k; tmpj = j + ktmove2k;if(tmpi < 0 | tmpj < 0

19、 | tmpi > 7 | tmpj > 7)continue; if(boardtmpitmpj = 0) nextil = tmpi;nextjl = tmpj; l+;count = l; if(count = 0) return 0;else if(count = 1) min = 0;else for(l = 0; l < count; l+) for(k = 0; k < 8; k+) tmpi = nextil + ktmove1k; tmpj = nextjl + ktmove2k; if(tmpi < 0 | tmpj < 0 |tmpi

20、> 7 | tmpj > 7) continue;if(boardtmpitmpj = 0) existsl+;tmp = exists0; min = 0;for(l = 1; l < count; l+) if(existsl < tmp) tmp = existsl; min = l;i = nextimin; j = nextjmin; boardij = m;return 1;int main()int startx, starty; int i, j;printf("輸入起始點： "); scanf("%d %d",

21、&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 ", boardij);putchar('n');return 0;實驗三計算幾何算法的實現(xiàn)實驗名稱實驗二計算幾何算法的實現(xiàn)姓名汪子成系院專業(yè)信息工程系班級計算機 15-1 班學號2015216758實驗日期指導教

22、師徐本柱成績一、實驗目的和要求1. 理解線段的性質(zhì)、叉積和有向面積。2. 掌握尋找凸包的算法。3. 綜合運用計算幾何和搜索中的知識求解有關問題。二、實驗預習容1. 預習 icpc 講義，大致了解計算幾何算法的相關容。2. 了解實現(xiàn)該算法的中一些使用方法。3. 會使用該算法解決實際問題。三、實驗項目摘要1. 將講義第三章第三節(jié)中的凸包代碼上機運行并檢驗結果。2. 完成講義第三章的課后習題，上機運行并檢驗結果。3. 思考：判線段相交時，如果有個線段的端點在另一條線段上，注意可能與另一條線段上的端點重合，思考這樣的情況怎么辦。4. 房間最短路問題：給頂一個含阻礙墻的房間，求解出一條從起點到終點的最最

23、短路徑。房間的邊界固定在x=0,x=10,y=0和 y=10。起點和重點固定在(0,5)和(10,5)。房間里還有0 到18 個墻，每個墻有兩個門。輸入給定的墻的個數(shù)，每個墻的x 位置和兩個門的y 坐標區(qū)間， 輸出最短路的長度。以下圖是個例子：四、實驗結果與分析（源程序與相關說明）3. 思考：用跨立方法。線段相交滿足且只需滿足如下兩個條件就可以了：1 兩條線段相互跨立； 2 一條線段的一個端點在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對方。若p1p2 跨立 p3p4 ，則矢量 ( p1 p3 )和( p2 - p1 )位于矢量 ( p4 p3 )的兩側(cè)，即( p1 p3） ×

24、; ( p4- p3 ) * ( p2 p3 )× ( p4p3 ) < 0 。上式可改寫成 ( p1 p3 )× ( p4- p3 ) * ( p4 p3 )× ( p2 p3) > 0。當( p1 p3 )× ( p4 p3 ) = 0時，說明 ( p1 p3 )和 ( p4 p3 )共線，但是因為已經(jīng)通過快速排斥試 驗，所以 p1一定在線段 p3p4 上；同理， ( p4 p3 )×(p2 p3 ) = 0說明 p2一定在 p3p4 上。所以判斷p1p2 跨立 q1q2的依據(jù)是： ( p1 p3 )× (p4 p3

25、) * ( p4 p3 )× ( p2p3 ) >= 0。同理判斷 q1q2跨立 p1p2的依據(jù)是： ( p3 - p1 )× ( p2- p1 ) * ( p2 - p1 )× ( p4 - p1 ) >= 0。代碼中函數(shù)bool segment_intersect() 用于判斷 p1、p2 構成的線段和 p3、p4 構成的線段是否相交?？梢钥闯龉参宸N情況兩線段是相交的，反之就輸出“the two are not intersected!”4. 房間最短路問題： #include<iostream> #include<utility

26、> #include<vector> #include<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*

27、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; double 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.fir

28、st>=min_x&&p.first<max_x&&p.second>= min_y&&p.second<=max_y) return true;elsereturn 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&

29、;&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=point0; int k=0;for(int i=0;i<point.size();i+)if(pointi.second<p0.second| pointi.second=p0.second&&pointi.

30、first<p0.first) p0=pointi;k=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(

31、convex_hullconvex_hull.size()-1);while(1);for(int j=0;j<convex_hull.size();j+) cout<<convex_hullj.first<<' '<<convex_hullj.second<<endl;int main() vector<point> pv; double x,y;int i;cout<<"請輸入 10 個點<x,y> ："<<endl;for(i=1;i<=10;i

32、+)cout<<"no."<<i<<':' cin>>x>>y;pv.push_back(make_pair(x,y);cout<<endl; find_convex_hull(pv); system("pause");return 0;實驗四動態(tài)規(guī)劃算法的實現(xiàn)實驗名稱實驗四動態(tài)規(guī)劃算法的實現(xiàn)姓名汪子成系院專業(yè)信息工程系班級計算機 15-1 班學號2015216758實驗日期指導教師徐本柱成績一、實驗目的和要求1. 理解動態(tài)規(guī)劃的基本思想、動態(tài)規(guī)劃算法的基本步驟2.

33、掌握動態(tài)規(guī)劃算法實際步驟二、實驗預習容1. 動態(tài)規(guī)劃算法的基本要素2. 最長公共子序列3. 矩陣連乘問題三、實驗項目摘要(1) 求兩個字符串的最長公共子序列。- 151 - x的一個子序列是相應于x 下標序列 1, 2, m 的一個子序列，求解兩個序列的所有子序列中長度最大的，例如輸入：pear, peach輸出： pea。(2) 給定兩個字符串a(chǎn) 和 b，現(xiàn)將串 a 通過變換變?yōu)榇産，可用的操作為， 刪除串a(chǎn) 中的一個字符；在串a(chǎn) 的某個位置插入一個元素；將串a(chǎn) 中的某個字母換為另一個字母。對于任意的串 a 和串 b，輸出最少多少次能夠?qū)⒋優(yōu)榇産。 思考： 輸出變換的步驟。(3) 輸入一個

34、矩陣，計算所有的子矩陣中和的最大值。 例如，輸入 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2輸出為： 15 思考：當矩陣很大時，比如 100*100 的矩陣，你的程序還能夠很快的得出結果嗎，如果不能，請思考如何用動態(tài)規(guī)劃的思想解決。四、實驗結果與分析（源程序與相關說明） 源代碼如下：1. 求兩個字符串的最長公共子序列。#include<iostream> #include<string>using namespace std;void longest(string s1,string s2)int max,tep,i,j; int a100100;for(i=0;i<s1.size();i+)for(j=0;j<s2.size();j+) aij=0;for (j=0;j<s2.size();j+)if (s10=s2j)a0j=1;for (i=0;i<s1.size();i+) if (s1i=s20)ai0=1;max=a00; tep=0; for(i=1;i<s1.size();i+)for(j=1;j<s2.size();j+) if(s1i