算法分析大作业

1、算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题目录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)上的乘法表如表所示:abcabbabcbacacc依此乘法表,对任一定义于三上的字符串,适当加括号表达式后得到一 个表达式。例如，对于字符用x=bbbba,它的一个加括号表达式为(b(bb)(ba)。依乘 法表，该表达式的值为a。试设

2、计一个动态规划算法，对任一定义于三上的字符用x=x1x2 xn,计 算有多少种不同的加括号方式，使由x导出的加括号表达式的值为a。1.2 算法设计思想设常量a,b,c分别为1,2 ,3 o n为字符串的长度。设字符串的第i到第j位乘积为a的加括号法有resulti皿a种，字符串的第i到第j位乘积为b的加括号法有resultijb种，字符串的第i到第j位乘积为c的加括号法有resultijc种。则原问题的解是： resultina 。设k为i到j中的某一个字符，则对于k从i到j :resultija += resultika * resultk + 1jc +resultikb * result

3、k + 1jc + resultikc * resultk+ 1ja；resultijb += resultika * resultk + 1ja +resultika * resultk + 1jb + resultikb * resultk+ 1jb；resultijc += resultikb * resultk + 1ja +resultikc * resultk + 1jb + resultikc * resultk+ 1皿c；输入：输入一个以a,b,c组成的任意一个字符串输出：计算出的加括号方式数。1.3 设计方法乘法表问题直观理解就是通过加括号使得最终运算结果为a，该问题与矩阵连

4、乘问题类似，矩阵连乘是每一次加括号选择运算量最小的，写成数学 表达式有：而乘法表问题则是计算所有加括号运算结果为a的情况数，并不要求输出加括号方式。那么可以从乘法的最小单元两个符号相乘的所有可能开始， 接着在两个符号相乘的基础上计算三个符号相乘的所有可能。直到计算N长度的符号1-N的所有可能。可以定义一个三维数组ann3,n 为输入字符串的长度，ai用 为从字符串中第i个元素到第j个元素的子用表达 式值为a的加括号方式数，ai皿1 为从字符串中第i个元素到第j个元 素的子用表达式值为b的加括号方式数，aij2 为从字符串中第i个元 素到第j个元素的子用表达式值为c的加括号方式数。由乘法表的定义

5、则可知啊aij0= （对k求和，k从i到j-1 ） aik 0*aik+12+aik1*aik+12+aik2*aik+11；同理可得到ai皿1 和ai皿2。同时由上面的表达式可知，要计算ai用口，需先计算aik 和aik+1口，这里k从i U j-1 ,故ai皿可采取如下的计算次序1.4 源代码#include "iostream"#include "algorithm"#include "fstream"using namespace std;/*之间以某种方式加括号后，结果为a之间以某种方式加括号后，结果为b之间以某种方式加括号

6、后，结果为cfij0表示在chichjfij1表示在chichjfij2表示在chichja = a*c | b*c | c*ab = a*a | a*b | b*bc = b*a | c*b | c*c */int f50503;char chars3 = 'a', 'b', 'c'int mul(int n, char ch)for(int i=0; i<n; i+)for(int k=0; k<3; k+)fiik = (chi = charsk ? 1: 0);/* a = a*c | b*c | c*ab = a*a | a

7、*b | b*b c = b*a | c*b | c*c */规模for(int r=1; r<n; r+) /for(i=0; i<n-r; i+) /区间左端点int j = i + r; /区间右端点for(int k=i; k<j; k+) /fij0+=fik1*fk+1j2 + fik2*fk+1j0;断点fik0*fk+1j2fij1+=fik0*fk+1j1 + fik1*fk+1j1;fij2+=fik2*fk+1j1 + fik2*fk+1j2;fik0*fk+1j0fik1*fk+1j0return f0n-10;int main()ifstream f

8、in("mul.txt");cout << "输入字符串："char ch100;fin >> ch; cout << ch;int n = strlen(ch);cout << "n 结果为a的加括号方式为："<< mul(n, ch) << endl;fin.close();return 0;1.5 最终结果l = Jbblih口加括号方式为：62 .动态规划解决汽车加油行驶问题2.1 问题描述给定一个N*N的方形网络，设其左上角为起点坐标为(1 , 1),

9、X轴 向右为正，Y轴向下为正，每个方格边长为 1。一辆汽车从起点。出发驶向 右下角终点， 其坐标为(M N)o在若干网格交叉点处，设置了油库，可供 汽车在行驶途中，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下 规则：(1)汽车只能沿网格边行驶，装满油后能行驶 K条网格边。出发时汽车已 装满油，在起点与终点处不设油库。(2)当汽车行驶经过一条网格边时，若其 X坐标或Y坐标减小，则应付费 用B,否则免付费用。(3)汽车在行驶过程中遇油库则应加满油并付加油费用 A。(4)在需要时可在网格点处增设油库，并付增设油库费用C不含加油费A)。(5) (1) (4)中的各数N, K, A, B, C均为

