Provate anche voi a cambiare numero di telefono e trovare un modo simpatico per dirlo ai vostri amici, amanti e parenti. Voi vi ritrovereste a bere da soli il peggior rhum del migliore bar di Bolungarvík. Per Gianni è diverso: Gianni ha la Susi.
Susi: Gianni, so che hai un nuovo numero di telefono.
Gianni: Sì. È un numero di nove cifre, tutte diverse. Manca solo lo 0.
Susi: Come posso telefonarti?
Gianni: Semplice. Moltiplicando il numero formato dalle prime due cifre con quello formato dalle successive tre, si ottiene il numero formato dalle ultime quattro. E il numero formato dalle prime due cifre è un quarto di quello formato dalle successive due e un ottavo di quello formato dalle ultime due.
Susi: Ti chiamo stasera.
Alle solite
Siamo alle solite: estraiamo dal testo delle condizioni verificate le quali abbiamo trovato la nostra soluzione e iniziamo a provare tutti i numeri. Il numero più piccolo possibile è 123456789 e quello più grande è 987654321, quindi possiamo limitarci a questo intervallo e vedere se le condizioni sono verificate per 123456789, poi per 123456790, poi per 1234567891, ecc…
Oppure possiamo partire dai “pezzi” più piccoli (le prime due cifre, le tre successive…) e costruire il nostro numero a partire da questi1: potrebbe persino essere più efficiente così! Ma, lo ribadisco per l'ennesimo volta (non si sa mai), lo scopo di questa serie non è quello di sviluppare algoritmi eleganti, efficienti, interessanti, ecc.
Per l'ennesima volta traduciamo i vincoli del problema in modo che possano essere verificati in qualche linguaggio… Che questa volta è Ada. Da notare che ho fatto un certo uso disinvolto di alcune caratteristiche di questo (bellissimo2) linguaggio: si poteva scrivere in modo più ovvio3, per così dire, ma mi sarei annoiato di più 😄
with Ada.Text_IO;
procedure Susi958 is
use Ada.Text_IO;
subtype Two_Digits is Integer range 12 .. 98;
subtype Three_Digits is Integer range 123 .. 987;
subtype Four_Digits is Integer range 1234 .. 9876;
-- 12 345 6789
-- \ \ \ Last_Four
-- \ \ Second_Three
-- \ First_Two
First_Two : Two_Digits;
Second_Three : Three_Digits;
function Last_Four return Four_Digits is (First_Two * Second_Three);
-- 12 34 567 89
-- \ \ \ Last2
-- \ \ Second2
-- \ First_Two
function Second2 return Two_Digits is (Second_Three / 10);
function Last2 return Two_Digits is (Last_Four mod 100);
function Condition2_Holds return Boolean is
begin
return First_Two * 4 = Second2
and then First_Two * 8 = Last2;
exception
when Constraint_Error =>
return False;
end;
function All_Different_Digits return Boolean is
subtype Digits_No_Zero is Integer range 1 .. 9;
Gianni_Number : Integer :=
First_Two * 1_000_0000
+ Second_Three * 1_0000
+ Last_Four * 1;
T : Integer;
D, D1 : Digits_No_Zero;
begin
while Gianni_Number > 0 loop
D := Gianni_Number mod 10;
T := Gianni_Number / 10;
while T > 0 loop
D1 := T mod 10;
if D = D1 then
return False;
end if;
T := T / 10;
end loop;
Gianni_Number := Gianni_Number / 10;
end loop;
return True;
exception
when Constraint_Error =>
return False;
end;
begin
Outer_Loop:
for I2 in Two_Digits'Range loop
for I3 in Three_Digits'Range loop
First_Two := I2;
Second_Three := I3;
if Condition2_Holds
and then All_Different_Digits
then
Put_Line (Integer'Image (First_Two) &
Integer'Image (Second_Three) &
Integer'Image (Last_Four));
exit Outer_Loop;
end if;
end loop;
end loop Outer_Loop;
end;L'output dell'esecuzione del programma compilato4 è:
12 483 5796Mi sembra plausibile affermare che si tratti della soluzione corretta. Da notare che si ottiene lo stesso numero se si toglie la condizione malamente verificata da All_Different_Digits (che tra l'altro implicitamente verifica pure che lo 0 non compaia mai come cifra, cosa non controllata altrove). Però bisognerebbe dimostrare, non empiricamente, che non è necessaria per trovare la soluzione.
Soluzione manuale
Dimenticavo… forse dovrei aggiungere più spesso anche come si arriva alla soluzione “a mano”.
Indichiamo con A le prime due cifre (cioè un numero maggiore di 9 e minore di 100) e con D le ultime due; sappiamo che D = 8A. Inoltre non ci devono essere ripetizioni delle cifre e tra queste non ci deve essere lo zero; il più piccolo numero di due cifre che rispetta queste condizioni è 12. Che moltiplicato per 8 fa 96. Il successivo sarebbe 13, che moltiplicato per 8 fa un numero di tre cifre. Quindi le prime due cifre devono essere 12 e le ultime due saranno 96. La terza e la quarta dovranno essere 4 e 8 (perché 12×4 = 48); abbiamo quindi:
12 48 xyz 96Sappiamo anche che 12×(480+x) = (1000×y) + (100×z) + 96, e visto che non ci devono essere ripetizioni possiamo scegliere solo tra tre numeri (3, 5, 7) per i valori di x, y e z.
L'ultima cifra del prodotto 2x deve essere 6, quindi x deve essere per forza 3. Non abbiamo bisogno di altro per trovare le rimanenti due cifre: 12×483 = 5796.
Nel codice,
Last_Fourè calcolato a partire daFirst_TwoeSecond_Three, il che assicura che la prima condizione (che il prodotto dei numeri formati dalle prime due cifre e dalle tre cifre successive faccia il numero formato dalle ultime quattro) sia già automaticamente vera.↩Anni fa non l'avrei mai detto; ora invece, con la complicità di non so quale fattore invecchiante, del mio recente interesse per alcune cose e soprattutto del fatto che l'ho guardato più da vicino… lo dico. Certo, niente è perfetto…↩
Una cosa poco ovvia l'uso delle eccezioni, che non sono sempre gestite.
Last_Fourpuò alzare l'eccezioneConstraint_Errore viene usata nel corpo della procedura. Tuttavia, quando viene eseguito in quel punto, già si sono verificate le condizioni che garantiscono che la funzione generi un numero buono. Per questo il bloccoexceptioninCondition2_Holds, che usaLast_Fourindirettamente tramiteLast2, è sufficiente.↩Non provate a compilarlo con un compilatore per Ada 83… Io guardo da Ada 2012 in avanti 😁↩
Nessun commento:
Posta un commento
Sii educato, costruisci con cura le frasi, rifletti prima di pubblicare, evita parolacce e offese dirette, non uscire dal tema, cerca di non omettere la punteggiatura, evita errori ortografici, rileggi quel che hai scritto.