《程序設計藝術與方法》課程實驗報告

程序設計藝術與方法》課程實驗報告實驗名稱STL得熟悉與使用姓名系院專業(yè)信息工程系班級物聯(lián)網(wǎng)一班學號實驗日期指導教師成績一、實驗目得與要求1.(1)掌握C++中STL得容器類使用。(2)掌握C++中STL得算法類得使用。二、實驗預習內(nèi)容Vector,list可當作列表使用得數(shù)據(jù)結構，它們都就是動態(tài)增長得。1、vector表示一段連續(xù)得內(nèi)存區(qū)域每個元素被順序儲存在這段內(nèi)存中。對vector得隨即訪問效率很高。但就是在任意位置而不就是在vector末尾插入兀素則效率很低，因為它需要把待插入兀素得右邊得每個兀素都拷貝一遍。類似得刪除任一個而不就是vector得最后一個兀素效率低。2list表示非連續(xù)得內(nèi)存區(qū)域并通過一對指向首尾元素得指針雙向進行遍歷在list得任意位置插入與刪除兀素得效率都很高，指針必須被賦值但不需要用拷貝兀素來實現(xiàn)移動，另一方面它對隨機訪問得支持并不好訪問一個兀素需要遍歷中間得兀素，另外每個兀素還有倆不能給個指針得額外空間開銷。3泛型算法讓編寫一般化并可重復使用得算法，其效率與指針對某特定數(shù)據(jù)類型而設計得算法相冋。泛型即就是指具有在多種數(shù)據(jù)類型上皆可操作得含義，與模板有些相似。STL巨大而且可以擴充，它包含很多計算機基本算法與數(shù)據(jù)結構，而且將算法與數(shù)據(jù)結構完全分離，其中算法就是泛型得，不與任何特定數(shù)據(jù)結構或?qū)ο箢愋拖翟谝黄?。三、實驗項目摘?、練習vector與1ist得使用。定義一個空得vector,元素類型為int，生成10個隨機數(shù)插入到vector中,用迭代器遍歷vector并輸出其中得元素值。在vector頭部插入一個隨機數(shù)，用迭代器遍歷vector并輸出其中得元素值。用泛型算法find查找某個隨機數(shù)，如果找到便輸出，否則將此數(shù)插入vector尾部。用泛型算法sort將vector排序,用迭代器遍歷vector并輸出其中得元素值。刪除vector尾部得元素,用迭代器遍歷vector并輸出其中得元素值。將vector清空。定義一個list,并重復上述實驗，并注意觀察結果2練習泛型算法得使用。定義一個vector,兀素類型為int,插入10個隨機數(shù)，使用sort按升序排序，輸出每個元素得值，再按降敘排序，輸出每個元素得值。練習用find查找元素。用min與max找出容器中得最小元素個最大元素，并輸出。四、實驗結果與分析(源程序及相關說明)1、練習vector與1ist得使用：#inc1ude<iostream>#includevvector>#includeviomanip>#inc1ude<ctime>#inc1udevalgorithm>usingnamespacestd;vector<int>myV;boolsortup(intv1,intv2){returnv1vv2;}intmain(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>::iteratorit1;for(it1=myV、begin;it1!=myV、end;it1++){coutvv(*it1)vvsetw(6);〃打印數(shù)組}coutvvendl;intmin=myV[0];for(itl=myV、begin+l;itl!=myV、end;itl++)if((*itl)vmin)min=(*itl);coutvv"最小元素為"vvminvvendl;intmax=myV[0];for(itl=myV、begin;itl!=myV、end;itl++)if((*itl)>max)max=(*itl);coutvv"最大元素為"vvmaxvvendl;coutvvendl;intvalue=rand;itl=find(myV、begin,myV、end,value);if((*itl)==value)coutvv"找到了這個隨機數(shù)"vvendl;elsecoutvv"沒有找到這個隨機數(shù)"vvendl;myV、insert(myV、end,value);〃數(shù)組中沒有隨機數(shù)，插入尾部coutvv"插入尾部得隨機數(shù)為"vvvaluevvendl;for(itl=myV、begin;itl!=myV、end;itl++){coutvv(*itl)vvsetw(6);}coutvv"\n"vvendl;〃隨機在vector頭部插入一個隨機數(shù)intt=rand;〃定義t;將一個隨機數(shù)賦給t,插入到數(shù)組?頭部myV、insert(myV、begin,t);coutvv"插入頭部得隨機數(shù)為"vvtvvendl;for(itl=myV、begin;itl!=myV、end;itl++){coutvv(*itl)vvsetw(6);}coutvvendl;〃刪除尾部元素myV、popback;for(itl=myV、begin;itl!=myV、end;itl++){coutvv(*it1)vvsetw(6);}coutvvendl;myV、clear;//清空數(shù)組if(myV、empty){cout<<"It'sempty!"<<endl;}system("PAUSE");//pressanykeytocontinue、、、return0;}運行截圖：2練習泛型算法得使用:#includevlist>#includeviostream>〃#incluedvalgorithm>usingnamespacestd;typedeflistvint>lin;intvalue[]={2,4,6,l,8};voidprint(lin&1){inti;lin::iteratorlit;//定義一個迭代器for(lit=l、begin;lit!=l、end;lit++)coutvv(*lit)vv"";//打印list中得元素coutvvendl;}boolsortsp(intv1,intv2)〃升序排序算法{returnv1>v2;}intmain{linlin2;lin2、push_front(3);lin2、push_front(4);lin2、insert(lin2、begin,value,value+5);coutvv"lin2內(nèi)得元素為:"；print(lin2);lin2、sort;coutvv"排序后得lin2:";print(lin2);lin2、push_front(10);〃在list頭部插入10coutvv"在list頭部插入10之后得結果:"；print(lin2);lin2、remove(6);coutvv"刪除一個數(shù)后得lin1:";print(lin2);system("PAUSE");//pressanykeytocontineu、、、

