1、程序設(shè)計(jì)藝術(shù)與方法課程實(shí)驗(yàn)報(bào)告一實(shí)驗(yàn)名稱 STL的熟悉與使用姓 名系院專業(yè)信息工程系班 級(jí)物聯(lián)網(wǎng)一班學(xué) 號(hào)實(shí)驗(yàn)日期指導(dǎo)教師成 績(jī)一、實(shí)驗(yàn)?zāi)康暮鸵?（1）掌握C+中STL的容器類使用。（2）掌握C+中STL的算法類的使用。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容 Vector,list可當(dāng)作列表使用的數(shù)據(jù)結(jié)構(gòu)，它們都是動(dòng)態(tài)增長(zhǎng)的。1.vector表示一段連續(xù)的內(nèi)存區(qū)域每個(gè)元素被順序儲(chǔ)存在這段內(nèi)存中。對(duì)vector的隨即訪問(wèn)效率很高。但是在任意位置而不是在vector末尾插入元素則效率很低，因?yàn)樗枰汛迦朐氐挠疫叺拿總€(gè)元素都拷貝一遍。類似的刪除任一個(gè)而不是vector的最后一個(gè)元素效率低。2list表示非連續(xù)的內(nèi)

2、存區(qū)域并通過(guò)一對(duì)指向首尾元素的指針雙向進(jìn)行遍歷在list的任意位置插入和刪除元素的效率都很高，指針必須被賦值但不需要用拷貝元素來(lái)實(shí)現(xiàn)移動(dòng)，另一方面它對(duì)隨機(jī)訪問(wèn)的支持并不好訪問(wèn)一個(gè)元素需要遍歷中間的元素，另外每個(gè)元素還有倆不能給個(gè)指針的額外空間開銷。3泛型算法讓編寫一般化并可重復(fù)使用的算法，其效率與指針對(duì)某特定數(shù)據(jù)類型而設(shè)計(jì)的算法相同。泛型即是指具有在多種數(shù)據(jù)類型上皆可操作的含義，與模板有些相似。STL巨大而且可以擴(kuò)充，它包含很多計(jì)算機(jī)基本算法和數(shù)據(jù)結(jié)構(gòu)，而且將算法與數(shù)據(jù)結(jié)構(gòu)完全分離，其中算法是泛型的，不與任何特定數(shù)據(jù)結(jié)構(gòu)或?qū)ο箢愋拖翟谝黄?。三、?shí)驗(yàn)項(xiàng)目摘要1. 練習(xí)vector 和list 的

3、使用。定義一個(gè)空的vector，元素類型為int，生成10 個(gè)隨機(jī)數(shù)插入到vector 中，用迭代器遍歷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

4、，插入10 個(gè)隨機(jī)數(shù)，使用sort 按升序排序，輸出每個(gè)元素的值，再按降敘排序，輸出每個(gè)元素的值。練習(xí)用find 查找元素。用min 和max 找出容器中的最小元素個(gè)最大元素，并輸出。四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說(shuō)明）1. 練習(xí)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) srand(time(NULL); /隨機(jī)產(chǎn)

5、生十個(gè)數(shù) 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); /打印數(shù)組 coutendl; int min=myV0; for (it1=myV.begin()+1;it1!=myV.end();it1+) if(*it1)min)min=(*it1); cout最小元素為 minmax)max=(*it

6、1); cout最大元素為 maxendl; coutendl; int value=rand(); it1=find(myV.begin(),myV.end(),value); if(*it1)=value) cout找到了這個(gè)隨機(jī)數(shù)endl ; else cout沒(méi)有找到這個(gè)隨機(jī)數(shù)endl; myV.insert(myV.end(),value); /數(shù)組中沒(méi)有隨機(jī)數(shù),插入尾部 cout插入尾部的隨機(jī)數(shù)為valueendl; for (it1=myV.begin();it1!=myV.end();it1+) cout(*it1)setw(6); coutnendl; /隨機(jī)在vector頭

