esercizi sulla ricorsione

[OmarCore93]

calma ragazzi io sono ancora a questo, che effettivamente si avvicina molto a quello che sto studiando.
purtroppo la complessità ancora non l'ho studiata (lacuna mia, nel corso di studi ovviamente viene prima la complessità e poi lo studio delle strutture dati).
Ed a proposito del fatto che non so pensare ricorsivamente, non ho idea di come risolverlo ad esempio io penserei alla necessità di una variabile esterna "max" da mantenere fuori dalla funzione, ma credo che tu sia di parere diverso
un paio di suggerimenti e vediamo se ci arrivo

ps: per inciso il fatto che il tuo nick sia "93" non fa altro che infagianarmi ulteriormente

Questo esercizio che ti ho proposto l'ho preso da un appello del corso di Algoritmi e Strutture Dati che ho seguito, non ricordo benissimo la soluzione visto che il prof neanche l'ha messa, però una volta gliela avevo chiesta a ricevimento dunque ricordo qualcosa. Si risolve bene con lo schema del divide et impera su alberi, che conoscerai se stai frequentando/hai frequentato un corso di Algoritmi e Strutture Dati (da quello che hai scritto sembra così ), in pratica definisci un caso base: in questo caso quando l'albero ha un solo nodo, in questo caso restituisci una coppia di dati data dal colore del sottoalbero e dalla sua dimensione, credo che bastino questi due valori. Nei casi "ricorsivi" invece vai a richiamare la funzione nei due sottoalberi (sinistro e destro) e poi se non sbaglio basta confrotare questi due risultati con il valore della radice, per vedere se la radice si può includere nel conteggio.
Comunque provo ad abozzare un mezzo codice e te lo posto.
Sulla mia età qual'è il problema? Non ti seguo, dici perchè ti sembro giovane? :P
EDIT: Effettivamente come dato da mantenere c'è anche quello del massimo sottoalbero monocolore che hai trovato al momento del controllo.

[jimbo0]

Comunque provo ad abozzare un mezzo codice e te lo posto.
Sulla mia età qual'è il problema? Non ti seguo, dici perchè ti sembro giovane? :P

non postare codici! avevo chiesto un suggerimento e l'hai dato..ora vedo di scribacchiare qualcosa..anche se da come hai spiegato non capisco come posso "ricordare" un sottoalbero monocolore e non un insieme sparso e non contiguo di nodi..

certo sembri giovane, tra te 93 e scara95 realizzo che ho perso un bel po' di tempo (come se non lo sapessi )

[OmarCore93]

non postare codici! avevo chiesto un suggerimento e l'hai dato..ora vedo di scribacchiare qualcosa..anche se da come hai spiegato non capisco come posso "ricordare" un sottoalbero monocolore e non un insieme sparso e non contiguo di nodi..

certo sembri giovane, tra te 93 e scara95 realizzo che ho perso un bel po' di tempo (come se non lo sapessi )

Eh lo so, questa idea dell'albero monocolore è una cosa che non sai, è una nuova definizione, i prof di Algoritmi e Strutture Dati da noi si divertono con queste nuove definizioni. Alberi monocolore e altre robe varie, vogliono che tu dopo aver letto la definizione sappia affrontare il problema, poi magari quando uno va a lavorare difficile che ti trovi ad operare su alberi monocolore e robe del genere, sono solo definizioni un po' di fantasia, si sbizzarriscono su queste nuove tipologie di alberi affinchè possano vedere se hai veramente capito come fare gli algoritmi.
Comunque se ne vuoi uno con definizioni meno stravaganti:
Dato un albero binario bt definire una funzione check(bt, x, n) (bt, x e n sono i parametri della funzione) che restituisce true se e solo se nell'albero bt esiste una foglia con etichetta x a profondità n.
P.S. L'albero non deve essere per forza di ricerca, oltre al fatto che è binario non ha altre proprietà.
Comunque non preoccuparti, pure io non sono messo benissimo, anzi in realtà con gli esami sono parecchio incasinato.

[jimbo0]

Un esercizio:
Dato un albero binario in cui ogni nodo è bianco o nero (identificali come vuoi), un sottoalbero monocolore è un sottoalbero avente tutti i nodi dello stesso colore: scrivere un algoritmo che calcola la dimensione massima di un sottoalbero monocolore nell'albero, dove per dimensione si intende la quantità di nodi del sottoalbero.
Non so se sai cos'è la complessità computazionale, fatto sta che puoi farlo in tempo O(n), se non sai cos'è fallo pure senza tenere conto dell'efficienza.

ho scritto questa roba che almeno dovrebbe contare le occorrenze del colore (so che non è quello che chiede il problema posto )
ho usato le implementazioni usate nel corso ma credo sia tutto comprensibile (BTPosition<E> è un nodo dell'albero che usa tipo generico E, Position è l'interfaccia implementata da BTPosition).
il problema qui è che num viene azzerato ad ogni ricorsione credo quindi?

	public int getMaxSubtree(E color, Position<E> c){
		BTPosition<E> cc = checkPosition(c);
		int num=0;
		if(hasLeft(cc)) { 
			if(color==cc.element()) num+=getMaxSubtree(color, left(cc));			
			getMaxSubtree(color, left(cc));
			}
		if(hasRight(cc)){
			if(color==cc.element()) num+=getMaxSubtree(color, left(cc));
			getMaxSubtree(color, left(cc));
		}
		return num;
	}