課程實(shí)驗(yàn)報(bào)告

1、課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)一 STL的熟悉與使用實(shí)驗(yàn)名稱實(shí)驗(yàn)一 STL 的熟悉與使用姓 名汪子成系院專業(yè)信息工程系班 級計(jì)算機(jī)15-1班學(xué) 號2015216758實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成 績一、實(shí)驗(yàn)?zāi)康暮鸵?掌握C+中STL的容器類的使用;2掌握C+中STL的算法類的使用.二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1預(yù)習(xí)ICPC講義，大致了解STL的相關(guān)內(nèi)容。2了解STL中一些類 vector list類的使用方法3了解泛型算法的使用三、實(shí)驗(yàn)項(xiàng)目摘要(1) 練習(xí)vector 和list 的使用。定義一個(gè)空的vector，元素類型為int，生成10 個(gè)隨機(jī)數(shù)插入到vector 中，用迭代器遍歷vector 并輸出其中的元素值。在

2、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

3、 和max 找出容器中的最小元素和最大元素，并輸出。四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）1. 練習(xí)vector 和list 的使用：#include #include #include#include #include using namespace std;vector myV;bool sortup(int v1,int v2)return v1v2; int main(int argc, char *argv) srand(time(NULL); for (int i=0;i10;i+) myV.push_back(rand(); sort(myV.begin(),myV.end(),

4、sortup); vector:iterator it1; for (it1=myV.begin();it1!=myV.end();it1+) cout(*it1)setw(6); coutendl; int min=myV0; for (it1=myV.begin()+1;it1!=myV.end();it1+) if(*it1)min)min=(*it1); cout最小元素為 minmax)max=(*it1); cout最大元素為 maxendl; coutendl; int value=rand(); it1=find(myV.begin(),myV.end(),value); if

5、(*it1)=value) cout找到了這個(gè)隨機(jī)數(shù)endl ; else cout沒有找到這個(gè)隨機(jī)數(shù)endl; myV.insert(myV.end(),value); cout插入尾部的隨機(jī)數(shù)為valueendl; for (it1=myV.begin();it1!=myV.end();it1+) cout(*it1)setw(6); coutnendl; int t=rand(); myV.insert(myV.begin(),t); cout插入頭部的隨機(jī)數(shù)為 tendl; for (it1=myV.begin();it1!=myV.end();it1+) cout(*it1)setw

6、(6); coutendl; myV.pop_back (); for (it1=myV.begin();it1!=myV.end();it1+) cout(*it1)setw(6); coutendl; myV.clear(); if(myV.empty() cout Its empty! endl; system(PAUSE); /press any key to continue. return 0;2 練習(xí)泛型算法的使用：#include#includeusing namespace std;typedef list lin;int value=1,6,7,8,9; void prin

7、t(lin &l)int i;lin:iterator lit;for(lit=l.begin();lit!=l.end();lit+)cout(*lit) ;coutv2; int main()lin lin2; lin2.push_front(3); lin2.push_front(4); lin2.insert(lin2.begin(),value,value+5);coutlin2內(nèi)的元素為：;print(lin2);lin2.sort(); cout排序后的lin2: ;print(lin2);lin2.push_front(10);cout在list頭部插入10之后的結(jié)果：; pr

8、int(lin2);lin2.remove(6);cout刪除一個(gè)數(shù)后的lin1:; print(lin2); system(PAUSE);return 0;實(shí)驗(yàn)二 搜索算法的實(shí)現(xiàn)實(shí)驗(yàn)名稱實(shí)驗(yàn)二 搜索算法的實(shí)現(xiàn)姓 名汪子成系院專業(yè)信息工程系班 級計(jì)算機(jī)15-1班學(xué) 號2015216758實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成 績一、實(shí)驗(yàn)?zāi)康暮鸵?掌握寬度優(yōu)先搜索算法;2掌握深度優(yōu)先搜索算法.二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1預(yù)習(xí)ICPC講義中的搜索的內(nèi)容2. 了解什么是深度優(yōu)先搜索和廣度優(yōu)先搜索。三、實(shí)驗(yàn)項(xiàng)目摘要1. 將書上的走迷宮代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果，并注意體會搜索的思想。2.八皇后問題：在一個(gè)國際象棋棋盤上放八個(gè)皇