7、部插入一個(gè)隨機(jī)數(shù) int t=rand();/定義t;將一個(gè)隨機(jī)數(shù)賦給t，插入到數(shù)組頭部 myV.insert(myV.begin(),t); cout插入頭部的隨機(jī)數(shù)為 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();/清空數(shù)組 if(myV.empty() cout It

8、s empty! endl; system(PAUSE); /press any key to continue. return 0;運(yùn)行截圖：2 練習(xí)泛型算法的使用：#include#include/#incluedusing namespace std;typedef list lin;int value=2,4,6,1,8; void print(lin &l)int i;lin:iterator lit;/定義一個(gè)迭代器 for(lit=l.begin();lit!=l.end();lit+)cout(*lit) ;/打印list中的元素 coutv2; int main()lin l

9、in2; lin2.push_front(3); lin2.push_front(4); lin2.insert(lin2.begin(),value,value+5);coutlin2內(nèi)的元素為：;print(lin2);lin2.sort();cout排序后的lin2: ;print(lin2);lin2.push_front(10);/在list頭部插入10 cout在list頭部插入10之后的結(jié)果：; print(lin2);lin2.remove(6);cout刪除一個(gè)數(shù)后的lin1:; print(lin2); system(PAUSE);/press any key to con

10、tineu. return 0;運(yùn)行截圖：二實(shí)驗(yàn)名稱 搜索算法的實(shí)驗(yàn)姓 名系院專業(yè)信息工程系班 級(jí)物聯(lián)網(wǎng)一班學(xué) 號(hào)實(shí)驗(yàn)日期指導(dǎo)教師成 績(jī)一、實(shí)驗(yàn)?zāi)康暮鸵?掌握寬度優(yōu)先搜索算法。2掌握深度優(yōu)先搜索算法。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1寬度優(yōu)先搜索算法：又稱廣度優(yōu)搜索。是最簡(jiǎn)單的圖的算法的原形。其屬于一種盲搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以尋找結(jié)果。換句話說(shuō)，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。2深度優(yōu)先搜索算法：它的目的是要達(dá)到被搜索結(jié)構(gòu)的葉結(jié)點(diǎn)。在一個(gè)HTML文件中，當(dāng)一個(gè)超鏈被選擇后，被連接的HTML文件將執(zhí)行深度優(yōu)先搜索，即在搜索其余的超鏈走到不能再深入為止，然

11、后返回到某一個(gè)HTML文件，再繼續(xù)選擇該HTML文件中的其他超鏈。當(dāng)不再有其他超鏈可選擇時(shí)，說(shuō)明搜索已經(jīng)結(jié)束。三、實(shí)驗(yàn)項(xiàng)目摘要1.將書上的走迷宮代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果，并注意體會(huì)搜索的思想。2 .八皇后問(wèn)題：在一個(gè)國(guó)際象棋棋盤上放八個(gè)皇后，使得任何兩個(gè)皇后之間不相互攻擊，求出所有的布棋方法。上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。思考：將此題推廣到N 皇后的情況，檢驗(yàn)在N 比較大的情況下，比方說(shuō)N=16 的時(shí)候，你的程序能否快速的求出結(jié)果，如果不能，思考有什么方法能夠優(yōu)化算法。3騎士游歷問(wèn)題：在國(guó)際棋盤上使一個(gè)騎士遍歷所有的格子一遍且僅一遍，對(duì)于任意給定的頂點(diǎn)，輸出一條符合上述要求的路徑。4 倒水問(wèn)題：給定2 個(gè)

12、沒(méi)有刻度容器，對(duì)于任意給定的容積，求出如何只用兩個(gè)瓶裝出L 升的水，如果可以，輸出步驟，如果不可以，請(qǐng)輸出No Solution。四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說(shuō)明）2，八皇后問(wèn)題：#include /*聲明常量N存儲(chǔ)行和列*/#define N 8#define NUM 8/*聲明全局變量，hNN控制盤格，HNN控制輸出，nN存儲(chǔ)每一步的*縱坐標(biāo)，count用于計(jì)數(shù)。*/int hNN,nN,HNN;int count=0;/*聲明函數(shù)void tryit(int,int)嘗試符合條件的方法*/void tryit(int,int);/*聲明函數(shù)void outputArray(intN)

13、輸出數(shù)組*/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);/*定義函數(shù)void tryit(int,int)嘗試符合條件的方法*/void tryit(int x,int y)int i,j;if(count=0&x=0&y=N-1&hxy=0)/*對(duì)與皇后在同一行、列、斜線上的點(diǎn)作出處理*/for(j=0;j=0&x+j=0&y+j=0

14、&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;/*對(duì)皇后處的點(diǎn)作出標(biāo)志*/hxy=-x-1;/*完成一種走法作出處理*/if(x=7)/*轉(zhuǎn)換成輸出的格式*/for(i=0;i=N-1;i+)for(j=0;j=N-1;j+)if(hij0)Hij=1;elseHij=0; count=count+1;/*輸出前幾種情況*/if(count=NUM)printf(-布局%d-n,count); outputArray(H);/*對(duì)下一種走法，清楚前一次的影響*/ for(i=0;i=N-1;i+)for(j=0;j7)

15、/*清楚前一次影響*/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);/*定義函數(shù)void outputArray(intN)輸出數(shù)組*/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);運(yùn)行截圖：4.倒水問(wèn)題：#includestdio.hint main() int ca,cb,cc,x,y; while(scanf(%d%d%

16、d,&ca,&cb,&cc)!=EOF) if(cb=cc) printf(fill Bn); else if(ca=cc) printf(fill An); printf(pour A Bn); else x=y=0; if(caca-x) /如果b中的水大于a中的剩余容積，就把a(bǔ)灌滿/ 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中的水已經(jīng)和cc相等，那就結(jié)束/ break; if(ca=x) /如果a中的水滿了