實驗名稱搜索算法得實驗實驗名稱姓名系院專業(yè)系班物聯(lián)網(wǎng)一級班學號實驗日期指導教師成績一、實驗目得與要求1.掌握寬度優(yōu)先搜索算法2.掌握深度優(yōu)先搜索算法。二、實驗預習內(nèi)容1寬度優(yōu)先搜索算法:又稱廣度優(yōu)搜索。就是最簡單得圖得算法得原形。其屬于一種盲搜尋法,目得就是系統(tǒng)地展開并檢查圖中得所有節(jié)點,以尋找結果。換句話說,它并不考慮結果得可能位址,徹底地搜索整張圖,直到找到結果為止。2深度優(yōu)先搜索算法:它得目得就是要達到被搜索結構得葉結點。在一個HTML文件中，當一個超鏈被選擇后，被連接得HTML文件將執(zhí)行深度優(yōu)先搜索，即在搜索其余得超鏈走到不能再深入為止，然后返回到某一個HTML文件,再繼續(xù)選擇該HTML文件中得其她超鏈。當不再有其她超鏈可選擇時，說明搜索已經(jīng)結束。三、實驗項目摘要1、將書上得走迷宮代碼上機運行并檢驗結果,并注意體會搜索得思想。2、八皇后問題:在一個國際象棋棋盤上放八個皇后,使得任何兩個皇后之間不相互攻擊,求出所有得布棋方法。上機運行并檢驗結果。思考:將此題推廣到N皇后得情況,檢驗在N比較大得情況下，比方說N=16得時候,您得程序能否快速得求出結果,如果不能,思考有什么方法能夠優(yōu)化算法。3騎士游歷問題:在國際棋盤上使一個騎士遍歷所有得格子一遍且僅一遍,對于任意給定得頂點,輸出一條符合上述要求得路徑。4倒水問題:給定2個沒有刻度容器,對于任意給定得容積，求出如何只用兩個瓶裝出L升得水,如果可以,輸出步驟,如果不可以,請輸出NoSolution。四、實驗結果與分析(源程序及相關說明)2，八皇后問題:#include<stdio、h>/*聲明常量N存儲行與列*/#defineN8#defineNUM8/*聲明全局變量,h[N][N]控制盤格,H[N][N]控制輸出,n[N]存儲每一步得*縱坐標,count用于計數(shù)。*/inth[N][N],n[N],H[N][N];intcount=0;/*聲明函數(shù)voidtryit(int,int)嘗試符合條件得方法*/voidtryit(int,int);/*聲明函數(shù)voidoutputArray(int[][N])輸出數(shù)組*/voidoutputArray(int[][N]);main{intx=0,y=0,i,j;/*初始化為零*/for(i=0;i<=N1;i++){for(j=0;j<=N1;j++)h[i][j]=0;}tryit(x,y);printf("〃其她得布局略\n");printf("共有％4種布局、\n",92);return(0);}/*定義函數(shù)voidtryit(int,int)嘗試符合條件得方法*/voidtryit(intx,inty){inti,j;if(count<=NUM){/*重復時跳出遞歸*/if((H[0][0]==1&&H[1][4]==1&&H[2][7]==1&&H[3][5]==1&&H[4][2]==1&&H[5][6]==1&&H[6][1]==1&&H[7][3]==1)&&count!=1){}else{if(x>=0&&x<=N1&&y>=0&&y<=N1&&h[x][y]==0){/*對與皇后在同一行、列、斜線上得點作出處理*/for(j=0;j<=7;j++){if(h[x][j]==0)h[x][j]=x+1;if(h[j][y]==0)h[j][y]=x+1;if(x+j>=0&&x+j<=N1&&y+j>=0&&y+j<=N1&&h[x+j][y+j]==0)h[x+j][y+j]=x+1;if(x+j>=0&&x+j<=N1&&yj>=0&&yj<=N1&&h[x+j][yj]==0)h[x+j][yj]=x+1;if(xj>=0&&xj<=N1&&y+j>=0&&y+j<=N1&&h[xj][y+j]==0)h[xj][y+j]=x+1;if(xj>=0&&xj<=N1&&yj>=0&&yj<=N1&&h[xj][yj]==0)h[xj][yj]=x+1;}/*對皇后處得點作出標志*/h[x][y]=x1;/*完成一種走法作出處理*/if(x==7){/*轉換成輸出得格式*/for(i=0;i<=N1;i++){for(j=0;j<=N1;j++){if(h[i][j]<0)H[i][j]=1;elseH[i][j]=0;}}count=count+1;/*輸出前幾種情況*/if(count<=NUM){printf("布局％d\n",count);outputArray(H);}/*對下一種走法,清楚前一次得影響*/for(i=0;i<=N1;i++){for(j=0;j<=N1;j++){if(h[i][j]==x||h[i][j]==x||h[i][j]==x1)h[i][j]=0;}}/*遞歸,嘗試另一種方法*/tryit(x1,n[x1]+1);}/*未走完一次,繼續(xù)下一行*/else{n[x]=y;tryit(x+1,0);}}else{/*此路不通時,返回上一行,嘗試下一種方法*/if(y>7){/*清楚前一次影響*/for(i=0;i<=N1;i++){for(j=0;j<=N1;j++){if(h[i][j]==x||h[i][j]==x)h[i][j]=0;}}/*分情況遞歸*/if(x1>=0)tryit(x1,n[x1]+1);elsetryit(0,0);}/*嘗試下一格*/elsetryit(x,y+1);}}}}/*定義函數(shù)voidoutputArray(int[][N])輸出數(shù)組*/voidoutputArray(inth[][N]){inti,j;for(i=0;i<=N1;i++){for(j=0;j<=N1;j++)printf("%d",h[i][j]);printf("\n");}}運行截圖:

