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

Una lista di numeri può essere rappresentata da un vettore di coppie < valore, next > 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 (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

   0 -> *2* -> 6 -> *10* -> 8 -> *12* -> 4

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

• 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

7
0
1
2
3
4
-1
6
5
8
6
10
4
12
2

Output: 24

Consegna entro le ore 24 di venerdì 22 aprile

Per consegnare il programma:

• dovete essere iscritti a twiki
• usare la 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 pagina dei test, per usarli usate la linea di comando

• java -jar Mars_4.5.jar me nc sm ic file.asm < es1.in > es1.out
• per controllare che l'output sia uguale potete usare il comando diff (ma prima installate Linux )

-- AndreaSterbini - 03 Apr 2016