[AVVISO] Homework 4 - manipolazione di un albero di coppie <etichetta, valore> [DEFINITIVO]

andrea.sterbini (172680 points)
511 927 1776
asked May 15, 2018 in Homework 4 by andrea.sterbini (172,680 points)
closed May 23, 2018 by andrea.sterbini

Sia dato un albero binario in cui ogni nodo contiene una coppia di caratteri: etichetta: carattere qualsiasi tranne '\0' o '.' e valore: una cifra tra '0' e '9', memorizzato in un vettore di coppie di byte in modo che:

  • la radice dell'albero è a posizione 1 (ovvero al byte 2)
  • un nodo a posizione X ha i figli a posizioni 2X e 2x+1
  • un nodo vuoto ha coppia etichetta-valore '..' (punto punto)

Ogni nodo X dell'albero è individuato dal percorso che porta dalla radice al nodo, cioè la stringa composta dalle etichette dei nodi dalla radice al nodo X (inclusi)

Esempio se l'albero è

                a9
            /       \
         b0          c2
       /            /  \
      d1           e3   f7
        \         /
         g1      h6

La stringa che lo definisce è

a9b0c2d1..e3f7..g1....h6......

e il percorso che porta a h6 è la stringa "aceh"

In caso di ambiguità, (i figli di un nodo hanno la stessa etichetta), il percorso sceglie il figlio DESTRO.

Funzioni da realizzare

Leggi_albero(buffer, dim_max) che:

  • dato l'indirizzo di una zona di memoria (buffer) di dimensione dim_max
  • legge la stringa che rappresenta un intero albero
  • torna il numero di nodi presenti nella stringa (compresi i nodi vuoti)

Nota: la stringa va posizionata nel buffer a partire dall'elemento 1 (ovvero dal byte 2)

Inserisci_nodo(albero, percorso, etichetta_e_valore, sx_o_dx) che: (ricorsiva)

  • dato l'albero, il percorso che individua il nodo X, una nuova coppia di caratteri etichetta_e_valore del nuovo nodo, ed un bit che indica se il nodo va inserito a sinistra (1) oppure a destra (0)
  • sostituisce il figlio sinistro/destro di X con il nodo formato dalla coppia etichetta_e_valore

Elimina_sottoalbero(albero, percorso) che: (ricorsiva)

  • dato l'albero ed il percorso che individua un nodo X
  • elimina tutti i nodi del sottoalbero radicato in X, sostituendoli con '..' (punto punto)

Sposta_sottoalbero(albero, percorso1, percorso2) che: (ricorsiva)

  • dato un albero e due percorsi che individuano due nodi X ed Y
  • elimina tutti i nodi del sottoalbero radicato in Y
  • copia il sottoalbero radicato in X nel sottoalbero radicato in Y
  • azzera tutti i nodi del sottoalbero radicato in X

Stampa_vettore(albero) che:

  • dato un albero
  • stampa la stringa delle coppie di caratteri contenute nel vettore

Esempio: per l'albero precedente la stringa stampata è

a9b0c2d1..e3f7..g1....h6......

Trova_cammino_massimo(albero, buffer) che: (ricorsiva)

  • dato un albero e l'indirizzo di una area di memoria (buffer) sufficientemente grande
  • individua il più lungo cammino che da una foglia raggiunge un'altra foglia (non necessariamente passando per la radice dell'albero)
  • copia nel buffer la sequenza di etichette che portano dal nodo più a sinistra del cammino individuato, al nodo più a destra, seguita dal carattere '\0'
  • In caso di parità (più percorsi massimi) si deve scegliere il percorso che parte dal nodo più a sinistra, ed in caso di ulteriore parità quello che arriva al nodo più a destra

Esempio: se l'albero è quello sopra, il buffer conterrà la stringa

gdbaceh

Cerca_max_prof_nodo(albero, valore) che: (ricorsiva)

  • dato un albero ed un valore (tra '0' e '9')
  • trova il nodo a profondità massima che contiene il valore cercato
  • torna la profondità e l'etichetta del nodo trovato
  • In caso di ambiguità (se più nodi hanno quel valore alla stessa profondità massima) si deve tornare il nodo più a destra

Somma_alterna(albero, percorso) che: (ricorsiva)

  • dato un albero ed un percorso che individua il nodo X
  • nel sottoalbero radicato in X
    • somma tutti i valori a profondità pari rispetto a X (compreso X, a profondità 0)
    • sottrae tutti i valori a profondità dispari

Programma principale

Il programma main legge una successione di comandi e li esegue nell'ordine.

Un comando inizia con una lettera, seguita sulla stessa riga dal testo che contiene i parametri (separati da ' ' spazio) della chiamata da eseguire

