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

1、程序設計藝術與方法課程實驗報告一實驗名稱STL 的熟悉與使用計算機與計算機科姓名班級學與技術學號系院專業(yè)信息學院122 班實驗日期指導教師徐本柱成績一、實驗目的和要求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

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

3、起。三、實驗項目摘要1. 練習 vector 和 list 的使用。定義一個空的 vector ，元素類型為 int ，生成 10個隨機數(shù)插入到 vector中，用迭代器遍歷 vector 并輸出其中的元素值。在vector頭部插入一個隨機數(shù)，用迭代器遍歷vector并輸出其中的元素值。用泛型算法find查找某個隨機數(shù)，如果找到便輸出，否則將此數(shù)插入 vector 尾部。用泛型算法sort 將 vector 排序，用迭代器遍歷vector 并輸出其中的元素值。刪除 vector 尾部的元素，用迭代器遍歷vector并輸出其中的元素值。將vector 清空。定義一個 list ，并重復上述實驗，

4、并注意觀察結果2 練習泛型算法的使用。定義一個 vector ，元素類型為 int ，插入 10 個隨機數(shù)，使用 sort 按升序排序，輸出每個元素的值，再按降敘排序，輸出每個元素的值。練習用find查找元素。用 min 和max 找出容器中的最小元素個最大元素，并輸出。四、實驗結果與分析（源程序及相關說明）1. 練習 vector 和 list 的使用：#include <iostream>#include <vector>#include<iomanip>#include<ctime>#include <algorithm>usi

5、ng namespace std;vector<int> myV;bool sortup(int v1,int v2)return v1<v2;int main(int argc, char *argv)srand(time(NULL);/隨機產(chǎn)生十個數(shù)for (int i=0;i<10;i+)myV.push_back(rand();sort(myV.begin(),myV.end(),sortup);/用 sort 排序升序vector<int>:iterator it1;for (it1=myV.begin();it1!=myV.end();it1+)

6、cout<<(*it1)<<setw(6);/打印數(shù)組cout<<endl;int min=myV0;for (it1=myV.begin()+1;it1!=myV.end();it1+)if(*it1)<min)min=(*it1);cout<<"最小元素為 " <<min<<endl;int max=myV0;for (it1=myV.begin();it1!=myV.end();it1+)if(*it1)>max)max=(*it1);cout<<"最大元素為 &

7、quot; <<max<<endl;cout<<endl;int value=rand();it1=find(myV.begin(),myV.end(),value);if(*it1)=value)cout<<"找到了這個隨機數(shù) "<<endl ;elsecout<<"沒有找到這個隨機數(shù) "<<endl;myV.insert(myV.end(),value); / 數(shù)組中沒有隨機數(shù) ,插入尾部cout<<"插入尾部的隨機數(shù)為 "<&l

8、t;value<<endl;for (it1=myV.begin();it1!=myV.end();it1+)cout<<(*it1)<<setw(6);cout<<"n"<<endl;/隨機在 vector 頭部插入一個隨機數(shù)int t=rand();/定義 t;將一個隨機數(shù)賦給 t，插入到數(shù)組·頭部 myV.insert(myV.begin(),t);cout<<"插入頭部的隨機數(shù)為 " <<t<<endl;for (it1=myV.begin(

9、);it1!=myV.end();it1+)cout<<(*it1)<<setw(6);cout<<endl;/刪除尾部元素myV.pop_back ();for (it1=myV.begin();it1!=myV.end();it1+)cout<<(*it1)<<setw(6);cout<<endl;myV.clear();/ 清空數(shù)組if(myV.empty()cout << "It's empty!" << endl;system("PAUSE"

10、);/press any key to continue.return 0;運行截圖：2 練習泛型算法的使用：#include<list>#include<iostream>/#inclued<algorithm>using namespace std;typedef list<int> lin;int value=1,6,7,8,9;/ 定義一個數(shù)組 value 并賦值void print(lin &l)int i;lin:iterator lit;/ 定義一個迭代器for(lit=l.begin();lit!=l.end();lit+

11、)cout<<(*lit)<<" "/ 依次打印 list 中的元素cout<<endl;bool sortsp(int v1,int v2)/定義一個升序排序算法return v1>v2;int main()lin lin2;lin2.push_front(3); / 單獨逐個插入幾個數(shù)lin2.push_front(4);lin2.insert(lin2.begin(),value,value+5);cout<<"lin2 內(nèi)的元素為： "print(lin2);lin2.sort();/ 對鏈表

