實驗一 STL 的熟悉不使用 實驗名稱 實驗一 STL 的熟悉不使用 姓名 汪子成 系院與業 信息工程系 班級 計算機 15-1班 學號 20XX216758 實驗日期
指導教師 徐本柱 成績
一、實驗目的和要求 1．掌握 C++中 STL 的容器類的使用; 2．掌握 C++中 STL 的算法類的使用. 二、實驗預習內容 1．預習 ICPC 講義，大致了解 STL 的相關內容。
2．了解 STL 中一些類 vectorlist 類的使用方法 3．了解泛型算法的使用 三、實驗項目摘要 (1)練習vector和list的使用。定義一個空的vector，元素類型為int，生成10個隨機數插入到vector中，用迭代器遍歷 vector 并輸出其中的元素值。在 vector 頭部插入一個隨機數，用迭代器遍歷vector 并輸出其中的元素值。用泛型算法 find 查找某個隨機數，如果找到便輸出，否則將此數插入 vector 尾部。用泛型算法 sort 將 vector 排序，用迭代器遍歷 vector 并輸出其中的元素值。刪除 vector 尾部的元素，用迭代器遍歷 vector 并輸出其中的元素值。將 vector 清空。定義一個 list，并重復上述實驗，并注意觀察結果。
(2)練習泛型算法的使用。定義一個 vector，元素類型為 int，插入 10 個隨機數，使用 sort 按升序排序，輸出每個元素的值，再按降敘排序，輸出每個元素的值。練習用 find 查找元素。用 min和 maR 找出容器中的最小元素和最大元素，并輸出。
四、實驗結果與分析（源程序及相關說明）
1.練習vector和list的使用：
#include<iostream> #include<vector> #include<iomanip> #include<ctime> #include<algorithm> usingnamespacestd; vector<int>mRV; boolsortup(intv1,intv2) { returnv1<v2; } intmain(intargc,charRargv[]) { srand(time(NULL));for(inti=0;i<10;i++) mRV.push_back(rand()); sort(mRV.begin(),mRV.end(),sortup);vector<int>::iteratorit1; for(it1=mRV.begin();it1!=mRV.end();it1++) { cout<<(Rit1)<<setw(6); } cout<<endl; intmin=mRV[0];
for(it1=mRV.begin()+1;it1!=mRV.end();it1++)
if((Rit1)<min)min=(Rit1); cout<<"最小元素為"<<min<<endl; intmaR=mRV[0]; for(it1=mRV.begin();it1!=mRV.end();it1++) if((Rit1)>maR)maR=(Rit1); cout<<"最大元素為"<<maR<<endl; cout<<endl; intvalue=rand(); it1=find(mRV.begin(),mRV.end(),value); if((Rit1)==value) cout<<"找到了這個隨機數"<<endl; else cout<<"沒有找到這個隨機數"<<endl; mRV.insert(mRV.end(),value); cout<<"插入尾部的隨機數為"<<value<<endl; for(it1=mRV.begin();it1!=mRV.end();it1++) { cout<<(Rit1)<<setw(6); } cout<<"\n"<<endl; intt=rand(); mRV.insert(mRV.begin(),t); cout<<"插入頭部的隨機數為"<<t<<endl; for(it1=mRV.begin();it1!=mRV.end();it1++) {
cout<<(Rit1)<<setw(6); } cout<<endl; mRV.pop_back(); for(it1=mRV.begin();it1!=mRV.end();it1++) { cout<<(Rit1)<<setw(6); } cout<<endl; mRV.clear(); if(mRV.emptR()) { cout<<"It"semptR!"<<endl; } sRstem("PAUSE");//pressanRkeRtocontinue... return0; }
2 練習泛型算法的使用：
#include<list> #include<iostream> usingnamespacestd; tRpedeflist<int>lin; intvalue[]={1,6,7,8,9}; voidprint(lin&l) { inti; lin::iteratorlit; for(lit=l.begin();lit!=l.end();lit++) cout<<(Rlit)<<""; cout<<endl; } boolsortsp(intv1,intv2) { returnv1>v2; } intmain(){ linlin2; lin2.push_front(3); lin2.push_front(4); lin2.insert(lin2.begin(),value,value+5); cout<<"lin2 內的元素為："; print(lin2);
lin2.sort(); cout<<"排序后的 lin2:"; print(lin2); lin2.push_front(10); cout<<"在 list 頭部插入 10 乊后的結果："; print(lin2); lin2.remove(6); cout<<"刪除一個數后的 lin1:"; print(lin2); sRstem("PAUSE"); return0; }
實驗二搜索算法的實現 實驗名稱 實驗二搜索算法的實現 姓名 汪子成 系院與業 信息工程系 班級 計算機 15-1班 學號 20XX216758 實驗日期
指導教師 徐本柱 成績
一、實驗目的和要求 1．掌握寬度優先搜索算法; 2．掌握深度優先搜索算法.
二、實驗預習內容 1．預習 ICPC 講義中的搜索的內容 2.了解什么是深度優先搜索和廣度優先搜索。
三、實驗項目摘要 1.將書上的走迷宮代碼上機運行并檢驗結果，并注意體會搜索的思想。
2.八皇后問題：在一個國際象棋棋盤上放八個皇后，使得任何兩個皇后乊間丌相互攻擊，求出所有的布棋方法。上機運行并檢驗結果。
3.騎士游歷問題：在國際棋盤上使一個騎士遍歷所有的格子一遍丏僅一遍，對于任意給定的頂點，輸出一條符合上述要求的路徑。
4.倒水問題：給定 2 個沒有刻度容器，對于任意給定的容積，求出如何只用兩個瓶裝出 L 升 的水，如果可以，輸出步驟，如果丌可以，請輸出 NoSolution
四、實驗結果與分析（源程序及相關說明）
2，八皇后問題：
#include<stdio.h> #defineN8 #defineNUM8 inth[N][N],n[N],H[N][N]; intcount=0; voidtrRit(int,int); voidoutputArraR(int[][N]); main() {
intR=0,R=0,i,j;
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
h[i][j]=0;
}
trRit(R,R);
printf("......\n");
printf("共有%d 種布局.\n",92);
return(0); } voidtrRit(intR,intR) {
inti,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(R>=0&&R<=N-1&&R>=0&&R<=N-1&&h[R][R]==0)
{
for(j=0;j<=7;j++)
{
if(h[R][j]==0)
h[R][j]=R+1;
if(h[j][R]==0)
h[j][R]=R+1;
if(R+j>=0&&R+j<=N-1&&R+j>=0&&R+j<=N-1&&h[R+j][R+j]==0)
h[R+j][R+j]=R+1;
if(R+j>=0&&R+j<=N-1&&R-j>=0&&R-j<=N-1&&h[R+j][R-j]==0)
h[R+j][R-j]=R+1;
if(R-j>=0&&R-j<=N-1&&R+j>=0&&R+j<=N-1&&h[R-j][R+j]==0)
h[R-j][R+j]=R+1;
if(R-j>=0&&R-j<=N-1&&R-j>=0&&R-j<=N-1&&h[R-j][R-j]==0)
h[R-j][R-j]=R+1;
}
h[R][R]=-R-1;
if(R==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)
{
printf("------布局%d------\n",count);
outputArraR(H);
} for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
{
if(h[i][j]==R||h[i][j]==-R||h[i][j]==-R-1)
h[i][j]=0;
}
}
trRit(R-1,n[R-1]+1);
}
else
{
n[R]=R;
trRit(R+1,0);
}
}
else
{
if(R>7)
{
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
{
if(h[i][j]==R||h[i][j]==-R)
h[i][j]=0;
}
}
if(R-1>=0)
trRit(R-1,n[R-1]+1);
else
trRit(0,0);
}
else
trRit(R,R+1);
}
}
} } voidoutputArraR(inth[][N]) {
inti,j;
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
printf("%d",h[i][j]);
printf("\n");
} }
3.騎士游歷問題：
#include<stdio.h> intboard[8][8]={0}; inttravel(intR,intR) { intktmove1[8]={-2,-1,1,2,2,1,-1,-2}; intktmove2[8]={1,2,2,1,-1,-2,-2,-1}; intneRti[8]={0}; intneRtj[8]={0}; inteRists[8]={0}; inti,j,k,m,l; inttmpi,tmpj; intcount,min,tmp;
i=R; j=R; board[i][j]=1; for(m=2;m<=64;m++){ for(l=0;l<8;l++) eRists[l]=0; l=0; for(k=0;k<8;k++){ tmpi=i+ktmove1[k]; tmpj=j+ktmove2[k]; if(tmpi<0||tmpj<0||tmpi>7||tmpj>7) continue; if(board[tmpi][tmpj]==0){ neRti[l]=tmpi; neRtj[l]=tmpj; l++; } } count=l; if(count==0){ return0; } elseif(count==1){ min=0; }
else{ for(l=0;l<count;l++){ for(k=0;k<8;k++){ tmpi=neRti[l]+ktmove1[k]; tmpj=neRtj[l]+ktmove2[k]; if(tmpi<0||tmpj<0|| tmpi>7||tmpj>7){ continue; } if(board[tmpi][tmpj]==0) eRists[l]++; } } tmp=eRists[0]; min=0; for(l=1;l<count;l++){ if(eRists[l]<tmp){ tmp=eRists[l]; min=l; } } } i=neRti[min]; j=neRtj[min]; board[i][j]=m;
} return1; } intmain() { intstartR,startR; inti,j; printf("輸入起始點：");scanf("%d%d",&startR,&startR); if(travel(startR,startR)){ printf("游歷完成！\n"); } else{ printf("游歷失敗！\n"); } for(i=0;i<8;i++){ for(j=0;j<8;j++){ printf("%2d",board[i][j]); } putchar("\n"); } return0; }
實驗三計算幾何算法的實現 實驗名稱 實驗二計算幾何算法的實現 姓名 汪子成 系院與業 信息工程系 班級 計算機 15-1班 學號 20XX216758 實驗日期
指導教師 徐本柱 成績
一、實驗目的和要求 1.理解線段的性質、叉積和有向面積。
2.掌握尋找凸包的算法。
3.綜合運用計算幾何和搜索中的知識求解有關問題。
二、實驗預習內容 1．預習 ICPC 講義，大致了解計算幾何算法的相關內容。
2．了解實現該算法的中一些使用方法。
3．會使用該算法解決實際問題。
三、實驗項目摘要 1.將講義第三章第三節中的凸包代碼上機運行并檢驗結果。
2.完成講義第三章的課后習題，上機運行并檢驗結果。
3.思考：判線段相交時，如果有個線段的端點在另一條線段上，注意可能不另一條線段上的端點重合，思考這樣的情況怎么辦。
4.房間最短路問題：給頂一個內含阻礙墻的房間，求解出一條從起點到終點的最最短路徑。房間的邊界固定在 R=0,R=10,R=0 和 R=10。起點和重點固定在(0,5)和(10,5)。房間里還有 0 到18 個墻，每個墻有兩個門。輸入給定的墻的個數，每個墻的 R 位置和兩個門的 R 坐標區間，輸出最短路的長度。下圖是個例子：
四、實驗結果與分析（源程序及相關說明）
3.思考：
用跨立方法。線段相交滿足丏只需滿足如下兩個條件就可以了：1 兩條線段相互跨立；2一條線段的一個端點在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對方。若p1p2 跨立 p3p4，則矢量(p1–p3)和(p2-p1)位于矢量(p4–p3)的兩側，即(p1–p3）×(p4-p3)R(p2–p3)×(p4–p3)<0。上式可改寫成(p1–p3)×(p4-p3)R(p4–p3)×(p2–p3)>0。當(p1–p3)×(p4–p3)=0 時，說明(p1–p3)和(p4–p3)共線，但是因為已經通過快速排斥試驗，所以 p1 一定在線段 p3p4 上；同理，(p4–p3)×(p2–p3)=0 說明 p2 一定在 p3p4 上。所以判斷 p1p2 跨立 Q1Q2 的依據是：(p1–p3)×(p4–p3)R(p4–p3)×(p2–p3)>=0。同理判斷 Q1Q2 跨立 P1P2 的依據是：(p3-p1)×(p2-p1)R(p2-p1)×(p4-p1)>=0。代碼中凼數 boolsegment_intersect()用于判斷 p1、p2 構成的線段和 p3、p4 構成的線段是否相交。可以看出共五種情況兩線段是相交的，反乊就輸出“ThetwoareNotintersected!” 4.房間最短路問題：
#include<iostream> #include<utilitR>
#include<vector> #include<algorithm> usingnamespacestd; tRpedefpair<double,double>POINT; doubledirection(POINTp,POINTp1,POINTp2){ POINTv1,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; returnv1.firstRv2.second-v1.secondRv2.second;} boolon_segment(POINTp,POINTp1,POINTp2){ doublemin_R=p1.first<p2.first?p1.first:p2.first; doublemaR_R=p1.first>p2.first?p1.first:p2.first; doublemin_R=p1.second<p2.second?p1.second:p2.second; doublemaR_R=p1.second>p2.second?p1.second:p2.second; if(p.first>=min_R&&p.first<maR_R&&p.second>=min_R&&p.second<=maR_R) returntrue; else returnfalse; } POINTstartPoint; boolsortBRPolorAngle(constPOINT&p1,constPOINT&p2) { doubled=direction(startPoint,p1,p2);
if(d<0)returntrue; if(d>0)returnfalse; if(d==0&&on_segment(startPoint,p1,p2))returntrue; if(d==0&&on_segment(p2,startPoint,p1))returntrue; returnfalse; } voidfind_conveR_hull(vector<POINT>&point) { POINTp0=point[0]; intk=0; for(inti=0;i<point.size();i++) { if(point[i].second<p0.second|| point[i].second==p0.second&&point[i].first<p0.first){ p0=point[i]; k=i;} } point.erase(point.begin()+k); point.insert(point.begin(),p0); vector<POINT>conveR_hull; do{ conveR_hull.push_back(point[0]); startPoint=point[0]; point.erase(point.begin()); sort(point.begin(),point.end(),sortBRPolorAngle);
if(point[0]==conveR_hull[0])break; point.push_back(conveR_hull[conveR_hull.size()-1]); }while(1); for(intj=0;j<conveR_hull.size();j++){ cout<<conveR_hull[j].first<<""<<conveR_hull[j].second<<endl; }} intmain(){ vector<POINT>pv; doubleR,R; inti; cout<<"請輸入 10 個點<R,R>："<<endl; for(i=1;i<=10;i++){ cout<<"No."<<i<<":"; cin>>R>>R; pv.push_back(make_pair(R,R)); } cout<<endl;find_conveR_hull(pv); sRstem("Pause"); return0; }
實驗四動態規劃算法的實現 實驗名稱 實驗四動態規劃算法的實現 姓名 汪子成 系院與業 信息工程系 班級 計算機 15-1班 學號 20XX216758 實驗日期
指導教師 徐本柱 成績
一、實驗目的和要求 1．理解動態規劃的基本思想、動態規劃算法的基本步驟 2．掌握動態規劃算法實際步驟
二、實驗預習內容 1．動態規劃算法的基本要素 2．最長公共子序列 3．矩陣連乘問題
三、實驗項目摘要 (1)求兩個字符串的最長公共子序列。
-151-R 的一個子序列是相應于 R 下標序列{1,2,…,m}的一個子序列，求解兩個序列的所有子序列中長度最大的，例如輸入：pear,peach 輸出：pea。
(2)給定兩個字符串 a 和 b，現將串 a 通過變換變為串 b，可用的操作為，刪除串 a中的一個字符；在串 a 的某個位置插入一個元素；將串 a 中的某個字母換為另一個字母。對于任意的串 a 和串 b，輸出最少多少次能夠將串變為串 b。思考：輸出變換的步驟。
(3) 輸 入 一 個 矩 陣 ， 計 算 所 有 的 子 矩 陣 中 和 的 最 大 值 。
例 如 ， 輸 入0-2-7092-62-41-41-180-2 輸出為：15 思考：當矩陣很大時，比如 100R100的矩陣，你的程序還能夠很快的得出結果嗎，如果丌能，請思考如何用動態規劃的思想解決。
四、實驗結果與分析（源程序及相關說明）
源代碼如下：
1.求兩個字符串的最長公共子序列。
#include<iostream> #include<string> usingnamespacestd; voidlongest(strings1,strings2) { intmaR,tep,i,j; inta[100][100]; for(i=0;i<s1.size();i++) for(j=0;j<s2.size();j++) a[i][j]=0; for(j=0;j<s2.size();j++) if(s1[0]==s2[j]) a[0][j]=1; for(i=0;i<s1.size();i++) if(s1[i]==s2[0]) a[i][0]=1; maR=a[0][0]; tep=0; for(i=1;i<s1.size();i++) for(j=1;j<s2.size();j++)
if(s1[i]==s2[j]) { a[i][j]=a[i-1][j-1]+1; if(maR<a[i][j]) { maR=a[i][j]; tep=i; } } if(maR==0) cout<<"沒有公共子序列!"; else { cout<<"兩個字符串的最長公共子序列為:"; for(i=tep-maR+1;i<=tep;i++) cout<<s1[i]; cout<<endl; } } intmain() { strings1,s2; cout<<"請輸入兩個字符串:"<<endl; cout<<"一個字符串為:"; cin>>s1; cout<<"另一個字符串為:"; cin>>s2; longest(s1,s2);cout<<endl; return0; }
(2)給定兩個字符串a和b，現將串a通過變換變為串b #include<iostream> #include<string> usingnamespacestd; intmin(intR1,intR2,intR3) { if(R2<R1) R1=R2; elseif(R3<R1) R1=R3; returnR1; } voidchange(strings1,strings2) { constcharRstr=s1.c_str(); constcharRtep=s2.c_str(); intb[100][100]; b[0][0]=0; for(inti=1;i<=s1.length();i++) b[0][i]=i; for(intj=1;j<=s2.length();j++) b[j][0]=j; for(i=1;i<=s2.length();i++) for(intm=1;m<=s1.length();m++)
{ if(tep[i-1]==str[m-1]) b[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變為b需要"<<b[s2.length()][s1.length()]<<"步！"<<endl; } intmain() { strings1,s2; cout<<"輸入字符串a:"; cin>>s1; cout<<"輸入字符串b:"; cin>>s2; change(s1,s2); cout<<endl; return0; }
推薦訪問： 重磅 課程 實驗上一篇：理財規劃實例分析方案
下一篇：先進工作者申報材料
在偉大祖國73華誕之際，我參加了單位組織的“光影鑄魂”主題黨日活動，集中觀看了抗美援朝題材影片《長津湖》，再一次重溫這段悲壯歷史，再一次深刻感悟偉大抗美援朝精神。1950年10月，新中國剛剛成立一年，
根據省局黨組《關于舉辦習近平談治國理政（第四卷）讀書班的通知》要求，我中心通過專題學習、專題研討以及交流分享等形式，系統的對《習近平談治國理政》（第四卷)進行了深入的學習與交流，下面我就來談一談我個人
《習近平談治國理政》（第四卷）是在百年變局和世紀疫情相互疊加的大背景下，對以習近平同志為核心的黨中央治國理政重大戰略部署、重大理論創造、重大思想引領的系統呈現。它生動記錄了新一代黨中央領導集體統籌兩個
《真抓實干做好新發展階段“三農工作”》是《習近平談治國理政》第四卷中的文章，這是習近平總書記在2020年12月28日中央農村工作會議上的集體學習時的講話。文章指出，我常講，領導干部要胸懷黨和國家工作大
在《習近平談治國理政》第四卷中，習近平總書記強調，江山就是人民，人民就是江山，打江山、守江山，守的是人民的心。從嘉興南湖中駛出的小小紅船，到世界上最大的執政黨，在中國共產黨的字典里，“人民”一詞從來都
黨的十八大以來，習近平總書記以馬克思主義戰略家的博大胸襟和深謀遠慮，在治國理政和推動全球治理中牢固樹立戰略意識，在不同場合多次圍繞戰略策略的重要性，戰略和策略的關系，提高戰略思維、堅定戰略自信、強化戰
《習近平談治國理政》第四卷集中展示了以習近平同志為核心的黨中央在百年變局和世紀疫情相互疊加背景下，如何更好地堅持和發展中國特色社會主義而進行的生動實踐與理論探索；對于新時代堅持和發展什么樣的中國特色社
在黨組織的關懷下，我有幸參加了區委組織部組織的入黨積極分子培訓班。為期一周的學習，學習形式多樣，課程內容豐富，各位專家的講解細致精彩，對于我加深對黨的創新理論的認識、對黨的歷史的深入了解、對中共黨員的
《習近平談治國理政》第四卷《共建網上美好精神家園》一文中指出：網絡玩命是新形勢下社會文明的重要內容，是建設網絡強國的重要領域。截至2021年12月，我國網民規模達10 32億，較2020年12月增長4
剛剛召開的中國共產黨第十九屆中央委員會第七次全體會議上討論并通過了黨的十九屆中央委員會向中國共產黨第二十次全國代表大會的報告、黨的十九屆中央紀律檢查委員會向中國共產黨第二十次全國代表大會的工作報告和《