Dato qualcosa di simile:
1 5 3 4 = 18
Ho bisogno di determinare (usando un algoritmo) se c'è una combinazione di operatori e parentesi che mi porta a 18. Solo "+" e "*" e "(" e ")" sono consentiti.
Esempio:
1 + 5 + (3 * 4) = 18
Oltre alla forza bruta, c'è qualche particolare algoritmo che è in grado di calcolare tutta la combo possibile in un tempo ragionevole? L'RPN può aiutare a codificare le possibili soluzioni, ma le stesse sono molte (4 ^ n?).
La forza bruta è in realtà piuttosto veloce se si evitano calcoli inutili.
Nel peggiore dei casi hai 2 ^ (N-1) operatori e N! (N-1)! modi di scegliere le coppie di numeri per le operazioni N-1. Ad esempio, per N = 4, questo offre 1.152 possibilità.
Ma è possibile ridurlo in modo sostanziale: se si guardano i 6 + 2 e 6 * 2, non c'è bisogno di guardare 2 + 6 e 2 * 6: basta fare prima il numero più grande. Questo elimina un fattore 2 ^ (N-1) portando il numero di possibilità a N! (N-1) !, quindi a 144 per N = 4.
Ci sono ulteriori possibili risparmi in quanto (20 + 6) +2 è uguale a 20+ (6 + 2), ma sospetto che non valga la pena di ottimizzare questo valore fino a quando N diventa grande. Un altro è che la moltiplicazione per 1 non aiuta molto: questo tipo di cose potrebbe non essere un salvataggio con N = 4, ma potrebbe essere se si guardasse anche alla divisione (specialmente se il numero più piccolo non è un fattore o un divisore di il numero maggiore), in quanto è possibile rimuovere un sacco di possibilità. Il suggerimento di rzzzwilson di fermarsi quando il bersaglio viene superato funziona in modo simile, ma funziona solo se tutte le operazioni sono non-decrescenti (cioè addizione e moltiplicazione ma non sottrazione o divisione)
Come esempio di qualcosa di simile, prova la mia vecchia applet Java qui, con sei numeri e quattro operatori. Puoi mettere i tuoi numeri e il tuo obiettivo nella casella. Non è programmato graziosamente, ma è ancora abbastanza veloce.
Problema interessante.
Non ho scritto alcun codice, ma ecco i miei pensieri. Non sono stato in grado di pensa ad un approccio al di là della forza bruta, con un po 'di "potatura".
Utilizzare una rappresentazione RPN è la strada da percorrere, in quanto semplifica la gestione di parentesi (come tali, vanno via). Usando il tuo esempio, l'RPN è 1 5. 3. 4. dove ogni '.' è un luogo in cui potrebbe essere un operatore, ad eccezione di al massimo '.' dove sappiamo che ci deve essere uno o più operatori, perché è RPN. Ogni altro '.' ha zero o più operatori. Per i valori N devi avere operatori N-1, ovviamente.
Ora il problema si divide in queste parti: 1. Genera tutte le combinazioni di operatori N-1 (2 ^ N) 2. Per ogni combinazione di operatori, generare tutti i "riempimenti" dell'operatore punti '.', cioè raggruppare l'elenco degli operatori per 1s, 2s, ..., N-1s, mantenendo l'ordine dell'operatore (il mio combinatorics-fu è debole, non riesco a capirlo) 3. Per ciascuna combinazione di combinazioni, valuta l'espressione
L'eliminazione avviene nell'ultimo passaggio. Come valuti, se l'espressione il valore va oltre il risultato desiderato, si ferma con un errore, in quanto non ci sono operatori che potrebbero ridurre il valore dell'espressione.
Questo problema è NP completo e quindi non ci si può aspettare che sia risolvibile in qualcosa di meno di O (n!). Tuttavia, come in tutti i problemi NP completi, puoi ovviamente approssimare un algoritmo che ti avvicina a 18 o, in alternativa, generare un elenco di numeri simili con operatori che risulterebbero 18.
Leggi altre domande sui tag algorithms math