Lógica para resolução de um problema

Programação Java
#1

Bom, é o problema clássico do palíndrome, mas não para determinar se uma palavra é um palíndrome, mas em quantas vezes é necessário dividir uma sequência de letras para que todas se tornem palíndromes.

"Uma cadeia de caracteres é chamada de palíndrome se seqüência de caracteres da esquerda para a direita é igual à seqüência de caracteres da direita para a esquerda (uma outra definição é que o primeiro caractere da cadeia deve ser igual ao último caractere, o segundo caractere seja igual ao penúltimo caractere, o terceiro caractere seja igual ao antepenúltimo caractere, e assim por diante). Por exemplo, as cadeias de caracteres ‘mim’, ‘axxa’ e ‘ananaganana’ são exemplos de palíndromes.

Se uma cadeia não é palíndrome, ela pode ser dividida em cadeias menores que são palíndromes. Por exemplo, a cadeia ‘aaxyx’ pode ser dividida de quatro maneiras distintas, todas elas contendo apenas cadeias palíndromes: {‘aa’, ‘xyx’}, {‘aa’, ‘x’, ‘y’, ‘x’}, {‘a’, ‘a’, ‘xyx’} e {‘a’, ‘a’, ‘x’, ‘y’, ‘x’}."

“Escreva um programa que determine qual o menor número de partes em que uma cadeia deve ser dividida de forma que todas as partes sejam palíndromes.”

Exemplo: bbabcbbaab deve ter 4 partes.

Alguém pode meajudar com a lógica? Eu queria usar um método recursivo mas estou com alguns problemas quando a sequência fica com número ímpar de letras.

#2

vc pode fazer o seguinte, vc cria um for q comeca com o valor inicial com o numero de letras, e vai decrementando, dai dentro dece for, vc poe um for interno q testa todas as posicoes, dai vc usa chamada recursiva para as duas partes, algo ± assim:

public void isPalidrome(String p){
 for (int i = 0; i < p.length() / 2; i++){
  if (p.charAt(i) != p.charAt(p.length() - i - 1)) return false;
 }
 return true;
}
public int getNum(String p){
 int x = 0;
 for (int i = p.length(); i > 0; i--){
  for (int j = 0; j >= p.length() - i; j++){
   if (isPalidrome(p.substring(j, i))){
    x++;
    x += getNum(p.substring(0, j));
    x += getNum(p.substring(j + i));
    return x;
   }
  }
 }
 return 0;
}

nem testei… mas eh soh vc seguir a logica q deve funcionar…

#3

Epa, gostei! :grin:

Mas, se por exemplo eu passar a sequência abccde? Seu programa só vai achar um palídrome quando atingir o cc. Então ele vai somar 1 ao x, e chamar o getNum para ab e de. Como nenhum é palîndrome ele vai deixar por isso. Entretando ele deveria dividir o ab em a e b somando um ao x e o de em d e e, então somar mais um ao x.

#4

hum…
tenta fazer o seguinte…Palindrome…imagina assim WiM
W=cadei de carecteres
i=parte central
M=cadeia W inversa…
De repente podes tentar alguma coisa com StringTokenizer para achar o valor do meio…e separar as duas partes…W e M…
apos separadas as partes verifica se uma eh o inverso da outra…
Acho que eh por ai…

#5

tipo… o q tava acontecendo era q tava dando erro com o substring, mas a logica ta certa… agora com mais calma eu arrumei… agora funciona:

 public static boolean isPalidrome(String p){
  for (int i = 0; i < p.length() / 2; i++){
   if (p.charAt(i) != p.charAt(p.length() - i - 1)) return false;
  }
  return true;
 }
 public static int getNum(String p){
  int x = 0;
  for (int i = p.length(); i > 0; i--){
   for (int j = 0; j <= p.length() - i; j++){
    if (isPalidrome(p.substring(j, i + j))){
     x++;
     x += getNum(p.substring(0, j));
     x += getNum(p.substring(j + i));
     return x;
    }
   }
  }
  return 0;
 }
#6

Valeu a ajuda Felipe, aqui ta o resultado depois de algumas modificações:

	public static boolean isPalidrome(String p) {
		for (int i = 0; i < p.length() / 2; i++) {
			if (p.charAt(i) != p.charAt(p.length() - i - 1))
				return false;
		}
		return true;

	}
	public static int getNum(String p) {
		int x = 1;
		for (int i = 0; i < p.length(); i++) {
			for (int j = p.length(); j > i + 1; j--) {
				if (isPalidrome(p.substring(i, j))) {
					x += getNum(p.substring(0, i));
					x += getNum(p.substring(j));
					return x;
				}
			}
		}
		return p.length();
	}

Testado com as sequencias:
axa - Resp: 1
xyzyyx - Resp: 4
bbabcbbaab - Resp: 4

#7

[quote=“Highter”]Bom, é o problema clássico do palíndrome, mas não para determinar se uma palavra é um palíndrome, mas em quantas vezes é necessário dividir uma sequência de letras para que todas se tornem palíndromes.

"Uma cadeia de caracteres é chamada de palíndrome se seqüência de caracteres da esquerda para a direita é igual à seqüência de caracteres da direita para a esquerda (uma outra definição é que o primeiro caractere da cadeia deve ser igual ao último caractere, o segundo caractere seja igual ao penúltimo caractere, o terceiro caractere seja igual ao antepenúltimo caractere, e assim por diante). Por exemplo, as cadeias de caracteres ?mim?, ?axxa? e ?ananaganana? são exemplos de palíndromes.

Se uma cadeia não é palíndrome, ela pode ser dividida em cadeias menores que são palíndromes. Por exemplo, a cadeia ?aaxyx? pode ser dividida de quatro maneiras distintas, todas elas contendo apenas cadeias palíndromes: {?aa?, ?xyx?}, {?aa?, ?x?, ?y?, ?x?}, {?a?, ?a?, ?xyx?} e {?a?, ?a?, ?x?, ?y?, ?x?}."

“Escreva um programa que determine qual o menor número de partes em que uma cadeia deve ser dividida de forma que todas as partes sejam palíndromes.”

Exemplo: bbabcbbaab deve ter 4 partes.

Alguém pode meajudar com a lógica? Eu queria usar um método recursivo mas estou com alguns problemas quando a sequência fica com número ímpar de letras.[/quote]

esta estudando os exercicios para aq OBI?

#8

OIB?

Não isso foi um problema que um amigo me pediu pra resolver que um professor tinha passado.

#9