Lo spazio di memoria necessario a contenere l'albero ed eventuali buffer va definito staticamente ed il suo indirizzo viene passato come argomento alle funzioni che ne hanno bisogno.

Comando Funzione da usare Output Note
L<albero> Leggi_albero(buffer, dim_max) stampa il numero di nodi letti,
seguito da '\n'
al massimo 1000 nodi,
(2000 caratteri)
I<perc> <e_v> <sx_o_dx> Inserisci_nodo(albero, percorso, etichetta_e_valore, sx_o_dx)
E<percorso> Elimina_sottoalbero(albero, percorso)
S<percorso1> <percorso2> Sposta_sottoalbero(albero, percorso1, percorso2)
V Stampa_vettore(albero) stampa il vettore di coppie
come unica stringa
seguita da '\n'
C Trova_cammino_massimo(albero, buffer) stampa il cammino individuato
seguito da '\n'
Il massimo cammino possibile
dovrebbe essere < 20 nodi
M<valore> Cerca_max_prof_nodo(albero, valore) stampa l'etichetta
e la profondità trovate,
separate da uno spazio
e seguite da un '\n'
A<percorso> Somma_alterna(albero, percorso) stampa il risultato
seguito da '\n'
Q esce dal programma

Consegna entro domenica 27/5 ore 24

Per i file di test vedete http://twiki.di.uniroma1.it/pub/Architetture2/MZ/AA17_18/HomeWork4/

1,152 views
closed with note: ok così

9 Answers

answered May 15, 2018 by Anon1 (9,920 points)

Avrei alcune domande per adesso:

  • La scadenza sarebbe domenica 29 Maggio, ma il 29 è Martedì; quindi la scadenza è il 29 od il 27 (domenica)?
  • La funzioni che dobbiamo realizzare sono obbligatoriamente ricorsive oppure anche iterative?
  • Pur sapendo gli argomenti delle funzioni possiamo gestirci per conto nostro i registri $a0-$a3?
andrea.sterbini (172680 points)
511 927 1776
commented May 15, 2018 by andrea.sterbini (172,680 points)
- Giusto, domenica è il 27
- meglio se sono ricorsive,fate esercizio per l'esame
- potete usare i registri che preferite
commented May 15, 2018 by Anon1 (9,920 points)
Quindi siamo liberi di scegliere un approccio ricorsivo o iterativo, senza penalità nel punteggio?
andrea.sterbini (172680 points)
511 927 1776
commented May 15, 2018 by andrea.sterbini (172,680 points)
edited May 15, 2018 by andrea.sterbini
Tranne la prima e la stampa del vettore, tutte devono essere ricorsive.

Nota che farò test separati per le diverse funzioni quindi anche se ne implementate qualcuna di meno potrete ottenere parte del punteggio (che per questo homework vale 1 punto invece che 0.5)
commented May 15, 2018 by Anon1 (9,920 points)
Capito, grazie per la risposta.
V
Valerio.Pescatori (1940 points)
6 25 38
answered May 19, 2018 by Valerio.Pescatori (1,940 points)
Quando viene chiamata una funzione che prende in input l'albero, possiamo assumere che venga passato l'indirizzo da cui parte realmente l'albero o dobbiamo sempre 'skippare' il primo elemento ?
andrea.sterbini (172680 points)
511 927 1776
commented May 19, 2018 by andrea.sterbini (172,680 points)
Basta che poi fate i conti giusti per trovare i figli :)
eduardo_rinaldi (2780 points)
7 16 25
answered May 19, 2018 by eduardo_rinaldi (2,780 points)

L'implementazione ricorsiva deve essere fatta esclusivamente sulle funzioni che sono sulla traccia, oppure è possibile definire altre funzioni ricorsive, con altri parametri, da richiamare all'interno di quelle presenti sulla traccia?

Esempio:

Def. della funzione inserisci_nodo

Inserisci_nodo(albero, percorso, etichetta_e_valore, sx_o_dx){

       #codice per inizializzare i parametri della prossima funzione

       return Inserisci_nodo_RICORSIVO(albero, percorso, etichetta_e_valore, sx_o_dx,  qui_altri_parametri_a_nostra_scelta )

}

Oppure dobbiamo rendere ricorsive direttamente quelle che lei ci fornisce? Grazie

andrea.sterbini (172680 points)
511 927 1776
commented May 19, 2018 by andrea.sterbini (172,680 points)
basta che una sottofunzione chiamata sia ricorsiva
gianpcr (4620 points)
5 16 34
answered May 19, 2018 by gianpcr (4,620 points)
Possiamo assumere che i comandi presi in input siano sempre corretti?
andrea.sterbini (172680 points)
511 927 1776
commented May 20, 2018 by andrea.sterbini (172,680 points)
Sì                               .
A
Angelo9787 (3670 points)
6 32 51
answered May 20, 2018 by Angelo9787 (3,670 points)
La dim_max della prima funzione è pari al valore degli elementi inseriti all'interno del buffer oppure alla grandezza totale del buffer?
andrea.sterbini (172680 points)
511 927 1776
commented May 20, 2018 by andrea.sterbini (172,680 points)
Secondo il testo sarebbe la dimensione del buffer in byte, ma potete scegliere voi cosa preferite, passare il numero di elementi e calcolare la dimensione in byte oppure passare direttamente la dim in byte.
answered May 21, 2018 by Anon1 (9,920 points)
edited May 22, 2018 by Anon1

