Algoritmo di Euclide per il calcolo del MCD in Excel

QUI ho accennato all'Algoritmo di Euclide per il calcolo del Massimo Comune Divisore (MCD) di due numeri interi (positivi).
L'algoritmo di Euclide (Euclide lo descrisse nel suo libro degli Elementi) è un procedimento che permette di calcolare il MCD di due numeri mediante l'esecuzione di sottrazioni successive oppure di divisioni successive.
Supponiamo di voler calcolare il MCD di due numeri interi a e b.
Nel primo caso si procede, praticamente, in questo modo:
Si esegue la sottrazione a-b con differenza d;
[se a è minore di b, si considera il valore assoluto della differenza, cioè il numero senza il segno. E così per tutte le differenze successive]
si esegue quindi la sottrazione b- d con differenza d_1;
si esegue la sottrazione d - d_1 con differenza d_2 ;
si procede in questo modo fino a che l'ultima differenza ottenuta risulta uguale a zero (0).
Il valore che origina la differenza uguale a zero è il MCD cercato.
Seguiamo meglio mediante un piccolo esempio:
Calcoliamo il MCD di 18 e 12:
18-12 = 6
12-6 = 6
6-6 = 0
6 è il MCD di 18 e 12 (la differenza che ha dato luogo al valore zero).
In certi casi questo algoritmo può richiedere numerosissimi passaggi.

Euclide con i suoi Elementi:-)

E' possibile renderlo più veloce ricorrendo ad una serie di divisioni successive anziché sottrazioni.
Si considera il resto delle divisioni.
Calcoliamo il MCD di due numeri interi a e b.
Praticamente si procede così:
si esegue la divisione a:b con resto r
si esegue la divisione b:r con resto r_1
si esegue la divisione r : r_1
si procede in questo modo fino a che il l'ultimo resto ottenuto è zero(0).
Il resto che precede quello uguale a zero è il MCD cercato.
Si comprende meglio con un esempio:
Calcoliamo il MCD di 28 e 16
28: 16 = 1 con resto 12
16:12 = 1 con resto 4
12:4 = 3 con resto 0
MCD (28;16) = 4 (il resto precedente quello uguale a zero).
Rimando ancora a questa pagina per una spiegazione per ... più adulti!
Si può vedere anche qui.

In Excel si può applicare l'algoritmo euclideo utilizzando le funzioni RESTO() e ASS().
ASS() restituisce il valore assoluto, il numero privo di segno, di un numero reale.
Un'immagine del file:

La verifica con formula utilizza la funzione di excel MCD(num1;num2;...)
In cella G3 è immessa la formula: =MCD(A3;A4)
Da scaricare AlgoritmoEuclideoMCD.xls
Ci si può esercitare!

Il codice ISBN e la divisibilità per 11

