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

程序設(shè)計(jì)藝術(shù)與方法程序設(shè)計(jì)藝術(shù)與方法程序設(shè)計(jì)藝術(shù)與方法xxx公司程序設(shè)計(jì)藝術(shù)與方法文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度程序設(shè)計(jì)藝術(shù)與方法實(shí)驗(yàn)一STL的熟悉與使用1．實(shí)驗(yàn)?zāi)康模?）掌握C++中STL的容器類(lèi)的使用。（2）掌握C++中STL的算法類(lèi)的使用。2．試驗(yàn)設(shè)備硬件環(huán)境：PC計(jì)算機(jī)軟件環(huán)境：操作系統(tǒng)：Windows2000/WindowsXP/Linux語(yǔ)言環(huán)境：Devcpp/gnuc++3．試驗(yàn)內(nèi)容(1)練習(xí)vector和list的使用。定義一個(gè)空的vector，元素類(lèi)型為int，生成10個(gè)隨機(jī)數(shù)插入到vector中，用迭代器遍歷vector并輸出其中的元素值。在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í)泛型算法的使用。-149定義一個(gè)vector，元素類(lèi)型為int，插入10個(gè)隨機(jī)數(shù)，使用sort按升序排序，輸出每個(gè)元素的值，再按降敘排序，輸出每個(gè)元素的值。練習(xí)用find查找元素。用min和max找出容器中的小元素個(gè)大元素，并輸出。源代碼：#include<iostream>#include<vector>#include<iomanip>#include<ctime>#include<algorithm>usingnamespacestd;vector<int>myV;boolsortup(intv1,intv2){returnv1<v2;}intmain(intargc,char*argv[]){srand(time(NULL));for(inti=0;i<10;i++)(rand());sort(),(),sortup);vector<int>::iteratorit1;for(it1=();it1!=();it1++){cout<<(*it1)<<setw(6);}cout<<endl;intmin=myV[0]; for(it1=()+1;it1!=();it1++)if((*it1)<min)min=(*it1);cout<<"最小元素為"<<min<<endl;intmax=myV[0];for(it1=();it1!=();it1++)if((*it1)>max)max=(*it1);cout<<"最大元素為"<<max<<endl;cout<<endl;intvalue=rand();it1=find(),(),value);if((*it1)==value)cout<<"找到了這個(gè)隨機(jī)數(shù)"<<endl;elsecout<<"沒(méi)有找到這個(gè)隨機(jī)數(shù)"<<endl;(),value);cout<<"插入尾部的隨機(jī)數(shù)為"<<value<<endl;for(it1=();it1!=();it1++){cout<<(*it1)<<setw(6);}cout<<"\n"<<endl;intt=rand();(),t);cout<<"插入頭部的隨機(jī)數(shù)為"<<t<<endl;for(it1=();it1!=();it1++){cout<<(*it1)<<setw(6);}cout<<endl;();for(it1=();it1!=();it1++){cout<<(*it1)<<setw(6);}cout<<endl;();if()){cout<<"It'sempty!"<<endl;}system("PAUSE");return0;}運(yùn)行截圖：2練習(xí)泛型算法的使用：源代碼：#include<list>#include<iostream>實(shí)驗(yàn)?zāi)康?1)掌握寬度優(yōu)先搜索算法。(2)掌握深度優(yōu)先搜索算法。2.試驗(yàn)設(shè)備硬件環(huán)境：PC計(jì)算機(jī)軟件環(huán)境：操作系統(tǒng)：Windows2000/WindowsXP/Linux語(yǔ)言環(huán)境：Devcpp/gnuc++3.試驗(yàn)內(nèi)容(1)將書(shū)上的走迷宮代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果，并注意體會(huì)搜索的思想。(2)八皇后問(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)輸出NoSolution。（2）八皇后問(wèn)題源代碼：#include<iostream>usingnamespacestd;#include<>intsum=0;intupperlimit=1;voidcompare(introw,intld,intrd){ if(row!=upperlimit){ intpos=upperlimit&~(row|ld|rd);while(pos!=0) { intp=pos&-pos;pos-=p;compare(row+p,(ld+p)<<1,(rd+p)>>1); }}else{sum++;}}intmain(){ intn; cout<<"請(qǐng)輸入皇后的個(gè)數(shù):"; cin>>n; upperlimit=(upperlimit<<n)-1; compare(0,0,0); cout<<"問(wèn)題的解如下:"<<sum<<endl; return0;}運(yùn)行截圖：

