程序設(shè)計藝術(shù)與方法課程實驗報告

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

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

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

4、值，再按降敘排序，輸出每個元素的值。練習(xí)用find查找元素。用min和max找出容器中的最小元素個最大元素，并輸出。四、實驗結(jié)果與分析（源程序及相關(guān)說明）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)行截圖：實驗名稱

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

6、其他超鏈可選擇時，說明搜索已經(jīng)結(jié)束。三、實驗項目摘要1 .將書上的走迷宮代碼上機(jī)運(yùn)行并檢驗結(jié)果，并注意體會搜索的思想。2 .八皇后問題：在一個國際象棋棋盤上放八個皇后，使得任何兩個皇后之間不相互攻擊，求出所有的布棋方法。上機(jī)運(yùn)行并檢驗結(jié)果。思考：將此題推廣到N皇后的情況，檢驗在N比較大的情況下，比方說N=16的時候，你的程序能否快速的求出結(jié)果，如果不能，思考有什么方法能夠優(yōu)化算法。3騎士游歷問題：在國際棋盤上使一個騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂點(diǎn)，輸出一條符合上述要求的路徑。4 倒水問題：給定2個沒有刻度容器，對于任意給定的容積，求出如何只用兩個瓶裝出L升的水，如果可以，輸出

7、步驟，如果不可以，請輸出NoSolution。四、實驗結(jié)果與分析(源程序及相關(guān)說明)2，八皇后問題：#include/*聲明常量N存儲行和列*/# defineN8# defineNUM8/*聲明全局變量，hNN控制盤格，HNN控制輸出，nN存儲每一步的# 縱坐標(biāo)，count用于計數(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)/*對與皇后在同一行、列、斜線上的點(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;)/*對皇后處的點(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);)/*對下一種走法，清楚前一次的影響*/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.倒水問題：#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)考：用跨立方法，跨立的含義是：如果一條線段的一個端點(diǎn)在一條直線的一邊，另一個端點(diǎn)在這條直線的另一端，我們就說這條線段跨立在這條直線上。線段相交滿足且只需滿足如下兩個條件就可以了：1兩條線段相互跨立；2條線段的一個端點(diǎn)在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對方。若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時，說明(pl-p3)和(p4-p3)共線，但是因為已經(jīng)通過快速排斥試驗，所以pl一定在線段p3P4上；同理

12、，(p4-p3)X(p2-p3)=0說明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.房間最短路問題：#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