Ricerca ternaria ricorsiva

CiroCappy

il 29 giu 2020, 11:06

13 risposte

CiroCappy

Pochi posts

Iscritto da: giu, 2020

Messaggi:: 6

Ricerca ternaria ricorsiva

29 giu 2020, 11:43

Salve sono un novizio nella programmazione Java e nel forum, spero mi possiate aiutare con questo esercizio.
"Scrivere un algoritmo ricorsivo di ricerca ternaria che divida un array in tre parti anziché le due utilizzate dalla ricerca binaria"!
Questo di seguito è il codice che ho prodotto sbagliando:


package ricorsione;

import java.util.Scanner;

public class SestoEsercizioRicorsione {

	public static int ricercaTernaria(int a[],int obiettivo,int primo,int ultimo){
		int risultato;
		if(primo>ultimo)
			risultato=-1;
		else{
			int med= (primo+ultimo)/3;
			if(obiettivo==a[med])
				risultato = a[med];
			else if(obiettivo==a[med*2])
				risultato=a[med*2];
			else if (obiettivo < a[med])
				risultato= ricercaTernaria(a, obiettivo, primo, med-1);
			else if(obiettivo>a[med] && obiettivo<a[med*2])
				risultato= ricercaTernaria(a, obiettivo, med+1, 2*med-1);
			else 
				risultato= ricercaTernaria(a, obiettivo, 2*med+1, ultimo);
		}
		return risultato;
	}


	public static int trova(int[] a, int obiettivo) {
		return ricercaTernaria(a, obiettivo, 0, a.length-1);
	}


	//7.4 esercizi numero 8
	public static void main(String[] args) {
		int [] unArray = {1,2,3,4,5,6,7,8,9,10};
		Scanner tastiera = new Scanner (System.in);
		System.out.println();
		for (int i = 0; i < 10; i++)
			System.out.print("a[" + i + "]=" + unArray[i] + " ");
		System.out.println();
		System.out.println();
		String risposta;
		do {
			System.out.println("Inserire un valore da cercare:");
			int obiettivo = tastiera.nextInt();
			int risultato = trova(unArray, obiettivo); 
			if (risultato < 0) 
				System.out.println(obiettivo +" non è nell'array.");

			else
				System.out.println(obiettivo + " è alla posizione " + risultato);
			System.out.println("Nuova ricerca?"); 
			risposta = tastiera.next();
		} while (risposta.equalsIgnoreCase("si"));
	}

}

Spero mi sappiate correggere dove ho sbagliato e se ho preso una strada del tutto errata, mi sappiate dare la giusta imbeccata per risolvere l'esercizio. Grazie in anticipo.

13 Risposte

andbin
Super Famoso
Iscritto da
ott, 2013
Messaggi:
6272
Re: Ricerca ternaria ricorsiva
29 giu 2020, 14:45
CiroCappy ha scritto:
Spero mi sappiate correggere dove ho sbagliato e se ho preso una strada del tutto errata, mi sappiate dare la giusta imbeccata per risolvere l'esercizio.
Partiamo da un aspetto generale. Quando si fa una ricerca di questo tipo ("dicotomica" come si dice in italiano), l'obiettivo dovrebbe essere quello di trovare e restituire l'INDICE (o -1), non il valore che stai proprio cercando. Se cerchi es. 6 e poi il trova ti restituisce 6.... non è molto utile .... e poi non potresti facilmente distinguere un valore -1 dal -1="non trovato". Quindi, ripeto, l'obiettivo è fornire un indice.

Poi comunque il tuo ricercaTernaria fallisce (nel senso che va in "loop" continuo e poi si schianta con StackOverflowError) quando cerchi dei valori specifici.

Con l'array {1,2,3,4,5,6,7,8,9,10}, se cerchi 5 le invocazioni di ricercaTernaria sono:
```
primo=0 ; ultimo=9  (invocazione iniziale)
    primo=3 ; ultimo=6  (prima ricorsione)
        primo=4 ; ultimo=5  (seconda ricorsione)
```
Il problema è che (4+5)/3 fa ... 3 ovvero è prima di primo!!

Quindi ragionaci un po' sopra (anche il fatto dell'indice detto sopra). Per ulteriori dubbi, chiedi.
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6011
Re: Ricerca ternaria ricorsiva
29 giu 2020, 15:06
Intanto DESCRIVI come DOVREBBE FUNZIONARE una ""ricerca ternaria"".

Quello che hai scritto NON CENTRA UNA ""CIPPA"" con la ricerca TERNARIA

