Olá, 
Criei um programa que lê uma matriz quadrada e com a ordem dessa matriz determina todas as sequencias possiveis. Por exemplo, se a ordem da matriz for 4 determina todas combinaçoes com os numeros 0, 1, 2, 3.
Sendo que os numeros das combinações correspondem a posiçoes na matriz inserida. Para cada combinação o programa faz a soma maxima dos elementos da matriz.
O programa já cria todas as sequencias e descobre a soma maxima. Mas nao guarda a sequencia correspondente à soma maxima.
O codigo é o seguinte:
package mdisc;
import java.io.PrintStream;
import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;
/**
*
* @author
*/
public class MDISC {
public static void main(String[] args) {
MDISC programa = new MDISC();
programa.menu();
}
private final Scanner entrada = new Scanner(System.in);
private final PrintStream saida = System.out;
private static int[][] matriz;
private static int[] p;
private static int somaMax;
private static int[] seq;
/**
* Executa este programa
*/
public void executarMatrizInserida(){
// Introdução dos valores da matriz no formato x,y,z,...
saida.println("Introduza os valores no formato A,B,C,D: ");
saida.println(" A B ");
saida.println(" C D ");
saida.println("Valores: ");
String stringDeNumeros = entrada.nextLine();
// converte a string para um vetor de strings
String[] vetorString = stringDeNumeros.split(",");
int[] vetorInt = stringsParaInts(vetorString);
saida.println("Matriz introduzida: ");
// converte o vetor para uma matriz
matriz = converteVetorEmMatriz(vetorInt);
int ordem = matriz.length;
int v[] = new int[ordem];
for (int y=0; y<ordem; y++){
v[y]=y;
}
// imprime a matriz
imprimirMatriz(matriz);
permuta1(v);
// sequencia
System.out.println("Valor máximo: " + somaMax);
System.out.println("Sequencia com soma máxima: " );
for (int y=0; y<seq.length;y++) System.out.print(seq[y] + " ");
menu();
}
private void permuta(int []vet, int n) {
if (n==vet.length) {
sequencias();
} else {
for (int i=0; i < vet.length; i++) {
boolean enc = false;
for (int j = 0; j < n; j++) {
if (p[j]==vet[i]) enc = true;
}
if (!enc) {
p[n] = vet[i];
permuta(vet,n+1);
}
} //--for
} //--if/else
}
public void permuta1(int [] vet) {
p = new int[vet.length];
permuta(vet,0);
}
public void sequencias(){
int soma=0;
for (int i=0; i < p.length; i++) {
if ( i+1==p.length){
soma=soma+matriz[p[0]][p[p.length-1]];
}
else {
soma=soma+matriz[p[i]][p[i+1]];
}
somaMaximaSeq(soma);
}
}
public void somaMaximaSeq(int soma){
seq = new int[p.length];
if (soma<somaMax){
somaMax=soma;
for (int i=0; i < p.length; i++) {
seq[i]=p[i];
}
}
}
public void executarMatrizAleatoria(){
saida.println(" ");
saida.println("Insira a ordem da matriz a gerar: ");
int ordem = Integer.parseInt(entrada.nextLine());
// gerar matrizes aleatoriamente com valores entre [0,100] com as diagonais em zero.
int[][] matrizAleatoria = gerarMatriz(ordem, 100);
saida.println(" ");
// Imprimir matriz gerada aleatoriamente
saida.println("Matriz gerada aleatoriamente de ordem " + ordem + ":");
saida.println(" ");
imprimirMatriz(matrizAleatoria);
int v[] = new int[ordem];
for (int y=0; y<ordem; y++){
v[y]=y;
}
permuta1(v);
// Sequencia da matriz
//int [] seq = sequencia(ordem, 2);
System.out.println(" ");
System.out.println("Soma máxima: " + somaMax);
System.out.println(" ");
System.out.println("Sequencia com soma máxima: " );
for (int y=0; y<seq.length;y++) System.out.print(seq[y] + " ");
menu();
}
public void menu(){
Scanner ler2 = new Scanner(System.in);
System.out.println(" ");
System.out.println("Insira a operação que deseja efetuar:");
System.out.println(" ");
System.out.println("1 - Matriz inserida e sequencia e soma máxima ");
System.out.println("2 - Matriz aleatoria e sequencia e soma máxima ");
System.out.println("3 - Fatorial");
System.out.println("4 - Sair");
System.out.println(" ");
System.out.print("Insira a opção: ");
int opcao = ler2.nextInt();
System.out.println(" ");
switch(opcao){
case (1):
executarMatrizInserida();
break;
case (2):
executarMatrizAleatoria();
break;
case (3):
executarFatorial();
break;
case (4):
System.exit(0);
break;
}
}
/*
* Converte o vetor anteriormente convertido em int para uma matriz quadrada
*/
private int[][] converteVetorEmMatriz(int[] vetor) {
int ordem = (int) Math.sqrt(vetor.length);
matriz = new int[ordem][ordem];
try {
int posicao = 0;
for (int linha = 0; linha < ordem; linha++) {
for (int coluna = 0; coluna < ordem; coluna++) {
matriz[linha][coluna] = vetor[posicao++];
}
}
} catch (ArrayIndexOutOfBoundsException e) {
saida.println("Erro: Não introduziu valores correspondentes a uma matriz quadrada! " + e);
}
return matriz;
}
public void executarFatorial(){
System.out.println("Insira um valor: ");
int valor = entrada.nextInt();
try {
System.out.println(fatorial(valor));
} catch (ArrayIndexOutOfBoundsException e) {
saida.println("Erro: Não introduziu valores correspondentes a uma matriz quadrada! " + e);
}
menu();
}
/*
* Calcula o fatorial de um valor. Utilizamos o bigInteger para permitir calcular valores elevados
*/
private BigInteger fatorial(int valor) {
BigInteger factorial = new BigInteger("1");
for (int i = 1; i <= valor; i++) {
factorial = factorial.multiply(new BigInteger(i + ""));
}
return factorial;
}
/**
* Gerar matrizes de ordem informada aleatoriamente com valores entre 0 e o 100, com as diagonais em zero.
*/
private int[][] gerarMatriz(int ordem, int limite) {
Random gerador = new Random();
matriz = new int[ordem][ordem];
for (int linha = 0; linha < ordem; linha++) {
for (int coluna = 0; coluna < ordem; coluna++) {
if (linha == coluna){
matriz[linha][coluna] = 0;
}
else {
int ger = gerador.nextInt(limite);
matriz[linha][coluna]=ger;
matriz[coluna][linha]=ger;
}
}
}
return matriz;
}
/**
* Imprime a matriz passada pelo parametro
*/
private void imprimirMatriz(int[][] matriz) {
for (int linha = 0; linha < matriz.length; linha++) {
for (int coluna = 0; coluna < matriz[linha].length; coluna++) {
String espaco = matriz[linha][coluna] < 10 ? " " : " ";
saida.print(espaco + matriz[linha][coluna] + espaco);
}
saida.println(" ");
}
}
/**
* Converte um array de String para um array de inteiros
*/
private int[] stringsParaInts(String[] strings) {
int ints[] = new int[strings.length];
try {
for (int i = 0; i < strings.length; ++i) {
ints[i] = Integer.parseInt(strings[i].trim());
}
} catch (NumberFormatException e) {
saida.println("Erro: Não introduziu apenas numeros! " + e);
}
return ints;
}
}
O codigo correspondente a fazer a soma maxima é o seguinte:
public void sequencias(){
int soma=0;
for (int i=0; i < p.length; i++) {
if ( i+1==p.length){
soma=soma+matriz[p[0]][p[p.length-1]];
}
else {
soma=soma+matriz[p[i]][p[i+1]];
}
somaMaximaSeq(soma);
}
}
public void somaMaximaSeq(int soma){
seq = new int[p.length];
if (soma<somaMax){
somaMax=soma;
for (int i=0; i < p.length; i++) {
seq[i]=p[i];
}
}
}
Alguem me consegue ajudar a guardar na seq a seuqencia com a primeira maior soma? Obrigado