Esercizi: Algoritmi

Descrivi con un elenco di passi (pseudocodice) un algoritmo che, dati due numeri $a$ e $b$, stabilisce quale dei due è maggiore.

Esegui a mano il seguente algoritmo con $n = 5$:

1. $s \leftarrow 0$

2. per $i$ da 1 a $n$: $s \leftarrow s + i$

3. stampa $s$

Che cosa calcola l'algoritmo?

Scrivi un algoritmo che, dato un numero intero positivo $n$, stabilisce se è pari o dispari, usando il resto della divisione per 2.

Scrivi in pseudocodice un algoritmo che, data una sequenza di 6 voti, calcola la media e il voto massimo. Eseguilo poi con i voti 7, 5, 8, 6, 9, 7.

Considera l'algoritmo:

1. leggi $a$ e $b$ (interi positivi)

2. finché $b \neq 0$: $r \leftarrow a \bmod b$, $a \leftarrow b$, $b \leftarrow r$

3. stampa $a$

1. a) Esegui l'algoritmo con $a = 84$, $b = 36$ riportando i valori a ogni passo.

1. b) Che cosa calcola?

Un algoritmo risolve l'equazione $ax + b = 0$.

1. a) Scrivilo in pseudocodice considerando i casi $a \neq 0$, $a = 0$ con $b = 0$, e $a = 0$ con $b \neq 0$.

1. b) Eseguilo con $(a, b) = (4, -6)$, $(0, 0)$ e $(0, 5)$.

Progetta un algoritmo che, dato un intero $n \geq 2$, stabilisce se $n$ è primo provando i divisori fino a $\sqrt{n}$.

1. a) Scrivi lo pseudocodice.

1. b) Giustifica perché basta fermarsi a $\sqrt{n}$.

1. c) Eseguilo con $n = 91$ e $n = 97$.

Un algoritmo di ricerca binaria cerca un numero tra 1 e 1.000 ponendo domande del tipo «è maggiore di $m$?».

1. a) Descrivi la strategia.

1. b) Calcola il numero massimo di domande necessarie, giustificando con le potenze di 2.

1. c) Confronta con la ricerca sequenziale nel caso peggiore.

Considera l'algoritmo:

1. $a \leftarrow 0$, $b \leftarrow 1$

2. ripeti 8 volte: stampa $b$; $t \leftarrow a + b$; $a \leftarrow b$; $b \leftarrow t$

1. a) Esegui l'algoritmo e scrivi i valori stampati.

1. b) Riconosci la successione generata.

1. c) Spiega la differenza tra un algoritmo iterativo e uno ricorsivo, riscrivendo la definizione in forma ricorsiva.