HW8 - Albero n-ario

Question

Salve a tutti, ho letto la consegna dell'HW8obb e sono giunto alla conclusione che potrebbe essere utile utilizzare un albero n-ario per rappresentare le lettere delle parole che devo cercare all'interno della matrice, solo che ho difficoltà nel costruirlo. Ho costruito la matrice iterativamente e volevo costruire l'albero ricorsivamente come consigliato nella consegna quindi ho cercato su internet e consigliano di utilizzare l'implementazione dinamica figlio-fratello ma non capisco bene come usare quest'ultima in python. Qualcuno potrebbe chiarirmi questo argomento?

Answer 1

Non so se è quello che intendi tu, ma io l'ho creato utilizzando dei dizionari.

Come chiavi della radice hai la prima lettera di ogni stringa.
Come nodi, per ogni chiave nel dizionario hai un altro dizionario che contiene i possibili secondi caratteri delle stringhe che iniziano con la chiave della radice.
E così via... puoi crearlo passandogli una parola per volta ed usando gli indici.

Non è semplicissimo da gestire però...

Comments

È esattamente quello che intendo ma l'albero credo sia la struttura che si presta meglio a questa idea, avevi pensato anche ad usare i dizionari ma come hai detto tu non è molto semplice gestirli. Proverò un'altra soluzione..

---

ma l'albero credo sia la struttura che si presta meglio a questa idea

Certo ma non sta scritto da nessuna parte che devi implementarlo con una classe eh!
Quello che ti ho descritto è fondamentalmente un albero, semplicemente realizzato con i dizionari.

---

Si, certo. È che il difficile dell'albero (classe) è l'implementazione ma poi é facile gestirlo mentre per l'albero (dizionari) il contrario.

---

No, è la stessa cosa. Semplicemente nella struttura che ti ho elencato, se vuoi avere il nodo avente come id 'A', allora accedi a dizionario['A'].

Puoi realizzare la stessa identica cosa con una classe, ma ti servirebbero comunque i dizionari, il che la renderebbe una sovrastruttura ridondante ed inutile.

Inoltre il dizionario si presta molto bene a questo tipo di idea, perchè quando vuoi continuare la ricorsione, è sufficiente che passi come parametro dizionario['A'] (che è un altro dizionario, e puoi continuare ricorsivamente).

---

Ok, grazie non avevo capito, ci proverò :)

---

Tieni conto che potrebbero servirti altre informazioni all'interno dei dizionari, ad esempio quando hai completato una parola (e quale hai completato). Dipende tutto da come lo imposti.

Answer 2

Personalmente ho semplicemente usato liste e set per fare il programma, non dico che non sia possibile farlo con un albero n-ario ma secondo me ti stai solo complicando la vita

Comments

Potresti spiegare più o meno come usi liste e insiemi? Perché non riesco a trovare altre soluzione ricorsive oltre a questa.

---

La ricorsione deve essere fatta per ogni parola che devi trovare all'interno della matrice per trovare la combinazione D/G e questa ricorsione puo essere benissimo essere svolta solo con le liste senza il bisogno di alberi. Se il tuo problema è trovare la lettera successiva della parola ricordati che puoi usare nome_stringa[posizione della/e lettera/e] per trovare una lettera/sequenza di quella stringa

Answer 3

Avevo la stessa idea ma l'ho abbandonata per una più semplice. È infatti difficile (almeno secondo me) creare alberi del genere con la ricorsione. Credo che ci sia un modo più semplice con i for ma non so se è più efficiente visto che non la ho realizzata.

Comments

L'altra idea che mi è venuta é creare un albero binario dalla matrice e poi cercare la parola all'interno dell'albero ma penso sia molto più lenta dell'albero n-ario

Answer 4

È un'idea carina ma è davvero complicata, una volta trovata matrice e parole creare un albero penso sia uno spreco di tempo, perché lo stesso tipo di ricerca che si fa negli alberi puoi utilizzarlo per controllare all'interno della matrice.

Comments

Era per ciclare una sola volta la matrice in modo da rendere veloce il programma ma a questo punto cercherò un'altra soluzione.