Stai ANCORA facendo una ricerca BINARI ANCHE se hai diviso il range per 3!!!!

No ti possiamo anche ""imbeccare", ma tu, il mangime, lo devi ""digerire""
andbin
Super Famoso
Iscritto da
ott, 2013
Messaggi:
6272
Re: Ricerca ternaria ricorsiva
29 giu 2020, 15:19
migliorabile ha scritto:
Stai ANCORA facendo una ricerca BINARI ANCHE se hai diviso il range per 3!!!!
Premetto che "ricerca ternaria" non l'avevo ancora sentito .... ma non è come quella binaria solo con 3 suddivisioni invece che 2?? Con 3 partizioni per invocazione, intuitivamente, si dovrebbe arrivare prima al risultato (riduce di più ...).

EDIT:
@CiroCappy, comunque direi che è sbagliato il (primo+ultimo)/3 cioè NON va fatto così.
C
CiroCappy
Pochi posts
Iscritto da
giu, 2020
Messaggi:
6
Re: Ricerca ternaria ricorsiva
29 giu 2020, 15:51
Innanzi tutto grazie a tutti per la celerità e le risposte! Scusate nel codice postato vi sono errori di logica, sono molto acerbo ! Allora il testo di questo esercizio mi confonde alquanto, difatti ho fatto diverse ricerche sul web e di ricerca ternaria neanche l'ombra
andbin ha scritto:
Premetto che "ricerca ternaria" non l'avevo ancora sentito ....
Per l'appunto, penso che si debba procedere come suggerisce andbin,
andbin ha scritto:
ma non è come quella binaria solo con 3 suddivisioni invece che 2??
sempre una ricerca binaria o dicotomica, come dir si voglia soltanto che al posto di dividere idealmente l'array in 2 parti e procedere con ricerche ricorsive, penso l'esercizio intenda che bisogna dividerlo in 3 parti!

andbin ha scritto:
Con 3 partizioni per invocazione, intuitivamente, si dovrebbe arrivare prima al risultato (riduce di più ...)
Potresti spiegarmi cosa intendi con 3 partizioni per invocazione? Dividere l'array in tre parti? Mi sa che hai ragione @andbin (primo+ultimo)/3 è una sciocchezza! Grazie per le diritte che mi hai dato nella risposta di prima, hai perfettamente ragione, restituivo i valori presenti nell'array e non i loro indici, una cosa al quanto inutile, dato che il valore che restituivo era quello che davo in input ! @migliorabile, grazie anche a te per la risposta e la disponibilità!
andbin
Super Famoso
Iscritto da
ott, 2013
Messaggi:
6272
Re: Ricerca ternaria ricorsiva
29 giu 2020, 16:09
CiroCappy ha scritto:
Potresti spiegarmi cosa intendi con 3 partizioni per invocazione? Dividere l'array in tre parti?
Sì dividere ... ma "logicamente", non fisicamente. Hai sempre i due indici primo e ultimo che ti danno la "vista" di una porzione dell'array. Ad ogni invocazione di ricercaTernaria suddividi questa vista in 3 parti e poi "entri" solo in una di queste. Ecc...
C
CiroCappy
Pochi posts
Iscritto da
giu, 2020
Messaggi:
6
Re: Ricerca ternaria ricorsiva
30 giu 2020, 15:51
Grazie ancora della disponibilirà, allora mi è chiaro il fatto che gli indici primo e ultimo mi diano una "vista" sulla porzione di array che vado a considerare ogni qual volta richiamo il metodo ricercaTernaria, ma non mi è chiaro come devo aggiornare la variabile med, ogni qual volta vi è l'invocazione del metodo ricercaTernaria, incorro sempre in errori di stack overflow o esce dai margini dell'array! Mi consigli di riscrivere in codice da capo o c'è qualcosa di salvabile?
EDIT:
@CiroCappy, comunque direi che è sbagliato il (primo+ultimo)/3 cioè NON va fatto così.
Ho provato a cogliere il tuo suggerimento, ma niente!
andbin
Super Famoso
Iscritto da
ott, 2013
Messaggi:
6272
Re: Ricerca ternaria ricorsiva
30 giu 2020, 16:53
CiroCappy ha scritto:
ma non mi è chiaro come devo aggiornare la variabile med

Ho provato a cogliere il tuo suggerimento, ma niente!
Te ne servono 2 di variabili, es medA, medB. Non puoi fare es. med*2, te ne accorgi subito, ragionando, che NON avrebbe senso.

CiroCappy

Pochi posts

Iscritto da: giu, 2020

Messaggi:: 6

Re: Ricerca ternaria ricorsiva

