Tags:
create new tag
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 < 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 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

   0 -> *2* -> 6 -> *10* -> 8 -> *12* -> 4
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

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:

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 smile )

-- AndreaSterbini - 03 Apr 2016

Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r3 - 2016-05-05 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback