程序設(shè)計(jì)藝術(shù)與方法(共16頁(yè))

1、程序設(shè)計(jì)(chn x sh j)藝術(shù)與方法實(shí)驗(yàn)(shyn)一 STL 的熟悉(shx)與使用1 實(shí)驗(yàn)?zāi)康?（1） 掌握 C+中 STL 的容器類(lèi)的使用。 （2） 掌握C+中 STL 的算法類(lèi)的使用。2 試驗(yàn)設(shè)備 硬件環(huán)境：PC 計(jì)算機(jī) 軟件環(huán)境： 操作系統(tǒng)：Windows 2000 / Windows XP / Linux 語(yǔ)言環(huán)境：Dev cpp / gnu c+ 3 試驗(yàn)內(nèi)容 (1) 練習(xí) vector 和 list 的使用。 定義一個(gè)空的 vector，元素類(lèi)型為 int，生成 10 個(gè)隨機(jī)數(shù)插入到 vector 中，用迭代 器遍歷 vector 并輸出其中的元素值。在 vector 頭

2、部插入一個(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í)泛型算法的使用。 - 149 定義一個(gè) vector，元素類(lèi)型為 int，插入 10 個(gè)隨機(jī)數(shù)，使用 sort 按升序排序，輸出 每個(gè)元素的值，再按降敘排序，輸出每個(gè)元素的

3、值。練習(xí)用 find 查找元素。用 min 和 max 找出容器中的小元素個(gè)大元素，并輸出。源代碼：#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(),sortup); vector:i

4、terator 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最小元素(yun s)為 minmax)max=(*it1); cout最大元素(yun s)為 maxendl; coutendl; int value=rand(); it1=find(myV.begin(),myV.end(),value); if(*i

5、t1)=value) cout找到了這個(gè)(zh ge)隨機(jī)數(shù)endl ; else cout沒(méi)有找到這個(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)

6、setw(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); return 0;運(yùn)行(ynxng)截圖：2 練習(xí)泛型算法(sun f)的使用：源代碼：#include#include/#incluedusing namespace std;typedef list lin;int value=1,2,3,4,5; v

7、oid print(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)的元素(yun s)為：;print(lin2);lin2.sort();cout排序(pi x)后的lin2: ;print(lin2);lin2.push_front(10); co

8、ut在list頭部插入(ch r)10之后的結(jié)果：; print(lin2);lin2.remove(6);cout刪除一個(gè)數(shù)后的lin1:; print(lin2); system(PAUSE); return 0;運(yùn)行截圖：實(shí)驗(yàn)二 搜索算法的實(shí)現(xiàn)1. 實(shí)驗(yàn)?zāi)康?(1) 掌握寬度優(yōu)先搜索算法。 (2) 掌握深度優(yōu)先搜索算法。 2. 試驗(yàn)設(shè)備 硬件環(huán)境：PC 計(jì)算機(jī) 軟件環(huán)境： 操作系統(tǒng)：Windows 2000 / Windows XP / Linux 語(yǔ)言環(huán)境：Dev cpp / gnu c+ 3. 試驗(yàn)內(nèi)容 (1) 將書(shū)上的走迷宮代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果，并注意體會(huì)搜索的思想。 (2) 八

9、皇后問(wèn)題：在一個(gè)國(guó)際象棋棋盤(pán)上放八個(gè)皇后，使得任何兩個(gè)皇后之間不相互攻擊，求出所有的布棋方法。上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。 思考：將此題推廣到 N 皇后的情況，檢驗(yàn)在 N 比較大的情況下，比方說(shuō) N=16 的時(shí) 候，你的程序能否快速的求出結(jié)果，如果不能，思考有什么方法能夠優(yōu)化算法。 (3) 騎士游歷問(wèn)題： 在國(guó)際棋盤(pán)上使一個(gè)騎士遍歷所有的格子一遍且僅一遍，對(duì)于任意給定的頂點(diǎn)， 輸出一條符合上述要求的路徑。 (4) 倒水問(wèn)題：給定 2 個(gè)沒(méi)有刻度容器，對(duì)于任意給定的容積，求出如何只用兩個(gè)瓶裝出 L 升 的水，如果可以，輸出步驟，如果不可以，請(qǐng)輸出 No Solution。（2）八皇后(hunghu)問(wèn)題

10、源代碼：#include using namespace std;#include int sum = 0;int upperlimit = 1;void compare(int row,int ld,int rd)if(row!=upperlimit)int pos=upperlimit&(row|ld|rd); while(pos!=0)int p=pos&-pos;pos-=p;compare(row+p,(ld+p)1);elsesum+;int main()int n;coutn;upperlimit = (upperlimitn)-1;compare(0,0,0);cout問(wèn)題(w

11、nt)的解如下:sumendl;return 0;運(yùn)行截圖：（4）倒水問(wèn)題(wnt)源代碼：4.倒水問(wèn)題(wnt)：#includestdio.hint 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); else x=y=0; if(caca-x) /如果(rgu)b中的水大于a中的剩余(shngy)容積，就把a(bǔ)灌滿(mǎn)/ y-=ca-x; x=ca; printf(p