Mi sono venute in mente altre domande:

  1. Possiamo assumere che venga fornito in input un albero con almeno la radice?
  2. Per tutte le funzioni che ricevono in input uno o più percorsi, possiamo assumere che tali percorsi siano corretti?
  3. Possiamo assumere che i percorsi dati in input alle varie funzioni contenga come minimo la radice?
  4. Nella funzione "sposta_sottoalbero", possiamo assumere che i due percorsi NON indichino due sottoalberi annidati?
andrea.sterbini (172680 points)
511 927 1776
commented May 23, 2018 by andrea.sterbini (172,680 points)
1: sì
2: sì (gli input saranno sempre corretti, l'HW mi pare più che sufficientemente complesso così)
3: il percorso minimo contiene la radice
4: esatto
P
Powner (5600 points)
24 68 85
answered May 21, 2018 by Powner (5,600 points)

Io non ho capito se quello su cui dobbiamo lavorare, per ogni funzione, è una stringa o un vettore e, qualunque caso sia corretto, da cosa è occupato il primo byte (quest'ultima cosa, credo non sia importante, ma non ho capito se quel byte sarà "compreso" o no nella struttura dati su cui dovremo lavorare). Collegato a questo, cosa significa avere in input "albero"? Se un "buffer" è l'indirizzo iniziale del vettore/stringa che rappresenta l'albero, perché differenziare le due cose?

Infine, nella funzione leggi_albero il parametro dim_max cosa rappresenta? Il numero di byte (o di half?) dell'albero?

commented May 22, 2018 by Anon1 (9,920 points)
> Io non ho capito se quello su cui dobbiamo lavorare, per ogni funzione, è una stringa o un vettore ...

Una stringa o un vettore sono la stessa cosa a basso livello, solo nel primo caso c'è un carattere di terminazione '\0' che indica quando si ferma la stringa. Nel nostro caso tale stringa è usata per rappresentare l'albero.

> da cosa è occupato il primo byte

I primi due byte della stringa (o vettore, chiamalo come vuoi) non hanno nessun valore. L'albero lo devi salvare dal terzo byte in poi. Questo perchè, ipotizzando che ti salvi la radice dell'albero nei primi due byte, quando vai a calcolare la posizione degli indici dei figli risulta l'indice 0 (perchè 2 * 0 fa 0). Salvando la radica dal terzo byte in poi avrai invece l'indice di tale nodo a 1, quindi i figli si troveranno negli indici 2 e 3.

> Collegato a questo, cosa significa avere in input "albero"?

Un indirizzo che punti al primo elemento dell'albero (la radice), ossia al terzo byte del vettore/stringa.

> Se un "buffer" è l'indirizzo iniziale del vettore/stringa che rappresenta l'albero, perché differenziare le due cose?

Penso sia solo un nome simbolico, ossia quello che è indicato come vettore/stringa è anche buffer. Insomma è una zona di memoria contigua che contiene l'albero.

> Infine, nella funzione leggi_albero il parametro dim_max cosa rappresenta?

La dimensione massima in byte dell'albero che riceverai in input. Questo valore va dato alla syscall. Ricordati anche lo spazio per il terminatore '\0', che verrà aggiunto alla fine dell'albero.Ricordati anche che 2 byte = 1 nodo dell'albero. Ricordati anche che i primi due byte sono vuoti.
P
Powner (5600 points)
24 68 85
commented May 22, 2018 by Powner (5,600 points)
Era proprio il carattere terminativo ad essere fondamentale nell'impostazione del codice, oltre che volevo sapere quale fosse la dimensione del dato da caricare ogni volta.

Per quanto riguarda i primi byte, il professore ha scritto che l'albero inizia al secondo byte (posizione 1), tu perché hai detto dal terzo? E l'input "albero" sei sicuro che parta dalla radice e non dall'inizio della stringa? (https://q2a.di.uniroma1.it/5155/homework-manipolazione-coppie-etichetta-valore-iniziale?course=homework-4%2Farchitettura-degli-elaboratori&show=5162#a5162 in questa risposta mi sembra si dicesse l'opposto).

Per quanto concerne dim_max, se rappresenta la dimensione dell'albero, per contare i nodi non basta restituire i dim_max/2 (o (dim_max-1)/2, in base a come viene dato l'indirizzo)?
commented May 22, 2018 by Anon1 (9,920 points)
> Era proprio il carattere terminativo ad essere fondamentale nell'impostazione del codice, oltre che volevo sapere quale fosse la dimensione del dato da caricare ogni volta.

