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

1、程序設(shè)計(jì)藝術(shù)與方法課程實(shí)驗(yàn)報(bào)告 學(xué)號(hào)： 姓名：周旋 2015.10.10實(shí)驗(yàn)一 STL的熟悉與使用實(shí)驗(yàn)名稱實(shí)驗(yàn)一 STL 的熟悉與使用姓 名周旋系院專業(yè)信息工程系班 級(jí)計(jì)算機(jī)14-4班學(xué) 號(hào)實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成 績(jī)一、實(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的使用2練習(xí)泛型算法的使用四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）以下程序?qū)崿F(xiàn)了下述幾個(gè)功能：1 定義一個(gè)vecto

2、r，生成十個(gè)隨機(jī)數(shù)插入到vector中。2 多次使用迭代器iterator遍歷vector，輸出完成不同功能的vector元素。3 使用泛型算法find 查找vector中的隨機(jī)數(shù)，如果找到輸出該隨機(jī)數(shù)，如果沒找到將該隨機(jī)數(shù)插入到vector中。4 使用泛型算法 sort 對(duì)vector中的元素進(jìn)行升序與降序排列，使用迭代器iterator輸出。5 使用min, max算法求出vector中的最小值與最大值。6 刪除vector 中的尾部元素以及全部元素，輸出vector的大小。（注：源代碼見下頁）#include #include #include #include using namesp

