Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Risoluzione algoritmo OII
Forum - Algoritmi - Risoluzione algoritmo OII

Avatar
Saik (Normal User)
Pro


Messaggi: 117
Iscritto: 07/08/2011

Segnala al moderatore
Postato alle 15:44
Mercoledì, 05/09/2012
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?  :d :d

PM Quote
Avatar
XBarboX (Member)
Guru


Messaggi: 945
Iscritto: 31/12/2008

Segnala al moderatore
Postato alle 16:44
Mercoledì, 05/09/2012
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.

Spero di esserei stato utile :k:

PM Quote
Avatar
Saik (Normal User)
Pro


Messaggi: 117
Iscritto: 07/08/2011

Segnala al moderatore
Postato alle 18:55
Mercoledì, 05/09/2012
Si grazie mille  :asd: :asd:

PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 449
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 10:25
Giovedì, 06/09/2012
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.

PM Quote
Avatar
gigisoft (Member)
Guru


Messaggi: 696
Iscritto: 11/10/2008

Segnala al moderatore
Postato alle 17:08
Giovedì, 06/09/2012
Testo quotato

Postato originariamente da lumo:

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 :rofl: :pat:

Ciao. :k:

Luigi

Ultima modifica effettuata da gigisoft il 06/09/2012 alle 17:14
PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 449
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 21:05
Giovedì, 06/09/2012
Testo quotato

Postato originariamente da gigisoft:

Testo quotato

Postato originariamente da lumo:

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 :rofl: :pat:

Ciao. :k:

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.

PM Quote