Un algoritmo è una successione di istruzioni che risolve un problema. Il numero di istruzioni deve essere finito e il risultato finale deve essere la soluzione del problema.
ESEMPI DI ALGORITMI
Disegnare su un foglio una figura geometrica non troppo complicata; chiamare uno studente che deve elencare alla classe i passi da fare per disegnare la figura senza mostrarla. La classe non può chiedere spiegazioni!
Illustrare i passi per fare una telefonata.
Ordinamento mazzo di 40 carte
Problema: Ordinare un mazzo di 40 carte in cuori, quadri, fiori e picche; le carte di uno stesso seme sono ordinate dall’asso al re
Algoritmo: Si suddivida il mazzo in 4 mazzetti, ciascuno costituito da tutte le carte dello stesso seme Si ordinino le carte di ciascun mazzetto dall’asso al re. Si prendano nell’ordine i mazzetti di cuori, quadri, fiori e picche
Ricerca chiave in un mazzo di chiavi
Problema: Si vuole ricercare, all’interno di un mazzo di chiavi, quella che apre un dato lucchetto
Algoritmo:
Si seleziona una chiave dal mazzo e la si marca con un pennarello
Si tenta di aprire il lucchetto con la chiave appena marcata; se funziona, si va al passo 6
Altrimenti, si controlla la chiave successiva
Se non è marcata, la si marca e si torna al passo 2.
Viceversa, se è marcata, si prende atto che nel mazzo non è presente la chiave che apre il lucchetto e si va al passo 4
Fine della ricerca
Teorema di Pitagora
Calcolare il valore dell’ipotenusa dati i due cateti:
Algoritmo che calcola la radice quadrata (di numeri che sono quadrati perfetti).
Calcolare l'area di un triangolo
Determinare se un numero è divisibile per un altro numero
Determinare la presenza di un numero in una lista
Utilizzando operazioni di confronto e scambio ordinare 2, 3, 4... dati numerici
Scopri la funzione svolta dall'algoritmo del famoso Papiro Rhind, che si ritiene scritto dallo scriba egizio Ahmes, circa nel 1650 a.C., e conservato nel British Museum di Londra.
1. Disegna una tabella con 3 colonne: a, b, c
2. Inserisci nelle colonne a, b due numeri interi
3. Poni c=0
4. Ripeti finché la condizione (a > 0 ) è vera:
4.1 se a è dispari, allora:
4.1.1 fai la somma di b e c e metti il risultato in c;
4.2 Dimezza a trascurando il resto;
4.3 Raddoppia b.
5. Il risultato finale è c.
Scopri la funzione svolta dal seguente algoritmo
0. Disegna una tabella con 3 colonne: a, b, c
1. scrivi un numero intero in a
2. scrivi un numero intero in b
3. scrivi 0 in c
4. ripeti le seguenti istruzioni finché la condizione (b > 0 ) è vera:
4.1 fai la somma a+c
4.2 scrivi il risultato in c
4.3 decrementa b
5. leggi il risultato riportato in c
Papiro di Mosca (1700a.c.): calcolo del volume del tronco di piramide a base quadrata
Sia h l'altezza, a il lato della base inferiore, b il lato della base superiore.
Inizio dell'algoritmo (altezza 6, base 4, cima 2).
Calcola il quadrato di a
Moltiplica a per b.
Calcola il quadrato di b.
Somma i risultati dei calcoli precedenti
Calcola 1/3 di h.
Moltiplica quest'ultimo per la somma precedente.
Fine dell'algoritmo: Verifica se il risultato è giusto.
Il gioco dell’undici
Problema. Si gioca in due. Si disegnano 11 astine su un foglio: ogni giocatore, alternativamente, puo' eliminare da 1 a 3 astine; il giocatore che è costretto ad eliminare l’ultima astina perde.
Strategia vincente per il giocatore A che gioca per primo: A elimina inizialmente 2 astine, quindi 4-k, con k le astine eliminate da B.
Algoritmo vincente per il giocatore A che gioca per primo
Inizio
1. elimina due astine
2. ripeti finchè la condizione (ci sono astine) è vera
2.1 aspetta la mossa di B che elimina k astine con 0<k<4
2.2 elimina 4-k astine
Fine
Equazione di 1° grado
Problema: Calcolo della soluzione ax+b=0
Algoritmo:
Acquisire i coefficienti a,b
Se a=0 e b=0 esistono infinite soluzioni; eseguire l’istruzione 6
Se a=0 e b!=0 non ci sono soluzioni; eseguire l’istruzione 6
Se a!=0 e b=0 la soluzione risulta x=0; eseguire l’istruzione 6
Se a!=0 e b!=0 la soluzione risulta x=-b/a;
Comunicare il risultato
Fine
Calcolo del M.C.D.
Problema: Calcolare il M.C.D. di due interi a,b, con a>b
Calcolo MCD
1) Acquisire i valori di a e b
2) Se b>a, scambiare i valori di a e b
3) Calcolare il resto r della divisione intera di a per b
4) Se la condizione (r=0) è vera
4.1 MCD(a,b)=b;
4.2 comunicare il risultato all’esterno;
4.3 eseguire l’istruzione 5)
altrimenti
4.4 sostituire il valore di a con il valore di b
4.5 sostituire il valore di di b con il valore di r;
4.6 tornare al passo 3)
5) Fine
OSSERVAZIONI
Osserviamo che i resti diminuiscono sempre più fino ad arrivare a 0. Allora siamo sicuri che prima o poi ci fermiamo e troviamo il M.C.D.
Se cerchiamo il M.C.D. con il metodo della scomposizione in fattori troviamo lo stesso risultato. Infatti il M.C.D. tra due numeri dipende solo da quei due numeri e non dal metodo usato per calcolarlo!
ESERCIZI
Calcolare M.C.D.(45, 32) e M.C.D.(600, 580) con entrambi i metodi visti, cioè sia mediante scomposizione in fattori primi, sia con l'algoritmo di Euclide.
Calcolare M.C.D.(120, 48, 24, 60) con uno solo dei metodi visti. Quale metodo?
Calcolare M.C.D.(1934, 1933) con uno solo dei metodi visti. Quale metodo?