好文档 - 专业文书写作范文服务资料分享网站

程序设计艺术与方法

天下 分享 时间: 加入收藏 我要投稿 点赞

return false; }

void find_convex_hull(vector&point) {

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); vectorconvex_hull; do{

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 pv; double x,y; int i;

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 #include #define N 100 using namespace std;

//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

9415d4a8lz3blzb1bwa62p7v43zg0p00hwx
领取福利

微信扫码领取福利

微信扫码分享