Задача проста, если у нас нет скобок: все, что нам нужно сделать, - это перечислить все операции.Предполагая, что у нас есть +
, -
, *
, /
:
1 + 2 + 3 + 4
1 + 2 + 3 - 4
1 + 2 + 3 * 4
1 + 2 + 3 / 4
1 + 2 - 3 + 4
1 + 2 - 3 - 4
1 + 2 - 3 * 4
1 + 2 - 3 / 4
1 + 2 * 3 + 4
...
1 / 2 / 3 + 4
1 / 2 / 3 - 4
1 / 2 / 3 * 4
1 / 2 / 3 / 4
У нас всего 4 ** 3 = 64
формул.Давайте добавим круглые скобки .Мы можем использовать их 3! == 6
способами (пусть ^
будет операцией любой из +, -, *
):
(((1 ^ 2) ^ 3) ^ 4) // order of operations: 1, 2, 3
((1 ^ 2) ^ (3 ^ 4)) // -/- 1, 3, 2
((1 ^ (2 ^ 3)) ^ 4) // -/- 2, 1, 3
(1 ^ ((2 ^ 3) ^ 4)) // -/- 2, 3, 1
((1 ^ 2) ^ (3 ^ 4)) // -/- 3, 1, 2
(1 ^ (2 ^ (3 ^ 4))) // -/- 3, 2, 1
Теперь у нас есть 64 * 6 == 384
формул для проверки.
Наконецмы можем перетасовать числа (4! == 24
способами):
1 ^ 2 ^ 3 ^ 4
1 ^ 2 ^ 4 ^ 3
1 ^ 3 ^ 2 ^ 4
1 ^ 3 ^ 4 ^ 2
...
4 ^ 3 ^ 2 ^ 1
И у нас есть 24 * 384 == 9216
формул для выполнения, которые можно выполнить с помощью грубой силы (с eval
или его эквивалент)
Псевдокод:
# All possible arguments order
for (permutationIndex in 0..23) {
int[] numbers = Permutation({1, 2, 3, 4}, permutationIndex);
# All possible operations
foreach (op1 in {"+", "-", "*", "/"})
foreach (op2 in {"+", "-", "*", "/"})
foreach (op3 in {"+", "-", "*", "/"}) {
# All possible parenthesis
formulae[] = {
"(((numbers[0] op1 numbers[1]) op2 numbers[2]) op3 numbers[3])",
"((numbers[0] op1 numbers[1]) op2 (numbers[2] op3 numbers[3]))",
"((numbers[0] op1 (numbers[1] op2 numbers[2])) op3 numbers[3])",
"(numbers[0] op1 ((numbers[1] op2 numbers[2]) op3 numbers[3]))",
"((numbers[0] op1 numbers[1]) op2 (numbers[2] op3 numbers[3]))",
"(numbers[0] op1 (numbers[1] op2 (numbers[2] op3 numbers[3])))",
}
foreach (formula in formulae)
if (eval(formula) == 24)
Write(formula);
}
}