1、程序設計藝術與方法課程實驗報告一實驗名稱 STL的熟悉與使用姓 名系院專業計算機與信息學院班 級計算機科學與技術122班學 號2012211643實驗日期指導教師徐本柱成 績一、實驗目的和要求1（1）掌握C+中STL的容器類使用。（2）掌握C+中STL的算法類的使用。二、實驗預習內容 Vector,list可當作列表使用的數據結構，它們都是動態增長的。1.vector表示一段連續的內存區域每個元素被順序儲存在這段內存中。對vector的隨即訪問效率很高。但是在任意位置而不是在vector末尾插入元素則效率很低，因為它需要把待插入元素的右邊的每個元素都拷貝一遍。類似的刪除任一個而不是vector

2、的最后一個元素效率低。2list表示非連續的內存區域并通過一對指向首尾元素的指針雙向進行遍歷在list的任意位置插入和刪除元素的效率都很高，指針必須被賦值但不需要用拷貝元素來實現移動，另一方面它對隨機訪問的支持并不好訪問一個元素需要遍歷中間的元素，另外每個元素還有倆不能給個指針的額外空間開銷。3泛型算法讓編寫一般化并可重復使用的算法，其效率與指針對某特定數據類型而設計的算法相同。泛型即是指具有在多種數據類型上皆可操作的含義，與模板有些相似。STL巨大而且可以擴充，它包含很多計算機基本算法和數據結構，而且將算法與數據結構完全分離，其中算法是泛型的，不與任何特定數據結構或對象類型系在一起。三、實驗

3、項目摘要1. 練習vector 和list 的使用。定義一個空的vector，元素類型為int，生成10 個隨機數插入到vector 中，用迭代器遍歷vector 并輸出其中的元素值。在vector 頭部插入一個隨機數，用迭代器遍歷vector并輸出其中的元素值。用泛型算法find 查找某個隨機數，如果找到便輸出，否則將此數插入vector 尾部。用泛型算法sort 將vector 排序，用迭代器遍歷vector 并輸出其中的元素值。刪除vector 尾部的元素，用迭代器遍歷vector 并輸出其中的元素值。將vector 清空。定義一個list，并重復上述實驗，并注意觀察結果2 練習泛型算法

4、的使用。定義一個vector，元素類型為int，插入10 個隨機數，使用sort 按升序排序，輸出每個元素的值，再按降敘排序，輸出每個元素的值。練習用find 查找元素。用min 和max 找出容器中的最小元素個最大元素，并輸出。四、實驗結果與分析（源程序及相關說明）1. 練習vector 和list 的使用：#include #include #include#include #include using namespace std;vector myV;bool sortup(int v1,int v2)return v1v2; int main(int argc, char *argv)

5、 srand(time(NULL); /隨機產生十個數 for (int i=0;i10;i+) myV.push_back(rand(); sort(myV.begin(),myV.end(),sortup); /用sort排序升序 vector:iterator it1; for (it1=myV.begin();it1!=myV.end();it1+) cout(*it1)setw(6); /打印數組 coutendl; int min=myV0; for (it1=myV.begin()+1;it1!=myV.end();it1+) if(*it1)min)min=(*it1); co

6、ut最小元素為 minmax)max=(*it1); cout最大元素為 maxendl; coutendl; int value=rand(); it1=find(myV.begin(),myV.end(),value); if(*it1)=value) cout找到了這個隨機數endl ; else cout沒有找到這個隨機數endl; myV.insert(myV.end(),value); /數組中沒有隨機數,插入尾部 cout插入尾部的隨機數為valueendl; for (it1=myV.begin();it1!=myV.end();it1+) cout(*it1)setw(6);