12、 l1 進行從小到大排序cout<<"排序后的 lin2: "print(lin2);lin2.push_front(10);/在 list 頭部插入 10cout<<"在 list 頭部插入 10 之后的結果： "print(lin2);lin2.remove(6);cout<<"刪除一個數(shù)后的lin1:"print(lin2);system("PAUSE");/press any key to contineu.return 0;/List 不允許對隨機數(shù)進行操作運行截圖：二

13、實驗名稱搜索算法的實驗計算機與計算機科姓名黃星辰班級學與技術學號系院專業(yè)信息學院122 班實驗日期指導教師徐本柱成績一、實驗目的和要求1掌握寬度優(yōu)先搜索算法。2掌握深度優(yōu)先搜索算法。二、實驗預習內(nèi)容1 寬度優(yōu)先搜索算法：又稱廣度優(yōu)搜索。是最簡單的圖的算法的原形。其屬于一種盲搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以尋找結果。換句話說，它并不考慮結果的可能位址，徹底地搜索整張圖，直到找到結果為止。2 深度優(yōu)先搜索算法：被選擇后，被連接的它的目的是要達到被搜索結構的葉結點。在一個 HTML文件中， 當一個超鏈HTML文件將執(zhí)行深度優(yōu)先搜索，即在搜索其余的超鏈走到不能再深入為止，然后返回到某一

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

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

16、nt);/* 聲明函數(shù) void outputArray(intN) 輸出數(shù)組 */void outputArray(intN);main()int x=0,y=0,i,j;/* 初始化為零 */for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)hij=0;tryit(x,y);printf("/ 其他的布局略 n");printf(" 共有 %d 種布局 .n",92);return(0);/* 定義函數(shù) void tryit(int,int) 嘗試符合條件的方法 */ void tryit(int x,int y)i

17、nt i,j;if(count<=NUM)/* 重復時跳出遞歸 */if(H00=1&&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)/* 對與皇后在同一行、列、斜線上的點作出處理*/for(j=0;j<=7;j+)

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

19、;&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;/* 對皇后處的點作出標志*/hxy=-x-1;/* 完成一種走法作出處理*/if(x=7)/* 轉換成輸出的格式 */for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)if(hij<0)Hij=1;elseHij=0;count=count+1;/*

20、 輸出前幾種情況 */if(count<=NUM)printf("- 布局 %d-n",count);outputArray(H);/* 對下一種走法，清楚前一次的影響*/for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)if(hij=x|hij=-x|hij=-x-1)hij=0;/* 遞歸，嘗試另一種方法 */tryit(x-1,nx-1+1);/* 未走完一次，繼續(xù)下一行*/elsenx=y;tryit(x+1,0);else/* 此路不通時，返回上一行，嘗試下一種方法*/if(y>7)/* 清楚前一次影響 */for(i

21、=0;i<=N-1;i+)for(j=0;j<=N-1;j+)if(hij=x|hij=-x)hij=0;/* 分情況遞歸 */if(x-1>=0)tryit(x-1,nx-1+1);elsetryit(0,0);/* 嘗試下一格 */elsetryit(x,y+1);/* 定義函數(shù) void outputArray(intN) 輸出數(shù)組 */void outputArray(int hN)int i,j;for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)printf("%d ",hij);printf("n&q

22、uot;);運行截圖：3. 騎士游歷問題：在國際棋盤上使一個騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂點，輸出一條符合上述要求的路徑。#include <stdio.h>int board88 = 0;int main(void) int startx, starty;int i, j;printf(" 輸入起始點： "); scanf("%d %d", &startx, &starty); if(travel(startx, starty) printf(" 游歷完成！ n");else print

