Il problema delle tre monete

Cominciamo la nostra avventura nel mondo degli algoritmi con questo primo 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. 😉

Introduzione al pensiero computazionale

Comincia con questo primo articolo una nuova categoria del blog dedicata al pensiero computazionale.

Il pensiero computazionale è un processo mentale per la creazione di un algoritmo, ovvero di una sequenza finita di passi elementari (istruzioni), traducibili poi in un linguaggio di programmazione (codice sorgente) in grado di permettere ad un computer di risolvere un problema.

Gli articoli che andranno a comporre questa categoria prenderanno spunto dal testo Il pensiero computazionale – Dagli algoritmi al coding di Paolo Ferragina e Fabrizio Luccio.

Cercheremo quindi di risolvere alcuni problemi proposti nel libro per sviluppare le nostre capacità creative nella elaborazione degli algoritmi che poi andremo a tradurre in codice FreeBASIC.

Inoltre proveremo anche a risolvere i rompicapo proposti su Advent of Code. Le soluzioni potrete trovarle su GitHub, sia sullo spazio di JJFlash che sul mio.

Per testare il codice offline direttamente sulla propria macchina si rimanda all’articolo  FreeBASIC – esecuzione.

Per chi invece preferisce lavorare online, lo stesso codice verrà comunque messo a disposizione su JDoodle.

FreeBASIC – tipi di files

Vi avverto: questo sarà un articolo abbastanza noioso, ma, allo stesso tempo, anche indispensabile per affrontare con più consapevolezza la programmazione in FreeBASIC.

Cominciamo.

Dovete sapere che in FreeBASIC ci sono tre tipologie di files. Due delle quali abbastanza scontate, ma la terza… che dire… è un po’ strana.

I. File sorgente (o modulo)

Questi files contengono il nostro codice sorgente e hanno estensione .bas. Un semplice programma può essere scritto interamente anche in un solo file, ma se il programma che stiamo sviluppando è di una certa complessità, allora è preferibile organizzarlo su più files sorgente.

II. File eseguibile

Il processo di compilazione crea un file eseguibile contenente sia il codice oggetto ricavato a partire da uno o più files di codice sorgente, che eventuali collegamenti a una o più librerie. Negli ambienti Windows questi files hanno estensione .exe.

III. File di intestazione

Eccoci arrivati al terzo tipo di file, quello strano.

Abbiamo detto che quando ci troviamo a dover sviluppare un programma complesso è bene organizzarlo in più files di codice sorgente. Ebbene, in questi casi, è spesso conveniente anche scrivere un particolare tipo di file sorgente che viene appunto chiamato file di intestazione e che ha come estensione .bi. Questo particolare file contiene generalmente soltanto alcuni specifici tipi di informazioni, quali, per esempio:

  • dichiarazioni di variabili o costanti
  • definizioni di funzioni

La presenza di questo tipo di file aiuta i programmatori ad avere una visione complessiva delle variabili, delle costanti, delle funzioni, ecc., che possono essere utilizzate senza dover prendere visione ogni volta di tutti i files sorgente.

Incastrare tutti i pezzi come in un puzzle

Per utilizzare più files sorgenti o più files di intestazione occorre includerli nel file sorgente che si sta scrivendo attraverso la direttiva #include che informa il compilatore FreeBASIC sul percorso e sul nome della risorsa da includere durante il processo di compilazione.

Nota: un file di intestazione può a sua volta includere altri files di intestazione.

Avendo a che fare con un grande progetto contenente molti files sorgente (magari non tutti scritti da noi), e magari anche più files di intestazione, potrebbe capitare il caso che più files contengano una direttiva di inclusione per la stessa risorsa. Onde evitare un lavoro inutile al compilatore è bene utilizzare la direttiva #include in questa sua variante:

#include once "percorso e nome della risorsa"

Riguardo alla scrittura del percorso, ovvero della sequenza delle cartelle siano ad arrivare a quella che contiene la nostra risorsa, è bello sapere che:

Il compilatore FreeBASIC converte in automatico i simboli di separazione delle cartelle (la barra / negli ambienti Linux, la barra rovesciata \ negli ambienti Windows) in base al sistema operativo dove viene utilizzato.

Evviva! Ce l’abbiamo fatta.

La prossima settimana daremo uno sguardo nel magico mondo delle librerie. 🙂