Estratto del documento

Calcolo la somma di tutti i num interi compresi nell'intervallo ]n1, n2[

BeneSUM (n1, n2)

  • If n2 - n1 <= 1 return 0
  • Else if n2 - n1 == 2 return n1 + 1
  • Else return (n1 + 1) + (n2 - 1) + SUM(n1 + 1, n2 - 1)

Complessità altro? Θ(m)? con n = n2 - n1

Correttezza: CASO BASE: ]2, 4[ -> linee 3, 4 OK
]2, 1[ -> linee 1, 2 OK

HP IND: vero ∀ h <= m. La linea 5 somma gli "estremi" e restituisce SUM chiamato su input n = 2 < m CORRETTO

Anteprima
Vedrai una selezione di 1 pagina su 1
Algoritmi e strutture dati - Esercitazione Pag. 1
1 su 1
D/illustrazione/soddisfatti o rimborsati
Acquista con carta o PayPal
Scarica i documenti tutte le volte che vuoi
Dettagli
SSD
Scienze matematiche e informatiche INF/01 Informatica
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Rod75 di informazioni apprese con la frequenza delle lezioni di Algoritmi e strutture dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Università degli studi di Napoli Federico II o del prof Sansone Lucio.
Appunti correlati Invia appunti e guadagna

Domande e risposte

Hai bisogno di aiuto?
Chiedi alla community
Vai al forum