ALGORITMI E PSEUDOCODICE
a cura di Tommaso Bonetti
Introduzione
COS'È UN ALGORITMO
Lo scopo del programmatore è quello di insegnare a una macchina (il proprio computer) come risolvere un problema al posto suo. Per raggiungere questo scopo, è necessario che il programmatore comprenda a fondo il problema da risolvere e analizzi i passi da seguire per giungere alla soluzione corretta, ed è qui che entra in gioco il concetto di algoritmo.
Le caratteristiche di un algoritmo
Un algoritmo è, per definizione, una sequenza di passi che, a partire dai dati iniziali del problema, è in grado di produrre un risultato: la soluzione. Ogni passo dell’algoritmo deve essere un’istruzione elementare, che non può essere scomposta in più operazioni: per esempio, un’operazione aritmetica o un confronto sono istruzioni elementari, mentre la risoluzione di un’equazione non la è, in quanto si articola in più passi.
Per essere definito tale, un algoritmo deve essere:
-
Non ambiguo: chiunque legga l’algoritmo deve poterlo interpretare allo stesso modo
-
Finito: deve essere in grado di risolvere il problema in un numero finito di passi
-
Deterministico: gli stessi dati iniziali producono sempre lo stesso risultato
Per ogni problema che ci viene sottoposto possono esistere più algoritmi risolutivi, ognuno in grado di trovare la soluzione corretta tramite passi diversi: questo significa che ogni algoritmo richiederà un certo tempo per risolvere il problema.
La difficoltà nel programmare, quindi, può nascere dal fatto che, oltre a dover individuare un algoritmo per il problema da risolvere, è anche necessario capire se l’algoritmo proposto è il più veloce e, in caso non lo fosse, cercare di trovarne uno migliore. Quando inizierai a programmare scoprirai che una delle difficoltà della programmazione è proprio questa, ma non preoccuparti: con l’esperienza questo processo diventa sempre più semplice e nelle prossime lezioni avrai modo di esercitarti.
TIPOLOGIE DI ELABORAZIONE
A seconda del problema da risolvere, sarà necessario adottare diversi tipi di approcci risolutivi: i principali sono l’elaborazione sequenziale e l’elaborazione condizionale.
Elaborazione sequenziale
L’elaborazione sequenziale è basata su algoritmi i cui passi vengono eseguiti, una sola volta, a prescindere dai dati del problema.
Prendi in considerazione l’algoritmo che trasforma un intervallo di tempo, espresso in secondi, in termini di minuti e secondi. I passi da seguire sono:
-
Per trovare il numero di minuti divido il numero di secondi per 60 (i secondi in un minuto)
-
Per trovare il numero di secondi considero semplicemente il resto della divisione precedente
Per esempio, considerando un tempo T = 135 s, il numero di minuti è 135 / 60 = 2 con il resto di 15, che corrisponde al numero di secondi.
Noterai che i passi dell’algoritmo vengono eseguiti in ogni caso (non dipendono, cioè, dai dati in input) e vengono eseguiti una volta sola.
Elaborazione condizionale
L’elaborazione condizionale si basa su una serie di scelte che possono variare la sequenza di istruzioni che vengono eseguite. Contrariamente all’elaborazione sequenziale, quindi, alcuni passi dell’algoritmo potrebbero non essere eseguiti, e altri potrebbero essere eseguiti più volte: queste decisioni dipendono esclusivamente dai dati in input.
Per esempio, considera l’algoritmo che, dato un numero intero, restituisce il suo valore assoluto.
L'algoritmo può essere scritto in questo modo:
-
Il numero è positivo o nullo?
-
Sì: |num| = num
-
No: |num| = -num
-
Si nota facilmente che, in base al dato iniziale (il numero di cui si vuole ottenere il valore assoluto), la sequenza delle istruzioni da eseguire varia.
Come dicevamo prima, l’elaborazione condizionale implica che alcuni passi dell’algoritmo possano essere eseguiti più volte: in questo caso vengono utilizzati i cicli.
Un ciclo non è altro che una sezione dell’algoritmo che viene ripetuta più volte: il numero di esecuzioni (o iterazioni) può essere stabilito a priori, oppure le iterazioni possono continuare fino al raggiungimento di una certa condizione.
Per esempio, considera l’algoritmo per calcolare se un numero n è primo.
I passi da seguire sono:
-
Per ogni numero intero, che chiameremo div, compreso tra 1 e il nostro n, esclusi, eseguo le seguenti istruzioni:
-
n è divisibile per div? (cioè il resto della divisione n / div è 0)
-
Sì: n non è un numero primo, fine dell’algoritmo
-
No: torno a "n è divisibile per div?" e ricomincio il ciclo, utilizzando un nuovo divisore: div+1
-
-
-
Fine del ciclo: se sono arrivato qui, significa che ho analizzato tutti i numeri tra 1 e n, esclusi, e nessuno di essi è divisore di n: pertanto posso concludere che n è un numero primo
Prosegui nella lezione per vedere altri esempi e metterti alla prova con i tuoi primi algoritmi!
Un numero primo è un numero i cui unici divisori sono 1 e sé stesso.
Il numero 1 è un caso particolare e non è considerato un numero primo.
Il valore assoluto di un numero è il numero stesso senza il segno,
Il valore assoluto di un numero positivo è il numero stesso, mentre quello di un numero negativo è il suo opposto.
LO PSEUDOCODICE
Prima di affrontare gli esercizi, ecco qualche semplice regola per scrivere lo pseudocodice in modo omogeneo:
-
ogni passo dell’algoritmo deve essere scritto su una riga a sé stante
-
dai un nome significativo ai tuoi dati e, se comprende più parole, uniscile con un underscore (per esempio: data_di_oggi)
-
per assegnare un valore a un dato, scrivi nome_dato = … (per esempio: età = anno_attuale - anno_nascita)
-
se l’algoritmo comprende una scelta condizionale, scrivi se [condizione]: … / altrimenti: …
-
se l’algoritmo comprende un ciclo da eseguire un numero fisso di volte, scrivi per … volte: …oppure per ogni … da … a …: … (per esempio: per 10 volte oppure per ogni numero n da 1 a 5)
-
se l’algoritmo comprende un ciclo da eseguire fino al raggiungimento di una condizione, scrivi finché [condizione]: …
Esercizi risolti
Esercizio 1
Data l'età di una persona e l'anno attuale verificare se la persona è nata nel terzo millennio, scrivendo sì o no come risultato.
Scrivi ogni istruzione su una nuova riga.
anno_nascita = anno_attuale - età
se anno_nascita >= 2000:
sì, la persona è nata nel terzo millennio
altrimenti:
no, la persona non è nata nel terzo
millennio
Esercizio 2
Nello scenario di una partita di calcio, dato il numero di gol della squadra in casa e in trasferta, dire se la squadra di casa ha vinto, pareggiato o perso.
Scrivi ogni istruzione su una nuova riga.
se gol_casa > gol_trasferta:
la squadra di casa ha vinto
altrimenti se gol_casa < gol_trasferta:
la squadra di casa ha perso
altrimenti:
le squadre hanno pareggiato
Esercizio 3
Dato un numero intero n, stabilire se tale numero è primo. Suggerimento: prova a prendere spunto dall'esempio sopra!
Scrivi ogni istruzione su una nuova riga.
per ogni intero div da 2 a n-1:
se n è divisibile per div:
n non è un numero primo, fine algoritmo
altrimenti:
div = div + 1
fine ciclo: n è un numero primo
CONCLUSIONE
Complimenti, hai completato la seconda lezione!
In questa lezione hai imparato cos'è un algoritmo e che caratteristiche ha, per poi risolvere i tuoi primi problemi in pseudocodice.
Usa i pulsanti qui sotto per avanzare alla terza lezione o per tornare alla home del corso.