30 giu 2020, 18:38

	
	public static int ricercaTernaria(int a[],int obiettivo,int primo,int ultimo){
		int risultato;
		if(primo>ultimo)
			risultato=-1;
			int med = (primo + ultimo) / 2; 
			if (obiettivo == a[med]) 
				risultato= med; 
			else if (obiettivo > a[med]) 
				risultato=ricercaTernaria(a, obiettivo, med+1, ultimo); 
			else 
				risultato= ricercaTernaria(a, obiettivo, primo, med-1); 
		} 
		return risultato;
	}

Nel caso di una ricerca binaria ricorsiva normale ho capito, almeno credo, che l'algoritmo si ferma in due casi o quando trova l'elemento nell'array

if (obiettivo == a[med]) 
				risultato= med;

oppure quando non trova l'elemento e l'indice primo, nel mio caso è maggiore di ultimo.

if(primo>ultimo)
			risultato=-1;

e mi è chiaro anche del perchè aggiorni media facendo

int med = (primo + ultimo) / 2;

"sfoglia " gli elementi dell'array come se fosse un dizionario, dove non sono presenti li scarta ricorsivamente fino ad incorrere in una delle due situazioni sopra. Le mie domande sono, sul codice che vi sto scrivendo di seguito, che assegnazione devo fare e quindi come aggiornare le variabili "parte1" e "parte2" ad ogni ricorsione in modo che come nella ricerca binaria non mi diano indici che escano dall'array e se "primo", con le giuste correzioni sarà mai maggiore di ultimo per far si che il programma restituisca -1, quando l'emento non c'è nell'array!

public static int ricercaTernaria(int a[],int obiettivo,int primo,int ultimo){
		int risultato;
		if(primo>ultimo)
			risultato=-1;
		else{
			int parte1= ultimo/3; //so che è uguale al codice che ho scritto prima, ma sto impazzendo 
			int parte2=parte1*2;
			if(obiettivo==a[parte1])
				risultato = parte1;
			else if(obiettivo==a[parte2])
				risultato=parte2;
			else if (obiettivo < a[parte1])
				risultato= ricercaTernaria(a, obiettivo, primo, parte1-1);
			else if(obiettivo>a[parte1] && obiettivo<a[parte2])
				risultato= ricercaTernaria(a, obiettivo, parte1+1, parte2-1);
			else 
				risultato= ricercaTernaria(a, obiettivo, parte2+1, ultimo);
		}
		return risultato;

Grazie ancora di tutto! So che sono una testa di rame!

andbin
Super Famoso
Iscritto da
ott, 2013
Messaggi:
6272
Re: Ricerca ternaria ricorsiva
30 giu 2020, 19:12
CiroCappy ha scritto:

public static int ricercaTernaria(int a[],int obiettivo,int primo,int ultimo){ int risultato; if(primo>ultimo) risultato=-1; int med = (primo + ultimo) / 2; if (obiettivo == a[med]) risultato= med; else if (obiettivo > a[med]) risultato=ricercaTernaria(a, obiettivo, med+1, ultimo); else risultato= ricercaTernaria(a, obiettivo, primo, med-1); } return risultato; }
L'hai scritto male (guarda le graffe) e così non compila ovviamente. Comunque sì, il senso è quello (sviste a parte).

CiroCappy ha scritto:
Nel caso di una ricerca binaria ricorsiva normale ho capito, almeno credo, che l'algoritmo si ferma in due casi o quando trova l'elemento nell'array
Nel caso di ricerca "binaria", se il valore che cerchi NON è all'indice medio, allora essendo (per requisito) l'array ordinato, il valore O si trova nella prima metà O nella seconda metà. E quindi si "aggiusta" l'intervallo man mano per arrivare sempre più vicino a trovare il valore.
Il concetto in sostanza è questo.

