AIUTO IN ALGORITMI JAVA URGENTISSIMO

[Valh3g]

Salve a tutti devo sostenere l'esame di Algoritmi e strutture dati, ma chiedo il vostro aiuto in quanto questa materia non mi entra in testa...!!!

Vi scrivo un paio di esempi di traccia d'esame se qualcuno e cosi gentile da scrivermi la soluzione con qualche suggerimento sarei molto GRATO!!


Si consideri una classe ABRB che rappresenti alberi binari di ricerca bilanciati in cui la parte informativa di ogni nodo è un numero intero.Si assuma che in tali classe siano implementati i seguenti metodi:

public interface ABRB{
// restituisce il sottoalbero destro,complessità temporale è teta(1)
public ABRB destro();
// restituisce il sottoalbero sinistro,complessità temporale è teta(1)
public ABRB sinistro();
//restituisce valore memorizzato in radice; complessità temporale è teta(1)
public int val();
}

Si deve realizzare un metodo ricorsivo
PUBLIC STATIC BOOLEAN ESISTEVALORIPARI(ABRB a, int valmin, int valmax) {......}

che restituisce true se e solo se l'albero a contiene un int x di valori pari e compreso nell'intervallo [valmin,valmax] con valmin<=valmax

poi chiede di calcolare la complessita temporale e spaziale nel caso migliore e peggiore e di specificare quali sono questi casi.

AIUTATEMI PERFAVORE...

GRAZIE GRAZIE A TUTTI!!!


SECONDA TRACCIA:

public....

...int val()... tutto uguale al primo..solo che si chiama CLASSE ABB

mi chiede realizzare metodo ricorsivo:

public static boolean uguali(ABB a1,ABB a2){...}

che ritorna true se e solo se alberi a1 e a2 sono identici ossia la copia uno dell altro.

e chiede i vari casi di complessita come prima!

TERZO ESEMPIO:

classe albero B albero binario

public interface...come prima

realizzare metodo:

public static boolean eRipetuto(alberoB a, int x){...}

restituisce true se e solo se vi e almeno un nodo n nell albero a tale che l intero x appare sia nel sottoalbero sinistro che nel sottoalbero destro di n.

anche qui chiede la varie complessità!

QUARTA TRACCIA:

come la terza

public static boolean eRipetuto(alberoB a, int x){...}

chiede: che restituisce true se e solo se l'int x appare almeno 2 volte nel sotto albero a.


AIUTATEMI VI PREGO SONO VERAMENTE DISPERATO!!!!

[variabilepippo]

Dovresti postare le tue soluzioni, per quanto sbagliate e/o incomplete.

[Valh3g]

allora nel caso della complessità non so proprio calcolarla per quello che so di teoria O(grande) la nostra compl. vista come limite superiore(upper bound) mentre per omega() e il nostro limite inferiore (lower bound)...lo so in teoria ma non so come calcolarla nella varie righe di codice che mi trovo nei vari programmi.
Per quanto riguarda la parte degli alberi non credo che possa scrivere molto perchè diciamo che scrivo qualche riga di codice ma poi mi perdo nel VUOTO ecco perchè sto chiedendo aiuto...non avendo mai fatto questo tipo di esercizi non so come andare avanti e quindi confidavo nella vostra esperienza per avere un punto di partenza. Spero di essere stato il piu chiaro possibile.
Ringrazio nuovamente tutti quanti!

[Mr Emme]

allora per gli algoritmi te la devi vedere tu. per quanto riguarda la complessità:

prima traccia: complessità O(n) dove n è il numero di nodi dell'albero. questa complessità è dovuta al fatto che nel caso pessimo(cioè il numero non è presente e i valori dei nodi dell'albero sono compresi nell'intervallo) l'albero viene visitato tutto. ovviamente nel caso favorevole(la radice è il valore cercato) si ha O(1)

seconda traccia: anche quì complessità O(n) perchè i due alberi vanno visitati interamente, ovviamente non c'entra il fatto che sono 2 perchè le operazioni di controllo sui nodi sono costanti. il caso favorevole lo si ha quando le radici sono diverse e quindi basta fare un confronto e ci si ferma restituendo false, complessità O(1)