9、后，使得任何兩個(gè)皇后之間不相互攻擊，求出所有的布棋方法。上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。3. 騎士游歷問題：在國際棋盤上使一個(gè)騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂點(diǎn)，輸出一條符合上述要求的路徑。4.倒水問題：給定2 個(gè)沒有刻度容器，對于任意給定的容積，求出如何只用兩個(gè)瓶裝出L 升的水，如果可以，輸出步驟，如果不可以，請輸出No Solution四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）2，八皇后問題：#include #define N 8#define NUM 8int hNN,nN,HNN;int count=0;void tryit(int,int);void outputArray(int

10、N);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);void tryit(int x,int y)int i,j;if(count=0&x=0&y=N-1&hxy=0)for(j=0;j=0&x+j=0&y+j=0&x+j=0&y-j=0&x-j=0&y+j=0&x-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

11、;j=N-1;j+)if(hij0)Hij=1;elseHij=0; count=count+1;if(count=NUM)printf(-布局%d-n,count); outputArray(H); for(i=0;i=N-1;i+)for(j=0;j7)for(i=0;i=N-1;i+)for(j=0;j=0) tryit(x-1,nx-1+1);else tryit(0,0);elsetryit(x,y+1);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

12、);3. 騎士游歷問題：#include int board88 = 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; int exists8 = 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

