《2022年程序设计艺术与方法 .pdf》由会员分享，可在线阅读，更多相关《2022年程序设计艺术与方法 .pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、程序设计艺术与方法实验一STL 的熟悉与使用1实验目的（1）掌握C+中 STL 的容器类的使用。（2）掌握 C+中 STL 的算法类的使用。2试验设备硬件环境：PC 计算机软件环境：操作系统：Windows 2000/Windows XP/Linux 语言环境：Dev cpp/gnu c+3试验内容(1)练习vector 和 list 的使用。定义一个空的vector，元素类型为int，生成10 个随机数插入到vector 中，用迭代器遍历vector 并输出其中的元素值。在vector 头部插入一个随机数，用迭代器遍历vector 并输出其中的元素值。用泛型算法find 查找某个随机数，如果
2、找到便输出，否则将此数插入vector 尾部。用泛型算法sort 将 vector 排序，用迭代器遍历vector 并输出其中的元素值。删除vector 尾部的元素，用迭代器遍历vector 并输出其中的元素值。将vector 清空。定义一个list，并重复上述实验，并注意观察结果。(2)练习泛型算法的使用。-149 定义一个vector，元素类型为int，插入10 个随机数，使用sort 按升序排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用find 查找元素。用min 和 max 找出容器中的小元素个大元素，并输出。源代码：#include#include#include#i
3、nclude#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:iterator it1;for(it1=myV.begin();it1!=myV.end();it1+)cout(*it1)setw(6);coutendl;int min=m
4、yV0;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 16 页 -for(it1=myV.begin()+1;it1!=myV.end();it1+)if(*it1)min)min=(*it1);cout最小元素为 minmax)max=(*it1);cout最大元素为 maxendl;coutendl;int value=rand();it1=find(myV.begin(),myV.end(),value);if(*it1)=value)cout找到了这个随机数 endl;else cout没有找到这个随机数 endl;myV.insert(myV.end(),value)
5、;cout插入尾部的随机数为 valueendl;for(it1=myV.begin();it1!=myV.end();it1+)cout(*it1)setw(6);coutnendl;int t=rand();myV.insert(myV.begin(),t);cout插入头部的随机数为 tendl;for(it1=myV.begin();it1!=myV.end();it1+)cout(*it1)setw(6);coutendl;myV.pop_back();for(it1=myV.begin();it1!=myV.end();it1+)cout(*it1)setw(6);coutendl
6、;myV.clear();if(myV.empty()cout Its empty!endl;system(PAUSE);return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 16 页 -运行截图：2 练习泛型算法的使用：源代码：#include#include/#inclued using namespace std;typedef list lin;int value=1,2,3,4,5;void print(lin&l)int i;lin:iterator lit;for(lit=l.begin();lit!=l.end();lit+)cout(*lit);co
7、utv2;int main()lin lin2;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 16 页 -lin2.push_front(3);lin2.push_front(4);lin2.insert(lin2.begin(),value,value+5);coutlin2 内的元素为：;print(lin2);lin2.sort();cout排序后的 lin2:;print(lin2);lin2.push_front(10);cout在 list 头部插入 10 之后的结果：;print(lin2);lin2.remove(6);cout删除一个数后的lin1:;prin
8、t(lin2);system(PAUSE);return 0;运行截图：实验二搜索算法的实现1.实验目的(1)掌握宽度优先搜索算法。(2)掌握深度优先搜索算法。2.试验设备硬件环境：PC 计算机软件环境：操作系统：Windows 2000/Windows XP/Linux 语言环境：Dev cpp/gnu c+3.试验内容(1)将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。(2)八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。思考：将此题推广到 N 皇后的情况，检验在N 比较大的情况下，比方说N=16 的时候，你
9、的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。(3)骑名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 16 页 -士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。(4)倒水问题：给定2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L 升的水，如果可以，输出步骤，如果不可以，请输出No Solution。（2）八皇后问题源代码：#include using namespace std;#include int sum=0;int upperlimit=1;void compare(int
10、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问题的解如下:sumendl;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 16 页 -return 0;运行截图：（4）倒水问题源代码：4.倒水问题：#includestdio
11、.h int 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)/如果 b 中的水大于 a 中的剩余容积，就把a 灌满/y-=ca-x;x=ca;printf(pour B An);else/如果 b 中的水小于 a 中的剩余容积，那么把b 中的水全加入 a/x+=y;y=0;printf(pour B An);if(y=cc)/如果 b
12、中的水已经和 cc 相等，那就结束/break;if(ca=x)/如果 a 中的水满了，就把a 倒空/x=0;printf(empty An);else while(1)名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 16 页 -if(x=0)x=ca;printf(fill An);if(xcb-y)/如果 a 中的水大于 b 中的剩余容积，就把b 灌满/x-=cb-y;y=cb;printf(pour A Bn);else/如果 a 中的水小于 b 中的剩余容积，那么把a中的水全加入 b/y+=x;x=0;printf(pour A Bn);if(y=cc)/如果 b 中的水
13、已经和 cc 相等，那就结束/break;if(y=cb)/如果 b 中的水满了，就把b 倒空/y=0;printf(empty Bn);名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 16 页 -printf(successn);return 0;运行截图:实验三计算几何算法的实现1.实验目的(1)理解线段的性质、叉积和有向面积。(2)掌握寻找凸包的算法。(3)综合运用计算几何和搜索中的知识求解有关问题。2.试验设备硬件环境：PC 计算机软件环操作系统：Windows 2000/Windows XP/Linux 语言环境：Dev cpp/gnu c+3.试验内容(1)将讲义第三
14、章第三节中的凸包代码上机运行并检验结果。(2)完成讲义第三章的课后习题，上机运行并检验结果。(3)思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。(4)房间短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的短路径。房间的边界固定在x=0,x=10,y=0 和 y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0 到 18 个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间，输出最短路的长度。（4）房间短路问题源代码：#include 名师资料总结-精品资料欢迎下载-名师精心整理-第
15、 9 页，共 16 页 -#include#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;return v1.first*v2.second-v1.second*v2.second;bool on_
16、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 return false;POINT startPoint;bool sortByPolorAngle(const POINT&p1,const POINT&p2)double d=direction(st
17、artPoint,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;名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 16 页 -void find_convex_hull(vector&point)POINT p0=point0;int k=0;for(int i=0;ipoint.size();i+)if(pointi.secondp0.second|pointi
18、.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(point.begin(),point.end(),sortByPolorAngle);if(point0=convex_hull0)break;point.push_bac
19、k(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请输入 10 个点：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;运行截图：实验四动态
20、规划算法的实现1.实验目的(1)理解动态规划的基本思想、动态规划算法的基本步骤。(2)掌握动态规划算法实际步骤。2.试验设备硬件环境：PC 计算机软件环境：操作系统：Windows 2000/Windows XP/Linux 语言环境：Dev cpp/gnu c+3.试验内容(1)求两个字符串的最长公共子序列。X 的一个子序列是相应于X 下标序列 1,2,m的一个子序列，求解两个序列的所有子序列中长度大的，例如输入：pear,peach 输出：pea。(2)给定两个字符串 a 和 b，现将串 a 通过变换变为串b，可用的操作为，删除串a 中的一个字符；在串 a 的某个位置插入一个元素；将串 a
21、 中的某个字母换为另一个字母。对于任意的串a 和串 b，输出少多少次能够将串变为串b。思考：输出变换的步骤。(3)输入一个矩阵，计算所有的子矩阵中和的大值。例如，输入 0-2-7 0 9 2-6 2-4 1-4 1-1 8 0-2 输出为：15 思考：当矩阵很大时，比如 100*100 的矩阵，你的程序还能够很快的得出结果吗，如果不能，请思考如何用动态规划的思想解决名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 16 页 -（1）求两个字符串的最长公共子序列源代码：#include#include#define N 100 using namespace std;/str1 存
22、储字符串 x，str2 存储字符串 y char str1N,str2N;/lcs 存储最长公共子序列char lcsN;/cij 存储 str11.i与 str21.j的最长公共子序列的长度int cNN;/flagij=0 为 str1i=str2j/flagij=1 为 ci-1j=sij-1/flagij=-1 为 ci-1jsij-1 int flagNN;/求长度int LCSLength(char*x,char*y)int i,j;/分别取得 x,y 的长度int m=strlen(x);int n=strlen(y);for(i=1;i=m;i+)ci0=0;for(i=0;i
23、=n;i+)c0i=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;flagij=1;else cij=cij-1;flagij=-1;return cmn;/求出最长公共子序列char*getLCS(char*x,char*y,int len,char*lcs)int i=strlen(x);int j=strlen(y);while(i&j)if(flagij=0)lcs-len=xi-1;i-;j-;名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 16 页 -else if(flagij=1)i-;else j-;return lcs;int main()int i;cout请输入字符串 x：str1;cout请输入字符串 y：str2;int lcsLen=LCSLength(str1,str2);cout最长公共子序列长度：lcsLenendl;char*p=getLCS(str1,str2,lcsLen,lcs);cout最长公共子序列为：;for(i=0;ilcsLen;i+)coutlcsi;coutendl;return 0;运行截图：名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 16 页 -名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 16 页 -