算法分析大作业

算法分析大作业 动态规划方法解

乘法表问题和汽车加油行驶问题

目录

1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结

1.动态规划解决乘法表问题

1.1问题描述

定义于字母表∑{a,b,c)上的乘法表如表所示：

依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。

例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。

试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。

1.2算法设计思想

设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。

设字符串的第 i 到 第 j 位乘积为 a 的加括号法有result[i][j][a] 种，

字符串的第 i 到 第 j 位乘积为 b 的加括号法有result[i][j][b] 种,

字符串的第 i 到 第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。

则原问题的解是： result[i][n][a] 。

设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ： result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a];

result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b];

result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c];

输入：输入一个以a,b,c组成的任意一个字符串。 输出：计算出的加括号方式数。

1.3设计方法

乘法表问题直观理解就是通过加括号使得最终运算结果为a，该问题与矩阵连乘问题类似，矩阵连乘是每一次加括号选择运算量最小的，写成数学表达式有：

而乘法表问题则是计算所有加括号运算结果为a的情况数，并不要求输出加括号方式。那么可以从乘法的最小单元两个符号相乘的所有可能开始，接着在两个符号相乘的基础上计算三个符号相乘的所有可能。直到计算N长度的符号1-N的所有可能。可以定义一个三维数组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][]可采取如下的计算次序

1.4源代码

#include \#include \#include %using namespace std; /*

f[i][j][0] 表示在ch[i]~ch[j]之间以某种方式加括号后，结果为a f[i][j][1] 表示在ch[i]~ch[j]之间以某种方式加括号后，结果为b f[i][j][2] 表示在ch[i]~ch[j]之间以某种方式加括号后，结果为c a = a*c || b*c || c*a b = a*a || a*b || b*b c = b*a || c*b || c*c */ int f[50][50][3];

char chars[3] = {'a', 'b', 'c'};

int mul(int n, char ch[]) {

for(int i=0; i