Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

di il
9 risposte

Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

Salve a tutti,

mi sono appena iscritto e vi anticipo che ho iniziato a studiare il linguaggio Java da circa due mesetti.
Precedentemente non avevo alcuna nozione sulla programmazione in generale.
Sto seguendo gli esercizi del libro e ho una domanda in merito ai metodi ricorsivi.

Per trovare il valore maggiore contenuto in un array di tipo int con metodo ricorsivo, ho scritto questa soluzione :
public static int getPiuGrande(int[] array, int lung) {

		int risultato = array[0];

		if ((lung >= 0) && (array[lung] > risultato))
			risultato = array[lung];
		if ((lung >= 0) && (getPiuGrande(array, lung - 1) > risultato))
			risultato = getPiuGrande(array, lung - 1);
		return risultato;
	}

	public static void main(String[] args) {

		int[] array = { 99555, 29999, 7779, 7, 4355, 3323212, 563, 776, 453, 9884, 3884, 999, 10000, 20000, };

		System.out.println(getPiuGrande(array, array.length - 1));

	}
tutto funzione alla grande e volevo chiedere ai navigati : cosa ne pensate della soluzione ? occupa troppa memoria ?

9 Risposte

  • Re: Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

    Ho appena provato anche a dividere la ricerca in due parti dell'array per cercare di fare prima in termini di velocita....
    attendo vostri suggerimenti:
    public static int getPiuGrande(int[] array, int iFineMeta, int lung) {
    		int risultato = array[0];
    
    		if ((lung >= 0) && (array[lung] > risultato))
    			risultato = array[lung];
    		if ((iFineMeta >= 0) && (array[iFineMeta] > risultato))
    			risultato = array[iFineMeta];
    		if ((lung >= 0) && (getPiuGrande(array, iFineMeta - 1, lung - 1) > risultato))
    			risultato = getPiuGrande(array, iFineMeta - 1, lung - 1);
    		return risultato;
    	}
    
    	public static void main(String[] args) {
    		int[] array = { 90, 3, 99, 435, 8832, 563, 776, 453, 9884, 3884, 999, 070, 266220, };
    		int iFineMeta = (array.length - 1) / 2;
    		System.out.println(getPiuGrande(array, iFineMeta, array.length - 1));
    	}
  • Re: Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

    È piu leggibile così?
    grazie per la pazienza...
    ris = (lung >= 0) && (a[lung] > ris) ? a[lung] : ris * 1;
    	ris = (iFMeta >= 0) && (a[iFMeta] > ris) ? a[iFMeta] : ris * 1;
    	ris = (lung >= 0) && (getMax(a, iFMeta - 1, lung - 1) > ris) ? getMax(a, iFMeta - 1, lung - 1) : ris * 1;
    	return ris;
  • Re: Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

    neofitaJava ha scritto:


    public static int getPiuGrande(int[] array, int lung) {
    
    		int risultato = array[0];
    
    		if ((lung >= 0) && (array[lung] > risultato))
    			risultato = array[lung];
    		if ((lung >= 0) && (getPiuGrande(array, lung - 1) > risultato))
    			risultato = getPiuGrande(array, lung - 1);
    		return risultato;
    	}
    Questa implementazione è "fumosa", fa "troppe" cose e oltretutto invoca 2 volte getPiuGrande ricorsivamente.
    Si fa con ben meno!

    neofitaJava ha scritto:


    occupa troppa memoria ?
    Chiaramente gli algoritmi ricorsivi "consumano" stack e lo stack .... è una risorsa preziosa e tipicamente abbastanza limitata. Questo è il motivo per cui normalmente gli algoritmi ricorsivi non si usano per trattare quantità enormi di dati.

    Per dire, già con un array di 16000 elementi ti puoi beccare lo StackOverflowError.
  • Re: Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

    Salve,

    in aggiunta a quanto gia' detto da Andrea, in un insieme non ordinato direi che una ricerca binaria non ha molto senso, la ricerca deve comunque "scandire" tutti gli elementi...

    io solitamente scrivo in c# ma anche Java dovrebbe avere la funzione Math.Max, ed in questo senso, l'algoritmo della funzione potrebbe essere riassunto in 4 righe, compresa la riga di if(...) e la riga di else... quindi
    
    int getMaggiore(parametri in ingresso)
        {
            if (condizione)
                primo pezzo dell'algoritmo, e sta su una riga e non ha comparazioni molto "particolari";
            else
                secondo pezzo dell'algoritmo, e sta su una riga;
        }
    
    dove ho "ovviamente" omesso il codice vero e proprio... non so se questo ti aiuta ma potrebbe farlo unitamente all'indicazione che ho dato sopra

    salutoni romagnoli
    --
    Andrea
  • Re: Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

    Sto approfondendo il capitolo della ricorsione e devo fare ancora molti esercizi prima di fare quelli del capitolo successivo, che comunque ho già letto.(come lettura sono arrivato molto più avanti rispetto agli esercizi.
    Devo dire che è molto interessante !

    GRAZIE MILLE A TUTTI PER LE RISPOSTE!

    Andrea intendi di utilizzare il metodo max della classe Math? ma senza fare ricorsione..e senza fare iterazione giusto?
    beh comunque ci provo senz'altro...
  • Re: Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

    Ciao...
    no, sempre con ricorsione, visto che stiamo parlando di un esercizio e come Andrea (@AndBin) ti ha enunciato e' un'operazione da valutare nel suo utilizzo.. che ovviamente risulta in un costo lineare...

    comunque, considera l'utilizzo sia di Math.Max che della ricorsione... insieme tanto piu' che l'esercizio questo ti chiede

    salutoni romagnoli
    --
    Andrea
  • Re: Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

    Di nuovo grazie a tutti .
    Faccio tesoro di tutto ciò che mi scrivete esattamente come una spugna assorbe l'acqua!! Grazie davvero !
    Ottima metafora quella del cacciavite martello chiodo e vite !!

    In realtà negli esercizi che ho svolto, uno chiedeva con un algoritmo ricorsivo e ricerca binaria, di restituire il più grande e l'altro con ricerca ternaria ma credo che tutti gli esercizi abbiano scopo puramente didattico, indipendentemente dalla convenienza di utilizzo nei casi reali.
    Infatti credo che ci sia poi bisogno di approfondire ulteriormente. ma comunque....

    con il metodo max della classe Math e in maniera ricorsiva ho sviluppato questa soluzione ...
    sempre che sia leggibile
    public static int getPiuGrande(int[] a, int i, int lung) {
    
    			return  (lung == i) ? a[0] : Math.max(a[i], getPiuGrande(a, i + 1, lung));
    	}
    
    	public static void main(String[] args) {
    
    		int[] a = { 27, 32, 39, 44, 88, 563, 776, 786, 987, 1000, 3333 };
    
    		System.out.println(getPiuGrande(a, 0, a.length));
    
    	}
    	
    	Oppure forse più leggibile :
    	
    	if (lung == inizio) 
    		return a[0];
    	else
    		return Math.max(a[inizio], getPiuGrande(a, inizio + 1, lung));

    Andrea grazie !! credo che tu intendessi una cosa di questo genere...



    (adesso sto sbattendo la testa su un'altro esercizio che chiede di calcolare somme cumulative e si deve sommare ad ogni elemento dell'array la somma degli elementi che lo precedono ...ma appena avrò scritto qualcosa vi chiederò consiglio su come migliorarlo ....
  • Re: Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

    Salve,

    puoi ancora "semplificare" e rimuovere 1 parametro alla funzione...

    salutoni romagnoli
    --
    Andrea
  • Re: Cerca il valore maggiore contenuto in un array di tipo int con metodo ricorsivo

    asql ha scritto:


    Salve,

    puoi ancora "semplificare" e rimuovere 1 parametro alla funzione...

    salutoni romagnoli
    --
    Andrea
    eliminando il parametro lung ... comunque la prima o versione 2 ? quale si utilizza di piú?
    public static int getPiuGrande(int[] array, int i) {
    
    			return  (array.length == i) ? a[0] : Math.max(array[i], getPiuGrande(a, i + 1));
    	}
    
    	public static void main(String[] args) {
    
    		int[] array = { 27, 32, 39, 44, 88, 563, 776, 786, 987, 1000, 3333 };
    
    		System.out.println(getPiuGrande(array, 0));
    
    	}
    	
    versione 2 
    	
    	if (array.length == inizio) 
    		return a[0];
    	else
    		return Math.max(a[inizio], getPiuGrande(a, inizio + 1));
    
Devi accedere o registrarti per scrivere nel forum
9 risposte