南京邮电大学算法分析与设计实验二（动态规划法）"/>
南京邮电大学算法分析与设计实验二（动态规划法）
文章目录
- 一、LCS问题
- 二、矩阵连乘问题
一、LCS问题
//习题7-10-用备忘录算法求LCS
//备忘录方法是动态规划法的一个变种，它采用分治法思想，自顶向下直接递 归 求最优解。
//但与分治法不同的是，备忘录方法为每个已经计算的子问题建立备忘录，即保存子问题的计
//算结果以备需要时引用，从而避免子问题的重复求解。
//试改写当前程序的int LCS::LCSLength()函数，用备忘录方法来求解最长公共子序列。
//提示：备忘录方法采用的是递归求解方式，因此需要用一个公有成员函数int LCSLength()
//来调用私有递归成员函数int LCSLength(int i,int j); 共同实现。
#include "iostream"
#include "math.h"
using namespace std;class LCS
{
public:LCS(int nx, int ny, char *a, char *b);~LCS();int LCSLength(); //求c和s数组，返回LCS的长度int LCSLength_Memo(); //备忘录算法求c和s数组，返回LCS长度，非递归函数void CLCS(); //构造LCS，非递归private:int LCSLength_Memo(int i,int j); //备忘录算法求c和s数组，返回LCS长度，递归函数void CLCS(int i, int j); //构造LCS，递归int **c, **s, m, n; // 算法中的二维数组c，二维数组s，字符串 x 和 y 的长度char *x, *y; // 要求最大公共子串的两个字符串 x 和 y
}; /// <summary>
/// 构造函数
/// 初始化两个字符串的长度，地址；为c数组和s数组申请堆内存
/// </summary>
/// <param name="nx">字符串 x 的长度</param>
/// <param name="ny">字符串 y 的长度</param>
/// <param name="a">字符串 x 的地址</param>
/// <param name="b">字符串 y 的地址</param>
LCS::LCS(int nx, int ny, char *a, char *b)
{ m=nx; n=ny;x=a; y=b;c=new int*[m+1]; s=new int*[m+1];for(int i=0; i<=m; i++){ c[i]=new int [n+1];s[i]=new int [n+1];}
}/// <summary>
/// 析构函数
/// 释放c数组和s数组的内存
/// </summary>
LCS::~LCS()
{ for(int i=0; i<=m; i++) { delete []c[i]; delete []s[i];}delete []c; delete []s;
}/// <summary>
/// 求c和s数组，返回LCS的长度
/// 算法描述：
/// 1、初始化c数组：将c数组第0行和第0列除去c[0][0]赋初值0
/// 2、计算c数组：
/// 2.1：如果x[i] == y[j]，c[i][j] 等于其左上角的格子c[i-1][j-1]加1，s[i][j] = 1
/// 2.2：否则，c[i][j] = Max{ c[i-1][j], c[i][j-1] } ,
/// 即c[i][j]等于其左边和上边中值较大的那一个。
/// 如果上边大，s[i][j] = 2；
/// 否则左边大，s[i][j] = 3；
/// 3、返回c数组最后一个元素的值c[m][n]，即公共子序列的长度
/// </summary>
/// <returns></returns>
int LCS::LCSLength()
{for (int i = 1; i <= m; i++)c[i][0] = 0;for (int j = 1; j <= n; j++)c[0][j] = 0;for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){if (x[i] == y[j]){c[i][j] = c[i - 1][j - 1] + 1;s[i][j] = 1;}else if (c[i - 1][j] >= c[i][j - 1]){c[i][j] = c[i - 1][j];s[i][j] = 2;}else{c[i][j] = c[i][j - 1];s[i][j] = 3;}}}return c[m][n];}/// <summary>
/// 调用递归的重载函数 CLCS(int, int)
/// </summary>
void LCS::CLCS() //构造LCS，非递归
{ CLCS(m,n);
}/// <summary>
/// 输出最大公共子序列
/// 算法分析：
/// 1、从 s 数组最后一格开始，按照向上或左上的方向查看s数组
/// 2、如果s[i][j] = 1，则输出x[i]，并向左上方向移动
/// 3、如果s[i][j] = 2，则往上移动
/// 4、如果s[i][j] = 3，则往左移动
/// 5、直到i == 0 || j == 0 END
/// </summary>
/// <param name="i"></param>
/// <param name="j"></param>
void LCS::CLCS(int i, int j) //构造LCS，递归
{ if (i == 0 || j == 0)return;if (s[i][j] == 1){CLCS(i - 1, j - 1);cout << x[i];}else if (s[i][j] == 2)CLCS(i - 1, j);elseCLCS(i, j - 1);} //O(m+n)//备忘录算法求c和s数组，返回LCS长度
int LCS::LCSLength_Memo()
{ memset(c, INT_MAX, sizeof(c));return LCSLength_Memo(m, n);
}/// <summary>
/// 求解最大公共子序列的备忘录算法
/// </summary>
/// <param name="i"></param>
/// <param name="j"></param>
/// <returns></returns>
int LCS::LCSLength_Memo(int i,int j)
{if (c[i][j] < INT_MAX)return c[i][j];if ((i == 0) || (j == 0))c[i][j] = 0;else if (x[i - 1] == y[j - 1])c[i][j] = LCSLength_Memo(i - 1, j - 1) + 1;else{int p = LCSLength_Memo(i - 1, j);int q = LCSLength_Memo(i, j - 1);if (p >= q)c[i][j] = p;elsec[i][j] = q;}return c[i][j];}void main()
{int nx = 7, ny = 6, len1, len2;char x[] = "0abcbdab", y[] = "0bdcaba";LCS LL(nx, ny, x, y);cout << "x[]=\"0abcbdab\"; y[]=\"0bdcaba\"" << endl << endl;cout << "1. 不用备忘录算法求LCS的长度:" << endl;len1 = LL.LCSLength(); //长度为4cout << " LCS的长度=" << len1 << endl << endl;cout << "2. 用备忘录算法求LCS的长度:" << endl;len2 = LL.LCSLength_Memo(); //长度为4cout << " LCS的长度=" << len2 << endl << endl;cout << "3. LCS=\""; //LCS="bcba"LL.CLCS();cout << "\"" << endl;
}二、矩阵连乘问题
//程序7-3-矩阵连乘算法和程序7-4-矩阵连乘算法的备忘录方法
#include "iostream"
#include "math.h"
#include "iomanip" //输出格式头文件
using namespace std;//【程序7-3】 矩阵连乘算法
class MatrixChain
{ public:MatrixChain(int mSize, int *q); //创建二维数组m和s，一维数组p，并初始化int MChain(); //一般动态规划法求最优解值int LookupChain(); //备忘录方法求最优解值（程序7-4）void Traceback(); //构造最优解的公有函数void Output();private:void Traceback(int i, int j); //构造最优解的私有递归函数int LookupChain(int i, int j); //备忘录方法私有递归（程序7-4）int *p, **m, **s, n;
};MatrixChain::MatrixChain(int mSize, int *q)
{ n=mSize;m=new int*[n]; s=new int*[n]; p=new int[n+1];for(int i=0; i<n; i++){ m[i]=new int [n]; m[i][i]=0;s[i]=new int [n]; s[i][i]=0;p[i]=q[i];}p[n]=q[n];
}int MatrixChain::MChain()
{for (int i = 0; i < n; i++) m[i][i] = 0;for (int r = 2; r <= n; r++) {for (int i = 0; i <= n - r; i++) {int j = i + r - 1;m[i][j] = m[i + 1][j] + p[i] * p[i + 1] * p[j + 1];s[i][j] = i;for (int k = i + 1; k < j; k++) {int t = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];if (t < m[i][j]) {m[i][j] = t;s[i][j] = k;}}}}return m[0][n - 1];
}void MatrixChain::Traceback(int i, int j)
{if (i == j) {cout << "A" << i;return;}if (i < s[i][j]) cout << "(";Traceback(i, s[i][j]);if (i < s[i][j]) cout << ")";if (s[i][j] + 1 < j) cout << "(";Traceback(s[i][j] + 1, j);if (s[i][j] + 1 < j) cout << ")";}void MatrixChain::Traceback()
{ cout << "(";Traceback(0, n - 1);cout << ")";cout << endl;}//【程序7-4】 矩阵连乘的备忘录方法
int MatrixChain::LookupChain(int i, int j)
{ if (m[i][j] > 0)return m[i][j];if (i == j)return 0;int u = LookupChain(i + 1, j) + p[i] * p[i + 1] * p[j + 1];s[i][j] = i;for (int k = i + 1; k < j; k++) {int t = LookupChain(i, k) + LookupChain(k + 1, j) + p[i] * p[k + 1] * p[j + 1];if (t < u) {u = t;s[i][j] = k;}} m[i][j] = u;return u;}int MatrixChain::LookupChain()
{ return LookupChain(0, n - 1);
}void MatrixChain::Output()
{ int i,j;cout<<" m="<<endl;cout<<" ";for(j=0; j<n; j++)if(j<2) cout<<setw(4)<<j;else cout<<setw(6)<<j;cout<<endl;for(i=0; i<n; i++){ cout<<" "<<i<<" ";for(j=0; j<n; j++){ if(i<j) cout<<setw(6)<<m[i][j]; //setw(6), 指定输出域宽为6else if(i==j) cout<<setw(2)<<m[i][j];else cout<<setw(6)<<" ";}cout<<endl;}cout<<" s="<<endl;cout<<" ";for(j=0; j<n; j++) cout<<j<<" ";cout<<endl;for(i=0; i<n; i++){ cout<<" "<<i<<" ";for(j=0; j<n; j++){ if(i<=j) cout<<s[i][j]<<" ";else cout<<" ";}cout<<endl;}
}//例7-5: 6个矩阵连乘积A0*A1*A2*A3*A4*A5
// A0:30*35, A1:35*15, A2:15*5, A3:5*10, A4:10:20, A5:20*25
//p={p0,p1,p2,p3,p4,p5,p6}={30,35,15,5,10,20,25}
void main()
{ int nn=6,k;int pp[7]={30,35,15,5,10,20,25};MatrixChain mm(nn,pp);cout<<"数据来源例7-5"<<endl;cout<<endl<<"1.不用备忘录方法求矩阵连乘的数乘最少次数"<<endl;k=mm.MChain(); cout<<" 最少数乘次数k="<<k<<endl; //最少数乘次数k=15125mm.Traceback(); //矩阵连乘次序: ( (A0(A1A2)) ((A3A4)A5) )cout<<endl;mm.Output();//下面是备忘录方法cout<<endl<<"2.用备忘录方法求矩阵连乘的数乘最少次数"<<endl;MatrixChain a(nn,pp);k=a.LookupChain(); cout<<" 最少数乘次数k="<<k<<endl;a.Traceback();cout<<endl;a.Output();
}Thanks♪(･ω･)ﾉ
更多推荐
南京邮电大学算法分析与设计实验二（动态规划法）
发布评论