Un nodo equivale a due byte, uno per l'etichetta ed uno per il velore.

> Per quanto riguarda i primi byte, il professore ha scritto che l'albero inizia al secondo byte (posizione 1), tu perché hai detto dal terzo?

Perchè un nodo è composto da due byte, quindi il nodo radice deve essere posizionato nel terzo byte del vettore (i primi due sono vuoti).

> E l'input "albero" sei sicuro che parta dalla radice e non dall'inizio della stringa? (https://q2a.di.uniroma1.it/5155/homework-manipolazione-coppie-etichetta-valore-iniziale?course=homework-4%2Farchitettura-degli-elaboratori&show=5162#a5162 in questa risposta mi sembra si dicesse l'opposto).

Sei libero di passare l'indirizzo che punta alla radice o al primo byte vuoto. Io per comodità gli passo direttamente l'indirizzo al terzo byte (la radice).

> Per quanto concerne dim_max, se rappresenta la dimensione dell'albero, per contare i nodi non basta restituire i dim_max/2 (o (dim_max-1)/2, in base a come viene dato l'indirizzo)?

la syscall che legge la stringa non ti dice quanto era lunga, perciò devi analizzarla a mano finchè non incontri il terminatore '\0'.
P
Powner (5600 points)
24 68 85
commented May 22, 2018 by Powner (5,600 points)
Ok, ho realizzato solo ora che "leggi la stringa" significava leggerlo da input. per qualche ragione ero convinto che la funzione desse per assodato che l'albero fosse già stato richiesto nel main. Questo spiega la maggior parte dei dubbi che avevo.

L'unica cosa che non mi torna, è perché il professore ha parlato di "secondo byte", anche se in realtà potrebbe essere comunque esatto in entrambi i casi, dipende da come si fanno i calcoli.
commented May 22, 2018 by Anon1 (9,920 points)
> L'unica cosa che non mi torna, è perché il professore ha parlato di "secondo byte",

Perchè gli indici partono da zero, quindi:

byte 0 -> vuoto
byte 1 -> vuoto
byte 2 -> etichetta radice
byte 3 -> valore radice
...
P
Powner (5600 points)
24 68 85
commented May 22, 2018 by Powner (5,600 points)
Ha scritto "la radice dell'albero è a posizione 1 (ovvero al byte 2)", questo significa:

posizione 0 -> byte 1, vuoto
posizione 1 -> byte 2, quindi radice dell'albero

O no?
commented May 23, 2018 by Anon1 (9,920 points)
Sì è vero. Non so cosa dirti allora, dipende da come vuoi calcolare l'indice.
andrea.sterbini (172680 points)
511 927 1776
commented May 23, 2018 by andrea.sterbini (172,680 points)
la radice si trova nell'ELEMENTO 1, quindi al byte 3
Se preferite potete mettere la radice nell'elemento 0, ma allora data la posizione X di un nodo le formule per calcolare i due figli sono diverse (ma non troppo difficili da ricavare)
andrea.sterbini (172680 points)
511 927 1776
commented May 23, 2018 by andrea.sterbini (172,680 points)
elemento 0 etichetta -> byte 0
elemento 0 valore -> byte 1
elemento 1 etichetta radice -> byte 2
elemento 1 valore radice -> byte 3
...
P
Powner (5600 points)
24 68 85
commented May 23, 2018 by Powner (5,600 points)
Ok grazie, tutto chiaro ora!
A
Angelo9787 (3670 points)
6 32 51
answered May 22, 2018 by Angelo9787 (3,670 points)
Alle funzioni possiamo passare altri parametri utili? O solamente quelli definiti nel testo?
commented May 22, 2018 by Anon1 (9,920 points)
Sì, possiamo passare altri parametri utili (ha risposto in un altro commento qui sopra).
A
Angelo9787 (3670 points)
6 32 51
answered May 22, 2018 by Angelo9787 (3,670 points)

Per quanto riguarda la funzione Sposta_sottoalbero nel caso in cui l'albero sia questo:

               a9
            /       \
         b0          c2
       /  \          /  \
      d1   l5      e3   f7
        \         / \
         g1      h6  i7

Con x= b0 e y = e3 l'altezza dell'albero si incrementerà, f7 in questo caso come lo trattiamo?
andrea.sterbini (172680 points)
511 927 1776
commented May 23, 2018 by andrea.sterbini (172,680 points)
L'abero conterrà sempre abbastanza nodi vuoti da ospitare nuovi nodi da inserire o sottoalberi da spostare