return false; }
void find_convex_hull(vector
POINT p0=point[0]; int k=0;
for(int i=0;i if(point[i].second point[i].second==p0.second&&point[i].first point.erase(point.begin()+k); point.insert(point.begin(),p0); vector convex_hull.push_back(point[0]); startPoint=point[0]; point.erase(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 cout< int main(){ vector cout<<\请输入10个点 — 精选文档 11 精选文档 for(i=1;i<=10;i++){ cout<<\ cin>>x>>y; pv.push_back(make_pair(x,y)); } cout< 实验四 动态规划算法的实现 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 中的某个字母换为另一个字母。对于 任意的串 a 和串 b,输出少多少次能够将串变为串 b。 思考:输出变换的步骤。 (3) 输入一个矩阵,计算所有的子矩阵中和的大值。 例如,输入 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 输出为:15 思考:当矩阵很大时,比如 — 12 精选文档 100*100 的矩阵,你的程序还能够很快的得出结果吗,如果 不能,请思考如何用动态规划的思想解决 (1) 求两个字符串的最长公共子序列 源代码: #include //str1存储字符串x,str2存储字符串y char str1[N],str2[N]; //lcs存储最长公共子序列 char lcs[N]; //c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度int c[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] 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++) c[i][0] = 0; for(i=0;i<=n;i++) c[0][i] = 0; — 13 精选文档 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; } else if(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; } } return c[m][n]; } //求出最长公共子序列 char* getLCS(char *x, char *y,int len,char *lcs) { int i = strlen(x); int j = strlen(y); while(i&&j) { if(flag[i][j]==0) { lcs[--len] = x[i-1]; — 14 i--; j--; } else if(flag[i][j]==1) i--; else j--; } return lcs; } int main() { int i; cout<<\请输入字符串x:\ cin>>str1; cout<<\请输入字符串y:\ cin>>str2; int lcsLen = LCSLength(str1,str2); cout<<\最长公共子序列长度:\ char *p = getLCS(str1,str2,lcsLen,lcs); cout<<\最长公共子序列为:\ for(i=0;i 运行截图: — 精选文档 15