Oggi entreremo nel mondo degli algoritmi con questo problema che potete trovare a pagina 13 del testo Il pensiero computazionale – Dagli algoritmi al coding di Paolo Ferragina e Fabrizio Luccio.

Tra tre monete di identico aspetto una potrebbe essere falsa e di peso differente. Disponendo di una bilancia a due piatti per confrontare le monete tra loro si vuole individuare la moneta falsa se c’è, e in questo caso stabilire se pesa più o meno delle altre, mediante non più di due pesate.

Prima di partire a testa bassa immaginando un ipotetico algoritmo o, peggio ancora, cominciando a scrivere direttamente del codice, fermiamoci e leggiamo lentamente, più volte, e con molta attenzione l’enunciato del problema.

Cerchiamo quindi di individuare e ordinare le informazioni essenziali che rappresenteranno i nostri dati.

Poi sforziamoci di capire cosa ci viene chiesto, in modo tale da essere in grado di formulare con precisione le giuste domande a cui dovremo cercare di dare risposta con il nostro algoritmo tradotto in codice FreeBASIC.

Le giuste domande ci guidano nella definizione del nostro obiettivo.

Raccolta delle informazioni essenziali (dati)

Suddividiamo e ordiniamo le informazioni in punti:

• «tre monete di identico aspetto»;
• «una potrebbe essere falsa e di peso differente»;
• «bilancia a due piatti per confrontare le monete»;
• «non più di due pesate».

Una volta raccolte le informazioni essenziali che, come già detto, non sono altro che i dati su cui potremo operare, analizziamo i nostri punti.

Il primo, il terzo e il quarto non sembrano presentare ambiguità. Concentriamoci quindi sul secondo punto. Questo punto, se letto in maniera poco attenta, potrebbe crearci dei problemi nel momento in cui inizieremo a progettare l’algoritmo risolutivo: il testo, infatti, riferendosi alle monete ci dice che «una potrebbe essere falsa».

Stiamo bene attenti…

Cosa ci dice questa frase?

Che ci sono delle monete false?

No!

La frase semplicemente asserisce due cose:

1. la prima è che non ci possono essere più monete false;
2. la seconda è che potrebbero anche non essercene.

Quindi i casi sono soltanto due:

1. o c’è una moneta falsa;
2. oppure non ci sono monete false.

Il secondo punto rappresenta quindi una informazione chiave per la definizione del nostro obiettivo.

Dobbiamo quindi stare sempre attenti non soltanto a ciò che di esplicito ci dicono le informazioni in nostro possesso, ma anche a ciò che ci viene suggerito in modo implicito. Molto spesso sono proprio le informazioni implicite a sfuggirci con più facilità.

Ecco allora che è bene seguire questa regola:

È bene trasformare sempre le informazioni implicite in esplicite.

Proviamo quindi a farlo con il nostro secondo punto:

• frase implicita: «una potrebbe essere falsa e di peso differente»;
• frase esplicita: se esiste una moneta tra le tre date che ha un peso differente dalle altre due che per definizione devono avere in questo caso pari peso, allora questa è falsa.

Definizione precisa delle domande (obiettivo)

Torniamo all’enunciato del problema per cercare di scoprire qual è il nostro obiettivo: ovvero a quali domande dobbiamo rispondere.

Ecco le frasi che ci interessano:

• «individuare la moneta falsa se c’è»;
• «in questo caso stabilire se pesa più o meno delle altre».

Che possiamo tradurre in queste due domande:

1. Esiste una moneta falsa?
2. Se esiste, pesa di più o di meno delle altre due?

Progettazione di un algoritmo risolutivo (pensiero computazionale)

Bene, ora che abbiamo raccolto i dati e definito le domande a cui dobbiamo rispondere, proviamo ad immaginare il cuore del nostro algoritmo procedendo per passi.

