У меня есть задача, и хотелось бы узнать как её можно реализовать с помощью C++:
Есть цифры 1,3,4,6. Нужно написать программу реализующую последовательный перебор этих цифр и знаков четырех элементарных арифметических операций (сложение, вычитание, умножение и деление), чтобы получилось выражение с результатом 24.
Нужно именно как-то перебором это реализовать что бы подставлялись цифры
и операции над ними последовательно а когда будет 24 перебор остановился и выдал результат.
У меня вообще нет идей как это можно реализовать подскажите пожалуйста или если можно напишите код или хотя бы кусок кода.
Ответ
Код писать не буду, опишу алгоритм.
Перво-наперво, определяетесь, что будете делать с потерей точности при делении(в числах с плавающей запятой). Предлагаю 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)));
Комментариев нет:
Отправить комментарий