程序设计艺术与方法

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 头部插入一个随机数，用

2、迭代器遍历 vector 并输出其中的元素值。用泛型算法 find 查找某个随机数，如果找到便输出，否则将此数 插入 vector 尾部。用泛型算法 sort 将 vector 排序，用迭代器遍历 vector 并输出其中的元 素值。删除 vector 尾部的元素，用迭代器遍历 vector 并输出其中的元素值。将 vector 清 空。 定义一个 list，并重复上述实验，并注意观察结果。 (2) 练习泛型算法的使用。 - 149 定义一个 vector，元素类型为 int，插入 10 个随机数，使用 sort 按升序排序，输出 每个元素的值，再按降叙排序，输出每个元素的值。练习用 find

3、 查找元素。用 min 和 max 找出容器中的小元素个大元素，并输出。源代码：#include <iostream>#include <vector>#include<iomanip>#include<ctime> #include <algorithm>using namespace std;vector<int> myV;bool sortup(int v1,int v2)return v1<v2; int main(int argc, char *argv) srand(time(NULL); for (in

4、t i=0;i<10;i+) myV.push_back(rand(); sort(myV.begin(),myV.end(),sortup); vector<int>:iterator it1; for (it1=myV.begin();it1!=myV.end();it1+) cout<<(*it1)<<setw(6); cout<<endl; int min=myV0; for (it1=myV.begin()+1;it1!=myV.end();it1+) if(*it1)<min)min=(*it1); cout<<

5、;"最小元素为" <<min<<endl; int max=myV0; for (it1=myV.begin();it1!=myV.end();it1+) if(*it1)>max)max=(*it1); cout<<"最大元素为" <<max<<endl; cout<<endl; int value=rand(); it1=find(myV.begin(),myV.end(),value); if(*it1)=value) cout<<"找到了这个随机数

6、"<<endl ; else cout<<"没有找到这个随机数"<<endl; myV.insert(myV.end(),value); cout<<"插入尾部的随机数为"<<value<<endl; for (it1=myV.begin();it1!=myV.end();it1+) cout<<(*it1)<<setw(6); cout<<"n"<<endl; int t=rand(); myV.inse

7、rt(myV.begin(),t); cout<<"插入头部的随机数为" <<t<<endl; for (it1=myV.begin();it1!=myV.end();it1+) cout<<(*it1)<<setw(6); cout<<endl; myV.pop_back (); for (it1=myV.begin();it1!=myV.end();it1+) cout<<(*it1)<<setw(6); cout<<endl; myV.clear(); if(m

8、yV.empty() cout << "It's empty!" << endl; system("PAUSE"); return 0;运行截图：2 练习泛型算法的使用：源代码：#include<list>#include<iostream>/#inclued<algorithm>using namespace std;typedef list<int> lin;int value=1,2,3,4,5; void print(lin &l)int i;lin:iter

9、ator lit; for(lit=l.begin();lit!=l.end();lit+)cout<<(*lit)<<" " cout<<endl;bool sortsp(int v1,int v2) return v1>v2; int main()lin lin2; lin2.push_front(3); lin2.push_front(4); lin2.insert(lin2.begin(),value,value+5);cout<<"lin2内的元素为："print(lin2);lin2.so

10、rt();cout<<"排序后的lin2: "print(lin2);lin2.push_front(10); cout<<"在list头部插入10之后的结果：" print(lin2);lin2.remove(6);cout<<"删除一个数后的lin1:" print(lin2); system("PAUSE"); return 0;运行截图：实验二 搜索算法的实现1. 实验目的 (1) 掌握宽度优先搜索算法。 (2) 掌握深度优先搜索算法。 2. 试验设备 硬件环境：PC 计

11、算机 软件环境： 操作系统：Windows 2000 / Windows XP / Linux 语言环境：Dev cpp / gnu c+ 3. 试验内容 (1) 将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。 (2) 八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。 思考：将此题推广到 N 皇后的情况，检验在 N 比较大的情况下，比方说 N=16 的时 候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。 (3) 骑士游历问题： 在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的

12、顶点， 输出一条符合上述要求的路径。 (4) 倒水问题：给定 2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出 L 升 的水，如果可以，输出步骤，如果不可以，请输出 No Solution。（2）八皇后问题源代码：#include <iostream>using namespace std;#include <math.h>int sum = 0;int upperlimit = 1;void compare(int row,int ld,int rd)if(row!=upperlimit)int pos=upperlimit&(row|ld|rd

13、); while(pos!=0)int p=pos&-pos;pos-=p;compare(row+p,(ld+p)<<1,(rd+p)>>1);elsesum+;int main()int n;cout<<"请输入皇后的个数:"cin>>n;upperlimit = (upperlimit<<n)-1;compare(0,0,0);cout<<"问题的解如下:"<<sum<<endl;return 0;运行截图：（4）倒水问题源代码：4.倒水问题：#

