Ricorsione Array

[OvettoKinder]

Ho un problema:

Scrivere un metodo ricorsivo che restituisce il massimo di un array di double.
Ora,non è precisato se l'array è o non è ordinato.

Se io ipotizzo che l'array è ordinato come posso procedere?

[Alex'87]

Originariamente inviato da OvettoKinder
Ho un problema:

Scrivere un metodo ricorsivo che restituisce il massimo di un array di double.
Ora,non è precisato se l'array è o non è ordinato.

Se io ipotizzo che l'array è ordinato come posso procedere?

Se l'array è ordinato
- in maniera crescente: il massimo è l'ultimo elemento
- in maniera decrescente: il massimo è il primo elemento
Detto questo, lo svolgimento è banale

[OvettoKinder]

in giornata di domani provo...
Se non riesco riprovo...

Grazie della risposta...

[mxa]

Soluzione 1:
Beh se e' ordinato, come dice Alex, non c'e' nulla da fare, il min e' array[0] e il max e' array[array.length].

Se non e' ordinato lo ordini con la versione ricorsiva di merge sort o con quick sort e hai ottenuto quello che ti serve, ovvero un metodo ricorsivo per determinare il massimo ed il minimo.

Soluzione 2:
Piu' semplicemente e piu' efficientemente puoi implementare un algoritmo di binary search (http://en.wikipedia.org/wiki/Binary_search_algorithm)

[Alex'87]

Originariamente inviato da mxa
Soluzione 1:
Beh se e' ordinato, come dice Alex, non c'e' nulla da fare, il min e' array[0] e il max e' array[array.length - 1].

[mxa]

Originariamente inviato da Alex'87

ops... distrazione

[daniele391]

La ricorsione non è solo applicare un metodo ricorsivo e poi prenderne un valore.
Per trovare il massimo valore di un array di double, con un metodo ricorsivo, bisogna procedere per induzione, ovvero:
1) Si stabilisce un caso base, detto di "stop della ricorsione". Nel tuo caso potrebbe essere quando la dimensione del tuo array è pari a 1. Quindi stabilisci che l'unico valore del tuo array è il massimo per quell'array.
2)Saputo questo massimo, procedi a ritroso con il penultimo valore, poi con il terzultimo, poi con il quart'ultimo, e così via, fino a ritornare al primo valore. Quando vai a confrontare il primo valore, questo viene confrontato con gli altri n-1 valori dell'array, di cui tu già conosci il massimo.

private static double getMaxValueRecursive(double[] array) {
double max = 0;
if(array.length == 1) // Se ho un solo elemento, quello è il massimo
max = array[0];
else{ // creo un nuovo array, di dimensioni più piccole di uno di quello di partenza
double[] newArray = new double[array.length-1];
for(int i=1; i<array.length; i++) // ci metto tutti i valori, dal secondo fino all'ultimo...
newArray[i-1] = array[i];
double maxRel = getMaxValueRecursive(newArray); // ne calcolo il massimo con il metodo ricorsivo...
if(array[0] > maxRel) // vedo quale tra i due è il massimo e lo ritorno...
max = array[0];
else
max = maxRel;
}
return max;
}


Io l'ho provato e funziona...
Daniele.

[daniele391]

Originariamente inviato da mxa
Soluzione 1:
Beh se e' ordinato, come dice Alex, non c'e' nulla da fare, il min e' array[0] e il max e' array[array.length].

Se non e' ordinato lo ordini con la versione ricorsiva di merge sort o con quick sort e hai ottenuto quello che ti serve, ovvero un metodo ricorsivo per determinare il massimo ed il minimo.

Soluzione 2:
Piu' semplicemente e piu' efficientemente puoi implementare un algoritmo di binary search (http://en.wikipedia.org/wiki/Binary_search_algorithm)

Volevo solo dirti che questo metodo, correttamente ricorsivo, non può essere utilizzato per determinare il massimo valore in un array perchè la ricerca binaria è utile quando tu vuoi sapere se esiste un determinato valore all'interno di un array, semplicemente effettuando un numero di confronti che è pari la log(n), dove n è la dimensione dell'array. Per capirci, con un array di 8 elementi, in 3 passi riesco a determinare se il valore da me cercato c'è oppure non c'è. Ma la condizione di partenza, per poter utilizzare una ricerca binaria è quello di avere l'array già ordinato in senso crescente, e quindi si andrebbe a prendere direttamente l'ultimo valore dell'array, senza dover riempire la memoria con le varie istanze per la ricorsione. Siccome il problema è avere un metodo ricorsivo che ritorni un massimo valore, la soluzione da me postata sopra è corretta, perchè è il metodo ricorsivo che restituisce il valore massimo e nn basta solo che ti ordini l'array.
Daniele.