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

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

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

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

4、，輸出每個元素的值，再按降敘排序，輸出每個元素的值。練習用find查找元素。用min和max找出容器中的最小元素個最大元素、并輸出。四、實驗結(jié)果與分析(源程序及相關(guān)說明)1.練習vector和list的使用：#include<iostream>#include<vector>#include<iomanip>#include<ctime>#include<algorithm>usingnamespacestd;vector<int>myV;boolsortup(intv1,intv2)returnv1<v2;intm

5、ain(intargc,char*argv口)srand(time(NULL);隨機產(chǎn)生十個數(shù)for(inti=0;i<10;i+)myV.push_back(rand();sort(myV.begin(),myV.end(),sortup);用sort排序升序vector<int>二iterato門t1;for(it1=myV.begin();it1!=myV.end();it1+)cout<<(*it1)<<setw(6);打印數(shù)組cout<<endl;intmin=myV0;for(it1=myV.begin()+1;it1!=myV

6、.end();it1+)if(*it1)<min)min=(*it1);cout<<"最小元素為"<<min<<endl;intmax=myV0;for(it1=myV.begin();it1!=myV.end();it1+)if(*it1)>max)max=(*it1);cout<<”最大元素為"<<max<<endl;cout<<endl;intvalue=rand();it1=find(myV.begin(),myV.end(),value);if(*it1)=v

7、alue)cout<<"找到了這個隨機數(shù)"<<endl;elsecout<<"沒有找到這個隨機數(shù)"<<endl;myV.insert(myV.end(),value);/數(shù)組中沒有隨機數(shù)，插入尾部cout<<”插入尾部的隨機數(shù)為"<<value<<endl;for(it1=myV.begin();it1!=myV.end();it1+)cout<<(*it1)<<setw(6);cout<<"n"<&

8、lt;endl;/隨機在vector頭部插入一個隨機數(shù)intt=rand();/定義t;將一個隨機數(shù)賦給t,插入到數(shù)組頭部myV.insert(myV.begin(),t);cout<<"插入頭部的隨機數(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!=myV.end();it1+)cout&

