160217 soluzione

Pagina 1

Algoritmi e Strutture Dati 15/16 Durata: 3 ore Prova Scritta del 17 Febbraio 2016 1. Si vuole progettare una struttura dati per polinomi, definiti come una sequenza ordinata di coppie < esponente, coefficiente >. Ad esempio il polinomio p(x) = x2 +3 corrisponde alla sequenza{< 0, 3 > , < 2, 1 >}. Completare la specifica di polinomio, fornendo la specifica semantica per mezzo di pre e post condizioni (specifica costruttiva o modello astratto), rispetto alla seguente specifica sintattica: domini: polinomio, coefficiente, esponente operatori: (a) crea() → polinomio // crea un nuovo polinomio di grado 0, p(x) = 0 (b) settaEsponente(polinomio, esponente, coefficiente) → polinomio // imposta il coefficiente (ultimo parametro) di un dato esponente (secondo parametro) (c) rimuoviEsponente(polinomio, esponente) → polinomio // imposta a zero il coefficiente di un dato esponente (secondo parametro) (d) leggiCoefficiente(polinomio, esponente) → coefficiente // restituisce il coefficiente di un dato esponente (secondo parametro) (e) grado(polinomio) → esponente // restituisce l’esponente pi` u grande (f) somma(polinomio, polinomio) → polinomio // restituisce la somma di due polinomi (g) prodotto(polinomio, polinomio) → polinomio // restituisce il prodotto di due polinomi [7pt] SOLUZIONE domini: polinomio: famiglia di insiemi di coppie di tipo < c, e > dove c ` e di tipo coefficiente ede ` e di tipo esponente; coefficiente: insieme dei valori tipo reale; esponente: insieme dei valori di tipo intero. operatori: (a) crea() → p • PRE: - • POST: p =∅ (b) settaEsponente(p, e, c) → p’ • PRE:̸∃ < c ′, e′ >∈ p t.c. e = e′ • POST: p′ = p∪ < c, e > (c) rimuoviEsponente(p, e) → p’ • PRE:∃ < c ′, e′ >∈ p t.c. e = e′ • POST: p′ = p\ < c, e > (d) leggiCoefficiente(p, e) → c • PRE:∃ < c ′, e′ >∈ p t.c. e = e′ • POST: c = c′…