9、：
#include
#include
using namespace std;
typedef list lin;
int value[]={1,6,7,8,9};
void print(lin &l)
{
int i;
lin::iterator lit;
for(lit=l.begin();lit!=l.end();lit++)
cout<<(*lit)<<" ";
cout<v2;
}
10、
int main(){
lin lin2;
lin2.push_front(3);
lin2.push_front(4);
lin2.insert(lin2.begin(),value,value+5);
cout<<"lin2內(nèi)的元素為：";
print(lin2);
lin2.sort();
cout<<"排序后的lin2: ";
print(lin2);
lin2.push_front(10);
cout<<"在list頭部插入10之后的結(jié)果：";
print(lin2);
lin2.remove(6);
cout<<"刪除一個數(shù)后的lin1:";
11、
print(lin2);
system("PAUSE");
return 0;
}
實(shí)驗(yàn)二 搜索算法的實(shí)現(xiàn)
實(shí)驗(yàn)名稱
實(shí)驗(yàn)二 搜索算法的實(shí)現(xiàn)
姓 名
汪子成
系院專業(yè)
信息工程系
班 級
計算機(jī)15-1班
學(xué) 號
2015216758
實(shí)驗(yàn)日期
指導(dǎo)教師
徐本柱
成 績
一、實(shí)驗(yàn)?zāi)康暮鸵?
1．掌握寬度優(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)項目摘要
1. 將書上的走迷宮代碼上機(jī)運(yùn)
12、行并檢驗(yàn)結(jié)果，并注意體會搜索的思想。
2.八皇后問題：在一個國際象棋棋盤上放八個皇后，使得任何兩個皇后之間不相互攻擊，求出所有的布棋方法。上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。
3. 騎士游歷問題：在國際棋盤上使一個騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂點(diǎn)，輸出一條符合上述要求的路徑。
4.倒水問題：給定2 個沒有刻度容器，對于任意給定的容積，求出如何只用兩個瓶裝出L 升
的水，如果可以，輸出步驟，如果不可以，請輸出No Solution
四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）
2，八皇后問題：
#include
#define N 8
#define NUM 8
13、
int h[N][N],n[N],H[N][N];
int count=0;
void tryit(int,int);
void outputArray(int[][N]);
main()
{
int x=0,y=0,i,j;
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
h[i][j]=0;
}
tryit(x,y);
printf("......\n");
printf("共有%d種布局.\n",92);
return(0);
}
void tryit(int x,int y)
{
14、int i,j;
if(count<=NUM)
{
if((H[0][0]==1&&H[1][4]==1&&H[2][7]==1&&H[3][5]==1&&H[4][2]==1&&H[5][6]==1&&H[6][1]==1&&H[7][3]==1)&&count!=1)
{}
else
{
if(x>=0&&x<=N-1&&y>=0&&y<=N-1&&h[x][y]==0)
{
for(j=0;j<=7;j++)
{
if(h[x][j]==0)
h[x][j]=x+1;
if(h[j][y]==0)
15、 h[j][y]=x+1;
if(x+j>=0&&x+j<=N-1&&y+j>=0&&y+j<=N-1&&h[x+j][y+j]==0)
h[x+j][y+j]=x+1;
if(x+j>=0&&x+j<=N-1&&y-j>=0&&y-j<=N-1&&h[x+j][y-j]==0)
h[x+j][y-j]=x+1;
if(x-j>=0&&x-j<=N-1&&y+j>=0&&y+j<=N-1&&h[x-j][y+j]==0)
h[x-j][y+j]=x+1;
if(x-j>=0&&x-j<=N-1&&y-j>=0&
16、&y-j<=N-1&&h[x-j][y-j]==0)
h[x-j][y-j]=x+1;
}
h[x][y]=-x-1;
if(x==7)
{
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
{
if(h[i][j]<0)
H[i][j]=1;
else
H[i][j]=0;
}
}
count=count+1;
if(count<=NUM)
{
pr
17、intf("------布局%d------\n",count);
outputArray(H);
}
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
{
if(h[i][j]==x||h[i][j]==-x||h[i][j]==-x-1)
h[i][j]=0;
}
}
tryit(x-1,n[x-1]+1);
}
else
{
n[x]=y;
tryit(x+1,
18、0);
}
}
else
{
if(y>7)
{
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
{
if(h[i][j]==x||h[i][j]==-x)
h[i][j]=0;
}
}
if(x-1>=0)
tryit(x-1,n[x-1]+1);
else
tryit(0,0);
}
else
tryit(x,y+1);
}
}
}
}
19、
void outputArray(int h[][N])
{
int i,j;
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
printf("%d ",h[i][j]);
printf("\n");
}
}
3. 騎士游歷問題：
#include
int board[8][8] = {0};
int travel(int x, int y)
{
int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int ktmove2[8
20、] = {1, 2, 2, 1, -1, -2, -2, -1};
int nexti[8] = {0};
int nextj[8] = {0};
int exists[8] = {0};
int i, j, k, m, l;
int tmpi, tmpj;
int count, min, tmp;
i = x;
j = y;
board[i][j] = 1;
for(m = 2; m <= 64; m++) {
for(l = 0; l < 8; l++)
exists[l] = 0;
l = 0;
for(k = 0; k < 8; k+
21、+) {
tmpi = i + ktmove1[k];
tmpj = j + ktmove2[k];
if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7)
continue;
if(board[tmpi][tmpj] == 0) {
nexti[l] = tmpi;
nextj[l] = tmpj;
l++;
}
}
count = l;
if(count == 0) {
return 0;
}
else if(count == 1) {
min = 0;
}
else {
22、for(l = 0; l < count; l++) {
for(k = 0; k < 8; k++) {
tmpi = nexti[l] + ktmove1[k];
tmpj = nextj[l] + ktmove2[k];
if(tmpi < 0 || tmpj < 0 ||
tmpi > 7 || tmpj > 7) {
continue;
}
if(board[tmpi][tmpj] == 0)
exists[l]++;
}
}
tmp = exists[0];
min = 0;
for(l = 1; l < count; l++
23、) {
if(exists[l] < tmp) {
tmp = exists[l];
min = l;
}
}
}
i = nexti[min];
j = nextj[min];
board[i][j] = m;
}
return 1;
}
int main()
{
int startx, starty;
int i, j;
printf("輸入起始點(diǎn)："); scanf("%d %d", &startx, &starty);
if(travel(startx, starty)) {
printf("游歷完成！\n");
24、
}
else {
printf("游歷失敗！\n");
}
for(i = 0; i < 8; i++) {
for(j = 0; j < 8; j++) {
printf("%2d ", board[i][j]);
}
putchar('\n');
}
return 0;
}
實(shí)驗(yàn)三 計算幾何算法的實(shí)現(xiàn)
實(shí)驗(yàn)名稱
實(shí)驗(yàn)二 計算幾何算法的實(shí)現(xiàn)
姓 名
汪子成
系院專業(yè)
信息工程系
班 級
計算機(jī)15-1班
學(xué) 號
2015216758
實(shí)驗(yàn)日期
指導(dǎo)教師
徐本柱
成 績
25、
一、實(shí)驗(yàn)?zāi)康暮鸵?
1. 理解線段的性質(zhì)、叉積和有向面積。
2. 掌握尋找凸包的算法。
3. 綜合運(yùn)用計算幾何和搜索中的知識求解有關(guān)問題。
二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容
1．預(yù)習(xí)ICPC講義，大致了解計算幾何算法的相關(guān)內(nèi)容。
2．了解實(shí)現(xiàn)該算法的中一些使用方法。
3．會使用該算法解決實(shí)際問題。
三、實(shí)驗(yàn)項目摘要
1. 將講義第三章第三節(jié)中的凸包代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。
2. 完成講義第三章的課后習(xí)題，上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。
3. 思考：判線段相交時，如果有個線段的端點(diǎn)在另一條線段上，注意可能與另一條線段上的端點(diǎn)重合，思考這樣的情況怎么辦。
4. 房間最短路問題：給頂一個內(nèi)含阻
26、礙墻的房間，求解出一條從起點(diǎn)到終點(diǎn)的最最短路徑。房 間的邊界固定在x=0,x=10,y=0 和y=10。起點(diǎn)和重點(diǎn)固定在(0,5)和(10,5)。房間里還有0 到18 個墻，每個墻有兩個門。輸入給定的墻的個數(shù)，每個墻的x 位置和兩個門的y 坐標(biāo)區(qū)間，輸出最短路的長度。下圖是個例子：
四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）
3.思考：
用跨立方法。線段相交滿足且只需滿足如下兩個條件就可以了：1 兩條線段相互跨立；2 一條線段的一個端點(diǎn)在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對方。若p1p2跨立p3p4 ，則矢量 ( p1 –p3 ) 和( p2 - p1 )位于矢量(
27、 p4 – p3 )的兩側(cè)，即( p1 –p3） × ( p4- p3 ) * ( p2 – p3 ) × ( p4 –p3 ) < 0。上式可改寫成( p1 – p3 ) × ( p4- p3 ) * ( p4 – p3 ) × ( p2 – p3) > 0。當(dāng)( p1 –p3 ) × ( p4–p3 ) = 0 時，說明( p1 – p3 ) 和 ( p4 – p3 )共線，但是因?yàn)橐呀?jīng)通過快速排斥試驗(yàn)，所以 p1 一定在線段 p3p4上；同理，( p4 – p3 ) ×(p2 – p3 ) = 0 說明 p2 一定在 p3p4上。所以判斷p1p2跨立Q1Q2的依據(jù)是：( p1 – p3
28、) × ( p4 – p3 ) * ( p4 – p3 ) × ( p2–p3 ) >= 0。同理判斷Q1Q2跨立P1P2的依據(jù)是：( p3 - p1 ) × ( p2 - p1 ) * ( p2 - p1 ) × ( p4 - p1 ) >= 0。代碼中函數(shù)bool segment_intersect()用于判斷p1、p2構(gòu)成的線段和p3、p4構(gòu)成的線段是否相交?？梢钥闯龉参宸N情況兩線段是相交的，反之就輸出“The two are Not intersected!”
4.房間最短路問題：
#include
#include
#
29、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.first-p.first;
v2.second=p1.second-p.second;
30、
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.secondp
31、2.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(d<0)return true;
32、
if(d >0)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[0];
int k=0;
for(int i=0;i
33、point[i].secondconvex_hull;
do{
convex_hull.push_back(point[0]);
startPoint=point[0];
point.era
34、se(point.begin());
sort(point.begin(),point.end(),sortByPolorAngle);
if(point[0]==convex_hull[0])break;
point.push_back(convex_hull[convex_hull.size()-1]);
}while(1);
for(int j=0;j
35、int main(){
vector pv;
double x,y;
int i;
cout<<"請輸入10個點(diǎn)："<>x>>y;
pv.push_back(make_pair(x,y));
}
cout<
36、
實(shí)驗(yàn)四 動態(tài)規(guī)劃算法的實(shí)現(xiàn)
實(shí)驗(yàn)名稱
實(shí)驗(yàn)四 動態(tài)規(guī)劃算法的實(shí)現(xiàn)
姓 名
汪子成
系院專業(yè)
信息工程系
班 級
計算機(jī)15-1班
學(xué) 號
2015216758
實(shí)驗(yàn)日期
指導(dǎo)教師
徐本柱
成 績
一、實(shí)驗(yàn)?zāi)康暮鸵?
1．理解動態(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)項目摘要
(1) 求兩個字
37、符串的最長公共子序列。
- 151 - X的一個子序列是相應(yīng)于X下標(biāo)序列{1, 2, …, m}的一個子序列，求解兩個序列的所有子序列中長度最大的，例如輸入：pear, peach輸出：pea。
(2) 給定兩個字符串a(chǎn)和b，現(xiàn)將串a(chǎn)通過變換變?yōu)榇産，可用的操作為，刪除串a(chǎn)中的一 個字符；在串a(chǎn)的某個位置插入一個元素；將串a(chǎn)中的某個字母換為另一個字母。對于任意的串a(chǎn)和串b，輸出最少多少次能夠?qū)⒋優(yōu)榇産。 思考：輸出變換的步驟。
(3) 輸入一個矩陣，計算所有的子矩陣中和的最大值。 例如，輸入 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 輸
38、出為：15 思考：當(dāng)矩陣很大時，比如100*100的矩陣，你的程序還能夠很快的得出結(jié)果嗎，如果不能，請思考如何用動態(tài)規(guī)劃的思想解決。
四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）
源代碼如下：
1.求兩個字符串的最長公共子序列。
#include
#include
using namespace std;
void longest(string s1,string s2)
{
int max,tep,i,j;
int a[100][100];
for
39、(i=0;i
40、+)
for(j=1;j
41、 else
{
cout<<"兩個字符串的最長公共子序列為:";
for(i=tep-max+1;i<=tep;i++)
cout<>s1;
cout<<"另一個字符串為:";
cin>>s2;
longest(s1
42、,s2); cout<
#include
using namespace std;
int min(int x1,int x2, int x3)
{
if(x2
43、* str=s1.c_str();
const char * tep=s2.c_str();
int b[100][100];
b[0][0]=0;
for(int i=1;i<=s1.length();i++)
b[0][i]=i;
for(int j=1;j<=s2.length();j++)
b[j][0]=j;
for( i=1;i<=s2.length(); i++)
for(int m=1;m<=s1.length();m++)
{
if(tep[i-1]==str[m-1])
b
44、[i][m]=b[i-1][m-1];
else
b[i][m]=1+min(b[i-1][m-1],b[i-1][m],b[i][m-1]);
}
cout<<"將a變?yōu)閎需要"<>s1;
cout <<"輸入字符串b:";
cin >> s2;
change(s1,s2);
cout<
《課程實(shí)驗(yàn)報告》word版
