程序設(shè)計(jì)藝術(shù)與方法課程實(shí)驗(yàn)報(bào)告

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)的。表示一段連續(xù)的內(nèi)存區(qū)域每個(gè)元素被順序儲(chǔ)存在這段內(nèi)存中。對(duì)vector的隨即訪問(wèn)效率很高。但是在任意位置而不是在vector末尾插入元素則效率很低，因?yàn)樗枰汛迦朐氐挠疫叺拿總€(gè)元素都拷貝一遍。類似的刪除任一個(gè)而不是vector的最后-個(gè)元素效率低。2list表示非連續(xù)的內(nèi)存區(qū)域并通過(guò)一對(duì)指向首尾元素

2、的指針雙向進(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的使用。定義一個(gè)空的vector,元

3、素類型為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í)泛型算法的使用。te義一個(gè)vector,兀素類型為int,插入10個(gè)隨機(jī)數(shù)，使用sort按升殍排序，輸出每個(gè)元素的

4、值，再按降敘排序，輸出每個(gè)元素的值。練習(xí)用find查找元素。用min和max找出容器中的最小元素個(gè)最大元素，并輸出。四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說(shuō)明）1.練習(xí)vector和list的使用：#include#include#include#include#includeusingnamespacestd;vectormyV;boolsortup(intv1,intv2)returnv1v2;intmain(intargc,char*argv口)srand(time(NULL);return0;運(yùn)行截圖：2練習(xí)泛型算法的使用：#include#include.return0;運(yùn)行截圖：實(shí)驗(yàn)名稱

5、搜索算法的實(shí)驗(yàn)系院專業(yè)信息工程物聯(lián)網(wǎng)一級(jí)班實(shí)驗(yàn)日期指導(dǎo)教師一、實(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)先搜索，即在搜索其余的超鏈走到不能再深入為止，然后返回到某一個(gè)HTML文件，再繼續(xù)選擇該HTML文件中的其他超鏈。當(dāng)不再有

6、其他超鏈可選擇時(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è)沒有刻度容器，對(duì)于任意給定的容積，求出如何只用兩個(gè)瓶裝出L升的水，如果可以，輸出

7、步驟，如果不可以，請(qǐng)輸出NoSolution。四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說(shuō)明)2，八皇后問(wèn)題：#include/*聲明常量N存儲(chǔ)行和列*/# defineN8# defineNUM8/*聲明全局變量，hNN控制盤格，HNN控制輸出，nN存儲(chǔ)每一步的# 縱坐標(biāo)，count用于計(jì)數(shù)。*/inthNN,nN,HNN;intcount=0;/*聲明函數(shù)voidtryit(int,int)嘗試符合條件的方法*/voidtryit(int,int);/*聲明函數(shù)voidoutputArray(intN)輸出數(shù)組*/voidoutputArray(intN);main()intx=0,y=0,i,j;

8、/*初始化為零*/for(i=0;i=N-1;i+)for(j=0;j=N-1;j+)hij=0;tryit(x,y);printf(n,92);return(0);/*定義函數(shù)voidtryit(int,int)嘗試符合條件的方法*/voidtryit(intx,inty)inti,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&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=-

9、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(布局dn,count);outputArray(H);)/*對(duì)下一種走法，清楚前一次的影響*/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);elsetryit(0,0);/*嘗試

10、下一格*/elsetryit(x,y+1);/*定義函數(shù)voidoutputArray(intN)輸出數(shù)組*/voidoutputArray(inthN)inti,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)題：#includeintmain()intca,cb,cc,x,y;while(scanf(%d%d%d,&ca,&cb,&cc)!=EOF)if(cb=cc)printf(fillBn);elseif(ca=cc)printf(fillAn);printf(pourABn);elsex=y

11、=0;if(caca-x)考：用跨立方法，跨立的含義是：如果一條線段的一個(gè)端點(diǎn)在一條直線的一邊，另一個(gè)端點(diǎn)在這條直線的另一端，我們就說(shuō)這條線段跨立在這條直線上。線段相交滿足且只需滿足如下兩個(gè)條件就可以了：1兩條線段相互跨立；2條線段的一個(gè)端點(diǎn)在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對(duì)方。若p1p2跨立p3P4,則矢量(pl-p3)和(p2-pl)位于矢量(p4p3)的兩側(cè)，即(pl-p3)X(p4-p3)*(p2-p3)義(p4-p3)0。當(dāng)(pl-p3)X(p4-p3)=0時(shí)，說(shuō)明(pl-p3)和(p4-p3)共線，但是因?yàn)橐呀?jīng)通過(guò)快速排斥試驗(yàn)，所以pl一定在線段p3P4上；同理

12、，(p4-p3)X(p2-p3)=0說(shuō)明p2一定在p3P4上。所以判斷p1p2跨立Q1Q2的依據(jù)是：(pl-p3)X(p4-p3)*(p4-p3)X(p2-p3)=0。同理判斷Q1Q2跨立P1P2的依據(jù)是：(p3-pl)X(p2-pl)*(p2-pl)X(p4-pl)=0O代碼中函數(shù)boolsegment_intersect(用于判斷pl、p2構(gòu)成的線段和p3、p4構(gòu)成的線段是否相交?？梢钥闯龉参宸N情況兩經(jīng)段是相交而，友之就輸出“ThetwoareNotintersected!4.房間最短路問(wèn)題：#include#include#includeinncludeusingnamespacestd;typedefpairPOINT;econd|pointi.second=&pointi.firstp0=pointi;k=i;()+k)；(),P0)；vectorconvex_hull;do(point0);startPoint=point0;()；sort(),(),sortByPolorAngle);if(point0=convex_hull0)break;(convex_hull()-1);while(1);for(intj