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

程序設(shè)計藝術(shù)與方法》課程實驗報告實驗名稱STL的熟悉與使用姓名系院專業(yè)計算機與信息學院班級計算機科學與技術(shù)12—2班學號2012211643實驗日期指導(dǎo)教師徐本柱成績一、實驗?zāi)康暮鸵?.(1)掌握C++中STL的容器類使用。(2)掌握C++中STL的算法類的使用。二、實驗預(yù)習內(nèi)容Vector,list可當作列表使用的數(shù)據(jù)結(jié)構(gòu)，它們都是動態(tài)增長的。l.vector表示一段連續(xù)的內(nèi)存區(qū)域每個兀素被順序儲存在這段內(nèi)存中。對vector的隨即訪問效率很高。但是在任意位置而不是在vector末尾插入兀素則效率很低，因為它需要把待插入兀素的右邊的母個兀素都拷貝一遍。類似的刪除任一個而不是vector的取后一個兀素效率低。2list表示非連續(xù)的內(nèi)存區(qū)域并通過一對指向首尾元素的指針雙向進行遍歷在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的使用。定義一個空的vector，元素類型為int,生成10個隨機數(shù)插入到vector中，用迭代器遍歷vector并輸出其中的元素值。在vector頭部插入一個隨機數(shù)，用迭代器遍歷vector并輸出其中的元素值。用泛型算法find查找某個隨機數(shù)，如果找到便輸出，否則將此數(shù)插入vector尾部。用泛型算法sort將vector排序，用迭代器遍歷vector并輸出其中的元素值。刪除vector尾部的元素，用迭代器遍歷vector并輸出其中的元素值。將vector清空。定義一個list,并重復(fù)上述實驗，并注意觀察結(jié)果2練習泛型算法的使用。定義一個vector，兀素類型為int，插入10個隨機數(shù)，使用sort按升序排序，輸出母個元素的值，再按降敘排序，輸出母個元素的值。練習用find查找元素。用min和max找出容器中的最小元素個最大元素，并輸出。四、實驗結(jié)果與分析(源程序及相關(guān)說明)1.練習vector和list的使用：#include<iostream>#includevvector>#includeviomanip>#include<ctime>#includevalgorithm>usingnamespacestd;vector<int>myV;boolsortup(intvl,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[O];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);}