terza traccia: (ehm cos'è albero B albero? un B-albero?) questa è un po più complessa, cmq in questo caso l'algoritmo visita l'abero a partire dalla radice e per ogni nodo fa una visita del sotto albero destro e sinistro per cercare il valore x. tale visita costa O(n) quindi, dato che i nodi sono n, fa n volte questa visita e quindi complessità O(n^2).

quarta traccia: dipende da cosa sta per albero B albero

per la complessità spaziale non so cosa sia ma desumo si tratti dell'occupazione di memoria(giusto?), se è così allora restano le stesse complessità.

[Valh3g]

grazie a Mr Emme per il suo aiuto...

cmq ho provato a metter mano sul codice posto qui di si seguito cio' che ho fatto...cosi credo che ho capito come funziona il forum...SCUSATEMI ancora...

public static boolean eRipetuto(alberoB a, int x){
if(a==null)
return false;
if(a.getDato==val)&& contiene(a.getDestro(),val) ||(a.getDato==val)&& contiene(a.getsinistro(),val) || contiene(a.getDestro==val)&& contiene(a.getSinistro(),val)
return true;
else
return false;
}
N.B. il metodo contiene controlla se il valore e contenuto nel sottoalbero.?? dite che possa andare cosi???

public static boolean uguali(ABB a1,ABB a2){
if(a1==null && a2==null){
return true,
else
if(a1==null && a2!=null) || (a1!=null && a2==null)
return false;
}
if((a1.destro()==a2.destro())&& (a1.sinistro()==a2.sinistro())
return true;
else
return false;
}
}

Ditemi un po cosa ne è uscito fuori...qualsiasi offesa e ben accetta...


ma meglio di così per ora non riesco a fare...

[mindwings]

Originariamente inviato da Valh3g

Salve a tutti devo sostenere l'esame di Algoritmi e strutture dati, ma chiedo il vostro aiuto in quanto questa materia non mi entra in testa...!!!

Vi scrivo un paio di esempi di traccia d'esame se qualcuno e cosi gentile da scrivermi la soluzione con qualche suggerimento sarei molto GRATO!!


Si consideri una classe ABRB che rappresenti alberi binari di ricerca bilanciati in cui la parte informativa di ogni nodo è un numero intero.Si assuma che in tali classe siano implementati i seguenti metodi:

public interface ABRB{
// restituisce il sottoalbero destro,complessità temporale è teta(1)
public ABRB destro();
// restituisce il sottoalbero sinistro,complessità temporale è teta(1)
public ABRB sinistro();
//restituisce valore memorizzato in radice; complessità temporale è teta(1)
public int val();
}

Si deve realizzare un metodo ricorsivo
PUBLIC STATIC BOOLEAN ESISTEVALORIPARI(ABRB a, int valmin, int valmax) {......}

che restituisce true se e solo se l'albero a contiene un int x di valori pari e compreso nell'intervallo [valmin,valmax] con valmin<=valmax

poi chiede di calcolare la complessita temporale e spaziale nel caso migliore e peggiore e di specificare quali sono questi casi.

AIUTATEMI PERFAVORE...

GRAZIE GRAZIE A TUTTI!!!


SECONDA TRACCIA:

public....

...int val()... tutto uguale al primo..solo che si chiama CLASSE ABB

mi chiede realizzare metodo ricorsivo:

public static boolean uguali(ABB a1,ABB a2){...}

che ritorna true se e solo se alberi a1 e a2 sono identici ossia la copia uno dell altro.

e chiede i vari casi di complessita come prima!

TERZO ESEMPIO:

classe albero B albero binario

public interface...come prima

realizzare metodo:

public static boolean eRipetuto(alberoB a, int x){...}

restituisce true se e solo se vi e almeno un nodo n nell albero a tale che l intero x appare sia nel sottoalbero sinistro che nel sottoalbero destro di n.

anche qui chiede la varie complessità!

QUARTA TRACCIA:

come la terza

public static boolean eRipetuto(alberoB a, int x){...}

chiede: che restituisce true se e solo se l'int x appare almeno 2 volte nel sotto albero a.


AIUTATEMI VI PREGO SONO VERAMENTE DISPERATO!!!!

bello l'esame di Algoritmi e strutture dati con Java
io sto praticamente studiando la stessa materia maledicendo ogni giorno il
C++
...