23、f(" 游歷失?。?n");for(i = 0; i < 8; i+) for(j = 0; j < 8; j+) printf("%2d ", boardij);putchar('n');return 0;int travel(int x, int y)int ktmove18 = -2, -1, 1, 2, 2, 1, -1, -2; /int ktmove28 = 1, 2, 2, 1, -1, -2, -2, -1; /int nexti8 = 0;int nextj8 = 0; /記錄出路的個數(shù)int exists8

24、 = 0;int i, j, k, m, l;int tmpi, tmpj;int count, min, tmp;i = x;j = y;boardij = 1;for(m = 2; m <= 64; m+) for(l = 0; l < 8; l+)existsl = 0;l = 0;/ 試探八個方向for(k = 0; k < 8; k+) tmpi = i + ktmove1k;對應騎士可走的八個方向測試下一步的出路tmpj = j + ktmove2k; /如果是邊界了，不可走if(tmpi < 0 | tmpj < 0 | tmpi > 7 |

25、tmpj > 7)continue; / 如果這個方向可走，記錄下來if(boardtmpitmpj = 0) nextil = tmpi;nextjl = tmpj; /可走的方向加一個l+;count = l; / 如果可走的方向為0 個，返回if(count = 0) return 0;else if(count = 1) / 只有一個可走的方向/ 所以直接是最少出路的方向min = 0;else / 找出下一個位置的出路數(shù)for(l = 0; l < count; l+) for(k = 0; k < 8; k+) tmpi = nextil + ktmove1k;t

26、mpj = nextjl + ktmove2k;if(tmpi < 0 | tmpj < 0 |tmpi > 7 | tmpj > 7) continue;if(boardtmpitmpj = 0)existsl+;tmp = exists0;min = 0; / 從可走的方向中尋找最少出路的方向for(l = 1; l < count; l+) if(existsl < tmp) tmp = existsl;min = l;/ 走最少出路的方向i = nextimin;j = nextjmin;boardij = m;return 1;運行截圖：4.倒水問

27、題：#include"stdio.h"int main()int ca,cb,cc,x,y;while(scanf("%d%d%d",&ca,&cb,&cc)!=EOF)if(cb=cc) printf("fill Bn");else if(ca=cc)printf("fill An");printf("pour A Bn");elsex=y=0;if(ca<cc)while(1) if(y=0)y=cb;printf("fill Bn");if

28、(y>ca-x)/如果 b 中的水大于 a 中的剩余容積，就把a 灌滿 /y-=ca-x;x=ca;printf("pour B An");else/如果 b 中的水小于 a 中的剩余容積，那么把b 中的水全加入 a/x+=y;y=0;printf("pour B An");if(y=cc)/如果 b 中的水已經(jīng)和 cc 相等，那就結束 /break;if(ca=x)/如果 a 中的水滿了，就把a 倒空 /x=0;printf("empty An");elsewhile(1)if(x=0)x=ca;printf("fi

29、ll An");if(x>cb-y)/如果 a 中的水大于 b 中的剩余容積，就把b 灌滿 /x-=cb-y;y=cb;printf("pour A Bn");else/如果 a 中的水小于 b 中的剩余容積，那么把a 中的水全加入 b/y+=x;x=0;printf("pour A Bn");if(y=cc)/如果 b 中的水已經(jīng)和 cc 相等，那就結束 /break;if(y=cb)/如果 b 中的水滿了，就把b 倒空 /y=0;printf("empty Bn");printf("successn&qu

30、ot;);return 0;運行截圖：三實驗名稱計算幾何算法的實現(xiàn)計算機與計算機科姓名黃星辰班級學與技術學號系院專業(yè)信息學院122 班實驗日期指導教師徐本柱成績一、實驗目的和要求1理解線段的性質(zhì)、叉積和有向面積。2掌握尋找凸包的算法。3綜合運用計算幾何和搜索中的知識求解有關問題。二、實驗預習內(nèi)容凸包：是一組點集中的子集，這一子集形成的凸多邊形可以將點集中所有的點都圍住，并且這一凸邊形的面積是最小的。一種尋找凸包的算法：打包法首先，我們找出點集中最下方的點，如果這樣的點不止一個，就選用最左邊的點（如P0）。顯然，這個點（P0）是凸包子集中的一個點?？梢栽O想在P0處拴了一根皮筋的一端，另一端放在和

