Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Esercitandomi per le olimpiadi di informatica di questo anno mi sono imbattuto nel seguente problema
Si consideri la seguente moltiplicazione:
A * * * ×
B * =
C * * * *
dove ciascuna delle cifre dei tre numeri A, B e C (indicate dal simbolo può valere solo 3, oppure 5,
oppure 7.
Quali sono i tre numeri A, B e C?
Purtroppo non ci sono soluzioni e penso che il brute force non sia la soluzione ideale
Qualcuno può aiutarmi?
Se ricordo bene il calcolo combinatorio, questa dovrebbe essere una Disposizione con ripetizione, quindi:
D'(3,8) = 6561
Di conseguenza si può facilmente capire che non richiede un elevato numero di calcoli usando il metodo brute force. L'esecuzione dovrebbe essere praticamente istantanea.
Questo è uno di quei casi in cui non conviene neanche provare a cercare un algoritmo più efficiente poicé è già molto veloce così.
Nel caso tu voglia aumentare le cifre che si possono usare o la lunghezza dei fattori bisogna usare altri metodi.
Per esempio per velocizzarlo basterebbe evitare calcoli inutili bloccando ad esempio l'incremento dei fattori se i risultati sono più lunghi della lunghezza del risultato cercato.
Ma in questo caso direi che non hai da preoccuparti.
Secondo me conviene generare solo A e B e controllare manualmente se C sia composto dai numeri richiesti.
Notando che O l'ultima cifra di A o B devono essere 5 per ottenere qualcosa di valido, i numeri da generare in totale diventano 2*3*3*3 = 54.
Secondo me conviene generare solo A e B e controllare manualmente se C sia composto dai numeri richiesti.
Notando che O l'ultima cifra di A o B devono essere 5 per ottenere qualcosa di valido, i numeri da generare in totale diventano 2*3*3*3 = 54.
in realta', se ci pensi bene, per evitare che nella penultima cifra di C si abbia 6 o 8, l'ultima cifra di A e B devono essere entrambe pari a 5, e quindi scendiamo a 3*3 = 9 possibilita'
poi per lo stesso motivo, per evitare che nella seconda cifra di C si abbia 6 o 8, anche la penultima cifra di A deve essere pari a 5, e scendiamo a sole 3 possibilita'
alla fine, si vede che la prima cifra di A non puo' essere altro che 7; per cui si ha:
A 7 5 5 ×
B 5 =
C 3 7 7 5
il tutto senza scomodare disposizioni e bruteforce
Ciao.
Luigi
Ultima modifica effettuata da gigisoft il 06/09/2012 alle 17:14
Secondo me conviene generare solo A e B e controllare manualmente se C sia composto dai numeri richiesti.
Notando che O l'ultima cifra di A o B devono essere 5 per ottenere qualcosa di valido, i numeri da generare in totale diventano 2*3*3*3 = 54.
in realta', se ci pensi bene, per evitare che nella penultima cifra di C si abbia 6 o 8, l'ultima cifra di A e B devono essere entrambe pari a 5, e quindi scendiamo a 3*3 = 9 possibilita'
poi per lo stesso motivo, per evitare che nella seconda cifra di C si abbia 6 o 8, anche la penultima cifra di A deve essere pari a 5, e scendiamo a sole 3 possibilita'
alla fine, si vede che la prima cifra di A non puo' essere altro che 7; per cui si ha:
A 7 5 5 ×
B 5 =
C 3 7 7 5
il tutto senza scomodare disposizioni e bruteforce
Ciao.
Luigi
Già avevo trovato la soluzione a mano ma siccome non avevo voglia di fare il ragionamento successivo ho lasciato l'interrogativo di altre soluzioni lol. Good job.