[Java]sequenza palindroma

[ifts2004]

ciao a tutti dovrei controllare se all'interno di un array di interi vi è presente una sequenza palindorma:
-se presente devo fare una return del numero degli interi palindromi( es. 2 3 1 5 1 7 7 come return devo dare 3 perchè la sequenza palindroma è composta da 1 5 1 cioè 3 numeri)
-altrimenti se non è presente nessuna sequenza palindorma devo dare in return 1

io pensavo di fare un ciclo i che parte da 0 che controlla A , in i++ e poi faccio partire un ciclo j dall'ultimo elemento che controlla A[j] in j--. Se A==A[j] incremento un contatore c che faccio partire da 1(da 1 perchè se elemento dx =elemento sinistra vuol dire che sono 2 numeri uguali) altrimenti se A!=A[j] faccio una return di 1.


voi che ne dite?

[apatriarca]

Mi dispiace ma non credo di aver capito cosa vorresti fare esattamente. Prova a scrivere il tuo algoritmo in Java o pseudo-codice in modo da renderlo più chiaro.

[Umby2]

Per sequenza intendi dire almeno 3 numeri ?

Hai considerato anche le sequanze pari ? Ad esempio: [1 4 4 1] (sembra di no... almeno da quello che ho capito)

[provola-votailprof]

"ifts2004":ciao a tutti dovrei controllare se all'interno di un array di interi vi è presente una sequenza palindorma:
-se presente devo fare una return del numero degli interi palindromi( es. 2 3 1 5 1 7 7 come return devo dare 3 perchè la sequenza palindroma è composta da 1 5 1 cioè 3 numeri)
-altrimenti se non è presente nessuna sequenza palindorma devo dare in return 1

io pensavo di fare un ciclo i che parte da 0 che controlla A , in i++ e poi faccio partire un ciclo j dall'ultimo elemento che controlla A[j] in j--. Se A==A[j] incremento un contatore c che faccio partire da 1(da 1 perchè se elemento dx =elemento sinistra vuol dire che sono 2 numeri uguali) altrimenti se A!=A[j] faccio una return di 1.


voi che ne dite?

stavo per rispondere in un modo, ma non mi è ben chiaro l'esercizio... infatti nel tuo esempio io vedo due sequenze palindrome, 1 5 1 e 7 7...

[Mega-X]

Scrivo in metalinguaggio/Java un possibile algoritmo risolutore (Che molto probabilmente è molto lontano dall'essere il migliore )

int trovaPalindromi(int[] v)
{
 int ret = 0; // Il numero di palindromi trovati
 for (int i = 0; i < v.length; i++) // Scandisco la stringa in avanti
 {
  for (int j = v.length-1; j >= 0; j--) // Scandisco la stringa al contrario
  {
   int mid = Math.ceiling(Math.abs((i-j)/2)); // Vedi più sotto
   for (int k = 0; k < mid; k++) if (v[i+k] != v[j-k]) break; // Vedo se nell'intervallo $[i,j]$ il vettore è palindromo, se trovo un $k$ tale che v[i+k] != v[j-k] allora esco dal ciclo
   if (k == mid) ret++; // Se non esiste nessun $k$ tale che v[i+k] != v[j-k] allora ho trovato un palindromo
  }
 }
 return ret;
}

Ora rimane una questione da chiarire: perché ho scelto $mid = |~(|i-j|)/2~|$ ed il for con variabile $k$ va da $0$ a $mid$ (Estremo superiore escluso)?

Caso 1: ho un palindromo del tipo $x,x$

in questo caso $|i-j| = 1$ quindi $|~|i-j|/2~| = 1$ e quindi $mid$ va da $0$ a $0$ (Estremi inclusi) dunque l'algoritmo controlla se $x$ == $x$, il che è vero.

Caso 2: ho un palindromo del tipo $x,a,x$

in questo caso $|i-j| = 2$ quindi $|~|i-j|/2~| = 1$, quindi $mid$ va da $0$ a $0$ (Estremi inclusi) dunque l'algoritmo controlla semplicemente se $x$ == $x$, saltando l'elemento $a$.

Terzo e ultilmo caso: ho un palindromo del tipo $x, a_1, ..., a_n, x$ con $n >= 2$.

Questo caso contiene 2 sottocasi:

1. $n$ pari: in questo caso l'algoritmo controlla semplicemente se la sequenza è un palindromo.
2. $n$ dispari: in questo caso l'algoritmo salta, come nel caso 2, l'elemento centrale in posizione $(i+j)/2$

Detto ciò possiamo asserire che l'algoritmo è corretto.

[apatriarca]

Come già notato da altri, l'esercizio non è stato definito correttamente in quanto non è chiaro il comportamento da avere in caso di più sequenze palindrome. Suppongo quindi che il metodo debba restituire la lunghezza della successione palindroma più grande.

@Mega-X: il tuo metodo se pur corretto non è molto efficiente. Infatti verifichi che una successione palindroma con centro $mid$ esista per ogni $i$ e $j$ per cui valga la tua formula. Un'idea migliore sarebbe quindi quella di iterare su tutte le possibili posizioni e verificare se sono centro di una successione palindroma come segue:

int trovaPalindromi(int[] v) {
    int ret = 1; // massima lunghezza dei palindromi trovati
    
    final numPos = 2 * v.length - 3;

    for (int pos = 1; i <= numPos; ++i) {
        int halfPos = pos / 2;

        int i = (pos % 2 == 0) ? halfPos - 1 : halfPos;
        int j = halfPos + 1;
        
        int count = (pos % 2 == 0) ? 1 : 0;
        while (i >= 0 && j < v.length && v[i] == v[j]) {
            --i; ++j; count += 2;
        }

        if (count > ret) ret = count;
    }

    return ret; 
}

Il codice non è stato testato. Questo metodo rimane comunque di complessità quadratica mentre ne esistono di migliori.

[Mega-X]

"apatriarca":@Mega-X: il tuo metodo se pur corretto non è molto efficiente. Infatti verifichi che una successione palindroma con centro $mid$ esista per ogni $i$ e $j$ per cui valga la tua formula. Un'idea migliore sarebbe quindi quella di iterare su tutte le possibili posizioni e verificare se sono centro di una successione palindroma

Il punto è che io ho cercato TUTTE le sequenze palindrome dentro il vettore, non solo quella più grande.

[apatriarca]

Ma anche cercandole tutte è secondo me più conveniente partire dal centro.