• la prima cosa da fare che dovrebbe venirci in mente è quella di identificare in qualche modo le nostre tre monete per poterle riconoscere senza ambiguità: diamo quindi i nomi di prima, seconda e terza moneta;
• a questo punto possiamo procedere con la prima pesata (#1) tra la prima e la seconda moneta;
• da questa prima operazione potremo ricavare esclusivamente due possibili soluzioni:
  1. le due monete hanno lo stesso peso;
  2. le due monete hanno peso differente.
• a questo punto procediamo con la seconda pesata (#2) tra la prima moneta e la terza moneta;
• ovviamente anche da questa operazione non potremo che ottenere le due possibili soluzioni che abbiamo visto in precedenza, ovvero:
  1. le due monete hanno lo stesso peso;
  2. le due monete hanno peso differente.

E adesso viene il bello: che ce ne facciamo con questi risultati?

Proviamo a spremere le meningi…

Tabella associativa

La cosa migliore da fare sembra essere quella di costruire una Tabella associativa che metta in relazione tutti i possibili risultati delle due pesate ottenendo quindi le diverse soluzioni possibili:

'Tabella associativa risultati pesate/soluzioni possibili
'             pesata #2
'  pesata #1 |  1  |  2
'      1     |  A  |  B
'      2     |  C  |  D

Analizziamo ora il significato delle soluzioni:

• A: pesata #1 risultato 1, pesata #2 risultato 1 → la moneta falsa non esiste
• B: pesata #1 risultato 1, pesata #2 risultato 2 → la terza moneta è falsa
• C: pesata #1 risultato 2, pesata #2 risultato 1 → la seconda moneta è falsa
• D: pesata #1 risultato 2, pesata #2 risultato 2 → la prima moneta è falsa

Se siamo abbastanza confidenti – ancora non possiamo infatti dirci sicuri al 100% – che il nostro algoritmo funzioni, allora possiamo a ragion veduta cominciare a scrivere il nostro codice sorgente. Farlo prima ci avrebbe fatto perdere soltanto del tempo. Provare per credere. 😉

Scrittura del codice (coding)

Bene. Riprendiamo in mano il nostro algoritmo e cominciamo a scrivere:

'identificazione delle monete attraverso la loro dichiarazione
dim as integer m1, m2, m3

'definisci il caso di test assegnando
'i pesi delle monete
input "quanto pesa la prima moneta"; m1
input "quanto pesa la seconda moneta"; m2
input "quanto pesa la terza moneta"; m3

'verifica correttezza specifica
if m1 <> m2 and m1 <> m3 and m2 <> m3 then
  print "Attenzione! Non stai rispettando la"
  print "specifica che prevede che al massimo"
  print "ci possa essere una sola moneta falsa"
  print "con peso differente."
  end 'esci dal programma
end if

'pesata #1 tra la prima e la seconda moneta
if m1 = m2 then
  'procediamo con la seconda pesata
  if m1 = m3 then
    'Soluzione A
    print "la moneta falsa non esiste"
  elseif m1 < m3 then
    'Soluzione B
    print "la terza moneta è falsa e pesa di più"
  else 'm1 > m3
    'Soluzione B
    print "la terza moneta è falsa e pesa di meno"
  end if
elseif m1 < m2 then
  'procediamo con la seconda pesata
  if m1 = m3 then
    'Soluzione C
    print "la seconda moneta è falsa e pesa di più"
  else 'm1 < m3
    'Soluzione D
    print "la prima moneta è falsa e pesa di meno"
  end if
else 'm1 > m2
  'procediamo con la seconda pesata
  if m1 = m3 then
    'Soluzione C
    print "la seconda moneta è falsa e pesa di meno"
  else 'm1 > m3
    'Soluzione D
    print "la prima moneta è falsa e pesa di più"
  end if
end if

Rivediamo più volte il codice prima di compilarlo. Se la compilazione dovesse fallire leggiamo bene il tipo di errore che il compilatore FreeBASIC ci segnala e operiamo le opportune correzioni al codice. Una volta che la compilazione ha successo possiamo finalmente eseguire il nostro codice e passare alla fase di collaudo del software.

Test

Per collaudare il nostro software dobbiamo testare tutte le diverse combinazioni dei risultati delle due pesate (caso di test) e confrontare quindi i risultati (i nostri print a video) con le possibili soluzioni (oracolo).

Per fare questo non dobbiamo inventarci nulla, ma semplicemente riprendere la nostra Tabella associativa e giocare con i pesi rispettando le specifiche date: ovvero stando attenti a non inserire pesi diversi per tutte e tre le monete.

Potete testare il codice anche su JDoodle cliccando qui.

Buon divertimento e a presto. 😉