乘法表问题

[效云 李]

定义于字母表S={a,b,c}上的乘法表如下
| a b c
-------------
a | b b a
b | c b a
c | a c c
-------------
依此乘法表，对任一定义于S上的字符串，适当加括号后得到一个表达式。例如，对于字符串x=bbbba，它的一个加括号表达式为(b(bb))
(ba)。依乘法表，该表达式的值为a。试设计一个动态规划算法，对任一定义于S上的字符串x=x1x2x3x4...xn，计算有多少种不同的加括号
方式，使由x 导出的加括号表达式的值为a。

[效云 李]

// 动态规划-乘法表问题.cpp : Defines the entry point for the console
application.
//m[i][j][k] 表示以i开头，以j结尾，结果为k的方式数，a,b,c对应为1，2，3
VS2005，测试用例：
input.txt的内容为：
bbbba
结果为output.txt:
6
代码：
#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
string s;

ifstream finput;
finput.open("input.txt");
finput>>s;
int n=s.length();
finput.close();

vector<vector<vector<int> > > m(n,vector<vector<int> >(n,vector<int>
(4)));

void (*p_initial_m)(vector<vector<vector<int> > >&,string,int);
void initial_m(vector<vector<vector<int> > >&,string,int);
p_initial_m=initial_m;
(*p_initial_m)(m,s,n);

void (*p_calculate)(vector<vector<vector<int> > >&,string,int);
void calculate(vector<vector<vector<int> > >&,string,int);
p_calculate=calculate;
(*p_calculate)(m,s,n);

ofstream foutput;
foutput.open("output.txt");
foutput<<m[0][n-1][1];
foutput.close();

return 0;
}

void initial_m(vector<vector<vector<int> > >& m,string s,int n)
{
int i=0;
for(i=0;i<n;++i)
{
m[i][i][s[i]-'a'+1]=1;
}
}

void calculate(vector<vector<vector<int> > >& m,string s,int n)
{
for(int step=1;step<n;++step) //步长
for(int i=0;i<n-step;++i) //起点
{
int j=i+step; //尾
for(int k=i;k<j;++k)
{
//根据乘法表转化
m[i][j][1]+=m[i][k][3]*m[k+1][j][1]+m[i][k][1]*m[k+1][j][3]+m[i][k]
[2]*m[k+1][j][3];
m[i][j][2]+=m[i][k][1]*m[k+1][j][1]+m[i][k][1]*m[k+1][j][2]+m[i][k]
[2]*m[k+1][j][2];
m[i][j][3]+=m[i][k][2]*m[k+1][j][1]+m[i][k][3]*m[k+1][j][2]+m[i][k]
[3]*m[k+1][j][3];
}
}
}

你们赶紧，抓紧时间多做，赶紧交流

[higer]

这个题其实跟“矩阵连乘”问题很接近，它的递推结构是：A[i][j][dest]=A[i][k][p]+A[k+1][j][q],其中A[i]
[j][dest]表示字符串xi...xj导出结果为dest(dest取值为0 1 2,分别对应'a' 'b' 'c')的加括号方法数。
下面是我的c代码，在VC6.0和gcc 2.95.3-5下测试通过：
/
************************************************************************/
/* 乘法表问题 */
/
************************************************************************/
#include "stdio.h"
#include <string.h>
#define max_length 100
int table[3][3]={{1,1,0},{2,1,0},{0,2,2}};//乘法表,a b c 分别对应 0 1 2
int A[max_length][max_length][3];//表示字符串到a b c的不同的加括号方法
int calculate(int* x,int n,int dest){//dest取值为0 1 2,表示x(i,j)到dest的不同加括号
方法
int num=0;
int i=1,j=1;
int r=0;
for(r=2;r<=n;r++)//个数
for(i=0;i<=n-r;i++){
j=i+r-1;
int k=0;
for(k=i;k<j;k++){
int p=0,q=0,m=0;
for(m=0;m<3;m++)
for(p=0;p<3;p++)//查表
for(q=0;q<3;q++){
if(table[p][q]==m)
A[i][j][m]+=A[i][k][p]*A[k+1][j][q];
}
}
}
return A[0][n-1][dest];
}

int main()
{
int x[max_length];
memset(x,0,sizeof(x));
int i=0,j=0;
char c;
while((c=getchar())!='\n'){//如果是从文件读取就是!=EOF
switch(c) {
case 'a':
x[i]=0;
break;
case 'b':
x[i]=1;
break;
case 'c':
x[i]=2;
break;
default:
break;
}
i++;
}
int n=i;
memset(A,0,sizeof(A));
for(i=0;i<n;i++){
A[i][i][x[i]]=1;//(i,i)只有一个元素，它到x[i]的加括号方法为1
}

printf("%d\n",calculate(x,n,0));//到a的加括号方法数
return 0;
}