12、our B An); else /如果(rgu)b中的水小于a中的剩余容積，那么把b中的水全加入a/ x+=y; y=0; printf(pour B An); if(y=cc) /如果b中的水已經(jīng)和cc相等，那就結(jié)束/ break; if(ca=x) /如果a中的水滿(mǎn)了，就把a(bǔ)倒空/ x=0; printf(empty An); else while(1) if(x=0) x=ca; printf(fill An); if(xcb-y) /如果(rgu)a中的水大于b中的剩余(shngy)容積，就把b灌滿(mǎn)/ x-=cb-y; y=cb; printf(pour A Bn); else /如果

13、(rgu)a中的水小于b中的剩余容積，那么把a(bǔ)中的水全加入b/ y+=x; x=0; printf(pour A Bn); if(y=cc) /如果b中的水已經(jīng)和cc相等，那就結(jié)束/ break; if(y=cb) /如果b中的水滿(mǎn)了，就把b倒空/ y=0; printf(empty Bn); printf(successn); return 0;運(yùn)行(ynxng)截圖:實(shí)驗(yàn)(shyn)三 計(jì)算幾何算法(sun f)的實(shí)現(xiàn)1. 實(shí)驗(yàn)?zāi)康?(1) 理解線(xiàn)段的性質(zhì)、叉積和有向面積。 (2) 掌握尋找凸包的算法。 (3) 綜合運(yùn)用計(jì)算幾何和搜索中的知識(shí)求解有關(guān)問(wèn)題。 2. 試驗(yàn)設(shè)備 硬件環(huán)境：PC

14、計(jì)算機(jī) 軟件環(huán)操作系統(tǒng)：Windows 2000 / Windows XP / Linux 語(yǔ)言環(huán)境：Dev cpp / gnu c+ 3. 試驗(yàn)內(nèi)容 (1) 將講義第三章第三節(jié)中的凸包代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。 (2) 完成講義第三章的課后習(xí)題，上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。 (3) 思考： 判線(xiàn)段相交時(shí)，如果有個(gè)線(xiàn)段的端點(diǎn)在另一條線(xiàn)段上，注意可能與另一條線(xià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

15、 個(gè) 墻，每個(gè)墻有兩個(gè)門(mén)。輸入給定的墻的個(gè)數(shù)，每個(gè)墻的 x 位置和兩個(gè)門(mén)的 y 坐標(biāo)區(qū)間， 輸出最短路的長(zhǎng)度。（4）房間(fngjin)短路問(wèn)題源代碼： #include #include #include #include using namespace std; typedef pair POINT;/線(xiàn)段(xindun) 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.first-p.

16、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 retur

17、n 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=point

18、0; 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(); sort(poi

19、nt.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請(qǐng)輸入(shr)10個(gè)點(diǎn)：endl; for(i=1;i=10;i+) cou

20、tNo.ixy;pv.push_back(make_pair(x,y); coutendl; find_convex_hull(pv); system(Pause); return 0; 運(yùn)行(ynxng)截圖：實(shí)驗(yàn)(shyn)四 動(dòng)態(tài)規(guī)劃算法的實(shí)現(xiàn)1. 實(shí)驗(yàn)?zāi)康?(1) 理解動(dòng)態(tài)規(guī)劃的基本思想、動(dòng)態(tài)規(guī)劃算法的基本步驟。 (2) 掌握動(dòng)態(tài)規(guī)劃算法實(shí)際步驟。 2. 試驗(yàn)設(shè)備 硬件環(huán)境：PC 計(jì)算機(jī) 軟件環(huán)境： 操作系統(tǒng)：Windows 2000 / Windows XP / Linux 語(yǔ)言環(huán)境：Dev cpp / gnu c+ 3. 試驗(yàn)內(nèi)容 (1) 求兩個(gè)字符串的最長(zhǎng)公共子序列。 X 的一個(gè)

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

22、：15 思考：當(dāng)矩陣很大時(shí)，比如 100*100 的矩陣，你的程序還能夠很快的得出結(jié)果嗎，如果 不能，請(qǐng)思考如何用動(dòng)態(tài)規(guī)劃的思想解決求兩個(gè)字符串的最長(zhǎng)公共子序列源代碼：#include#include#define N 100using namespace std;/str1存儲(chǔ)字符串x，str2存儲(chǔ)字符串ychar str1N,str2N;/lcs存儲(chǔ)最長(zhǎng)公共子序列char lcsN;/cij存儲(chǔ)str11.i與str21.j的最長(zhǎng)公共子序列的長(zhǎng)度int cNN;/flagij=0為str1i=str2j/flagij=1為ci-1j=sij-1/flagij=-1為ci-1jsij-1int flagNN;/求長(zhǎng)度int LCSLength(char *x, char *y) int i,j; /分別取得x,y的長(zhǎng)度 int m = strlen(x); int n = strlen(y); for(i=1;i=m;i+) ci0 = 0; for(i=0;i=n;i