// Layout.cpp : Defines the entry point for the console application.
/*
作者：成曉旭
時(shí)間：2001年10月11日(11:35:38-12:35:00)
內(nèi)容：完成插花問(wèn)題的“動(dòng)態(tài)規(guī)劃法”算法及注解
*/
#include "stdafx.h"
#include "string.h"
#define MAX(A,B) ((A) > (B) ? (A):(B))
//--------------------鮮花問(wèn)題--------------------
#define F 100
#define V 100
/*
插花問(wèn)題描述:
將f束鮮花插入v個(gè)花瓶中,使達(dá)到最徍的視覺(jué)效果,
問(wèn)題相關(guān)約定及插花要求:
鮮花被編號(hào)為1--f,花瓶被編號(hào)為1--v,花瓶按從小到
大順序排列,一只花瓶只能插一支花,鮮花i插入花瓶j中的
視覺(jué)效果效果值已知,編號(hào)小的鮮花所放入的花瓶編號(hào)也小
問(wèn)題求解思路:
花瓶j(1<=j<=v)中插入鮮花的可能編號(hào)為[1..j](編號(hào)
小的鮮花所放入的花瓶編號(hào)也小);
設(shè)數(shù)組p[i][j]表示鮮花i插入花瓶j的好看程度,數(shù)組
q[i][j]表示[1..i]束鮮花插入[1..j]個(gè)花瓶所能得到的最大
好看程度,初始化q[0][0] = 0;q[0][j]=0(1<=j<=v),則q[f][v]
是問(wèn)題的解.
特別地,j束鮮花插入到前面的j只花瓶中,所得到的好看
程度是q[j][j] = p[1][1]+p[2][2]+...+[j][j].現(xiàn)將插花過(guò)
程按花瓶排列順序劃分成不同階段,則在第j階段,第i束鮮花
若放入第j號(hào)花瓶,最大好看程度是q[i-1][j-1]+p[i][j];第i束鮮
花若放入前j-1個(gè)花瓶中的某一個(gè),所得的好看程度是q[i][j-1],
那么在第j階段,插入第i束鮮花所能得到的最大好看程度為:
q[i][j] = MAX(q[i-1][j-1]+p[i][j],q[i][j-1]),要使q[i][j]
最大,應(yīng)使q[i-1][j-1]和q[i][j-1]也最大
*/
//初始化函數(shù)
void Initialize(int *f,int *v,int p[][V])
{
int i,j;
printf("輸入鮮花數(shù)量及花瓶個(gè)數(shù):");
scanf("%d%d",f,v);
printf("順序輸入各鮮花插入各花瓶的好看程度:\n");
for(i=1;i<=*f;i++)
for(j=1;j<=*v;j++)
p[i][j] = i+j;
//scanf("%d",&p[i][j]);
}
//鮮花問(wèn)題處理函數(shù)
int Sove(int p[][V],int f,int v,int *way)
{
int i,j,newv,q[F][V];
q[0][0] = 0;
/*設(shè)置v個(gè)花瓶分別被插入v束鮮花時(shí)各號(hào)花瓶對(duì)應(yīng)的(初始)最大好看程度*/
for(j=1;j<=v;j++)
{
q[0][j] = 0;
/*設(shè)置第j束鮮花放入第j號(hào)花瓶中的最大好看程度*/
q[j][j] = q[j-1][j-1]+p[j][j];
}
for(j=1;j<=v;j++)
for(i=1;i<j;i++)
q[i][j] = MAX(q[i-1][j-1]+p[i][j],q[i][j-1]);
newv = v;
for(i=f;i>0;i--)
{
while(q[i-1][newv-1]+p[i][newv] < q[i][newv])
newv--;
//確定鮮花i插在花瓶newv中,并準(zhǔn)備考慮前一只花瓶
way[i] = newv--;
}
return(q[f][v]);
}
//--------------------鮮花問(wèn)題--------------------
//--------------------最長(zhǎng)子串問(wèn)題--------------------
#define N 100
char a[N],b[N],str[N];
//計(jì)算兩個(gè)序列最長(zhǎng)公共子序列的長(zhǎng)度
int Get_LongSubStr_Len(char *a,char *b,int c[][N])
{
int m=strlen(a),n=strlen(b),//兩個(gè)序列的長(zhǎng)度
i,j;//循環(huán)變量
for(i=0;i<=m;i++) c[i][0] = 0;
for(i=1;i<=n;i++) c[0][i] = 0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(a[i-1]==b[j-1])
c[i][j] = c[i-1][j-1]+1;
else
c[i][j] = MAX(c[i-1][j],c[i][j-1]);
/*
if(c[i-1][j]>=c[i][j-1])
c[i][j] = c[i-1][j];
else
c[i][j] = c[i][j-1];
*/
return(c[m][n]);
}
//構(gòu)造最長(zhǎng)公共子序列
char *Build_LongSubStr(char s[],char *a,char *b)
{
int i=strlen(a),j=strlen(b),
k,c[N][N];
k = Get_LongSubStr_Len(a,b,c);
s[k] = '\0';
while(k>0)
{
if(c[i][j]==c[i-1][j])
i--;
else
{
if(c[i][j]==c[i][j-1])
j--;
else
{
s[--k]=a[i-1];
i--;
j--;
}
}
}
return(s);
}
//--------------------最長(zhǎng)子串問(wèn)題--------------------
int main(int argc, char* argv[])
{
int i,f,v,p[F][V],way[F];
//-----------------------------------
/*
Initialize(&f,&v,p);
printf("最大好看程度為%d\n",Sove(p,f,v,way));
printf("插有鮮花的花瓶是:\n");
for(i=1;i<=f;i++)
printf("%4d",way[i]);
*/
//-----------------------------------
printf("輸入兩個(gè)字符串(長(zhǎng)度<%d):\n",N);
scanf("%s%s",a,b);
printf("兩個(gè)串的最長(zhǎng)公共子序列是:%s\n",Build_LongSubStr(str,a,b));
//-----------------------------------
printf("\n\n應(yīng)用程序正在運(yùn)行......\n");
return 0;
}