（4）倒水問(wèn)題源代碼：4.倒水問(wèn)題：#include""intmain(){intca,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");printf("pourAB\n");}else{x=y=0;if(ca<cc){while(1){if(y==0){y=cb;printf("fillB\n");}if(y>ca-x)實(shí)驗(yàn)?zāi)康?1)理解線段的性質(zhì)、叉積和有向面積。(2)掌握尋找凸包的算法。(3)綜合運(yùn)用計(jì)算幾何和搜索中的知識(shí)求解有關(guān)問(wèn)題。2.試驗(yàn)設(shè)備硬件環(huán)境：PC計(jì)算機(jī)軟件環(huán)操作系統(tǒng)：Windows2000/WindowsXP/Linux語(yǔ)言環(huán)境：Devcpp/gnuc++3.試驗(yàn)內(nèi)容(1)將講義第三章第三節(jié)中的凸包代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。(2)完成講義第三章的課后習(xí)題，上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。(3)思考：判線段相交時(shí)，如果有個(gè)線段的端點(diǎ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個(gè)墻，每個(gè)墻有兩個(gè)門(mén)。輸入給定的墻的個(gè)數(shù)，每個(gè)墻的x位置和兩個(gè)門(mén)的y坐標(biāo)區(qū)間，輸出最短路的長(zhǎng)度。（4）房間短路問(wèn)題源代碼：#include<iostream>#include<utility>#include<vector>#include<algorithm>usingnamespacestd;typedefpair<double,double>POINT;econd<||point[i].second==&&point[i].first<{p0=point[i];k=i;}}()+k);(),p0);vector<POINT>convex_hull;do{(point[0]);startPoint=point[0];());sort(),(),sortByPolorAngle);if(point[0]==convex_hull[0])break;(convex_hull[()-1]);}while(1);for(intj=0;j<();j++){cout<<convex_hull[j].first<<''<<convex_hull[j].second<<endl;}}intmain(){vector<POINT>pv;doublex,y;inti;cout<<"請(qǐng)輸入10個(gè)點(diǎn)<x,y>："<<endl;for(i=1;i<=10;i++){cout<<"No."<<i<<':';cin>>x>>y;(make_pair(x,y));}cout<<endl;find_convex_hull(pv);system("Pause");return0;}運(yùn)行截圖：實(shí)驗(yàn)四動(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)：Windows2000/WindowsXP/Linux語(yǔ)言環(huán)境：Devcpp/gnuc++3.試驗(yàn)內(nèi)容(1)求兩個(gè)字符串的最長(zhǎng)公共子序列。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)通過(guò)變換變?yōu)榇産，可用的操作為，刪除串a(chǎn)中的一個(gè)字符；在串a(chǎn)的某個(gè)位置插入一個(gè)元素；將串a(chǎn)中的某個(gè)字母換為另一個(gè)字母。對(duì)于任意的串a(chǎn)和串b，輸出少多少次能夠?qū)⒋優(yōu)榇産。思考：輸出變換的步驟。(3)輸入一個(gè)矩陣，計(jì)算所有的子矩陣中和的大值。例如，輸入0-2-7092-62-41-41-180-2輸出為：15思考：當(dāng)矩陣很大時(shí)，比如100*100的矩陣，你的程序還能夠很快的得出結(jié)果嗎，如果不能，請(qǐng)思考如何用動(dòng)態(tài)規(guī)劃的思想解決求兩個(gè)字符串的最長(zhǎng)公共子序列源代碼：#include<cstring>#include<iostream>#defineN100usingnamespacestd;.i]與str2[1...j]的最長(zhǎng)公共子序列的長(zhǎng)度intc[N][N];//flag[i][j]==0為str1[i]==str2[j]//flag[i][j]==1為c[i-1][j]>=s[i][j-1]//flag[i][j]==-1為c[i-1][j]<s[i][j-1]intflag[N][N];//求長(zhǎng)度intLCSLength(char*x,char*y){inti,j;//分別取得x,y的長(zhǎng)度intm=strlen(x);intn=strlen(y);for(i=1;i<=m;i++)c[i][0]=0;for(i=0;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;flag[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];flag[i][j]=1;}else{c[i][j]=c[i][j-1];flag[i][j]=-1;}