3、ace std;vector vint;int main() int i; for (i=0;i10;i+) int r = rand()%99+0; vint.push_back(r); vector :iterator pit1; for (pit1=vint.begin();pit1!=vint.end();pit1+) cout *pit1 ; cout endl; int temp; temp = rand()%99+0; vector :iterator pit2; pit2 = find (vint.begin(),vint.end(),temp); if (pit2!=vint

4、.end() cout The number has been found ! endl; cout The number is: temp endl; else cout Sorry! The number has not been found! Please try again ! endl; vint.push_back(temp); random_shuffle(vint.begin(),vint.end(); cout The max number is : *max_element(vint.begin(),vint.end() endl; cout The min number

5、is : *min_element(vint.begin(),vint.end() endl; cout 數(shù)組升序排列的結(jié)果為: endl; vector :iterator pit3; sort (vint.begin(),vint.end(); for (pit3=vint.begin();pit3!=vint.end();pit3+) cout *pit3 ; cout endl; cout 數(shù)組降序排列的結(jié)果為: endl; vector :iterator pit4; sort (vint.rbegin(),vint.rend(); for (pit4=vint.begin();pi

6、t4!=vint.end();pit4+) cout *pit4 ; cout endl; vint.pop_back(); cout 數(shù)組的大小為: vint.size() endl; vint.erase (vint.begin(),vint.end(); cout 數(shù)組的大小為: vint.size() endl; return 0;實(shí)驗(yàn)二 搜索算法的實(shí)現(xiàn)實(shí)驗(yàn)名稱實(shí)驗(yàn)二 搜索算法的實(shí)現(xiàn)姓 名周旋系院專業(yè)信息工程系班 級(jí)計(jì)算機(jī)14-4班學(xué) 號(hào)實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成 績(jī)一、實(shí)驗(yàn)?zāi)康暮鸵?掌握寬度優(yōu)先搜索算法;2掌握深度優(yōu)先搜索算法.二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1將書上的走迷宮代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果，

7、體會(huì)搜索的思想2預(yù)習(xí)n皇后問題3預(yù)習(xí)騎士游歷問題三、實(shí)驗(yàn)項(xiàng)目摘要1n皇后問題： 在一個(gè)國際象棋棋盤上放n個(gè)皇后，使得任何兩個(gè)皇后之間不相互攻擊，求出所有的布棋方法。上機(jī)運(yùn)行并檢驗(yàn)結(jié)果2騎士游歷問題： 在國際棋盤上使一個(gè)騎士遍歷所有的格子一遍且僅一遍，對(duì)于任意給定的頂點(diǎn)，輸出一條符合上述要求的路徑3倒水問題： 給定2 個(gè)沒有刻度容器，對(duì)于任意給定的容積，求出如何只用兩個(gè)瓶裝出 L 升的水，如果可以，輸出步驟，如果不可以，請(qǐng)輸出No Solution 。四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）以下僅列出八皇后問題的源代碼：#include #include using namespace std;i

8、nt 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); else sum+; int main() int n; cout n; upperlimit = (upperlimitn)-1; compare(0,0,0); cout 問題的解如下: sum endl; return 0;實(shí)驗(yàn)

9、三 計(jì)算幾何算法的實(shí)現(xiàn)實(shí)驗(yàn)名稱實(shí)驗(yàn)二 計(jì)算幾何算法的實(shí)現(xiàn)姓 名周旋系院專業(yè)信息工程系班 級(jí)計(jì)算機(jī)14-4班學(xué) 號(hào)實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成 績(jī)一、實(shí)驗(yàn)?zāi)康暮鸵?. 理解線段的性質(zhì)、叉積和有向面積。2. 掌握尋找凸包的算法。3. 綜合運(yùn)用計(jì)算幾何和搜索中的知識(shí)求解有關(guān)問題。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1預(yù)習(xí)ICPC講義，大致了解計(jì)算幾何算法的相關(guān)內(nèi)容。2了解實(shí)現(xiàn)該算法的中一些使用方法。3會(huì)使用該算法解決實(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)在另一條線段上，注意可能與另一

10、條線段上的端點(diǎn)重合，思考這樣的情況怎么辦。4. 房間最短路問題：給頂一個(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)度。下圖是個(gè)例子：四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）源代碼如下：#include#include#include#includeusing namespace std;typedef pair POINT;double direction(POINT p

11、,POINT p1,POINT p2) POINT v1,v2; v1.first = p2.first-p1.first; v1.second = p2.second-p1.second; v2.first = p1.first-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;

12、 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 return 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) r

13、eturn true; if(d=0&on_segment(p2,startPoint,p1) return true; return false;void find_convex_hull(vector&point) POINT p0=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(po

14、int.begin(),p0); vectorconvex_hull; do convex_hull.push_back(point0); startPoint=point0; point.erase(point.begin(); sort(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+) coutconv

15、ex_hullj.first convex_hullj.secondendl; int main() vector pv; double x,y; int i; cout請(qǐng)輸入10個(gè)點(diǎn)：endl; for(i=1;i=10;i+) coutNo.ixy; pv.push_back(make_pair(x,y); coutendl; find_convex_hull(pv); system(Pause); return 0;實(shí)驗(yàn)四 動(dòng)態(tài)規(guī)劃算法的實(shí)現(xiàn)實(shí)驗(yàn)名稱實(shí)驗(yàn)四 動(dòng)態(tài)規(guī)劃算法的實(shí)現(xiàn)姓 名周旋系院專業(yè)信息工程系班 級(jí)計(jì)算機(jī)14-4班學(xué) 號(hào)實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成 績(jī)一、實(shí)驗(yàn)?zāi)康暮鸵?理解動(dòng)態(tài)規(guī)

16、劃的基本思想、動(dòng)態(tài)規(guī)劃算法的基本步驟 2掌握動(dòng)態(tài)規(guī)劃算法實(shí)際步驟二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1動(dòng)態(tài)規(guī)劃算法的基本要素2最長(zhǎng)公共子序列3矩陣連乘問題三、實(shí)驗(yàn)項(xiàng)目摘要1.求兩個(gè)字符串的最長(zhǎng)公共子序列。 - 151 -X 的一個(gè)子序列是相應(yīng)于X 下標(biāo)序列1, 2, , m 的一個(gè)子序列，求解兩個(gè)序列的所有子序列中長(zhǎng)度最大的，例如輸入：pear, peach 輸出：pea。2給定兩個(gè)字符串a(chǎn) 和b ，現(xiàn)將串a(chǎn) 通過變換變?yōu)榇産 ，可用的操作為，刪除串a(chǎn) 中的一個(gè)字符；在串 a 的某個(gè)位置插入一個(gè)元素；將串 a 中的某個(gè)字母換為另一個(gè)字母。對(duì)于任意的串a(chǎn) 和串b ，輸出最少多少次能夠?qū)⒋優(yōu)榇?b 。3輸入一個(gè)矩陣

17、，計(jì)算所有的子矩陣中和的最大值。 四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）源代碼如下：#include#includeusing namespace std;int min(int x1,int x2, int x3) if(x2x1) x1=x2; else if(x3x1) x1=x3; return x1;void change(string s1,string s2) int N,i; const char * str=s1.c_str(); const char * tep=s2.c_str(); int bNN; b00=0; for(int i=1;i=s1.length();i+) b0i=i; for(int j=1;j