Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

Notice Board

Per partecipare al corso di Fondamenti di programmazione 2023-24 loggatevi e attivatelo nella vostra pagina dei corsi preferiti. A quel punto il corso appare nel menù personale cliccando sul proprio avatar. Per i materiali degli anni precedenti seguite lo stesso metodo.

To join the Programming/Lab 2023-24 course, log-on and select it on the my courses page. It will appear on the personal menu of your avatar. For earlier years use the same method.

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

andrea.sterbini (207920 points)
750 1267 2373
in Homework 4 by (208k points)
closed by

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.8k views
closed with the note: ok così

9 Answers

by (9.9k 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 (207920 points)
750 1267 2373
by (208k points)
- Giusto, domenica è il 27
- meglio se sono ricorsive,fate esercizio per l'esame
- potete usare i registri che preferite
by (9.9k points)
Quindi siamo liberi di scegliere un approccio ricorsivo o iterativo, senza penalità nel punteggio?
andrea.sterbini (207920 points)
750 1267 2373
by (208k points)
edited by
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)
by (9.9k points)
Capito, grazie per la risposta.
V
Valerio.Pescatori (1940 points)
11 25 38
by (1.9k 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 (207920 points)
750 1267 2373
by (208k points)
Basta che poi fate i conti giusti per trovare i figli :)
eduardo_rinaldi (2780 points)
8 16 25
by (2.8k 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 (207920 points)
750 1267 2373
by (208k points)
basta che una sottofunzione chiamata sia ricorsiva
gianpcr (4620 points)
5 16 34
by (4.6k points)
Possiamo assumere che i comandi presi in input siano sempre corretti?
andrea.sterbini (207920 points)
750 1267 2373
by (208k points)
Sì                               .
A
Angelo9787 (3670 points)
10 32 51
by (3.7k 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 (207920 points)
750 1267 2373
by (208k 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.
by (9.9k points)
edited by

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 (207920 points)
750 1267 2373
by (208k 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)
36 68 85
by (5.6k 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?

by (9.9k 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)
36 68 85
by (5.6k 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)?
by (9.9k 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)
36 68 85
by (5.6k 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.
by (9.9k 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)
36 68 85
by (5.6k 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?
by (9.9k points)
Sì è vero. Non so cosa dirti allora, dipende da come vuoi calcolare l'indice.
andrea.sterbini (207920 points)
750 1267 2373
by (208k 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 (207920 points)
750 1267 2373
by (208k 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)
36 68 85
by (5.6k points)
Ok grazie, tutto chiaro ora!
A
Angelo9787 (3670 points)
10 32 51
by (3.7k points)
Alle funzioni possiamo passare altri parametri utili? O solamente quelli definiti nel testo?
by (9.9k points)
Sì, possiamo passare altri parametri utili (ha risposto in un altro commento qui sopra).
A
Angelo9787 (3670 points)
10 32 51
by (3.7k 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 (207920 points)
750 1267 2373
by (208k points)
L'abero conterrà sempre abbastanza nodi vuoti da ospitare nuovi nodi da inserire o sottoalberi da spostare