4、倒水問題:#include"stdio、h"intmain{intca,cb,cc,x,y;while(scanf("%d%d%d",&ca,&cb,&cc)!=EOF){if(cb==cc){printf("fillB\n");}elseif(ca==cc){printf("fillA\n");printf("pourAB\n");}else{x=y=0;if(ca<cc){while(1){if(y==0){y=cb;printf("fillB\n");}if(y>cax)//如果b中得水大于a中得剩余容積,就把a灌滿//{y=cax;x=ca;printf("pourBA\n");}else//如果b中得水小于a中得剩余容積,那么把b中得水全加入a//{x+=y;y=0;printf("pourBA\n");}if(y==cc)〃如果b中得水已經(jīng)與CC相等，那就結束〃{break;}if(Ca==x)〃如果a中得水滿了，就把a倒空〃{{x=0;printf("emptyA\n");}}}else{while(1){if(x==0){x=ca;printf("fillA\n");}if(x>cby)〃如果a中得水大于b中得剩余容積，就把b灌滿〃{x=cby;y=cb;printf("pourAB\n");}else//如果a中得水小于b中得剩余容積，那么把a中得水全加入b〃{y+=x;x=0;printf("pourAB\n");}if(y==cc)〃如果b中得水已經(jīng)與cc相等，那就結束〃break;}}if(y==cb)//如果b中得水滿了,就把b倒空//{y=0;printf("emptyB\n");}}}}printf("success\n");}return0;}運行截圖:實驗名稱計算幾何算法得實現(xiàn)姓名系院專業(yè)信息工程系班級物聯(lián)網(wǎng)一班學號實驗日期指導教師成績一、實驗目得與要求1?理解線段得性質(zhì)、叉積與有向面積。2?掌握尋找凸包得算法。3?綜合運用計算幾何與搜索中得知識求解有關問題。二、實驗預習內(nèi)容凸包:就是一組點集中得子集，這一子集形成得凸多邊形可以將點集中所有得點都圍住,并且這一凸邊形得面積就是最小得。一種尋找凸包得算法:打包法首先,我們找出點集中最下方得點，如果這樣得點不止一個,就選用最左邊得點(如P0)。顯然，這個點(P0)就是凸包子集中得一個點?？梢栽O想在P0處拴了一根皮筋得一端,另一端放在與P0成水平位置得右側。現(xiàn)在，將皮筋,沿逆時針方向轉動,首先會碰到P1,這樣就找到了另一個凸包子集中得點。以P1為中心，做與P0—樣得事,會發(fā)現(xiàn)，我們將碰到P3,又一個凸包得點。我們可以一直這樣做下去，直到再一次遇到P0,凸包就被找出來了。具體而言,在第一次找到P0點之后，以P0為每個矢量得起點，其它得點為矢量得終點，來比較任意兩個矢量得轉角，就可以對余下得點進行按極角排序三、實驗項目摘要1將講義第三章第三節(jié)中得凸包代碼上機運行并檢驗結果。2完成講義第三章得課后習題，上機運行并檢驗結果。3思考：判線段相交時，如果有個線段得端點在另一條線段上,注意可能與另一條線段上得端點重合，思考這樣得情況。4房間最短路問題：給頂一個內(nèi)含阻礙墻得房間，求解出一條從起點到終點得最最短路徑。房間得邊界固定在x=0,x=10,y=0與y=10。起點與重點固定在(0,5)與(10,5)。房間里還有0到18個墻，每個墻有兩個門。輸入給定得墻得個數(shù)，每個墻得x位置與兩個門得y坐標區(qū)間，輸出最短路得長度四、實驗結果與分析(源程序及相關說明)3、思考：用跨立方法,跨立得含義就是:如果一條線段得一個端點在一條直線得一邊，另一個端點在這條直線得另一端，我們就說這條線段跨立在這條直線上。線段相交滿足且只需滿足如下兩個條件就可以了：1兩條線段相互跨立;2一條線段得一個端點在另一條線段上。如果兩線段相交,則兩線段必然相互跨立對方。若plp2跨立p3p4，則矢量(pl-p3)與(p2pl)位于矢量(p4-p3)得兩側，即(pl-p3)X(p4p3)*(p2-p3)X(p4-p3)<0。上式可改寫成(pl-p3)X(p4p3)*(p4-p3)X(p2-p3)>0。當(pl-p3)X(p4-p3)=0時，說明(pl-p3)與(p4-p3)共線，但就是因為已經(jīng)通過快速排斥試驗，所以pl一定在線段p3p4上;同理，(p4-p3)X(p2-p3)=0說明p2一定在p3p4上。所以判斷plp2跨立QlQ2得依據(jù)就是:(pl-p3)X(p4-p3)*(p4-p3)X(p2-p3)>=0。同理判斷QlQ2跨立PlP2得依據(jù)就是:(p3pl)X(p2pl)*(p2pl)X(p4pl)>=0。代碼中函數(shù)boolsegment_intersect用于判斷pl、p2構成得線段與p3、p4構成得線段就是否相交?？梢郧瞥龉参宸N情況兩線段就是相交得，反之就輸出“ThetwoareNotintersected!"4、房間最短路問題：#includeviostream>#includevutility>#include<vector>innclude<algorithm>usingnamespacestd;typedefpair<double,double>POINT;//線段doubledirection(POINTp,POINTp1,POINTp2){POINTv1,v2;vl、first=p2、firstpl、first;vl、second=p2、secondpl、first;v2、first=p1、firstp、first;v2、second=p1、secondp、second;returnvl、first*v2、secondvl、second*v2、second;}boolon_segment(POINTp,POINTp1,POINTp2){doublemin_x=p1、firstvp2、first?p1、first:p2、first;max_x=p1、first>p2、first?p1、first:p2、first;doublemin_y=p1、secondvp2、second?p1、second:p2、second;doublemax_y=p1、second>p2、second?p1、second:p2、second;if(p、first>=minx&&p、first<maxx&&p、second>=min_y&&p、secondv=max_y)returntrue;elsereturnfalse;}POINTstartPoint;boolsortByPolorAngle(constPOINT&p1,constPOINT&p2){doubled=direction(startPoint,pl,p2);if(dvO)returntrue;if(d>0)returnfalse;if(d==0&&on_segment(startPoint,p1,p2))returntrue;if(d==0&&on_segment(p2,startPoint,p1))returntrue;returnfalse;}voidfind_convex_hull(vectorvPOINT>&point){PO