XXboolsortsp(intvl,intv2)〃定義一個升序排序算法{returnv1>v2;}intmain(){linlin2;lin2.push_front(3);〃單獨逐個插入幾個數(shù)lin2.push_front(4);lin2.insert(lin2.begin(),value,value+5);coutvv"lin2內(nèi)的元素為：”；print(lin2);lin2.sort();〃對鏈表l1進行從小到大排序coutvv"排序后的lin2:";print(lin2);lin2.push_front(10);〃在list頭部插入10coutvv"在list頭部插入10之后的結(jié)果：";print(lin2);lin2.remove(6);coutvv"刪除一個數(shù)后的lin1:";print(lin2);system("PAUSE");//pressanykeytocontineu...return0;}//List不允許對隨機數(shù)進行操作運行截圖：310134t789789:1Ei_y876-Tz-14_y87614314后1:10-n■■素龍播石繼5t任n2序Li辱11排在髻實驗名稱搜索算法的實驗姓名黃星辰系院專業(yè)計算機與信息學院班級計算機科學與技術(shù)12—2班學號2012211643實驗日期指導(dǎo)教師徐本柱成績一、實驗?zāi)康暮鸵笳莆諏挾葍?yōu)先搜索算法。掌握深度優(yōu)先搜索算法。二、實驗預(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)先搜索，即在搜索其余的超鏈走到不能再深入為止，然后返回到某一個HTML文件，再繼續(xù)選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經(jīng)結(jié)束。三、實驗項目摘要將書上的走迷宮代碼上機運行并檢驗結(jié)果，并注意體會搜索的思想。2.八皇后問題：在一個國際象棋棋盤上放八個皇后，使得任何兩個皇后之間不相互攻擊，求出所有的布棋方法。上機運行并檢驗結(jié)果。思考：將此題推廣到N皇后的情況，檢驗在N比較大的情況下，比方說N=16的時候，你的程序能否快速的求出結(jié)果，如果不能，思考有什么方法能夠優(yōu)化算法。3騎士游歷問題：在國際棋盤上使一個騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂點，輸出一條符合上述要求的路徑。4倒水問題：給定2個沒有刻度容器，對于任意給定的容積，求出如何只用兩個瓶裝出L升的水，如果可以，輸出步驟，如果不可以，請輸出NoSolution。main(){intx=O,y=O,i,j;/*初始化為零*/for(i=0;iv=N-l;i++){for(j=0;j<=N-1;j++)h[i][j]=O；}tryit(x,y);printf("〃其他的布局略\n");printf("共有％d種布局.\n",92);return(O);}/*定義函數(shù)voidtryit(int,int)嘗試符合條件的方法*/voidtryit(intx,inty){inti,j;if(countv=NUM){/*重復(fù)時跳出遞歸*/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<=N-1&&y>=0&&yv=N-1&&h[x][y]==0){/*對與皇后在同一行、列、斜線上的點作出處理*/for(j=0;j<=7;j++){if(h[x][j]=O)h[x][j]=x+l;if(h[j][y]==O)h[j][y]=x+1;if(x+j>=0&&x+jv=N-1&&y+j>=0&&y+jv=N-1&&h[x+j][y+j]==0)h[x+j][y+j]=x+1;if(x+j>=0&&x+j<=N-1&&y-j>=0&&y-jv=N-1&&h[x+j][y-j]==0)h[x+j][y-j]=x+1;if(x-j>=0&&x-j<=N-1&&y+j>=0&&y+j<=N-1&&h[x-j][y+j]==0)h[x-j][y+j]=x+1;if(x-j>=0&&x-j<=N-1&&y-j>=0&&y-jv=N-1&&h[x-j][y-j]==0)h[x-j][y-j]=x+1;}/*對皇后處的點作出標志*/h[x][y]=-x-1;/*完成一種走法作出處理*/if(x==7){/*轉(zhuǎn)換成輸出的格式*/for(i=0;iv=N-1;i++){for(j=0;j<=N-1;j++){if(h[i][j]vO)H[i][j]=1;elseH[i][j]=O;}}count=count+1;/*輸出前幾種情況*/

for(j=0;j<8;j++){printf("%2d",board[i][j]);}putchar('\n');}return0;}inttravel(intx,inty){intktmove1⑻={-2,-1,1,2,2,1,-1,-2};//對應(yīng)騎士可走的八個方向intktmove2[8]={1,2,2,1,-1,-2,-2,-1};//測試下一步的出路intnexti[8]={0};intnextj[8]={0};//記錄出路的個數(shù)intexists⑻={0};inti,j,k,m,l;inttmpi,tmpj;intcount,min,tmp;i=x;j=y;board[i][j]=1;for(m=2;m<=64;m++){for(l=0;l<8;l++)exists[l]=0;l=0;//試探八個方向for(k=0;k<&k++){tmpi=i+ktmove1[k];tmpj=j+ktmove2[k];//如果是邊界了，不可走if(tmpi<0||tmpj<0IItmpi>7IItmpj>7)continue;//如果這個方向可走，記錄下來if(board[tmpi][tmpj]==0){nexti[l]=tmpi;nextj[l]=tmpj;//可走的方向加一個1++；}}count=l;//如果可走的方向為0個，返回if(count==0){return0;}elseif(count==1){//只有一個可走的方向//所以直接是最少出路的方向min=0;}else{//找出下一個位置的出路數(shù)for(l=0;l<count;l++){for(k=0;k<&k++){tmpi=nexti[l]+ktmovel[k];tmpj=nextj[l]+ktmove2[k];if(tmpi<0IItmpj<0IItmpi>7IItmpj>7){continue;}if(board[tmpi][tmpj]==0)exists[l]++;}}tmp=exists[0];min=0;//從可走的方向中尋找最少出路的方向for(l=1;l<count;l++){

'C:\Debug\qi5hiyouli.exe"18365

'C:\Debug\qi5hiyouli.exe"18365

?44.倒水問題：#include"stdio.h"intmain(){/D2TOC\o"1-5"\h\z1528256221485558加35304S606S2052914bl34W44595436313841645369134033501184352323712394251107P^ess趙nyk^ytocontinueintca,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");

實驗名稱計算幾何算法的實現(xiàn)姓名黃星辰系院專業(yè)計算機與信息學院班級計算機科學與技術(shù)12—2班學號2012211643實驗日期指導(dǎo)教師徐本柱成績一、實驗?zāi)康暮鸵罄斫饩€段的性質(zhì)、叉積和有向面積。掌握尋找凸包的算法。綜合運用計算幾何和搜索中的知識求解有關(guān)問題。二、實驗預(yù)習內(nèi)容凸包：是一組點集中的子集，這一子集形成的凸多邊形可以將點集中所有的點都圍住，并且這一凸邊形的面積是最小的。一種尋找凸包的算法：打包法首先，我們找出點集中最下方的點，如果這樣的點不止一個，就選用最左邊的點(如P0)。顯然，這個點(P0)是凸包子集中的一個點?？梢栽O(shè)想在P0處拴了一根皮筋的一端，另一端放在和P0成水平位置的右側(cè)。現(xiàn)在，將皮筋，沿逆時針方向轉(zhuǎn)動，首先會碰到P1,這樣就找到了另一個凸包子集中的點。以P1為中心，做和P0—樣的事，會發(fā)現(xiàn)，我們將碰到P3，又一個凸包的點。我們可以一直這樣做下去，直到再一次遇到P0，凸包就被找出來了。具體而言，在第一次找到P0點之后，以P0為每個矢量的起點，其它的點為矢量的終點，來比較任意兩個矢量的轉(zhuǎn)角，就可以對余下的點進行按極角排序三、實驗項目摘要1將講義第三章第三節(jié)中的凸包代碼上機運行并檢驗結(jié)果。2完成講義第三章的課后習題，上機運行并檢驗結(jié)果。3思考：判線段相交時，如果有個線段的端點在另一條線段上，注意可能與另一條線段上的端點重合，思考這樣的情況。4房間最短路問題：給頂一個內(nèi)含阻礙墻的房間，求解出一條從起點到終點的最最短路徑。房間的邊界固定在x=0,x=10,y=0和y=10。起點和重點固定在(0,5)和(10,5)。房間里還有0到18個墻，每個墻有兩個門。輸入給定的墻的個數(shù)，每個墻的x位置和兩個門的y坐標區(qū)間，輸出最短路的長度四、實驗結(jié)果與分析(源程序及相關(guān)說明)3.思考：用跨立方法，跨立的含義是：如果一條線段的一個端點在一條直線的一邊，另一個端點在這條直線的另一端，我們就說這條線段跨立在這條直線上。線段相交滿足且只需滿足如下兩個條件就可以了：1兩條線段相互跨立；2一條線段的一個端點在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對方。若p1p2跨立p3p4，則矢量(p1-p3)和(p2-p1)位于矢量(p4-p3)的兩側(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時，說明(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)成的線段是否相交。可以看出共五種情況兩線段是相交的，反之就輸出“ThetwoareNotintersected!"4.房間最短路問題:#includeviostream>#includevutility>#includevvector>inncludevalgorithm>usingnamespacestd;typedefpairvdouble,double>POINT;//線段doubledirection(POINTp,POINTpl,POINTp2){POINTv1,v2;v1.first=p2.first-p1.first;v1.second=p2.second-p1.first;v2.first=p1.first-p.first;v2.second=p1.second-p.second;returnv1.first*v2.second-v1.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>=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(d==0&&on_segment(p2,startPoint,p1))returntrue;returnfalse;}voidfind_convex_hull(vectorvPOINT>&point){POINTp0=point[0];intk=0;for(inti=O;ivpoint.size();i++){if(p