Учитывая 4 числа генерируют все комбинации, используя основные операторы (+, -, *, / и круглые скобки), так что результат равен 24 - PullRequest
Новая
       15

Учитывая 4 числа генерируют все комбинации, используя основные операторы (+, -, *, / и круглые скобки), так что результат равен 24

0 голосов
/ 25 января 2019

Учитывая список из 4 целых чисел, я должен выяснить все их комбинации, используя базовые математические операторы и круглые скобки, чтобы он получал значение 24. Например, если 4 числа равны 1,2,3,4, выражения 1* 2 * 3 * 4 или (4 + 2) * (3 + 1) можно оценить до 24. Я нашел алгоритм здесь , но я не совсем понимаю его для реализации программы.

Простая рекурсия может дать мне комбинации, которые не включают скобки.Я хочу понять, как решить эту проблему, если использовать скобки.

Ответы [ 2 ]

0 голосов
/ 25 января 2019

Чтобы решить проблему с круглыми скобками, вы можете подумать о своей проблеме следующим образом:

"Создать все Дерево двоичных выражений s, содержащее операторы + - * / и заданные числа 1,2,3,4. Оцененное выражение должно быть 24."

Скобка является результатом неявного порядка оценки, представленного в дереве.

Так что просто создайте все возможные деревья, оцените их, чтобы проверить, равен ли результат 24, и затем распечатайте действительные, включая скобки (либо поместив скобки вокруг каждой операции, либо только если они нужны для порядка оценки)

0 голосов
/ 25 января 2019

Задача проста, если у нас нет скобок: все, что нам нужно сделать, - это перечислить все операции.Предполагая, что у нас есть +, -, *, /: 

   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); 
       }   
   }
...