13、+) 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 7 | tmpj 7) continue; if(boardtmpitmpj = 0) nextil = tmpi; nextjl = tmpj; l+; count = l; if(count = 0) return 0; else if(count = 1) min = 0; else for(l = 0; l count; l+) for(k = 0

14、; k 8; k+) tmpi = nextil + ktmove1k; tmpj = nextjl + ktmove2k; if(tmpi 0 | tmpj 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; int main() int startx, star

15、ty; int i, j; printf(輸入起始點(diǎn)：); scanf(%d %d, &startx, &starty); if(travel(startx, starty) printf(游歷完成！n); else printf(游歷失?。); for(i = 0; i 8; i+) for(j = 0; j 8; j+) printf(%2d , boardij); putchar(n); return 0; 實(shí)驗(yàn)三 計(jì)算幾何算法的實(shí)現(xiàn)實(shí)驗(yàn)名稱實(shí)驗(yàn)二 計(jì)算幾何算法的實(shí)現(xiàn)姓 名汪子成系院專業(yè)信息工程系班 級計(jì)算機(jī)15-1班學(xué) 號2015216758實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成 績一、實(shí)驗(yàn)?zāi)康暮?/p>

16、要求1. 理解線段的性質(zhì)、叉積和有向面積。2. 掌握尋找凸包的算法。3. 綜合運(yùn)用計(jì)算幾何和搜索中的知識求解有關(guān)問題。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1預(yù)習(xí)ICPC講義，大致了解計(jì)算幾何算法的相關(guān)內(nèi)容。2了解實(shí)現(xiàn)該算法的中一些使用方法。3會使用該算法解決實(shí)際問題。三、實(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. 房間最短路問題：給頂一個(gè)內(nèi)含阻礙墻的房間，求解出一條從起點(diǎn)到終點(diǎn)的最最短路徑。房 間的邊界固定在x=0,x

17、=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ū)間，輸出最短路的長度。下圖是個(gè)例子：四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）3.思考：用跨立方法。線段相交滿足且只需滿足如下兩個(gè)條件就可以了：1 兩條線段相互跨立；2 一條線段的一個(gè)端點(diǎn)在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對方。若p1p2跨立p3p4 ，則矢量 ( p1 p3 ) 和( p2 - p1 )位于矢量( p4 p3 )的兩側(cè)，即( p1 p3） ( p4- p3 ) * ( p2 p3 ) ( p4

18、p3 ) 0。當(dāng)( p1 p3 ) ( p4p3 ) = 0 時(shí)，說明( p1 p3 ) 和 ( p4 p3 )共線，但是因?yàn)橐呀?jīng)通過快速排斥試驗(yàn)，所以 p1 一定在線段 p3p4上；同理，( p4 p3 ) (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()

19、用于判斷p1、p2構(gòu)成的線段和p3、p4構(gòu)成的線段是否相交?？梢钥闯龉参宸N情況兩線段是相交的，反之就輸出“The two are Not intersected!”4.房間最短路問題：#include #include #include #include using namespace std; typedef pair POINT; double direction(POINT p,POINT p1,POINT p2) POINT v1,v2; v1.first=p2.first-p1.first; v1.second=p2.second-p1.first; v2.first=p1.firs

20、t-p.first; v2.second=p1.second-p.second; return v1.first*v2.second-v1.second*v2.second; bool on_segment(POINT p,POINT p1,POINT p2) double min_x=p1.firstp2.first?p1.first:p2.first; double min_y=p1.secondp2.second?p1.second:p2.second; if(p.first=min_x&p.first= min_y&p.second=max_y) return true; else r

21、eturn false; POINT startPoint; bool sortByPolorAngle(const POINT &p1,const POINT &p2) double d=direction(startPoint,p1,p2); if(d0)return false; if(d=0&on_segment(startPoint,p1,p2)return true; if(d= =0&on_segment(p2,startPoint,p1)return true; return false; void find_convex_hull(vector&point) POINT p0

22、=point0; int k=0; for(int i=0;ipoint.size();i+) if(pointi.secondp0.second| pointi.second=p0.second&pointi.firstp0.first) p0=pointi; k=i; point.erase(point.begin()+k); point.insert(point.begin(),p0); vectorconvex_hull; do convex_hull.push_back(point0); startPoint=point0; point.erase(point.begin(); so

23、rt(point.begin(),point.end(),sortByPolorAngle); if(point0=convex_hull0)break; point.push_back(convex_hullconvex_hull.size()-1); while(1); for(int j=0;jconvex_hull.size();j+) coutconvex_hullj.first convex_hullj.secondendl; int main() vector pv; double x,y; int i; cout請輸入10個(gè)點(diǎn)：endl; for(i=1;i=10;i+) co

24、utNo.ixy;pv.push_back(make_pair(x,y); coutendl; find_convex_hull(pv); system(Pause); return 0; 實(shí)驗(yàn)四 動態(tài)規(guī)劃算法的實(shí)現(xiàn)實(shí)驗(yàn)名稱實(shí)驗(yàn)四 動態(tài)規(guī)劃算法的實(shí)現(xiàn)姓 名汪子成系院專業(yè)信息工程系班 級計(jì)算機(jī)15-1班學(xué) 號2015216758實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成 績一、實(shí)驗(yàn)?zāi)康暮鸵?理解動態(tài)規(guī)劃的基本思想、動態(tài)規(guī)劃算法的基本步驟 2掌握動態(tài)規(guī)劃算法實(shí)際步驟二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1動態(tài)規(guī)劃算法的基本要素2最長公共子序列3矩陣連乘問題三、實(shí)驗(yàn)項(xiàng)目摘要(1) 求兩個(gè)字符串的最長公共子序列。 - 151 - X的一個(gè)

25、子序列是相應(yīng)于X下標(biāo)序列1, 2, , m的一個(gè)子序列，求解兩個(gè)序列的所有子序列中長度最大的，例如輸入：pear, peach輸出：pea。 (2) 給定兩個(gè)字符串a(chǎn)和b，現(xiàn)將串a(chǎn)通過變換變?yōu)榇産，可用的操作為，刪除串a(chǎn)中的一 個(gè)字符；在串a(chǎn)的某個(gè)位置插入一個(gè)元素；將串a(chǎn)中的某個(gè)字母換為另一個(gè)字母。對于任意的串a(chǎn)和串b，輸出最少多少次能夠?qū)⒋優(yōu)榇産。 思考：輸出變換的步驟。 (3) 輸入一個(gè)矩陣，計(jì)算所有的子矩陣中和的最大值。 例如，輸入 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 輸出為：15 思考：當(dāng)矩陣很大時(shí)，比如100*100的矩陣，你的程序還能夠很

26、快的得出結(jié)果嗎，如果不能，請思考如何用動態(tài)規(guī)劃的思想解決。 四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）源代碼如下：1.求兩個(gè)字符串的最長公共子序列。#include #include using namespace std; void longest(string s1,string s2) int max,tep,i,j; int a100100; for(i=0;is1.size();i+) for(j=0;js2.size();j+) aij=0; for (j=0;js2.size();j+) if (s10=s2j) a0j=1; for (i=0;is1.size();i+) if (s1i=s20) ai0=1; max=a00; tep=0