Как перебрать все комбинации из чисел и арифметических операций?

#cpp #алгоритм

У меня есть задача, и хотелось бы узнать как её можно реализовать с помощью C++:


  Есть цифры 1,3,4,6. Нужно написать программу реализующую последовательный перебор
этих цифр и знаков четырех элементарных арифметических операций (сложение, вычитание,
умножение и деление), чтобы получилось выражение с результатом 24.


Нужно именно как-то перебором это реализовать что бы подставлялись цифры
и операции над ними последовательно а когда будет 24 перебор остановился и выдал
результат.

У меня вообще нет идей как это можно реализовать подскажите пожалуйста или если можно
напишите код или хотя бы кусок кода.
    

Ответы

Ответ 1

Код писать не буду, опишу алгоритм.  

Перво-наперво, определяетесь, что будете делать с потерей точности при делении(в
числах с плавающей запятой). Предлагаю 2 варианта:  


Реализовать класс рациональных чисел, в котором определить числитель/знаменатель,
арифметические операции с автосокращением и т.п.
Сравнение с результатом проводить с учётом погрешности (Ввести так называемый epsilon)


Во втором случае, теоретически могут появиться неверные решения  

Далее, ознакомливаетесь, что такое обратная польская нотация...

1 + 2 * 3 === 1 2 3 * +


В вашем случае, оно сводится к выражению из четырёх чисел и трёх арифм.операций в
формах:  

a0 a1 a2 a3 op0 op1 op2  # линейное вычисление  
a0 a1 op1 a2 op2 a3 op3  # выражение вида a-b-c-d  
a0 a1 op1 a2 a3 op2 op3  # выражение вида (a+b)/(c-d)  


В более сложном задании придётся перебрать все формы. Возможно проще перебирать вообще
все, включая некорректные, но можно и формализовать.

Осуществляете перебор всех перестановок чисел 4!=24 и всех возможных операций. Операций
всего 4(+-*/), выполняются 3 раза. Итого перебор операций 4^3=64, а всего полный перебор
(двух форм) займёт 2*24*64 = около 3000 итераций.

На каждой итерации вычисляете выражение и сравниваете его с нужным результатом.  

На базе найденного выражения из ОПН форматируете вывод решения.  



ЗЫ: На этапе вычислений, не забудьте про edge cases. Деление на нуль нужно обработать
(перейти к следующей итерации).



Демонстрация алгоритма на javascript:  



class OPN {
  constructor() { this.stack = []; }
  __computeFn(a, b, op) {
    switch (op) {
      case '+': return a + b;
      case '-': return a - b;
      case '*': return a * b;
      case '/':
        if (b === 0) throw new Error('Division by zero');
        return a / b;
      default: throw new Error(`Unknown operator ${op}`);
    }
  }
  __renderFn(a, b, op) {
    return `(${a} ${op} ${b})`;
  }
  __process(tokens, fn) {
    for (let token of tokens) {
      if (typeof token === 'number') {
        this.stack.push(token);
      } else { // assume operation
        if (this.stack.length < 2) throw new Error('Incorrect expression');
        let b = this.stack.pop();
        let a = this.stack.pop();
        this.stack.push(fn(a, b, token));
      }
    }
    if (this.stack.length != 1) throw new Error('Incorrect expression');
    return this.stack.pop();
  }
  calc(tokens) {
    return this.__process(tokens, this.__computeFn);
  }
  render(tokens) {
    return this.__process(tokens, this.__renderFn);
  }
}


class Permutator {
  constructor() { this.current = []; this.used = [];}
  getAllFor(input) {
    for (let i = 0; i < input.length; i++) {
      let item = input.splice(i, 1)[0]; // take item

      this.used.push(item); // use item
      if (input.length == 0) this.current.push(this.used.slice());
      this.getAllFor(input);
      this.used.pop(); // restore state

      input.splice(i, 0, item); // restore item
    }
    return this.current;
  }
}

let calc = new OPN;
let permutator = new Permutator;

let numbers = [1, 3, 4, 6];
let ops = ['+', '-', '*', '/'];
const EPS = 1e-6;
function find () {
  let solutions = [];
  for (let perm of permutator.getAllFor(numbers)) {
    for (let op1 of ops) {
      for (let op2 of ops) {
        for (let op3 of ops) {
          let forms = [
            [perm[0], perm[1], perm[2], perm[3], op1, op2, op3],
            [perm[0], perm[1], op1, perm[2], perm[3], op2, op3],
            [perm[0], perm[1], op1, perm[2], op2, perm[3], op3],
          ];
          for (let form of forms) {
            try {
              let res = calc.calc(form);
              if (Math.abs(24 - res) < EPS) solutions.push(form);
            } catch(e) {}
          }
        }
      }
    }
  }
  return solutions;
}

let solutions = find();
solutions.forEach(solution => console.log('Solution: ', calc.render(solution)));