HomeWork3 < Architetture2/MZ/AA15

Tags: view all tags

---+++ Homework 3 - somma dei nodi in posizione dispari di una lista

Una lista di numeri può essere rappresentata da un vettore di coppie *&lt; valore, next &gt;* in cui:
   * si usa un vettore di *2N* interi per contenere le coppie
   * ogni coppia *X* si trova nella posizione *2X* del vettore ed ha nella posizione *2X+1* l'indice della prossima coppia
   * il valore *-1* viene usato per indicare che questo è l'ultimo nodo e non c'è un prossimo nodo nella lista
   * il primo elemento della lista si trova nella posizione *X=0*

Esempio: il vettore (in cui sono evidenziati i valori dei nodi)
| *0* | 1 | *2* | 3 | *4* | -1 | *6* | 5 | *8* | 6 | *10* | 4 | *12* | 2 |
Contiene le coppie:
   * *0*, 1     (che punta alla coppia *2*, 3)
   * *2*, 3     (che punta alla coppia *6*, 5)
   * *4*, -1    (che è l'ultimo nodo)
   * *6*, 5     (che punta alla coppia *10*, 4)
   * *8*, 6     (che punta alla coppia *12*, 2)
   * *10*, 4    (che punta alla coppia *8*, 6)
   * *12*, 2    (che punta alla coppia *4*, -1)

Corrisponde alla lista di valori
<verbatim>
   0 -> *2* -> 6 -> *10* -> 8 -> *12* -> 4
</verbatim>
I valori evidenziati sono i nodi in posizione dispari nell'ordine di visita della lista (contando da 0) 

---

Si scriva la funzione __ricorsiva__ che si chiama *sommaDispari* e che riceve come argomenti:
   * l'indirizzo *A* del vettore che contiene la lista
   * l'indice *X* della coppia considerata
   * il numero di nodi esaminati finora
e che torna come risultato:
   * la somma dei valori dei nodi che nell'ordine di visita della lista sono in posizione dispari

La funzione deve scandire la lista ricorsivamente finchè non arriva all'ultimo nodo e sommare tutti i nodi che sono in posizione dispari nell'ordine in cui sono stati visitati.

Nell'esempio precedente il valore da tornare è *2+10+12=24* perchè i nodi 2, 10 e 12 sono stati visitati nelle posizioni 1 3 e 5 nell'ordine di visita della lista

---

Si scriva il programma *main* che:
   * legge un intero *N<100*, numero di coppie da inserire nel vettore
   * inserisce nel vettore le N coppie *valore, prossimo*
   * chiama la funzione *sommaDispari* passando i valori
      * *A* indirizzo del vettore che contiene le coppie
      * 0   indice della prima coppia della lista
      * 0   numero di nodi esaminati finora
   * stampa la somma risultante

---+++ Esempio di input
<verbatim>
7
0
1
2
3
4
-1
6
5
8
6
10
4
12
2
</verbatim>

Output: *24*


---+++ Consegna entro le ore 24 di venerdì 22 aprile

Per consegnare il programma:
   * dovete essere [[TWiki.TWikiRegistration][iscritti a twiki]]
   * usare la [[/~andrea/consegna-HW-2016.html][pagina di consegna]] 
   * Non copiate o il compito verrà annullato ad entrambi
   * Scadenza della consegna: *venerdì 22 aprile ore 24*

__ATTENZIONE__ la funzione che esplora la lista verrà considerata ricorsiva solo se esegue un numero di chiamate ricorsive pari al numero di nodi della lista (non vale esplorare più nodi in uno stesso segmento di codice) 

*NOTA: chi fa una implementazione non ricorsiva riceverà metà del punteggio ottenuto dai test*

   * Ho completato i test sullo HomeWork3 ed ho notato alcuni errori eclatanti:
      * *-0.1* dimenticarsi completamente di allocare staticamente le strutture dati necessarie (ne possono derivare buffer overrun molto difficili da debuggare)
      * *-0.1* sbagliare le dimensioni delle strutture dati da allocare staticamente (ne possono derivare buffer overrun molto difficili da debuggare)
      * *-0.1* entrare nella funzione "cascandoci dentro" invece che facendo una chiamata *jal*
      * *-0.25* eseguire iterativamente la funzione e salvare su stack solo la chiamata più esterna


I due esempi sono disponibili anche come file sulla [[%ATTACHURL%][pagina dei test]], per usarli usate la linea di comando
   * __java -jar Mars_4.5.jar me nc sm ic file.asm &lt; es1.in &gt; es1.out__
   * per controllare che l'output sia uguale potete usare il comando *diff* (ma prima installate Linux :) )

-- Users.AndreaSterbini - 03 Apr 2016

<!--
   * Set ALLOWTOPICCHANGE = Users.AndreaSterbini
-->