Ricardo Pereira_738665

Não é programação dinamiica namespace Prob_mochla { class Program { /*Atributos da classe*/ /*string: atributo que recebe os dados de saída de printOptmalParents() * para poder exibir o resultado da parentização. */ public static string texto; /*m: atributo que recebe os valores das multiplicações feitas para o melhor custo*/ private static int[,] m; /*s: atributo que recebe o valor das posições de melhor multiplicação*/ private static int[,] s; /*linhas: recebe o valor total das linhas das matrizes.*/ private static int linhas; /*colunas: recebe ovalor total das colunas das matrizes*/ private static int colunas; private static Boolean inicioMatriz; public static int[,] MatrixChainOrder(int[] p) { int[,] retorno = new int[p.Length - 1, p.Length - 1]; //try { int i = 0; //linhas int j = 0; //colunas int k = 0; int q = 0; int infinito = int.MaxValue;//Integer.MAX_VALUE; // tipo infinito positivo (para simular o infinito) int n = p.Length - 1; int[,] m = new int[n, n]; // ixj int[,] s = new int[n, n]; for (i = 0; i < n; i++) { m[i, i] = 0; } for (int l = 1; l < n; l++) { for (i = 0; i < n - l; i++) { j = i + l; m[i, j] = int.MaxValue;//infinito; for (k = i; k < j; k++) { q = m[i, k] + m[k + 1, j] + p * p[k + 1] * p[j + 1]; if (q < m[i, j]) { m[i, j] = q; s[i, j] = k + 1; } } } } retorno = s; } /*catch (Exception e) { System.out.println("Erro: " + e); e.printStackTrace();*/ return retorno; } public String printOptmalParents(int[,] s, int i, int j) { if (i == j) { texto += "A" + (i + 1) + " "; } else { texto += " ( "; printOptmalParents(s, i, s[i, j] - 1); printOptmalParents(s, s[i, j], j); texto += " ) "; } return texto; } public static void inicializaRecursiveMatrixChain(int[] p) { int n = p.Length - 1; m = new int[n, n]; // ixj s = new int[n, n]; inicioMatriz = true; } public static int recursiveMatrixChain(int[] p, int i, int j) { int retorno = 0; if (inicioMatriz) { if (i == j) { retorno = 0; } else { m[i, j] = int.MaxValue;//Integer.MAX_VALUE; for (int k = i; k <= j - 1; k++) { int q = recursiveMatrixChain(p, i, k) + recursiveMatrixChain(p, k + 1, j) + p * p[k + 1] * p[j + 1]; if (q < m[i, j]) { m[i, j] = q; s[i, j] = k + 1; } } retorno = m[i, j]; } } return retorno; }