Con una ricerca "ternaria" (come l'abbiamo interpretato) hai semplicemente due punti intermedi invece che uno.
CiroCappy ha scritto:

int parte1= ultimo/3; //so che è uguale al codice che ho scritto prima, ma sto impazzendo int parte2=parte1*2;
No, questa è proprio la parte che è sbagliata.

Se ti do un intervallo da 50 a 80 (compresi), cosa faresti per calcolare i due punti a 1/3 e 2/3 dell'intervallo (che sono 60 e 70) ??

CiroCappy

Pochi posts

Iscritto da: giu, 2020

Messaggi:: 6

Re: Ricerca ternaria ricorsiva

30 giu 2020, 20:09

public static int ricercaTernaria(int a[],int obiettivo,int primo,int ultimo){
		int risultato;
		if(primo>ultimo)
			risultato=-1;
		else{
			int parte1= primo+(ultimo-primo)/3;
			int parte2=primo+(ultimo-primo)*2/3;
			if(obiettivo==a[parte1])
				risultato = parte1;
			else if(obiettivo==a[parte2])
				risultato=parte2;
			else if (obiettivo < a[parte1])
				risultato= ricercaTernaria(a, obiettivo, primo, parte1-1);
			else if(obiettivo>a[parte1] && obiettivo<a[parte2])
				risultato= ricercaTernaria(a, obiettivo, parte1+1, parte2-1);
			else 
				risultato= ricercaTernaria(a, obiettivo, parte2+1, ultimo);
		}
		return risultato;
	}

Così funziona, grazie per tutte le diritte che mi hai dato e per avermi sopportato andbin! Una domanda che potrà sembrare sciocca, quando devi risolvere un problema di programmazione, che poi dovrai tradurre in un linguaggio (che sia java o altro) tu passi per un metalinguaggio per ragionare o scrivi direttamente al pc! Perchè se non fosse stato per te sarei ancora in alto mare, per problemi futuri cosa mi consigli di fare?

andbin
Super Famoso
Iscritto da
ott, 2013
Messaggi:
6272
Re: Ricerca ternaria ricorsiva
30 giu 2020, 20:53
CiroCappy ha scritto:
Così funziona
Sì, pare corretto.

CiroCappy ha scritto:
tu passi per un metalinguaggio per ragionare o scrivi direttamente al pc!
No, io scrivo direttamente il codice.

CiroCappy ha scritto:
per problemi futuri cosa mi consigli di fare?
Più studio & più pratica
Poi se hai comunque dubbi, chiedi.

P.S. io da un po' di tempo sto studiando Kotlin (è un linguaggio che gira sulla Java Virtual Machine) e così per esercitarmi ho provato a scrivere in Kotlin la ricerca "ternaria".
```
fun main() {
    val arr = intArrayOf(4, 6, 10, 12, 19, 20, 35, 40, 42, 49, 53, 56, 65, 70, 84)

    for (v in arr) {
        println("Ricerca di $v ---> indice ${ternarySearch(arr, v)}")
    }

    println("Ricerca di 2 ---> indice ${ternarySearch(arr, 2)}")
    println("Ricerca di 50 ---> indice ${ternarySearch(arr, 50)}")
    println("Ricerca di 90 ---> indice ${ternarySearch(arr, 90)}")
}

tailrec fun ternarySearch(array: IntArray, value: Int, start: Int = 0, end: Int = array.size-1): Int {
    if (start > end) return -1

    val midA = (start * 2 + end) / 3
    val midB = (start + end * 2) / 3

    return when {
        value == array[midA] -> midA
        value == array[midB] -> midB
        value < array[midA] -> ternarySearch(array, value, start, midA - 1)
        value > array[midB] -> ternarySearch(array, value, midB + 1, end)
        else -> ternarySearch(array, value, midA + 1, midB - 1)
    }
}
```
A parte la differenza di sintassi, è concettualmente similare al tuo codice. Una cosa bella di Kotlin (a parte la sintassi e le tante feature che ha) è che ternarySearch è ottimizzabile perché è "tail recursive". Io l'ho scritta ricorsiva ma avendola marcata tailrec, Kotlin la trasforma nella versione iterativa (con un loop) e quindi NON c'è penalità per la ricorsione.
Se volessi provarlo, non avendo Kotlin, allora puoi andare su https://play.kotlinlang.or (incolli il codice e fai run)
C
CiroCappy
Pochi posts
Iscritto da
giu, 2020
Messaggi:
6
Re: Ricerca ternaria ricorsiva
01 lug 2020, 14:04
Grazie ancora per la disponibilità e per i consigli! Mi sembra molto accattivante questo linguaggio Kotlin, gli darò un'occhiata! (Il fatto che giri sulla Java Virtual Machine, mi alletta alquanto).
andbin
Super Famoso
Iscritto da
ott, 2013
Messaggi:
6272
Re: Ricerca ternaria ricorsiva
01 lug 2020, 14:10
CiroCappy ha scritto:
Mi sembra molto accattivante questo linguaggio Kotlin, gli darò un'occhiata! (Il fatto che giri sulla Java Virtual Machine, mi alletta alquanto).
Ok ma attenzione ... Kotlin è "tosto".
Ha un sacco di cose che Java al momento se le sogna soltanto ...

Devi accedere o registrarti per scrivere nel forum

13 risposte