<< pagina principale < ······················ << articoli < ······················
Dodici monete sono tutte uguali tra loro tranne una, diversa dalle altre solo per il peso. Come si puo' individuarla con
il solo uso di una bilancia a bracci ?
Il problema e' una riedizione di un celebre rompicapo "...saltato
fuori, apparentemente dal nulla, nel 1945" (M.
Gardner: 'Il sistema ternario', in 'Enigmi e gochi matematici'
vol.5, ed. Sansoni), dove si richiede di individuare la moneta
diversa con sole tre pesate.
Anche in 'La strutture degli algoritmi', ed. Boringhieri, F.Luccio esamina lo stesso rompicapo per introdurre l'analisi del concetto di algoritmo.
Il problema e' stato posto a gruppi di insegnanti di matematica e fisica in fase di "alfabetizzazione" informatica nell'ambito del Piano Nazionale d'Informatica.
Con cio` si sono volute mettere in evidenza le difficolta` di esporre in modo chiaro un procedimento risolutivo, anche nel caso di un problema semplice come questo, e motivare una riflessione sullo stile e le strutture espositive, primo approccio all'informatica di base.
Dopo qualche imbarazzo iniziale, quindi, sono state prodotte descrizioni come le seguenti.
- A_____________B
^
= #
A_____________C A_____________C
^ ^
= = #
A_____________D B moneta A moneta
^ diversa diversa
=
"
"
"
A_____________X
^
#
X moneta diversa
- Chiamiamo x1, x2, ....., x12 le monete.
x1 , x2
x1 = x2 x1 # x2
x1 , x3 x1 , x3
x1 = x3 x1 # x3 x1 = x3 x1 # x3
" x3 x2 x1
"
"
x1 # x12
x12
- Si fanno due gruppi di 6 monete e li si dispone sui due piatti. Essi non saranno in equilibrio. Si estrae una moneta per ogni piatto. Si controlla se la bilancia e' o no in equilibrio. Se lo e' si pone in un piatto una delle due monete estratte, nell'altro piatto una delle altre 10 per individuare quella cercata. Se la bilancia e' in equilibrio la moneta cercata e' l'altra della coppia, altrimenti e' quella della coppia sulla bilancia. Se dopo l'estrazione della prima coppia i piatti non sono in equilibrio si itera il procedimento.
- Si suddividono le monete in tre gruppi
A B C
o o o o o o o o o o o o
Se A = B ----> C
Se A # B ----> A = C ----> B
A # C ----> A
In tutti i casi si individua il gruppo (*) con la moneta
anomala
1 2 3 4
(*) o o o o
Se 1 = 2
1 = 3 ----> 4
Se 1 = 2
1 # 3 ----> 3
Se 1 # 2
1 = 3 ----> 2
Se 1 # 2
1 # 3 ----> 1
1 # 3 ----> 1
- 1 2 3 4 5 6 7 8 9
o o o = o o o o o o # o o o
1 2 3 4 5 6
o o o o o o
= #
/ \
o o o o o o o o
= # = #
/ \ / \
6 1 4 9 1 8
o o o o
=# =#
/ \ / \
5 4 7 8
- Dividiamo le monete in 4 gruppi da 3 che chiamiamo A, B,
C, D.
1^pesata: se A = B allora C # D
2^pesata: confronto B con C
= #
/ \
/ \
D contiene la moneta C contiene la moneta
diversa diversa
*Chiamo P1, P2, P3, le monete del gruppo di peso diverso.
3^pesata: se P1 = P2 allora la moneta diversa e' P3
se P1 # P2 allora 4^pesata
4^pesata: se P2 = P3 allora la moneta diversa e' P1
se P1 # P3 allora la moneta diversa e' P2 Se nella 1^pesata A#B allora nella 2^ confrontero` C con B
2^pesata: se C = B allora A contiene la moneta diversa
se C # B allora B contiene la moneta diversa
Lo stile prevalentemente scelto nelle descrizioni e' grafico
bidimensionale. In molti casi, per rendere sufficientemente
chiara la comunicazione, e' risultato essenziale il supporto di
un commento orale. Si sono avute naturalmente anche descrizione
che usano in modo piu' o meno preciso le forme dei diagrammi di
flusso o delle istruzioni numerate. A questi stili e' stata data
in seguito poca rilevanza.
Una prima riflessione puo` essere fatta evidenziando le strutture linguistiche piu` comunemente usate nelle descrizioni.
- Mettere una moneta sul piatto a destra, mettere un'altra moneta sul piatto a sinistra. Finche' pesano uguali sostituire la moneta sul piatto di destra con una delle monete rimanenti. Sostituire infine la moneta sul piatto a destra con un'altra qualsiasi; se queste due ora pesano uguale allora la moneta sostituita sul piatto a destra era quella diversa, altrimenti la moneta attualmente sul piatto a sinistra e' quella diversa.
I segni d'interpunzione separano la descrizione di un'azione dalla seguente. Le strutture
finche' <condizione> <procedimento> ,
se <condizione> allora <procedimento> altrimenti <procedimento>
bastano e avanzano per scrivere qualsiasi procedimento. Questa notazione lineare, che, se ci si limita ai segni d'interpunzione e alle due precedenti strutture, si puo' chiamare "strutturata", puo' essere usata come un meccano linguistico per descrivere procedimenti.
Puo` essere utile, se non indispensabile quando si debba fare uso di subordinate, utilizzare lo stile dell'"indentazione" cosi` come nella descrizione seguente.
- Mettere una moneta sul piatto a destra;
mettere un'altra moneta sul piatto a sinistra;
finche' pesano uguali
sostituire la moneta sul piatto di destra con una delle monete rimanenti;
sostituire la moneta sul piatto a destra con un'altra qualsiasi;
se queste due ora pesano uguale
allora
la moneta sostituita sul piatto a destra era quella diversa
altrimenti
la moneta attualmente sul piatto a sinistra e' quella diversa.
Un altro stile, non incompatibile con il precedente, e' esemplificato nel seguito. Consiste nella descrizione analitica del procedimento risolutivo a partire da indicazzioni generali fino ai livelli di dettaglio desiderati.
-1^ analisi:
dividere le monete in tre gruppi;
trovare in quale gruppo X c'e' quella diversa;
trovare fra le quattro monete del gruppo X la diversa.
2^ analisi:
dividere le monete in tre gruppi;
trovare in quale gruppo X c'e' quella diversa:
chiamare A, B, C i tre gruppi;
se A = B
allora
il gruppo X e' il gruppo C
altrimenti
se A = C
allora
il gruppo X e' il gruppo B
altrimenti
il gruppo X e' il gruppo A;
trovare fra le quattro monete del gruppo X la diversa:
confrontare una moneta del gruppo X con una di un gruppo diverso;
se sono uguali
allora
trovare fra le tre monete rimanenti del gruppo X quella diversa
altrimenti
quella moneta del gruppo X e' la diversa.
(Ci fosse necessita' di specificare meglio come cercare frale tre altre monete del gruppo X quella diversa si potrebbe passare ad una ulteriore analisi).Questo stile, di scomposizione del complesso in parti sempre piu` semplici, non e' utile soltanto ai fini della comunicazione ma soprattutto in fase di progettazione del procedimento.
Si puo` passare infine ad un esempio di descrizione basato su un'interessante "meta-struttura".
-Come cercare tra n ( >2 ) monete quella di peso diverso:
se n = 3
allora
se prima moneta = seconda moneta
allora
se prima moneta = terza moneta
allora
non ci sono monete diverse
altrimenti
la terza moneta e' diversa
altrimenti
se prima moneta = terza moneta
allora
la seconda moneta e' diversa
altrimenti
la terza moneta e' diversa
altrimenti
metti da parte una moneta;
cerca tra quelle rimanenti la moneta diversa;
se non c'e'
allora
quella appena messa da parte e' diversa;
La struttura linguistica, o meglio meta-linguistica, su cui si basa e' detta 'ricorsiva', come il procedimento descritto. Una descrizione e' detta ricorsiva quando in essa si fa riferimento all'intera descrizione. Analogamente un procedimento e' detto ricorsivo quando un suo passo consiste di tutto il procedimento.
Le monete possono essere riorganizzate in diverse strutture e in ognuno dei casi il procedimento, o soltanto la sua descrizione, ne sara` strettamente influenzato.
-Le monete sono distintamente rappresentate da p1, p2, ...., p12;
metti p1 sul piatto a sinistra;
metti p2 sul piatto a destra;
finche' p1 e pi sono in equilibrio
metti p(i+1) al posto di pi;
se i > 2
allora
pi e' diversa
altrimenti
metti p3 al posto di p2
se p1 e p3 sono in equilibrio
allora
p2 e' diversa
altrimenti
p1 e' diversa.
-Le dodici monete sono messe in fila. Si distinguono il piatto A e il piatto B.
Metti su A la moneta in testa;
metti su B la moneta in testa;
finche` c'e` equilibrio
metti in coda la moneta su B
metti su B la moneta in testa;
metti in coda la moneta su B;
metti su B la moneta in testa;
se c'e` equilibrio
allora
la moneta diversa e` quella in coda
altrimenti
la moneta diversa e` quella su A
-Le monete sono raggruppate in tre gruppi distinti, chiamati A, B, C, entro cui le monete sono indistinte;
se A e B sono in equilibrio
allora
cercare in C la moneta diversa
altrimenti
se A e C sono in equilibrio
allora
cercare in B la moneta diversa
altrimenti
cercare in A la moneta diversa;
Come cercare in X la moneta diversa:
prendere una qualsiasi moneta di X;
prendere una qualsiasi moneta non di X;
se la moneta di X pesa come la moneta non di X
allora
cercare fra le tre monete rimanenti quella diversa
altrimenti
la moneta presa da X e' diversa.
-Alle monete sono distintamente associati i seguenti simboli:
010, 011, 012, 001
120, 121, 122, 112
200, 201, 202, 220;
sia i inizialmente uguale a 1;
finche' i <= 3
metti sul piatto a sin tutte le monete rappresentate da un simbolo che abbia 0 al posto i-esimo;
metti sul piatto a des tutte le monete rappresentate da un simbolo che abbia 2 al posto i-esimo;
se i piatti sono in equilibrio
allora
il simbolo probabilmente associato alla moneta diversa ha 1 all'i-esimo posto
altrimenti
se va giu' il piatto a sin
allora
il simbolo probabilmente associato alla moneta diversa ha 0 all'i-esimo posto
altrimenti
il simbolo probabilmente associato alla moneta diversa ha 2 all'i-esimo posto;
se il simbolo cosi' ottenuto e' effettivamente associato ad una moneta
allora
quella moneta e' piu' pesante delle altre
altrimenti
scambiando 0 con 2 e viceversa nel probabile simbolo si ottiene il simbolo associato alla moneta piu' leggera.
Quest'ultimo algoritmo, fortemente caratterizzato dalla organizzazione scelta per i dati, e' il piu' efficiente: con esattamente tre pesate consente di individuare la moneta diversa e sapere se e' piu' pesante o piu' leggera. E' un chiaro esempio di come una opportuna organizzazione dei dati sia determinante per costruire procedimenti efficienti.
Un elemento essenziale di una "educazione informatica" e' la capacita` di servirsi consapevolmente delle strutture linguistiche di: sequenza, selezione, ripetizione, indentazione e ,infine, ricorsivita`; cio` non solo per comunicare procedimenti ma anche come strumento per concepirli. Un altro elemento essenziale consiste nella capacita` di differenziare le diverse strutture, numeriche e non, nelle quali si possono organizzare i dati relativi ad un certo problema. Anche questa capacità non serve soltanto a posteriori, per scrivere chiaramente procedimeli ti già pensati e renderne possibile ad esempio la comunicazione ad un esecutore, ma come modo di organizzare l'attività di ricerca dei procedimenti stessi. Si può aggiungere inoltre come la capacità di servirsi di un'elaboratore di lesti, in particolare per avere a disposizione un foglio in cui lo spazio tra le righe non è limitato, contribuisca notevolmente soprattutto in fase di ricerca creativa ad utilizzare ordinatamente le strutture linguistiche esaminate (rendendo obsoleti i diagrammi di flusso) e ad applicare lo stile di scomposizione del complesso in parti via via più semplici.