7、 coutnendl; /隨機在vector頭部插入一個隨機數 int t=rand();/定義t;將一個隨機數賦給t，插入到數組頭部 myV.insert(myV.begin(),t); cout插入頭部的隨機數為 tendl; for (it1=myV.begin();it1!=myV.end();it1+) cout(*it1)setw(6); coutendl; /刪除尾部元素 myV.pop_back (); for (it1=myV.begin();it1!=myV.end();it1+) cout(*it1)setw(6); coutendl; myV.clear();/清空數組

8、 if(myV.empty() cout Its empty! endl; system(PAUSE); /press any key to continue. return 0;運行截圖：2 練習泛型算法的使用：#include#include/#incluedusing namespace std;typedef list lin;int value=1,6,7,8,9;/定義一個數組value 并賦值 void print(lin &l)int i;lin:iterator lit;/定義一個迭代器 for(lit=l.begin();lit!=l.end();lit+)cout(*li

9、t) ;/依次打印list中的元素 coutv2; int main()lin lin2; lin2.push_front(3); /單獨逐個插入幾個數 lin2.push_front(4); lin2.insert(lin2.begin(),value,value+5);coutlin2內的元素為：;print(lin2);lin2.sort();/對鏈表l1進行從小到大排序 cout排序后的lin2: ;print(lin2);lin2.push_front(10);/在list頭部插入10 cout在list頭部插入10之后的結果：; print(lin2);lin2.remove(6)

10、;cout刪除一個數后的lin1:; print(lin2); system(PAUSE);/press any key to contineu. return 0;/List不允許對隨機數進行操作運行截圖：二實驗名稱 搜索算法的實驗姓 名黃星辰系院專業計算機與信息學院班 級計算機科學與技術122班學 號2012211643實驗日期指導教師徐本柱成 績一、實驗目的和要求1掌握寬度優先搜索算法。2掌握深度優先搜索算法。二、實驗預習內容1寬度優先搜索算法：又稱廣度優搜索。是最簡單的圖的算法的原形。其屬于一種盲搜尋法，目的是系統地展開并檢查圖中的所有節點，以尋找結果。換句話說，它并不考慮結果的可能位

11、址，徹底地搜索整張圖，直到找到結果為止。2深度優先搜索算法：它的目的是要達到被搜索結構的葉結點。在一個HTML文件中，當一個超鏈被選擇后，被連接的HTML文件將執行深度優先搜索，即在搜索其余的超鏈走到不能再深入為止，然后返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經結束。三、實驗項目摘要1.將書上的走迷宮代碼上機運行并檢驗結果，并注意體會搜索的思想。2 .八皇后問題：在一個國際象棋棋盤上放八個皇后，使得任何兩個皇后之間不相互攻擊，求出所有的布棋方法。上機運行并檢驗結果。思考：將此題推廣到N 皇后的情況，檢驗在N 比較大的情況下，比方說N=

12、16 的時候，你的程序能否快速的求出結果，如果不能，思考有什么方法能夠優化算法。3騎士游歷問題：在國際棋盤上使一個騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂點，輸出一條符合上述要求的路徑。4 倒水問題：給定2 個沒有刻度容器，對于任意給定的容積，求出如何只用兩個瓶裝出L 升的水，如果可以，輸出步驟，如果不可以，請輸出No Solution。四、實驗結果與分析（源程序及相關說明）2，八皇后問題：#include /*聲明常量N存儲行和列*/#define N 8#define NUM 8/*聲明全局變量，hNN控制盤格，HNN控制輸出，nN存儲每一步的*縱坐標，count用于計數。*/in

