課程實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)一 STL 的熟悉與使用實(shí)驗(yàn)名稱實(shí)驗(yàn)一 STL 的熟悉與使用姓名汪子成 系院專業(yè)信息工程系班 級 計(jì)算機(jī) 15-1 班學(xué)號2015216758實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成績一、實(shí)驗(yàn)?zāi)康暮鸵?掌握 C+中STL 的容器類的使用 ;2掌握 C+中STL 的算法類的使用 .二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1預(yù)習(xí) ICPC 講義，大致了解 STL 的相關(guān)內(nèi)容。 2了解 STL 中一些類 vector list 類的使用方法 3了解泛型算法的使用三、實(shí)驗(yàn)項(xiàng)目摘要(1) 練習(xí) vector 和 list 的使用。定義一個(gè)空的 vector，元素類型為 int ，生成 10 個(gè)隨機(jī)數(shù)插入到 vector 中，用迭代器遍歷

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

3、素的值， 再按降敘排序， 輸出每個(gè)元素的值。 練習(xí)用 find 查找元素。 用 min 和 max 找出容器中的最小元素和最大元素，并輸出。四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說明)1. 練習(xí) vector 和 list 的使用：#include <iostream> #include <vector> #include<iomanip> #include<ctime>#include <algorithm> using namespace std; vector<int> myV; bool sortup(int v1,in

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

5、=myV .begin()+1;it1!=myV .end();it1+) 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=

6、find(myV .begin(),myV.end(),value); if(*it1)=value) cout<<" 找到了這個(gè)隨機(jī)數(shù) "<<endl ; else cout<<" 沒有找到這個(gè)隨機(jī)數(shù) "<<endl; myV.insert(myV.end(),value); cout<<" 插入尾部的隨機(jī)數(shù)為 "<<value<<endl;for (it1=myV .begin();it1!=myV .end();it1+) cout<<

7、;(*it1)<<setw(6); cout<<"n"<<endl;int t=rand(); myV.insert(myV.begin(),t); cout<<" 插入頭部的隨機(jī)數(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

8、!=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 練習(xí)泛型算法的使用： #include<list> #include<iostream> using namespace std;

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

10、2.insert(lin2.begin(),value,value+5); cout<<"lin2 內(nèi)的元素為： "print(lin2);lin2.sort();cout<<" 排序后的 lin2: "print(lin2); lin2.push_front(10);cout<<" 在 list 頭部插入 10 之后的結(jié)果：print(lin2);lin2.remove(6); cout<<" 刪除一個(gè)數(shù)后的 lin1:" print(lin2); system("

11、PAUSE");return 0;實(shí)驗(yàn)二 搜索算法的實(shí)現(xiàn)實(shí)驗(yàn)名稱實(shí)驗(yàn)二 搜索算法的實(shí)現(xiàn)姓名汪子成系院專業(yè)信息工程系班級計(jì)算機(jī) 15-1 班學(xué)號2015216758實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成績一、實(shí)驗(yàn)?zāi)康暮鸵?掌握寬度優(yōu)先搜索算法 ;2掌握深度優(yōu)先搜索算法 .二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1預(yù)習(xí) ICPC 講義中的搜索的內(nèi)容2. 了解什么是深度優(yōu)先搜索和廣度優(yōu)先搜索。三、實(shí)驗(yàn)項(xiàng)目摘要1. 將書上的走迷宮代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果，并注意體會搜索的思想。2.八皇后問題：在一個(gè)國際象棋棋盤上放八個(gè)皇后，使得任何兩個(gè)皇后之間不相互攻擊，求出 所有的布棋方法。上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。3. 騎士游歷問題：在國際棋盤上

12、使一個(gè)騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂 點(diǎn)，輸出一條符合上述要求的路徑。4.倒水問題：給定 2 個(gè)沒有刻度容器，對于任意給定的容積，求出如何只用兩個(gè)瓶裝出 L 升 的水，如果可以，輸出步驟，如果不可以，請輸出 No Solution四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說明)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;

13、i<=N-1;i+)for(j=0;j<=N-1;j+)hij=0;tryit(x,y);printf("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

14、)elseif(x>=0&&x<=N-1&&y>=0&&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&a

15、mp;&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>=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+

16、) for(j=0;j<=N-1;j+) if(hij<0)Hij=1;elseHij=0;count=count+1;01114= =a(+r lnhvohd04(+±vnhvo上)04FA)七S-L+XWA4-(L+vxc-vx)七 AJ_(+r lnhvohd04(+±lnhvo上)04(H)Ae<lndlnogun8-=5p&nlfe=)匕 £d(lAInNHVluns)七if(x-1>=0) tryit(x-1,nx-1+1);elsetryit(0,0);elsetryit(x,y+1);void outputArray