9、lt;<(*it1)<<setw(6);cout<<endl;myV.clear();/清空數(shù)組if(myV.empty()cout<<"It'sempty!"<<endl;system("PAUSE");/pressanykeytocontinue.return0;運行截圖：2練習泛型算法的使用：#include<list>#include<iostream>/#inclued<algorithm>usingnamespacestd;typedeflist

10、<int>lin;intvalue=2,4,6,1,8;voidprint(lin&l)inti;lin二iterato門it;/定義一個迭代器for(lit=l.begin();lit!=l.end();lit+)cout<<(*lit)<<""/打印list中的元素cout<<endl;boolsortsp(intv1,intv2)/升序排序算法returnv1>v2;intmain()linlin2;lin2.push_front(3);lin2.push_front(4);lin2.insert(lin2

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

12、pressanykeytocontineureturn0;運行截圖：實驗名稱姓 名實驗日期一、實驗?zāi)康暮鸵? .掌握寬度優(yōu)先搜索算法。2 .掌握深度優(yōu)先搜索算法。搜索算法的實驗"上, 信息工程系院專業(yè) 系指導教師二、實驗預(yù)習內(nèi)容1寬度優(yōu)先搜索算法：又稱廣度優(yōu)搜索。是最簡單的圖的算法的原形。其屬于一種盲搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以尋找結(jié)果。換句話說，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。2深度優(yōu)先搜索算法：它的目的是要達到被搜索結(jié)構(gòu)的葉結(jié)點。在一個HTML文件中，當一個超鏈被選擇后，被連接的HTML文件將執(zhí)行深度優(yōu)先搜索，即在搜索其余的超鏈

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

14、問題：給定2個沒有刻度容器，對于任意給定的容積，求出如何只用兩個瓶裝出L升的水，如果可以，輸出步驟，如果不可以，請輸出NoSolution。四、實驗結(jié)果與分析(源程序及相關(guān)說明)2，八皇后問題：#include<stdio.h>/*聲明常量N存儲行和列*/#defineN8#defineNUM8/*聲明全局變量，hNN控制盤格，HNN控制輸出，nN存儲每一步的*縱坐標，count用于計數(shù)。*/inthNN,nN,HNN;intcount=0;/*聲明函數(shù)voidtryit(int,int)嘗試符合條件的方法*/voidtryit(int,int);/*聲明函數(shù)voidoutputA

15、rray(intN)輸出數(shù)組*/voidoutputArray(intN);main()intx=0,y=0,i,j;/*初始化為零*/for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)tryit(x,y);printf("其他的布局略n");printf("共有%d種布局.n",92);return(0);)/*定義函數(shù)voidtryit(int,int)嘗試符合條件的方法*/voidtryit(intx,inty)inti,j;if(count<=NUM)/*重復(fù)時跳出遞歸*/if(H00=1&&

16、;H14=1&&H27=1&&H35=1&&H42=1&&H56=1&&H61=1&&H73=1)&&count!=1)()elseif(x>=0&&x<=N-1&&y>=0&&y<=N-1&&hxy=0)/*對與皇后在同一行、歹h斜線上的點作出處理*/for(j=0;j<=7;j+)if(hxj=0)hxj=x+1;if(hjy=0)hjy=x+1;if(x+j>=0&&am

17、p;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;if(x-j>=0&&x-j<=N-1&&y+j>=0&&y+j<=N-1&&hx-jy+j=0)if(x-j>=0&

18、&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)(/*轉(zhuǎn)換成輸出的格式*/for(i=0;i<=N-1;i+)(for(j=0;j<=N-1;j+)(if(hij<0)Hij=1;elseHij=0;)count=count+1;/*輸出前幾種情況*/if(count<=NUM)(printf("布局dn",count);outputA

19、rray(H);)/*對下一種走法，清楚前一次的影響*/for(i=0;i<=N-1;i+)(for(j=0;j<=N-1;j+)(if(hij=x|hij=-x|hij=-x-1)hx-jy+j=x+1;/*遞歸，嘗試另一種方法*/tryit(x-1,nx-1+1);/*未走完一次，繼續(xù)下一行*/elsenx=y;tryit(x+1,0);else/*此路不通時，返回上一行，嘗試下一種方法*/if(y>7)/*清楚前一次影響*/for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)if(hij=x|hij=-x)hij=0;/*分情況遞歸*/i

20、f(x-1>=0)tryit(x-1,nx-1+1);elsetryit(0,0);/*嘗試下一格*/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");運行截圖：4.倒水問題：#include"stdio.h"intmain()intca,cb,cc,x,y;while(scanf(

21、"%d%d%d",&ca,&cb,&cc)!=EOF)if(cb=cc)printf("fillBn");elseif(ca=cc)printf("fillAn");printf("pourABn");elsex=y=0;if(ca<cc)while(1)if(y=0)y=cb;printf("fillBn");if(y>ca-x)/如果b中的水大于a中的剩余容積，就把a灌滿y-=ca-x;x=ca;printf("pourBAn");el

22、se/果b中的水小于a中的剩余容積，那么把b中的水全加入a/x+=y;y=0;printf("pourBAn");if(y=cc)/果b中的水已經(jīng)和cc相等，那就結(jié)束/break;if(ca=x)/果a中的水滿了，就把a倒空/x=0;printf("emptyAn");elsewhile(1)if(x=0)x=ca;printf("fillAn");if(x>cb-y)/果a中的水大于b中的剩余容積，就把b灌滿/x-=cb-y;y=cb;printf("pourABn");else/果a中的水小于b中的剩余容

23、積，那么把a中的水全加入b/y+=x;x=0;printf("pourABn");if(y=cc)/如果b中的水已經(jīng)和cc相等，那就結(jié)束break;if(y=cb)/果b中的水滿了，就把b倒空/y=0;printf("emptyB'n");printf("successn");return0;運行截圖：實驗名稱計算幾何算法的實現(xiàn)姓名系院專業(yè)信息工程系班級物聯(lián)網(wǎng)一班學號實驗日期指導教師成績一、實驗?zāi)康暮鸵? .理解線段的性質(zhì)、叉積和啟向回積。2 .掌握尋找凸包的算法。3 .綜合運用計算幾何和搜索中的知識求解有關(guān)問題。二、實驗預(yù)

24、習內(nèi)容凸包：是一組點集中的子集，這一子集形成的凸多邊形可以將點集中所有的點都圍住，并且這一凸邊形的面積是最小的。一種尋找凸包的算法：打包法首先，我們找出點集中最下方的點，如果這樣的點不止一個，就選用最左邊的點（如P0）。顯然，這個點（P0）是凸包子集中的一個點。可以設(shè)想在P0處拴了一根皮筋的一端，另一端放在和P0成水平位置的右側(cè)。現(xiàn)在，將皮筋，沿逆時針方向轉(zhuǎn)動，首先會碰到P1,這樣就找到了另一個凸包子集中的點。以P1為中心，做和P0一樣的事，會發(fā)現(xiàn)，我們將碰到P3,又一個凸包的點。我們可以一直這樣做下去，直到再L次遇到P0,凸包就被找出來了。具體而言，在第一次找到P0點之后，以P0為每個矢量的

25、起點，其它的點為矢量的終點，來比較任意兩個矢量的轉(zhuǎn)角，就可以對余下的點進行按極角排序三、實驗項目摘要1將講義第三章第三節(jié)中的凸包代碼上機運行并檢驗結(jié)果。2完成講義第三章的課后習題，上機運行并檢驗結(jié)果。3思考：判線段相交時，如果有個線段的端點在另一條線段上，注意可能與另一條線段上的端點重合，思考這樣的情況。4房間最短路問題：給頂一個內(nèi)含阻礙墻的房間，求解出一條從起點到終點的最最短路徑。房間的邊界固定在x=0,x=10,y=0和y=10。起點和重點固定在(0,5)和(10,5)。房間里還有0至M8個墻，每個墻有兩個門。輸入給定的墻的個數(shù)，每個墻的x位置和兩個門的y坐標區(qū)間，輸出最短路的長度四、實驗

26、結(jié)果與分析(源程序及相關(guān)說明)3 .思考：用跨立方法，跨立的含義是：如果一條線段的一個端點在一條直線的一邊，另一個端點在這條直線的另一端，我們就說這條線段跨立在這條直線上。線段相交滿足且只需滿足如下兩個條件就可以了：1兩條線段相互跨立；2條線段的一個端點在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對方。若p1p2跨立p3P4,則矢量(p1-p3)和(p2-p1)位于矢量(p4p3)的兩側(cè)，即(p1-p3)X(p4-p3)*(p2-p3)X(p4-p3)<0。上式可改寫成(p1-p3)X(p4-p3)*(p4-p3)X(p2-p3)>0。當(p1-p3)X(p4-p3)=0時

27、，說明(p1-p3)和(p4-p3)共線，但是因為已經(jīng)通過快速排斥試驗，所以p1一定在線段p3P4上；同理，(p4-p3)X(p2-p3)=0說明p2一定在p3P4上。所以判斷p1p2跨立Q1Q2的依據(jù)是：(p1-p3)X(p4-p3)*(p4-p3)X(p2-p3)>=0。同理判斷Q1Q2跨立P1P2的依據(jù)是：(p3-p1)X(p2-p1)*(p2-p1)X(p4-p1)>=0。代碼中函數(shù)boolsegment_intersect(用于判斷p1、p2構(gòu)成的線段和p3、p4構(gòu)成的線段是否相交?？梢钥闯龉参宸N情況兩覆段是相交而，應(yīng)之就輸出“ThetwoareNotintersecte

28、d!4 .房間最短路問題：#include<iostream>#include<utility>#include<vector>innclude<algorithm>usingnamespacestd;typedefpair<double,double>POINT;儂段doubledirection(POINTp,POINTp1,POINTp2)POINTv1,v2;v1.first=p2.first-p1.first;v1.second=p2.second-p1.first;v2.first=p1.first-p.first;v2.

29、second=p1.second-p.second;returnv1.first*v2.second-v1.second*v2.second;boolon_segment(POINTp,POINTp1,POINTp2)doublemin_x=p1.first<p2.first?p1.first:p2.first;max_x=p1.first>p2.first?p1.first:p2.first;doublemin_y=p1.second<p2.second?p1.second:p2.second;doublemax_y=p1.second>p2.second?p1.se

30、cond:p2.second;if(p.first>=min_x&&p.first<max_x&&p.second>=min_y&&p.second<=max_y)returntrue;elsereturnfalse;POINTstartPoint;boolsortByPolorAngle(constPOINT&p1,constPOINT&p2)doubled=direction(startPoint,p1,p2);if(d<0)returntrue;if(d>0)returnfalse;if(d=0&&on_segment(startPoint,p1,p2)returntrue;if