10、正整数。12 356789 丫2.2 算法设计思想这个题目，应该说是刚开始的时候被他给吓到了，只是想着如何去把所有 的条件构造起来，然后使用网络流的方式来解决问题！但是，如果真的是很 冷静下来好好地思考这道题目，就会发现如果没有那些限制条件，就是一个 求解最长路的题目，这样就可以直接使用S PFA来解决这个问题！关键就 是在于这个每次最多只能走K个网格边，这样就是限制了活动的范围，使得 有的边无法扩展！因此可以考虑使用这个分层思想的最短路问题！就是通过 将每一个点进行拆分，这样，就是相当于一种分类讨论的方式！而分类讨论了之后，就知道哪些边是可以扩展的，哪些边是不能扩展的！关键点就是在 于该如何

11、选取变量来分层，这就是因情况而异了！像这道题目之中，就是通 过油量的多少来扩展边的！分层思想，说穿了其实就是相当于这个动态规划 之中的增加变量的方式来确定状态一样，他们的实质其实都是一样的！2.3 设计方法采用的是动态规划的思想来解题，用备忘录的方法进行递归，递归的式子 后面写出.不能直接以汽车行驶的费用为目标来进行动态规划，因为最优子结构性质得不到证明.所以必须把油量和费用一起考虑，作为动态规划的对象，此时就有了最 优子结构性质.最优子结构性质的证明证明：假设品&径M是从起点到终点的一条最小费用路径，P(x,y)是M 经过的一个点(非加油站)，且油量和费用为(g,c),现假设有一条新

12、路径Q从 起点到点P(x,y),使得其在P(x,y)点的油量和费用为(g,c'),其中c'备忘 录递归刚开始的时候为每个网格点 P(x,y)建立一个记录，初始化时，为该记录 存入一个特殊值 W表示汽车未行驶过.那么在汽车行驶过程中，对每个待求 的汽车最小费用值COST先查看其相应的记录项C,如果存储的是初始值W, 那么表示这个点P(x,y)是第一次遇到，此时计算出该点的最小费用值，并保 存在其相应的记录项中，以备以后查看.若记录项C中存储的不是初始值 W, 那么表示该问题已经求解过了 ，其相应的记录项中存储的就是该点的最小费 用值COST此时要取出记录项C的值跟最新的计算出的C

13、OSTa行比较，取其 最小的那个数存入到C中.依此建立记录项C的值，当程序递归完成时，我们 也得到了汽车行驶到(n,n)的最小费用值COST.2.4源代码#include "iostream”#include "algorithm#include "fstream"using namespace std;#define INF 10000/*fij0 表示汽车从网格点(1,1) 行驶至网格点(i,j) 所需的最少费用fij1 表示汽车行驶至网格点(i,j) 还能行驶的网格边数si0表示x 轴方向si1表示y 轴方向si2 表示行驶费用fij0 = min

14、f i+sk0 j+sk1 0 + sk2 fij1 = f i+sk0 j+sk1 1 - 1;f110 = 0f111 = Kfij0 = fij0 + A , fij1 = K如果 (i, j) 是油库fij0 = fij0 + C + A, fij1 = K (i, j)不是油库，且 fij1 = 0*/int N; /方形网络规模int A; /汽车在行驶过程中遇到油库应加满油并付加油费Aint C; /在需要时可在网格点处增设油库，并付增设油库费用C (不含加油费A)int B; / 当汽车行驶经过一条网格边时，如果其x 坐标或 y 坐标减少，应付费用 Bint K; /装满油后，

15、还能行驶K条边int f50502;int s43 = -1,0,0,0,-1,0,1,0,B,0,1,B;int a5050; /方形网络int dyna()(int i, j, k;for (i=1;i<=N;i+)(for (j=1;j<=N;j+)(fij0=INF;fij1=K;f110 = 0;f111 = K;int count = 1;int tx, ty;while(count)(count = 0;for(i=1; i<=N; i+)(for(int j=1; j<=N; j+)(if(i=1 && j=1) continue;int

16、 minStep = INF;int minDstep;int step, dstep;可走的四个方向for(k=0; k<4; k+) / (tx = i + sk0;ty = j + sk1;如果出界if(tx<1 | ty<1 | tx>N | ty>N) /continue;step = ftxty0 + sk2;dstep = ftxty1 - 1;if(aij = 1) /step += A;dstep = K;if(aij=0如果不是油库, 且油已经用完step += A + C;dstep = K;if(step < minStep) /mi

17、nStep = step;minDstep = dstep;如果是油库&&dstep = 0 && (i!=N|j!=N) /可以走如果有更优解if(fij0 > minStep) /count+;fij0 = minStep;fij1 = minDstep;return fNN0;int main()(ifstream fin("car.txt");cout << "输入方格规模："fin >> N; cout << N;cout << "n输入装满油后能行

18、驶的网格边数："fin >> K; cout << K;cout << "n输入加油费："fin >> A; cout << A;cout << "n输入坐标减少时应付的费用："fin >> B; cout << B; s22 = s32 = B;cout << "n输入增设油库费用："fin >> C; cout << C;cout << "n 输入方形网络：n"for(int i=1; i<=N; i+)(for(int j=1; j<=N; j+)(fin >> aij;cout << aij << ""cout << endl;cout << "最优行驶路线所需的费用为："<< dyna() << endl;fin.close();return 0;2.5最终结果