14、include"stdio.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(ca<cc) while(1) if(y=0) y=cb; printf("fill Bn&

15、quot;); if(y>ca-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中的水已经和cc相等，那就结束/ break; if(ca=x) /如果a中的水满了，就把a倒空/ x=0; printf("empty An"); else while(1) if(x=0) x=ca; print

16、f("fill An"); if(x>cb-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中的水已经和cc相等，那就结束/ break; if(y=cb) /如果b中的水满了，就把b倒空/ y=0; printf("empty Bn"); printf("succ

17、essn"); return 0;运行截图:实验三 计算几何算法的实现1. 实验目的 (1) 理解线段的性质、叉积和有向面积。 (2) 掌握寻找凸包的算法。 (3) 综合运用计算几何和搜索中的知识求解有关问题。 2. 试验设备 硬件环境：PC 计算机 软件环操作系统：Windows 2000 / Windows XP / Linux 语言环境：Dev cpp / gnu c+ 3. 试验内容 (1) 将讲义第三章第三节中的凸包代码上机运行并检验结果。 (2) 完成讲义第三章的课后习题，上机运行并检验结果。 (3) 思考： 判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一

18、条线段上的 端点重合，思考这样的情况怎么办。 (4) 房间短路问题： 给顶一个内含阻碍墙的房间，求解出一条从起点到终点的短路径。房间的边界 固定在 x=0,x=10,y=0 和 y=10。起点和重点固定在(0,5)和(10,5)。房间里还有 0 到 18 个 墙，每个墙有两个门。输入给定的墙的个数，每个墙的 x 位置和两个门的 y 坐标区间， 输出最短路的长度。（4）房间短路问题源代码： #include<iostream> #include<utility> #include<vector> #include<algorithm> using

19、namespace std; typedef pair<double,double> 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_segment(POINT

20、p,POINT p1,POINT p2) double min_x=p1.first<p2.first?p1.first:p2.first; double max_x=p1.first>p2.first?p1.first:p2.first; double min_y=p1.second<p2.second?p1.second:p2.second; double max_y=p1.second>p2.second?p1.second:p2.second; if(p.first>=min_x&&p.first<max_x&&p.s

21、econd>= 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; if(d >0)return false; if(d=0&&on_segment(startPoint,p1,p2)return true

22、; if(d=0&&on_segment(p2,startPoint,p1)return true; return false; void find_convex_hull(vector<POINT>&point) POINT p0=point0; int k=0; for(int i=0;i<point.size();i+) if(pointi.second<p0.second| pointi.second=p0.second&&pointi.first<p0.first) p0=pointi; k=i; point.er

23、ase(point.begin()+k); point.insert(point.begin(),p0); vector<POINT>convex_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); whil

24、e(1); for(int j=0;j<convex_hull.size();j+) cout<<convex_hullj.first<<' '<<convex_hullj.second<<endl; int main() vector<POINT> pv; double x,y; int i; cout<<"请输入10个点<x,y>："<<endl; for(i=1;i<=10;i+) cout<<"No."<&

25、lt;i<<':' cin>>x>>y;pv.push_back(make_pair(x,y); cout<<endl; find_convex_hull(pv); system("Pause"); return 0; 运行截图：实验四 动态规划算法的实现1. 实验目的 (1) 理解动态规划的基本思想、动态规划算法的基本步骤。 (2) 掌握动态规划算法实际步骤。 2. 试验设备 硬件环境：PC 计算机 软件环境： 操作系统：Windows 2000 / Windows XP / Linux 语言环境：Dev c

26、pp / gnu c+ 3. 试验内容 (1) 求两个字符串的最长公共子序列。 X 的一个子序列是相应于 X 下标序列1, 2, , m的一个子序列，求解两个序列的所有 子序列中长度大的，例如输入：pear, peach 输出：pea。 (2) 给定两个字符串 a 和 b，现将串 a 通过变换变为串 b，可用的操作为，删除串 a 中的一 个字符；在串 a 的某个位置插入一个元素；将串 a 中的某个字母换为另一个字母。对于 任意的串 a 和串 b，输出少多少次能够将串变为串 b。 思考：输出变换的步骤。 (3) 输入一个矩阵，计算所有的子矩阵中和的大值。 例如，输入 0 -2 -7 0 9 2

27、-6 2 -4 1 -4 1 -1 8 0 -2 输出为：15 思考：当矩阵很大时，比如 100*100 的矩阵，你的程序还能够很快的得出结果吗，如果 不能，请思考如何用动态规划的思想解决（1） 求两个字符串的最长公共子序列源代码：#include<cstring>#include<iostream>#define N 100using namespace std;/str1存储字符串x，str2存储字符串ychar 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-1j<sij-1int flagNN;/求长度int LCSLength(char *x, c