2021⚓︎

Esercizio 1⚓︎

Leggere in input due interi \(n, k > 0\) e calcolare i primi \(n\) multipli di \(k\). Realizzare l'algoritmo in pseudo-codice, considerando i controlli sull'input.

Esempio:

Dati \(n = 3\) e \(k = 4\), i primi \(3\) multipli di \(4\) sono \(4, 8, 12\).

INPUT:: \(n\) – numero di multipli di \(k\) da calcolare, \(n \in \N^\ast\); \(k\) – numero di cui calcolare gli \(n\) multipli, \(n \in \N^\ast\)
OUTPUT:: multipli – Insieme di \(n\) multipli di \(k\), insieme di naturali, cardinalità \(n\).

ALGORITMO

Bozza
1 2 3 4	`leggere n leggere k controllare n e k // si può operare in due modi calcolare i multipli`

Il precedente non è un algoritmo ma, come sempre, un'idea di come risolvere il problema. Il controllo, come accennato, è possibile effettuarlo in due modi.

Primo modoSecondo modo

Bozza, v2a
1 2 3 4 5	`leggere n leggere k SE (n e k soddisfano i vincoli) ALLORA calcolare i multipli FINE`

Bozza, v2b
1 2 3 4 5 6	`leggere n leggere k SE (n e k soddisfano i vincoli) ALLORA ANDARE a 1 ALTRIMENTI calcolare i multipli FINE`

È presente l'istruzione ANDARE, ma questa è solo una bozza, verrà rimossa nell'algoritmo.

Bisogna rendere chiari i vincoli, magari con un messaggio che li specifichi o che chiarisca il comportamento aspettato. Poiché vengono richiesti due valori positivi dando in input, ad esempio, \(5, -1\) l'algoritmo tornerebbe al primo punto e richiederebbe entrambi i numeri, nonostante il primo fosse corretto. Sarebbe quindi consigliato controllare ogni dato separatamente.

Bozza, v2b.1
1 2 3 4 5 6 7 8 9	`leggere n SE (n non soddisfa i vincoli) ALLORA TORNARE a 1 FINE leggere k SE (k non soddisfa i vincoli) ALLORA TORNARE a 5 FINE calcolare i multipli`

In questo modo vengono evitate operazioni inutili. Dunque, traducendo:

Algoritmo, v1
1 2 3 4 5 6 7 8 9 10	`n := 0 MENTRE (n < 0) leggere n FINE k := 0 MENTRE (k < 0) leggere k FINE calcolare i multipli`

Con questa sintassi l'algoritmo non procede finché non riceve i dati corretti in input, per questo è possibile aggiungere un messaggio che renda noto che il valore di \(n\) o di \(k\) è errato.

Una possibile alternativa sarebbe:

Algoritmo, v1a
1 2 3 4 5 6 7 8 9 10 11 12 13	`ESEGUI scrivere messaggio leggere n FINCHÉ (n <= 0) FINE ESEGUI scrivere messaggio leggere k FINCHÉ (k <= 0) FINE calcolare i multipli`

Dal punto di vista dell'efficienza, questo algoritmo è migliore. Inoltre rimuove il problema di assegnare dei valori sia ad \(n\) che a \(k\). Entrambe le soluzioni sono valide, ma in questo caso è preferibile utilizzare il blocco ESEGUI [...] FINCHÉ.

Dopo aver migliorato la struttura di controllo, ora è necessario specificare cosa significhi calcolare i multipli. Bisogna calcolare \(n\) volte i multipli di \(k\) e poiché è presente una ripetizione è necessario usare un'iterazione. Dunque:

Calcolo dei multipli
1 2 3 4 5	`p := 1 MENTRE (p <= n) elemento p-esimo di multipli := k * p p := p + 1 FINE`

Attenzione

una cosa che non è possibile fare è la seguente

Text Only

multipli := k * p

poiché multipli è un insieme e non un singolo elemento. Questo significa che bisogna assegnare un valore in una posizione specifica.

Bisogna ora specificare il messaggio da mostrare nel caso in cui vengano inseriti dei dati non corretti.

Nel C sono presenti funzioni che permettono di stampare a video ciò che si desidera (printf()), nello pseudo-codice scriveremo StampareAVideo(), quindi, ad esempio:

Text Only

StampareAVideo("Inserire il numero di multipli da calcolare")

Leggere in input

Per leggere dei dati in input, il C offre la funzione scanf(), in pseudo-codice useremo LeggereDaTastiera(). In questo modo il programma si blocca finché non riceve un dato in input.

Mettendo tutto insieme si ottiene:

ALgoritmo

ESEGUI
  StampareAVideo("Inserire il numero di multipli da calcolare, maggiore di 0")
  n := LeggereDaTastiera()
FINCHÉ (n <= 0)
FINE

ESEGUI
  StampareAVideo("Inserire il numero di cui calcolare i multipli, maggiore di 0")
  k := LeggereDaTastiera()
FINCHÉ (k <= 0)
FINE

p := 1
MENTRE (p <= n)
  elemento p-esimo di multipli := k * p
  p := p + 1
FINE

Esercizio 2⚓︎

Leggere in input due interi \(n,k > 0\) e verificare se \(n\) è divisibile per \(k\). Realizzare l’algoritmo in pseudo-codice, considerando i controlli sugli input.

Esempio: Dati \(n = 3\) e \(k = 4\), \(n\) non è divisibile per \(k\).

INPUT:: \(n\) - numero di cui verificare la divisibilità per \(k\), \(n \in \N^\ast\); \(k\) - numero di cui verificare se sia divisore di \(n\), \(k \in \N^\ast\)
OUTPUT:: divisibile - indica se \(n\) sia divisibile (vero) o meno (falso) per \(k\), booleano

La prima bozza di questo algoritmo è molto simile a quella del'algoritmo dell'esercizio precedente, l'unica differenza consiste nel verificare la divisibilità anziché calcolare i multipli.

Algoritmo, v1
1 2 3 4	`SE (n modulo k = 0) ALLORA divisibile := vero ALTRIMENTI divisibile := falso FINE`

Nel caso in cui il resto (ovvero il modulo) sia zero, allora \(n\) è divisibile per \(k\). Ma com'è di preciso definita l'operazione modulo? Va specificata.

È possibile risolvere il problema senza utilizzare l'operazione modulo facendo uso di sottrazioni ripetute. Nel caso in cui il risultato sia zero allora non è presente resto, se invece il risultato fosse maggiore di zero, allora il resto è presente.

Algoritmo, v2
1 2 3 4 5 6 7 8	`MENTRE (n >= k) n := n - k FINE SE (n = 0) ALLORA divisibile := vero ALTRIMENTI divisibile := falso FINE`

In questo algoritmo si va a perdere il valore di \(n\) e sarebbe meglio preservarlo utilizzando una variabile come temp.

È importante notare come la prima versione dell'algoritmo nel caso in cui venga tradotto in un linguaggio che non possegga l'operazione modulo, l'esecutore non saprebbe come fare. Dunque o si risolve il problema in maniera differente, oppure si specifica cosa fa l'operazione modulo.

Abbiamo dato per scontato che esista una funzione

Text Only

r := modulo(n, k)

il che non è sempre vero ed è quindi un errore.