算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题目录1.动态规划解乘法表问题1.1问题描述－-－---1．2算法设计思想----－-1．3设计方法------1．4源代码----－-1.５最终结果－-----2.动态规划解汽车加油行驶问题2.1问题描述－－----２．2算法设计思想--－－－－2.3设计方法------2．4源代码－-－－－-2.5最终结果-－－---3.总结１.动态规划解决乘法表问题1．1问题描述定义于字母表∑{ａ,ｂ，c)上的乘法表如表所示：依此乘法表，对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。例如,对于字符串ｘ＝bbbba,它的一个加括号表达式为(b(ｂb))(bａ)。依乘法表,该表达式的值为a。试设计一个动态规划算法,对任一定义于∑上的字符串x=x1ｘ2…xｎ,计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。1.2算法设计思想设常量a，ｂ，ｃ分别为1,２,3。n为字符串的长度。设字符串的第i到第j位乘积为a的加括号法有resuｌｔ[ｉ］［j］[a］种,字符串的第i到第j位乘积为b的加括号法有reｓult[i][j]［b]种，字符串的第i到第j位乘积为ｃ的加括号法有resｕｌt［i］[j][c]种。则原问题的解是：resuｌt[i][ｎ］［a]。设k为i到ｊ中的某一个字符,则对于k从i到j：resulｔ[ｉ][j][a］+=reｓult[ｉ][k］[a]*resuｌt[k+1][j][ｃ]+resuｌt[i]［k］[b]*reｓuｌt[ｋ+１][j］[c]＋result[i][k]［c]*ｒesult［k+1］［j］[a];result［ｉ][j][b］+＝reｓult[i］［k]［a]*result[k＋１][j][a］+rｅｓuｌt[i］[ｋ][ａ]*resuｌｔ[k+1]［j][b]＋resｕｌt[i］[k]［b]＊resuｌｔ[k＋１]［j］［ｂ]；ｒesult[i][ｊ][c］+=result[ｉ]［k]［b]*resuｌt[ｋ+1］［j][a]+ｒesult[i][k][c]*rｅsｕlt[k+1][j］[b]+reｓult［i][k][c]*rｅsult［k＋１][ｊ][c］;输入：输入一个以ａ,b,c组成的任意一个字符串。输出:计算出的加括号方式数。1.３设计方法乘法表问题直观理解就是通过加括号使得最终运算结果为a,该问题与矩阵连乘问题类似，矩阵连乘是每一次加括号选择运算量最小的,写成数学表达式有:而乘法表问题则是计算所有加括号运算结果为a的情况数,并不要求输出加括号方式。那么可以从乘法的最小单元两个符号相乘的所有可能开始，接着在两个符号相乘的基础上计算三个符号相乘的所有可能。直到计算N长度的符号1-N的所有可能。可以定义一个三维数组a[n][n][3],n为输入字符串的长度,a[i][j］[０]为从字符串中第ｉ个元素到第ｊ个元素的子串表达式值为a的加括号方式数,ａ［ｉ][j][１]为从字符串中第ｉ个元素到第j个元素的子串表达式值为b的加括号方式数，a[i][ｊ][2］为从字符串中第i个元素到第j个元素的子串表达式值为ｃ的加括号方式数。ﻫ由乘法表的定义则可知啊a［i］[j][0]=（对k求和,k从i到j-1)ａ[ｉ][ｋ]［0]*ａ[i］[ｋ＋1]［2]+a[i][ｋ][１]*a[i］[k＋１][2]+a[i］［ｋ][２]*a［i］［k+1][1］;同理可得到a［ｉ］[ｊ][1]和a[i][j］[2]。ﻫ同时由上面的表达式可知,要计算a[i][ｊ][],需先计算a[ｉ］［k][]和a[i］[ｋ+１][]，这里k从i到j-1，故ａ[i][j］[］可采取如下的计算次序1.4源代码＃incｌuｄe＂iｏstｒeam"#ｉncludｅ"algorｉｔhｍ"#inclｕｄe"fstｒeam"uｓiｎgnaｍeｓpacesｔｄ;/*f[i］[ｊ］[0］表示在ｃh[i]~ch[j］之间以某种方式加括号后，结果为aｆ[i]［j][1］表示在cｈ［ｉ]~ch［j]之间以某种方式加括号后，结果为bf[i]［j][２]表示在ch[i]~ch[j]之间以某种方式加括号后,结果为ca＝ａ*ｃ||b*ｃ||c*ab=ａ*a||a*b||ｂ*ｂc=b*ａ|｜c＊b|｜c*c*/intf[５0][5０][3];chaｒchａrs[3］={'a'，'b','c'}；ｉnｔmul(iｎtn,cｈarch［]){for(inti=0;i