17、(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, -2, -2, -1; int nexti8 = 0;int nextj8 = 0

18、;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 | tmpi > 7 | tmpj > 7) continue;if

19、(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 > 7 | tmpj > 7) continue; if(board

20、tmpitmpj = 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(" 輸入起始點(diǎn)： "); scanf("%d %d", &startx, &starty); if(travel(s

21、tartx, 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;實(shí)驗(yàn)三 計(jì)算幾何算法的實(shí)現(xiàn)實(shí)驗(yàn)名稱實(shí)驗(yàn)二 計(jì)算幾何算法的實(shí)現(xiàn)姓名汪子成系院專業(yè)信息工程系班級計(jì)算機(jī) 15-1 班學(xué)號2015216758實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成績一、實(shí)驗(yàn)?zāi)康暮鸵?. 理解線段的性質(zhì)、叉積和有向

22、面積。2. 掌握尋找凸包的算法。3. 綜合運(yùn)用計(jì)算幾何和搜索中的知識求解有關(guān)問題。、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1預(yù)習(xí) ICPC 講義，大致了解計(jì)算幾何算法的相關(guān)內(nèi)容。 2了解實(shí)現(xiàn)該算法的中一些使用方法。3會使用該算法解決實(shí)際問題。、實(shí)驗(yàn)項(xiàng)目摘要1. 將講義第三章第三節(jié)中的凸包代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。2. 完成講義第三章的課后習(xí)題，上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。3. 思考：判線段相交時(shí)，如果有個(gè)線段的端點(diǎn)在另一條線段上，注意可能與另一條線段上的端 點(diǎn)重合，思考這樣的情況怎么辦。4. 房間最短路問題：給頂一個(gè)內(nèi)含阻礙墻的房間，求解出一條從起點(diǎn)到終點(diǎn)的最最短路徑。房 間的邊界固定在 x=0,x=10,y=0 和 y=10。

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

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

25、 × ( p2p3 ) >= 0。同理判 斷Q1Q2跨立P1P2的依據(jù)是： ( p3 - p1 ) × ( p2 - p1 ) * ( p2 - p1 ) × ( p4 - p1 ) >= 0。代 碼中函數(shù) bool segment_intersect(用) 于判斷 p1、p2 構(gòu)成的線段和 p3、p4 構(gòu)成的線段是否相 交。可以看出共五種情況兩線段是相交的，反之就輸出“ The two are Not intersected!”4.房間最短路問題：#include<iostream>#include<utility>#incl

26、ude<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*v2.second-v1.se

27、cond*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.first>=min_x&

28、amp;&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&&on segmen

29、t(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.first<p0.first)

30、 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(convex_hullconvex_h

31、ull.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 個(gè)點(diǎn) <x,y>："<<endl; for(i=1;i<=10;i+) cout<<&qu

32、ot;No."<<i<<':'cin>>x>>y;pv.push_back(make_pair(x,y);cout<<endl; find_convex_hull(pv); system("Pause");return 0;實(shí)驗(yàn)四 動態(tài)規(guī)劃算法的實(shí)現(xiàn)實(shí)驗(yàn)名稱實(shí)驗(yàn)四 動態(tài)規(guī)劃算法的實(shí)現(xiàn)姓名汪子成 系院專業(yè)信息工程系班 級 計(jì)算機(jī) 15-1 班學(xué)號2015216758實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成績一、實(shí)驗(yàn)?zāi)康暮鸵?理解動態(tài)規(guī)劃的基本思想、動態(tài)規(guī)劃算法的基本步驟2掌握動態(tài)規(guī)劃算法實(shí)際步驟、實(shí)驗(yàn)預(yù)習(xí)

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

34、陣中和的最大值。 例如，輸入 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 輸出為： 15 思考：當(dāng)矩陣很大時(shí)，比如 100*100的矩陣， 你的程序還能夠很快的得出結(jié)果嗎， 如果不能， 請思考如何用動態(tài)規(guī)劃的思想解 決。四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說明) 源代碼如下：1. 求兩個(gè)字符串的最長公共子序列。#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