13、t hNN,nN,HNN;int count=0;/*聲明函數void tryit(int,int)嘗試符合條件的方法*/void tryit(int,int);/*聲明函數void outputArray(intN)輸出數組*/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(/其他的布局略n);printf(共有%d種布局.n,92);return(0);/*定義函數void tryit(int,int)嘗試符合條件的

14、方法*/void tryit(int x,int y)int i,j;if(count=0&x=0&y=N-1&hxy=0)/*對與皇后在同一行、列、斜線上的點作出處理*/for(j=0;j=0&x+j=0&y+j=0&x+j=0&y-j=0&x-j=0&y+j=0&x-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(hij0)Hij=1;elseHij=0; count=count+1;/

15、*輸出前幾種情況*/if(count=NUM)printf(-布局%d-n,count); outputArray(H);/*對下一種走法，清楚前一次的影響*/ for(i=0;i=N-1;i+)for(j=0;j7)/*清楚前一次影響*/for(i=0;i=N-1;i+)for(j=0;j=0) tryit(x-1,nx-1+1);else tryit(0,0);/*嘗試下一格*/elsetryit(x,y+1);/*定義函數void outputArray(intN)輸出數組*/void outputArray(int hN)int i,j;for(i=0;i=N-1;i+)for(j=0

16、;j=N-1;j+)printf(%d ,hij);printf(n);運行截圖：3. 騎士游歷問題：在國際棋盤上使一個騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂點，輸出一條符合上述要求的路徑。#include int board88 = 0; int main(void) 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+

17、) for(j = 0; j 8; j+) printf(%2d , boardij); putchar(n); return 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; / 記錄出路的個數int exists8 = 0; int i, j, k, m, l; int tmpi, tmpj; int co

18、unt, 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 7 | tmpj 7) continue; / 如果這個方向可走，記錄下來if(boardtmpitmpj = 0) nextil = tmpi; nextjl = tmpj; / 可走的方向加一

19、個l+; count = l; / 如果可走的方向為0個，返回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 7 | tmpj 7) continue; if(boardtmpitmpj = 0) existsl+; tmp = e

20、xists0; min = 0; / 從可走的方向中尋找最少出路的方向for(l = 1; l count; l+) if(existsl tmp) tmp = existsl; min = l; / 走最少出路的方向i = nextimin; j = nextjmin; boardij = m; return 1; 運行截圖：4.倒水問題：#includestdio.hint main() int ca,cb,cc,x,y; while(scanf(%d%d%d,&ca,&cb,&cc)!=EOF) if(cb=cc) printf(fill Bn); else if(ca=cc) prin

21、tf(fill An); printf(pour A Bn); else x=y=0; if(caca-x) /如果b中的水大于a中的剩余容積，就把a灌滿/ y-=ca-x; x=ca; printf(pour B An); else /如果b中的水小于a中的剩余容積，那么把b中的水全加入a/ x+=y; y=0; printf(pour B An); if(y=cc) /如果b中的水已經和cc相等，那就結束/ break; if(ca=x) /如果a中的水滿了，就把a倒空/ x=0; printf(empty An); else while(1) if(x=0) x=ca; printf(f

22、ill An); if(xcb-y) /如果a中的水大于b中的剩余容積，就把b灌滿/ x-=cb-y; y=cb; printf(pour A Bn); else /如果a中的水小于b中的剩余容積，那么把a中的水全加入b/ y+=x; x=0; printf(pour A Bn); if(y=cc) /如果b中的水已經和cc相等，那就結束/ break; if(y=cb) /如果b中的水滿了，就把b倒空/ y=0; printf(empty Bn); printf(successn); return 0;運行截圖：三實驗名稱 計算幾何算法的實現姓 名黃星辰系院專業計算機與信息學院班 級計算機科

23、學與技術122班學 號2012211643實驗日期指導教師徐本柱成 績一、實驗目的和要求1理解線段的性質、叉積和有向面積。2掌握尋找凸包的算法。3綜合運用計算幾何和搜索中的知識求解有關問題。二、實驗預習內容凸包：是一組點集中的子集，這一子集形成的凸多邊形可以將點集中所有的點都圍住，并且這一凸邊形的面積是最小的。一種尋找凸包的算法：打包法首先，我們找出點集中最下方的點，如果這樣的點不止一個，就選用最左邊的點（如P0）。顯然，這個點（P0）是凸包子集中的一個點。可以設想在P0 處拴了一根皮筋的一端，另一端放在和P0 成水平位置的右側。現在，將皮筋，沿逆時針方向轉動，首先會碰到P1，這樣就找到了另一

