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

程序設(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)康门c要求1.(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)存區(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與1ist得使用。定義一個(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,插入10個(gè)隨機(jī)數(shù)，使用sort按升序排序，輸出每個(gè)元素得值，再按降敘排序，輸出每個(gè)元素得值。練習(xí)用find查找元素。用min與max找出容器中得最小元素個(gè)最大元素，并輸出。四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說(shuō)明)1、練習(xí)vector與1ist得使用：#inc1ude<iostream>#includevvector>#includeviomanip>#inc1ude<ctime>#inc1udevalgorithm>usingnamespacestd;vector<int>myV;boolsortup(intv1,intv2){returnv1vv2;}intmain(intargc,char*argv[]){srand(time(NULL));〃隨機(jī)產(chǎn)生十個(gè)數(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"找到了這個(gè)隨機(jī)數(shù)"vvendl;elsecoutvv"沒有找到這個(gè)隨機(jī)數(shù)"vvendl;myV、insert(myV、end,value);〃數(shù)組中沒有隨機(jī)數(shù)，插入尾部coutvv"插入尾部得隨機(jī)數(shù)為"vvvaluevvendl;for(itl=myV、begin;itl!=myV、end;itl++){coutvv(*itl)vvsetw(6);}coutvv"\n"vvendl;〃隨機(jī)在vector頭部插入一個(gè)隨機(jī)數(shù)intt=rand;〃定義t;將一個(gè)隨機(jī)數(shù)賦給t,插入到數(shù)組?頭部myV、insert(myV、begin,t);coutvv"插入頭部得隨機(jī)數(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;}運(yùn)行截圖：2練習(xí)泛型算法得使用:#includevlist>#includeviostream>〃#incluedvalgorithm>usingnamespacestd;typedeflistvint>lin;intvalue[]={2,4,6,l,8};voidprint(lin&1){inti;lin::iteratorlit;//定義一個(gè)迭代器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之后得結(jié)果:"；print(lin2);lin2、remove(6);coutvv"刪除一個(gè)數(shù)后得lin1:";print(lin2);system("PAUSE");//pressanykeytocontineu、、、

實(shí)驗(yàn)名稱搜索算法得實(shí)驗(yàn)實(shí)驗(yàn)名稱姓名系院專業(yè)系班物聯(lián)網(wǎng)一級(jí)班學(xué)號(hào)實(shí)驗(yàn)日期指導(dǎo)教師成績(jī)一、實(shí)驗(yàn)?zāi)康门c要求1.掌握寬度優(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)不再有其她超鏈可選擇時(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升得水,如果可以,輸出步驟,如果不可以,請(qǐng)輸出NoSolution。四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說(shuō)明)2，八皇后問(wèn)題:#include<stdio、h>/*聲明常量N存儲(chǔ)行與列*/#defineN8#defineNUM8/*聲明全局變量,h[N][N]控制盤格,H[N][N]控制輸出,n[N]存儲(chǔ)每一步得*縱坐標(biāo),count用于計(jì)數(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){/*重復(fù)時(shí)跳出遞歸*/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){/*對(duì)與皇后在同一行、列、斜線上得點(diǎn)作出處理*/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;}/*對(duì)皇后處得點(diǎn)作出標(biāo)志*/h[x][y]=x1;/*完成一種走法作出處理*/if(x==7){/*轉(zhuǎn)換成輸出得格式*/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);}/*對(duì)下一種走法,清楚前一次得影響*/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{/*此路不通時(shí),返回上一行,嘗試下一種方法*/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");}}運(yùn)行截圖:

4、倒水問(wèn)題:#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(bǔ)灌滿//{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相等，那就結(jié)束〃{break;}if(Ca==x)〃如果a中得水滿了，就把a(bǔ)倒空〃{{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ǔ)中得水全加入b〃{y+=x;x=0;printf("pourAB\n");}if(y==cc)〃如果b中得水已經(jīng)與cc相等，那就結(jié)束〃break;}}if(y==cb)//如果b中得水滿了,就把b倒空//{y=0;printf("emptyB\n");}}}}printf("success\n");}return0;}運(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)康门c要求1?理解線段得性質(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成水平位置得右側(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)重合，思考這樣得情況。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)在另一條線段上。如果兩線段相交,則兩線段必然相互跨立對(duì)方。若plp2跨立p3p4，則矢量(pl-p3)與(p2pl)位于矢量(p4-p3)得兩側(cè)，即(pl-p3)X(p4p3)*(p2-p3)X(p4-p3)<0。上式可改寫成(pl-p3)X(p4p3)*(p4-p3)X(p2-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上;同理，(p4-p3)X(p2-p3)=0說(shuō)明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構(gòu)成得線段與p3、p4構(gòu)成得線段就是否相交。可以瞧出共五種情況兩線段就是相交得，反之就輸出“ThetwoareNotintersected!"4、房間最短路問(wèn)題：#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