Il modo più semplice è la forza bruta. Generare tutti i modi per ordinare i numeri e applicare gli operatori, quindi verificare se corrisponde al valore di destinazione. Questo scala molto male, ma può essere migliorato con l'euristica.
Usando il tuo esempio, possiamo notare che abbiamo solo bisogno di provare la divisione quando uscirà da un intero (assumendo che tu non intenda /
come troncare la divisione di interi). Quindi, quando iniziamo con 3, non abbiamo bisogno di provare a dividere per qualcosa tranne 1.
Anche la Memoizzazione potrebbe essere d'aiuto, ma a meno che tu non stia pianificando su un ampio elenco di obiettivi o operazioni costose, probabilmente non ne varrebbe la pena. Se vai con la memoizzazione, ti consiglio di pensare attentamente a ciò che ti aspetti di ripetere. Se lo stesso obiettivo può comparire più volte, la memoizzazione di target => (numbers, operators)
avrebbe senso. Se i numeri possono essere ripetuti, puoi provare a memoizzare ogni operatore, (operator, operands) => value
. In ogni caso, vorrei definire le opzioni qui prima di prendere una decisione.
Inoltre, se la tua lingua ha un modo per fare riferimento alle funzioni (chiusure, puntatori di funzioni, funtori), sarà probabilmente più chiaro utilizzarle per gli operatori. Sicuramente evitare l'analisi delle stringhe o le espressioni eval
ing.
Alcuni pseudocodici ruby-ish:
numbers = [1, 2, 3, 4]
operators = [+, -, *, /]
target = 2
numbers.permutation(4).each do |p|
operators.permutation(3).each do |o|
x = o[0](p[0], p[1])
x = o[1](x, p[2])
x = o[2](x, p[3])
if (x == target)
return p, o
end
end
end