17、，就把a(bǔ)倒空/ x=0; printf(empty An); else while(1) if(x=0) x=ca; printf(fill An); if(xcb-y) /如果a中的水大于b中的剩余容積，就把b灌滿/ x-=cb-y; y=cb; printf(pour A Bn); else /如果a中的水小于b中的剩余容積，那么把a(bǔ)中的水全加入b/ y+=x; x=0; printf(pour A Bn); if(y=cc) /如果b中的水已經(jīng)和cc相等，那就結(jié)束/ break; if(y=cb) /如果b中的水滿了，就把b倒空/ y=0; printf(empty Bn); print

18、f(successn); return 0;運(yùn)行截圖：三實(shí)驗(yàn)名稱 計(jì)算幾何算法的實(shí)現(xiàn)姓 名系院專業(yè)信息工程系班 級(jí)物聯(lián)網(wǎng)一班學(xué) 號(hào)實(shí)驗(yàn)日期指導(dǎo)教師成 績(jī)一、實(shí)驗(yàn)?zāi)康暮鸵?理解線段的性質(zhì)、叉積和有向面積。2掌握尋找凸包的算法。3綜合運(yùn)用計(jì)算幾何和搜索中的知識(shí)求解有關(guān)問(wèn)題。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容凸包：是一組點(diǎn)集中的子集，這一子集形成的凸多邊形可以將點(diǎn)集中所有的點(diǎn)都圍住，并且這一凸邊形的面積是最小的。一種尋找凸包的算法：打包法首先，我們找出點(diǎn)集中最下方的點(diǎn)，如果這樣的點(diǎn)不止一個(gè)，就選用最左邊的點(diǎn)（如P0）。顯然，這個(gè)點(diǎn)（P0）是凸包子集中的一個(gè)點(diǎn)?？梢栽O(shè)想在P0 處拴了一根皮筋的一端，另一端放在和P0

19、成水平位置的右側(cè)?，F(xiàn)在，將皮筋，沿逆時(shí)針?lè)较蜣D(zhuǎn)動(dòng)，首先會(huì)碰到P1，這樣就找到了另一個(gè)凸包子集中的點(diǎn)。以P1 為中心，做和P0 一樣的事，會(huì)發(fā)現(xiàn)，我們將碰到P3，又一個(gè)凸包的點(diǎn)。我們可以一直這樣做下去，直到再一次遇到P0，凸包就被找出來(lái)了。具體而言，在第一次找到P0 點(diǎn)之后，以P0 為每個(gè)矢量的起點(diǎn)，其它的點(diǎn)為矢量的終點(diǎn)，來(lái)比較任意兩個(gè)矢量的轉(zhuǎn)角，就可以對(duì)余下的點(diǎn)進(jìn)行按極角排序三、實(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)重合，思考這樣的情況

20、。4房間最短路問(wèn)題：給頂一個(gè)內(nèi)含阻礙墻的房間，求解出一條從起點(diǎn)到終點(diǎn)的最最短路徑。房間的邊界固定在x=0,x=10,y=0 和y=10。起點(diǎn)和重點(diǎn)固定在(0,5)和(10,5)。房間里還有0 到18 個(gè)墻，每個(gè)墻有兩個(gè)門。輸入給定的墻的個(gè)數(shù)，每個(gè)墻的x 位置和兩個(gè)門的y 坐標(biāo)區(qū)間，輸出最短路的長(zhǎng)度四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說(shuō)明）3.思考：用跨立方法，跨立的含義是：如果一條線段的一個(gè)端點(diǎn)在一條直線的一邊，另一個(gè)端點(diǎn)在這條直線的另一端，我們就說(shuō)這條線段跨立在這條直線上。線段相交滿足且只需滿足如下兩個(gè)條件就可以了：1 兩條線段相互跨立；2 一條線段的一個(gè)端點(diǎn)在另一條線段上。如果兩線段相交，則兩

21、線段必然相互跨立對(duì)方。若p1p2跨立p3p4 ，則矢量 ( p1 p3 ) 和( p2 - p1 )位于矢量( p4 p3 )的兩側(cè)，即( p1 p3） ( p4- p3 ) * ( p2 p3 ) ( p4 p3 ) 0。當(dāng)( p1 p3 ) ( p4p3 ) = 0 時(shí)，說(shuō)明( p1 p3 ) 和 ( p4 p3 )共線，但是因?yàn)橐呀?jīng)通過(guò)快速排斥試驗(yàn)，所以 p1 一定在線段 p3p4上；同理，( p4 p3 ) (p2 p3 ) = 0 說(shuō)明 p2 一定在 p3p4上。所以判斷p1p2跨立Q1Q2的依據(jù)是：( p1 p3 ) ( p4 p3 ) * ( p4 p3 ) ( p2p3 ) =

22、 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.房間最短路問(wèn)題：#include #include #include innclude using namespace std; typedef pair POINT;/線段 double direction(POINT

23、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.firstp2.first?p1.first:p2.first; double min_y

24、=p1.secondp2.second?p1.second:p2.second; 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