Problema no algoritmo!

Programação Java
#1

Estou com um problema em um algoritimo onde eu tenho que contar quantas capicuas(nºs palindromos) existem dentro de um array que é inserido pelo usuário.

a idéia é +ou- assim:

vamos supor que seja o seguinte array

[1, 2, 3, 3, 2, 1]

aqui existem 3 capicuas, a 3,3; 2,3,3,2; e 1,2,3,3,2,1;

se fosse mudado para

[2,2,3,3,2,1]

seriam: 2,2; 3,3; 2,3,3,2;

enfim, não estou conseguindo gerar o algoritmo, eu até tenho a noção d como fazer, o mais facil seria gerar uma variável auxiliar para definir o tamanho de capicua a ser procurada, usando 2 for/while, porém o problema é quando eu acho 2 nºs iguais como no exemplo 2, [2,3,3,2], ele soh reconhece o 2==2, e não o 2,3,3,2.
se mudasse pra [2,3,1,2], ele continuaria contando.

se alguem puder me ajudar eu agradeço!!!

#2

alguém pls?

#3

[quote=kahhhxd]vamos supor que seja o seguinte array

[1, 2, 3, 3, 2, 1]

aqui existem 3 capicuas, a 3,3; 2,3,3,2; e 1,2,3,3,2,1; [/quote]

Desculpe a minha ignorancia, mas neste teu exemplo acho que existem 2 palindromos; o 123 e o 321. É isso mesmo ou estou completamente enganado?

flws

#4

Sim… acho que voce confundiu… palindromo é aquele que é lido da mesma forma da esquerda para a direita quanto da direita para a esquerda

#5

Humm…entendi.

Outras perguntas:

a) O número de elementos no array é sempre par?

b) O Tamanho dos polindromos tem que ser sugerido pelo usuario, ou o algoritimo tem que impor os possíveis tamanhos e retornar os polindromos possíveis para os tamanhos sugeridos?

flws

#6

Versão 1. Não testei muitos casos. Se alguém achar algum caso em que o programa falhe ou conseguir melhorar o código é só postar.

[code]public class Palindromos {

int[] arr;

public Palindromos(int… valores) {
arr = valores;
}

public void imprimirPalindromos() {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
boolean pali = true;
for (int k = i; k <= i + j - k; k++) {
if (arr[k] != arr[i + j - k]) {
pali = false;
break;
}
}
if (pali) {
imprimirPalidromo(i, j + 1);
}
}
}
}

private void imprimirPalidromo(int begin, int end) {
// Aqui eu imprimo mas dá pra fazer qualquer outra coisa
String palindromo = “”;
for (int i = begin; i < end; i++) {
palindromo += arr[i] + " ";
}
System.out.println(palindromo);
}

public static void main(String[] args) {
Palindromos pal = new Palindromos(2, 2, 3, 3, 2, 2, 1);
pal.imprimirPalindromos();
}
}[/code]Obs.: Não sou de entregar de cara a resposta mas como tem sempre alguém que assim faz, meu ego tá falando mais alto que meu lado didático estes dias, principalmente com esses desafios legais.

#7

Versão 2: public void imprimirPalindromos() { for (int i = 0; i < arr.length; i++) { for (int j = i, k = i+1; j >= 0 && k < arr.length; j--, k++) { if(arr[j] == arr[k]) { imprimirPalidromo(j, k+1); } } } }
EDIT: Há uma relação entre j e k, fazendo-se desnecessário o uso de k, mas ainda não a encontrei.

#8

Registre-se no projecteuler.net, acho que é mais interessante.

EDIT - Ah, vi que você se registrou, e resolveu o problema 12:

http://projecteuler.net/index.php?section=profile&profile=ozix

que é justamente aquele que a gente estava comentando aqui no GUJ.

#9

[quote=fantomas]Humm…entendi.

Outras perguntas:

a) O número de elementos no array é sempre par?

b) O Tamanho dos polindromos tem que ser sugerido pelo usuario, ou o algoritimo tem que impor os possíveis tamanhos e retornar os polindromos possíveis para os tamanhos sugeridos?

flws

[/quote]

a) não, o nº de elementos pode variar, no momento eu to usando um array de tamanhp 20

b)o algoritmo tem q impor os possiveis tamanhos e retornar qnts palindromos existem no total, não importando o tamanho.

mesmo assim vlw por tudo todo mundo, vou tentar aplicar o algoritmo que o ozix colocou ai no que eu já estava fazendo pra ver onde eu estava errando!

Obrigado.

#10

Agora to batendo cabeça com o 230. É melhor começar pelos mais fáceis, inclusive porque, como diz na página inicial, o conhecimento adquirido ajudará nos mais difíceis. Mas eu acabei me interessando por esse. Estou quase conseguindo, depois vou fazer na ordem de dificuldade.

#11

Não é só o conhecimento adquirido, mas também as próprias soluções dos problemas podem lhe ajudar. Por exemplo, muitos problemas requerem rotinas de fatoração ou de obtenção de números primos.

#12