Algoritmi

Gli algoritmi

Giovedì 29 gennaio 2026 18:00

Esempio

Il problema di calcolare il Massimo Comune Divisore MCD fra due numeri x e y (x > y).

• Ingressi: due numeri.
• Uscite: il Massimo Comune Divisore.

Per trovare un algoritmo occorre trovare un metodo di soluzione per ogni x e y tale che x > y.

Algoritmo per l’MCD (Euclide)

1. Calcola il resto della divisione di x per y.
2. Se il resto è diverso da zero, allora ricomincia dal punto 1 utilizzando come x il valore attuale di y, e come y il valore del resto; altrimenti prosegui con il passo successivo.
3. Il massimo comune divisore è uguale al valore attuale di y.

Scriviamo l'algoritmo

1. r <- x mod y
2. Se r diverso da zero, allora:
   • x <- y
   • y <- r
   • goto 1

Altrimenti:

• y è il risultato.

Definiamo ogni passaggio

1. Assegnamento

Usiamo la variabile r per definire il resto.

La freccia indica l'assegnamento del risultato di x mod y nella variabile r.

x mod y = operazione di modulo (resto della divisione).

2. Decisione

La condizione che valuteremo come predicato di verità.

x <- y è un altro assegnamento. Assegniamo il valore di y a x.

y <- r è un altro assegnamento. Assegniamo il valore di r a y.

goto 1 è un salto. Ci riporta a 1. Si verifica dunque una ripetizione.

Altrimenti -> un'altra decisione.

3. Output

MCD <- Y

Possiamo scrivere questo algoritmo usando dello pseudo codice.

Dobbiamo stabilire:

• Sequenza di istruzioni.
• Keyword per la decisione (if then).
• Controllo di flusso (goto).
• Istruzioni per catturare input ed associarlo a variabili (read).
• Istruzioni per scrivere in output il risultato (write).

Otteniamo:

1. read (x)
2. read (y) [assumiamo x > y]
3. r <- x mod y
4. if r = 0, then goto 8
5. x <- y
6. y <- r
7. goto 3
8. write (‘’MCD è’’, y)

Tuttavia mod non è eseguibile, va scomposto in sottrazioni ripetute:

1. read(x)
2. read(y)
3. r ← x;
4. if r < y then goto 7
5. r ← r − y;
6. goto 4
7. write (‘’il resto è’’, r)

La grammatica

< program > ::= < row> | < program > <row>

<row> ::= <linenumber> < istr>

<linenumber> ::= <number> ‘’.’’…

< istr> ::= <scrittura> | <lettura> | <assegnamento> | <decisione> | <salto>

<scrittura> ::= ‘’write’’ <parametro>

<parametro> ::= ‘’(’’ <stringa> ‘’,’’ <nomevariabile> ‘’)’’….

<decisione> ::= ‘’if’’ <condizione> ‘’then’’ <salto>

<salto> ::= ‘’goto’’ <number>

Possiamo rappresentare gli algoritmi tramite flow chart (diagrammi di flusso). I diversi