esercizi sulla ricorsione

[jimbo0]

salve, mi sono reso conto che sono più che arrugginito su quest'argomento..non mi viene naturale pensare ad una soluzione ricorsiva ad un problema postomi.
Cercando sul web si trovano solo esercizi e spiegazioni banali, io non cerco quello, so cos'è la ricorsione e come si applica, cerco degli esercizi un po' di avanzati, per abituarmi a pensare appunto in maniera ricorsiva, potete improvvisarli anche voi (per un programmatore è semplicissimo) magari usando anche qualche libreria standard di java tipo arraylist, stack o queue.
help mi?

[andbin]

cerco degli esercizi un po' di avanzati, per abituarmi a pensare appunto in maniera ricorsiva, potete improvvisarli anche voi

Bene, allora prova a scrivere una classe con un metodo ricorsivo per scansionare in "profondità" un albero di directory data una directory radice. Questa è una delle cose che si fa tipicamente in ricorsione. Fai ad esempio in modo da ottenere alla fine un List<File> con tutti i file (non le directory) trovati.

Una cosa che all'uso sarebbe es.:

DirTreeScanner dts = new DirTreeScanner();
List<File> files = dts.collectFiles("C:/blabla");

[OmarCore93]

Che strutture dati conosci? Se conosci anche gli alberi ne ho un sacco di esercizi ricorsivi sugli alberi.

[jimbo0]

si sto studiando gli alberi, ed in effetti anche se tempo fa programmavo agevolmente con file e db l'esercizietto di andbin mi è astruso perché dovrei riprendere dalla doc File e classi annesse. esercitarmi sugli alberi mi è più utile ora.

[OmarCore93]

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.

[Scara95]

Scrivi un implementazione delle liste scrivendo ogni operazione ricorsivamente:
-insert
-delete
-map
-fold
-reverse
-zip
-append
-sort (quicksort (per implementarlo devi prima implementare altre funzioni))

[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.

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

[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.