31、P0成水平位置的右側。現(xiàn)在，將皮筋，沿逆時針方向轉動，首先會碰到 P1，這樣就找到了另一個凸包子集中的點。以 P1 為中心，做和們將碰到 P3，又一個凸包的點。我們可以一直這樣做下去，直到再一次遇到P0一樣的事，會發(fā)現(xiàn)，我P0，凸包就被找出來了。具體而言，在第一次找到P0點之后，以P0為每個矢量的起點，其它的點為矢量的終點，來比較任意兩個矢量的轉角，就可以對余下的點進行按極角排序三、實驗項目摘要1 將講義第三章第三節(jié)中的凸包代碼上機運行并檢驗結果。2完成講義第三章的課后習題，上機運行并檢驗結果。3思考：判線段相交時，如果有個線段的端點在另一條線段上，注意可能與另一條線段上的端點重合，思考這樣的

32、情況。4房間最短路問題：給頂一個內(nèi)含阻礙墻的房間，求解出一條從起點到終點的最最短路徑。房間的邊界固定在 x=0,x=10,y=0 和 y=10 。起點和重點固定在 (0,5) 和(10,5) 。房間里還有墻，每個墻有兩個門。輸入給定的墻的個數(shù)，每個墻的 x 位置和兩個門的輸出最短路的長度0到18個y 坐標區(qū)間，四、實驗結果與分析（源程序及相關說明）3.思考：用跨立方法，跨立的含義是：如果一條線段的一個端點在一條直線的一邊，另一個端點在這條直線的另一端，我們就說這條線段跨立在這條直線上。線段相交滿足且只需滿足如下兩個條件就可以了：1 兩條線段相互跨立； 2 一條線段的一個端點在另一條線段上。如果

33、兩線段相交，則兩線段必然相互跨立對方。若p1p2 跨立 p3p4 ，則矢量( p1 p3 ) 和 ( p2 - p1 )位于矢量 ( p4 p3 )的兩側，即( p1 p3） × ( p4- p3 ) * ( p2 p3 ) × ( p4 p3 ) < 0。上式可改寫成 ( p1 p3 ) × ( p4- p3 ) * ( p4 p3 )×( p2 p3) > 0。當( p1 p3 ) × ( p4p3 ) = 0 時，說明 ( p1 p3 ) 和 ( p4 p3 )共線，但是因為已經(jīng)通過快速排斥試驗， 所以 p1 一定在線段 p3

34、p4 上；同理，( p4p3 ) × (p2 p3 ) =0 說明 p2 一定在 p3p4上。所以判斷 p1p2 跨立 Q1Q2 的依據(jù)是：( p1 p3 ) × ( p4 p3 ) * ( p4 p3 ) × ( p2p3 ) >= 0。同理判斷 Q1Q2 跨立P1P2 的依據(jù)是： ( p3 - p1 ) × ( p2 - p1 ) * ( p2 - p1 )× ( p4 - p1 ) >= 0 。代碼中函數(shù)bool segment_intersect()用于判斷 p1、p2 構成的線段和可以看出共五種情況兩線段是相交的，反之就輸

35、出“p3、p4 構成的線段是否相交。The two are Not intersected!”4.房間最短路問題：#include<iostream>#include<utility>#include<vector>innclude<algorithm>using namespace std;typedef pair<double,double> POINT;/線段double direction(POINT p,POINT p1,POINT p2)POINT v1,v2;v1.first=p2.first-p1.first;v1.s

36、econd=p2.second-p1.first;v2.first=p1.first-p.first;return v1.first*v2.second-v1.second*v2.second;bool on_segment(POINT p,POINT p1,POINT p2)double min_x=p1.first<p2.first?p1.first:p2.first;max_x=p1.first>p2.first?p1.first:p2.first;double min_y=p1.second<p2.second?p1.second:p2.second; double max_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)return true;elsereturn false;POINT startPoint;bool so