Data una serie di numeri, come calcolare un valore target

0

Chiacchierare con un amico su un gioco che giocavamo e pensare a come implementarlo nel codice.

Ecco le regole:

Dato un elenco di numeri ad es. {1,2,3,4}
Prova a utilizzare tutti i numeri dall'elenco per eseguire +, -, *, / operazioni per raggiungere un numero di destinazione (ad es. 2).
I numeri possono essere utilizzati solo una volta, gli operatori possono essere utilizzati più di una volta.

Quindi una soluzione sarebbe (1 + 3) * 2/4 = 2

Qualche idea per un algoritmo per ottenere la risposta (s)?

    
posta jojo 18.06.2016 - 07:12
fonte

1 risposta

1

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
    
risposta data 27.06.2016 - 20:51
fonte

Leggi altre domande sui tag