Ragazzi (vale per la classe prima e per la seconda), avete mai notato quella strana sigla seguita da alcune cifre che si trova sul retro della copertina dei libri, sia su quelli di testo che di narrativa ecc...?
La sigla è ISBN ed è seguita da diverse cifre.
La sigla ISBN sta per International Standard Book Number, e il numero è una vera e propria carta d'identità del libro, permette di individuarlo fra tutti i libri del mondo!
Vi propongo un'attività per scoprire alcuni dei suoi segreti.
(Oltre al codice ISBN, sul retro delle copertine vedete anche un disegno a strisce bianche e nere, che serve al computer per "leggere" il codice. E' il codice a barre, che ha ancora un altro numero, parzialmente uguale al ISBN, ma di questo non ci occupiamo).
Dunque, organizziamoci per la nostra attività.
Cercate di raccogliere almeno una decina di codici, da testi scolastici o testi che avete in casa, e create una tabella simile a questa:

(l'esempio si riferisce a codici precedenti al 1° gennaio 2007. Dopo tale data, in Italia è stato aggiunto il prefisso 978).
Ora osservate con attenzione le vostre tabelle e cercate di rispondere alle seguenti domande:
- Da quante cifre è formato il codice ISBN?
- In quante parti sono suddivise le cifre?
- Trovate qualche caso in cui due libri hanno lo stesso codice ISBN?
- Due libri che hanno uguale la prima parte del codice, che cosa hanno in comune?
- Due libri che hanno uguale la seconda parte del codice, che cosa hanno in comune?
- Nella quarta (o quinta) parte del codice quali simboli si trovano?
Per la raccolta dei dati e la discussione sulle domande, vi suddividerete in gruppi e confronterete poi le vostre ipotesi.
In seguito chiariremo insieme tutti i dubbi residui!
L'ultimo simbolo del codice ISBN: il carattere di controllo.
Come potete notare già sulla tabella di esempio, l'ultimo simbolo del codice può essere una delle 10 cifre del nostro sistema di numerazione oppure la lettera X (nel sistema romano, il numero 10).
Questo simbolo permette al computer di controllare la correttezza del codice. Durante l'immissione del codice per mezzo di uno scanner o di una tastiera, si possono verificare errori di trasmissione o di digitazione. Il carattere di controllo permette al computer di rilevare la presenza dell'errore.
Calcoliamo il carattere di controllo.
Considerate nuovamente i codici ISBN da voi raccolti.
Per ciascuno di essi compilate una tabella, come da figura seguente.
Ciascuna delle prime 9 cifre va moltiplicata per i numeri da 10 a 2 (detti pesi). Si sommano poi i prodotti ottenuti:

Il carattere di controllo è il più piccolo numero che, addizionato al totale, dà un multiplo di 11.

Nell'esempio in figura, il totale è 290. Non è divisibile per 11, il più piccolo multiplo di 11 maggiore di 290 è 297, quindi il numero da aggiungere è 7. Il carattere di controllo è infatti 7.
Se il numero da aggiungere fosse 10, il carattere di controllo sarebbe X.
Verificate per i codici da voi considerati, che addizionando il totale e il carattere di controllo, si ottiene sempre un multiplo di 11.
Naturalmente....
tutto si può fare con Excel!
Che, come al solito ci aiuta nell'acquisire qualche consapevolezza in più... per esempio sulla divisione.
Sul file da scaricare, cod_ISBN, in cella L5 troverete la formula per il calcolo del carattere di controllo.
Ho usato la funzione RESTO() (integrata con la funzione SE() per gestire il resto uguale a zero oppure a 10), in questo modo:
11-RESTO(K5;11)
Perché per calcolare il carattere di controllo, ho sottratto da 11 il resto della divisione del totale (290 nell'esempio in figura) per 11?
Ragioniamo:
se un numero è divisibile per 11, il resto della divisione è uguale a ...?
Se il resto della divisione è invece ad es. uguale a 4 (RESTO(K5;11)=4), questo cosa vuol dire? Vuol dire che il numero contiene l'11 un certo numero di volte e avanzano 4 unità (gli spiccioli!)
E non vuole dire che se il numero avesse avuto 7 unità in più, avrebbe contenuto il numero 11 una volta in più, quindi un numero esatto di volte?
Quindi come trovo le 7 unità in più? Naturalmente: 11-4!
Sul file avrete modo di verificare l'esattezza del carattere di controllo con una formula alternativa e inoltre, troverete le indicazioni, vi sarà possibile digitare in una cella le 9 cifre di un qualsiasi codice ISBN e avere automaticamente il completamento del codice stesso con il carattere di controllo.

[Esercitazioni]Divisibilità e funzione Resto e funzione Quoziente

Gian Mario, Anna Laura e Giulia G. si sono esercitati con le funzioni Resto() e Quoziente() in Excel.

Gimmi, ALaura e Giulia, notate le modifiche? Ora scaricate il file. Come da accordi presi ... osservate e studiate l'aggiunta del SE()! ook? :-)

La funzione RESTO() in Excel

Il foglio elettronico (come ormai i nostri lettori sanno, noi usiamo Microsoft Excel) mette a disposizione una serie di funzioni e strumenti che ci permettono di affrontare problemi, sia matematici che tratti da altre discipline (pensiamo alla possibilità di realizzazione di grafici a partire da tabelle di dati), sotto un nuovo punto di vista, sicuramente stimolante.
L'uso di Excel favorisce il raggiungimento di diversi obiettivi, educativi e cognitivi:

• abitudine a costruire modelli ed elaborare strategie, quindi giungere a consapevoli valutazioni
• sviluppo delle capacità di utilizzare in situazioni nuove quanto già appreso
• sviluppo delle capacità espressive, comunicando efficacemente i risultati
• capacità di produrre documentazione in modo corretto ed esauriente
• capacità di lavorare in gruppo.

Fra le funzioni matematiche di Excel, una ci offre un prezioso aiuto giusto per fare matematica!
E' la funzione RESTO()
Pensiamo all'importante tema della divisibilità.
Sappiamo che un numero a è divisibile per un numero b se il resto della divisione a:b è 0.
La funzione RESTO() permette di calcolare il resto di una divisione, senza eseguirla.

L'uso di questa funzione prevede l'inserimento di due numeri, separati da un punto e virgola, che sono rispettivamente il dividendo e il divisore.
Vogliamo calcolare ad esempio il resto della divisione 156:13
In una cella del foglio di lavoro digitiamo la formula:
=RESTO(156;13)
Premiamo il tasto Invio
RESTO ci restituirà (è il termine proprio, usato per indicare l'azione della funzione, sarebbe un po' il nostro "ci dà"!) in questo caso, il valore 0.
Sappiamo immediatamente che 156 è divisibile per 13. Bello no?
Se in una cella immettessimo invece la formula: =RESTO(456;15) ci verrebbe restituito il valore 6. La divisione ha resto, uguale a 6: il numero 456 non è divisibile per 15.

Sappiamo però che Excel … è molto più comodo!
Volendo calcolare i resti di più divisioni, non siamo costretti a cambiare continuamente la formula.
Basta immettere il dividendo e il divisore in due celle distinte e istruire Excel affinché utilizzi quei due valori.
Ipotizziamo in cella A1 il valore 156,
in cella B1 il valore 13,
la nostra formula diventerà: =RESTO(A1;B1) diamo l'OK (tasto Invio) e il gioco è fatto!

Descriviamo la funzione usando il linguaggio specifico di Excel.
La sintassi della funzione RESTO() [notare: indichiamo una funzione scrivendola senza il segno dell'uguale e, di seguito, aperta e chiusa parentesi tonda; una formula, invece, deve sempre essere preceduta dal segno = e, dentro le parentesi tonde, gli argomenti (vedi sotto)], è la seguente:
RESTO(dividendo;divisore)
La funzione restituisce il resto della divisione: dividendo:divisore.
Dividendo e divisore costituisco gli argomenti della funzione.

Osservazione importante:
Se divisore è 0, RESTO restituirà il valore di errore #DIV/0!
Questo in tutti i casi, sia quando dividendo è diverso da zero, sia quando esso è uguale a zero (noi sappiamo che una divisione del tipo 5:0 è impossibile, perché non esiste nessun numero che moltiplicato per 0 dia 5, mentre 0:0 è indeterminata, cioè sono possibili infiniti risultati in quanto vi sono infiniti numeri naturali che moltiplicati per 0 danno per risultato 0).

Applicazioni e utilizzo della funzione.
Oltre che per stabilire la divisibilità di un numero per un altro, possiamo sfruttare RESTO() in altre occasioni.
Possiamo utilizzare la funzione per stabilire se un dividendo è pari o dispari.
Come? Usando il valore 2 per l’argomento divisore: =RESTO(dividendo;2)
Se il dividendo è un numero pari la formula ci restituirà …?
Se esso è dispari invece….?

Ancora: La funzione RESTO() nidificata (si dice così quando in una formula si integrano più funzioni) in una formula un po' più complessa, permette di verificare se un numero è primo oppure no.

[Come da immagine, nel file da scaricare QUI si possono osservare i risultati di tali applicazioni. In seguito conosceremo meglio le formule utilizzate].

Ancora nel campo della matematica RESTO() può essere utilizzata per un primo approccio (nella scuola media) allo studio dell’insieme delle Classi dei resti modulo = k (k, numero intero qualsiasi).
Una classe resto è l’insieme di quei numeri interi che danno lo stesso resto se divisi per uno stesso intero.
{0, 3, 6, 9, 12, 15, 18, ...} formano una classe di resto [0] modulo 3, perchè divisi per 3 danno lo stesso resto: 0
Utilizzando Excel è facile far notare, quindi far acquisire una migliore consapevolezza, che il resto della divisione tra due numeri naturali a e b (b diverso da 0) è sempre minore del numero b.
Ad esempio, dividendo un qualsiasi numero a per 3, il resto della divisione, sarà un numero compreso tra 0 e 2.

I numeri naturali sono infiniti, mentre è finito l’insieme dei resti della divisione per k (resti modulo k). Ci sono perciò infiniti numeri che, divisi per k, hanno lo stesso resto. Tali numeri costituiscono una classe di equivalenza, il cui rappresentante è il resto considerato.
NB:
La comprensione dell'argomento è facilitata dalla consultazione e l'uso del file da scaricare. Il file contiene anche la guida all'uso e la spiegazione dettagliata della struttura del foglio ... Sono, come al solito, gradite osservazioni, segnalazioni di eventuali errori, e/o richieste di chiarimenti su formule o quant'altro. Basta lasciare un commento al post.
Per i lettori più interessati, ancora qualcosa su RESTO():
- La funzione può essere espressa anche tramite INT():

RESTO(a;b) = a-b*INT(a/b)Infatti: Resto = Dividendo - Divisore*(Quoziente Intero)

- La funzione RESTO() può essere usata in Excel per gestire innumerevoli altre problematiche.
Solo un esempio: sfruttando la periodicità descritta delle classi resto, consente la gestione delle date (stabilire a quale giorno della settimana corrisponde una data, calcolare differenze tra date escludendo particolari giorni ecc.......)

alla prox! :-)