24、個凸包子集中的點。以P1 為中心，做和P0 一樣的事，會發現，我們將碰到P3，又一個凸包的點。我們可以一直這樣做下去，直到再一次遇到P0，凸包就被找出來了。具體而言，在第一次找到P0 點之后，以P0 為每個矢量的起點，其它的點為矢量的終點，來比較任意兩個矢量的轉角，就可以對余下的點進行按極角排序三、實驗項目摘要1 將講義第三章第三節中的凸包代碼上機運行并檢驗結果。2完成講義第三章的課后習題，上機運行并檢驗結果。3思考：判線段相交時，如果有個線段的端點在另一條線段上，注意可能與另一條線段上的端點重合，思考這樣的情況。4房間最短路問題：給頂一個內含阻礙墻的房間，求解出一條從起點到終點的最最短路徑。

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

26、p2 - p1 )位于矢量( p4 p3 )的兩側，即( p1 p3） ( p4- p3 ) * ( p2 p3 ) ( p4 p3 ) 0。當( p1 p3 ) ( p4p3 ) = 0 時，說明( p1 p3 ) 和 ( p4 p3 )共線，但是因為已經通過快速排斥試驗，所以 p1 一定在線段 p3p4上；同理，( p4 p3 ) (p2 p3 ) = 0 說明 p2 一定在 p3p4上。所以判斷p1p2跨立Q1Q2的依據是：( p1 p3 ) ( p4 p3 ) * ( p4 p3 ) ( p2p3 ) = 0。同理判斷Q1Q2跨立P1P2的依據是：( p3 - p1 ) ( p2 -

27、p1 ) * ( p2 - p1 ) ( p4 - p1 ) = 0。代碼中函數bool segment_intersect()用于判斷p1、p2構成的線段和p3、p4構成的線段是否相交。可以看出共五種情況兩線段是相交的，反之就輸出“The two are Not intersected!”4.房間最短路問題：#include #include #include innclude using namespace std; typedef pair POINT;/線段 double direction(POINT p,POINT p1,POINT p2) POINT v1,v2; v1.firs

28、t=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.firstp2.first?p1.first:p2.first; double min_y=p1.secondp2.second?p1.second:p2.second;

29、if(p.first=min_x&p.first= 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(d0)return false; if(d=0&on_segment(startPoint,p1,p2)return true; if(d= =0&on_segment(p2,startPoint,p1)retu

30、rn true; return false; void find_convex_hull(vector&point) POINT p0=point0; int k=0; for(int i=0;ipoint.size();i+) if(pointi.secondp0.second| pointi.second=p0.second&pointi.firstp0.first) p0=pointi; k=i; point.erase(point.begin()+k); point.insert(point.begin(),p0); vectorconvex_hull; do convex_hull.

31、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_hull.size()-1); while(1); for(int j=0;jconvex_hull.size();j+) coutconvex_hullj.first convex_hullj.secondendl; int main()

32、vector pv; double x,y; int i; cout請輸入10個點：endl; for(i=1;i=10;i+) coutNo.ixy;pv.push_back(make_pair(x,y); coutendl; find_convex_hull(pv); system(Pause); return 0; 運行截圖：女人如春天的桃花。陽春三月，春暖花開時，婀娜多情的桃花會競相開放，如一片片紅霞，與如紗的垂柳，形成了桃紅柳綠的春日美景。而青春靚麗的美女，正恰如春光明媚中盛開的桃花，繽紛絢爛，激情四射，充滿青春的活力，充滿青春的幻想，充滿青春美妙的情懷。青春歲月， 容光煥發的美女，爽朗的笑聲，輕盈飄逸的秀發，眉飛色舞的眼神