动态规划算法——乘法表问题
问题描述：
定义于字母表∑{a,b,c)上的乘法表如表1所⽰
表1∑乘法表
a  b  c
a  b  b  a
b  c  b  a
c  a  c  c
依此乘法表，对任⼀定义于∑上的字符串，适当加括号表达式后得到⼀个表达式。例如，对于字符串x=bbbba，它的⼀个加括号表达式为i(b(bb)) (ba)。依乘法表，该表达式的值为a。试设计⼀个动态规划算法，对任⼀定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号⽅式，使由x导出的加括号表达式的值为a
booth算法乘法例题讲解要求：
输⼊：输⼊⼀个以a,b,c组成的任意⼀个字符串。
输出：计算出的加括号⽅式数。
算法实现：可以定义⼀个三维数组a[n][n][3],n为输⼊字符串的长度，a[i][j][0]为从字符串中第i个元素到第j个元素的⼦串表达式值为a的加括号⽅式数，a[i][j][1]为从字符串中第i个元素到第j个元素的⼦串表达式值为b的加括号⽅式数，a[i][j][2]为从字符串中第i个元素到第j个元素的⼦串表达式值为c的加括号⽅式数。
由乘法表的定义则可知啊a[i][j][0]=（对k求和，k从i到j-1）a[i][k][0]*a[i][k+1][2]+a[i][k][1]*a[i][k+1][2]+a[i][k][2]*a[i][k+1][1];
同理可得到a[i][j][1]和a[i][j][2]。
同时由上⾯的表达式可知，要计算a[i][j][]，需先计算a[i][k][]和a[i][k+1][]，这⾥k从i到j-1，故a[i][j][]可采取如下的计算次序
如图所⽰，先将主对⾓线上从上到下计算出来，再计算次对⾓线，再次次对⾓线.....依次顺序，直到全部计算完毕。
下⾯给出c语⾔程序：
#include "stdio.h"
#define num 50
void chengji_1(int (*a)[num][3],int n,char b[]);
int _tmain( )
{
int a[num][num][3];
char b[num];
int i,j,k,n;
char c;
printf("intput the num of array:");
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<3;k++)
a[i][j][k]=0;
i=0;
while((c=getchar())!='/n')
{
b[i]=c;
i++;
}
chengji_1(a,n,b);
printf("reslut is:%d",a[0][n-1][0]);
getchar();
}
void chengji_1(int (*a)[num][3],int n,char b[])
{
int i,j,k,t;
for(i=0;i<n;i++)
*(*(*(a+i)+i)+(b[i]-'a'))=1;
for(k=1;k<n;k++)
for(i=0;i<n;i++)
{
j=i+k;
for(t=i;t<j;t++)
{
*(*(*(a+i)+j)+0)+=((*(*(*(a+i)+t)+0))*(*(*(*(a+t+1)+j)+2))+(*(*(*(a+i)+t)+1))*(*(*(*(a+t+1)+j)+2))+(*(*(*(a+i)+t)+2))*(*(*(* (a+t+1)+j)+0)));
*(*(*(a+i)+j)+1)+=((*(*(*(a+i)+t)+0))*(*(*(*(a+t+1)+j)+0))+(*(*(*(a+i)+t)+0))*(*(*(*(a+t+1)+j)+1))+(*(*(*(a+i)+t)+1))*(*(*(* (a+t+1)+j)+1)));
*(*(*(a+i)+j)+2)+=((*(*(*(a+i)+t)+1))*(*(*(*(a+t+1)+j)+0))+(*(*(*(a+i)+t)+2))*(*(*(*(a+t+1)+j)+1))+(*(*(*(a+i)+t)+2))*(*(*(* (a+t+1)+j)+2)));
}
}
}
运⾏结果如下：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。