动态规划实验_算法分析与设计.doc

动态规划实验实验二：在=a,b,c上定义乘法：abcabbabcbacacc若x = x1x2.xn 是上的乘法运算表达式。则x存在多少种可能的运算顺序，其结果均为a.动态规划算法所解问题的基本特征：1、 最优子结构性质2、 子问题重叠性质分析：上的任意串x = x1x2.xn ，有多少种可能的计算顺序使x = a.设子问题：xij = xixi+1.xkxk+1.xj ,它有 mij0种不同的计算顺序，使得xij = amij1种不同的计算顺序，使得xij = bmij2种不同的计算顺序，使得xij = c（其中0代表a,1代表b,2代表c）1xi = a & i=jmij0=0xi != a & i=j(k=i,j-1)(mik0*mk+1j2+mik1*mk+1j2+mik2*mk+1j0)(k=i,j-1)：“k=i”在的下方，“j-1”在的上方)package dynamic_programming;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;public class MultiplicationTable private static String str = null;public static void main(String args) InputStream inputStream = System.in;InputStreamReader inputStreamReader = new InputStreamReader(inputStream);BufferedReader bufferedReader = new BufferedReader(inputStreamReader);tryout: while(true)System.out.print(Please input a string: );if(str = bufferedReader.readLine().length() = 0)System.out.println(Empty Input! );continue;for(char ch : str.toCharArray()if(ch c | ch a)System.out.println(Illegal Input! input among a, b or c);continue out;break;catch(IOException e)e.printStackTrace();int n = str.length();int a = new intnn3;/intialize the arrayfor(int i = 0; i n; i+)for(int j = 0; j n; j+)for(int k = 0; k 3; k+)aijk = 0;/get info from the given string for(int i = 0; i n; i+)aiistr.charAt(i) - a = 1;/here 0:a, 1:b, 2:c for(int s=0;sn;s+) for(int v=0;vn;v+) /System.out.print(asv0+ ); /System.out.println(); /System.out.println(b啊啊啊啊啊); for(int s=0;sn;s+) for(int v=0;vn;v+) /System.out.print(asv1+ ); /System.out.println(); /System.out.println(c啊啊啊啊啊); for(int s=0;sn;s+) for(int v=0;vn;v+) /System.out.print(asv2+ ); /System.out.println(); for(int k = 1; k n; k+) /the length of a pair of brackets from 1 to n - 1 for(int i = 0; i n - k; i+) /the position of the first bracket int j = i + k; for(int t = i;t j;t+) /t is the position of the second bracket from i to j - 1 aij0 += ait2 * at+1j0 /c * a = a + ait0 * at+1j2 /a * c = a + ait1 * at+1j2; /b * c = a / System.out.print(aij0=+aij0+t=+t+ +i=+i+ +j=+j+ ); aij1 += ait0 * at+1j0 /a * a = b + ait0 * at+1j1 /a * b = b + ait1 * at+1j1; /b * b = b / System.out.println(bbbbbbbbbbb); / System.out.print(aij1=+aij0+t=+t+ +i=+i+ +j=+j+ ); aij2 += ait1 * at+1j0 /b * a = c + ait2 * at+1j1 /c * b = c + ait2 * at+1j2; /c * c = c / System.out.println(cccccc); / System.out.print(aij2=+aij0+t=+t+ +i=+i+ +j=+j+ ); / System.out.println(); for(int s=0;sn;s+) for(int v=0;vn;v+) System.out.print(asv0+ ); System.out.println(); System.out.println(b啊啊啊啊啊); for(int s=0;sn;s+) for(int v=0;vn;v+) System.out.print(asv1+ ); System.out.println(); System.out.println(c啊啊啊啊啊); for(int s=0;sn;s+) for(int v=0;vn;v+) System.out.print(asv2+ ); System.out.println(); int result=0; for(int s=0;sn;s+) for(int v=0;vn;v+) result+=asv0; / a0n-10 means the number of methods str0 to n-1 which equals a / System.out.println(一共有: + a0n-10+.+result+种可能); System.out.println(一共有: +result+种可能); 程序的执行：输入：cbabca，结果是a有38种可能Please input a string: cbabca0 0 1 0 5 19 0 0 0 0 2 5 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 b啊啊啊啊啊0 0 0 1 1 6 0 1 0 1 1 4 0 0 0 1 1 2 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 c啊啊啊啊啊1 1 1 4 8 17 0 0 1 1 2 5 0 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 一共有: 38种可能输入：bcabca，结果是a有37种可能Please input a string: bcabca0 1 0 1 7 14 0 0 1 0 2 5 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 b啊啊啊啊啊1 0 1 3 3 15 0 0 0 1 1 3 0 0 0 1 1 2 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 c啊啊啊啊啊0 0 1 1 4 13 0 1 0 1 2 6 0 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 一共有: 37种可能输入：acbabba，结果是a有108种可能1 1 1 2 5 14 49 0 0 0 1 0 0 23 0 0 0 0 0 0 6 0 0 0 1 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 b啊啊啊啊啊0 0 1 2 8 26 51 0 0 0 0