Можно ли получить число N используя только /*-+()?

#алгоритм

Написать алгоритм, который используя числа 1, 3, 4, 6, а также умножение, деление,
сложение, вычитание и скобки, находит все комбинации для получения числа 24. Разрешается
использовать только эти числа и только эти операции. Каждое число должно использоваться
только один раз. Операции и скобки можно использовать любое число раз. Нельзя объединять
числа как цифры, составляя, например, 36 или 614.    

Ответы

Ответ 1

Что-то я ничего, кроме полного перебора не придумал.
Вкратце, для всевозможных перестановок данных чисел пытаемся всеми возможными способами
расставить скобки и действия между ними. Вот рабочий вариант написаный на python:
from fractions import Fraction
from itertools import permutations

OPS = {"+": lambda a, b: a + b,
       "-": lambda a, b: a - b,
       "/": lambda a, b: a / b,
       "*": lambda a, b: a * b}

class Expression:
    def __init__(self, value, op = None):
        self.value = value
        self.op = op
        self.left = None
        self.right = None

    def __str__(self):
        if self.left == None:
            return str(self.value)
        return "(" + str(self.left) + " " + self.op + " " + str(self.right) + ")"

def all_expressions(numbers):
    if len(numbers) == 1:
        yield Expression(numbers[0])
        return
    for i in xrange(1, len(numbers)):
        for left_expr in all_expressions(numbers[:i]):
            for right_expr in all_expressions(numbers[i:]):
                for op in OPS:
                    try: # For 0 division
                        value = OPS[op](left_expr.value, right_expr.value)
                        res = Expression(value, op)
                        res.left = left_expr
                        res.right = right_expr
                        yield res
                    except Exception:
                        pass

numbers = [Fraction(1), Fraction(3), Fraction(4), Fraction(6)]

for p in permutations(numbers):
    for e in all_expressions(p):
       if e.value == 24:
          print e

Результат всего один:
$ python tp.py
(6 / (1 - (3 / 4)))


Ответ 2

Моё решение на Delphi с использованием обратной польской нотации здесь.
Результат: 6/(1-(3/4))=24
Функция Solve:
function TReversePolishNotation.Solve: string;
var
  i,j: integer;
  Token: string;

  arg1,arg2: extended;
  arg1infix,arg2infix: string;

  tmp: extended;
begin
  try
    i:=0;

    repeat
      //идём по польской нотации, пока не натыкаемся на пробел
      j:=i+1;
      repeat
        Inc(i)
      until self.FNotation[i]=' ';

      //копируем в Token часть до пробела (оператор или аргумент)
      Token:=copy(self.FNotation,j,i-j);

      //если это не оператор - кладём в стек
      if not CharInSet(Token[1],['+','-','*','/']) then begin
        FSolveStack.Push(Token);
        FInfixStack.Push(Token);
      end
      //иначе - оператор
      else begin
        //достаём аргументы в обратном порядке
        arg2:=strtofloat(self.FSolveStack.Pop);
        arg1:=strtofloat(self.FSolveStack.Pop);

        //применяем оператор и кладём результат в стек
        case Token[1] of
          '+': self.FSolveStack.Push(floattostr(arg1+arg2));
          '-': self.FSolveStack.Push(floattostr(arg1-arg2));
          '*': self.FSolveStack.Push(floattostr(arg1*arg2));
          '/': self.FSolveStack.Push(floattostr(arg1/arg2));
        end;

        //делаем тоже самое, но без вычисления, для сборки в инфиксную нотацию
        arg2infix:=FInfixStack.Pop;
        arg1infix:=FInfixStack.Pop;

        if not TryStrToFloat(arg2infix,tmp) then
          arg2infix:='('+arg2infix+')';

        if not TryStrToFloat(arg1infix,tmp) then
          arg1infix:='('+arg1infix+')';

        FInfixStack.Push(
          arg1infix+Token+arg2infix
        );
      end;
    //цикл выполняется до тех пор пока не пройдём по всей польской нотации
    until (i>=Length(self.FNotation));

    //ответ лежит в стеке
    Result:=self.FSolveStack.Pop;

    self.InfixNotation:=self.FInfixStack.Pop;
  except
    Result:='Error';
  end;
end;


Ответ 3

Надо написать работающий вариант или описание сойдет?
Если сойдет:
Создаем массив массивов всех вариантов расположения чисел.
Сразу уходим в обратную польскую, чтобы о скобках не думать.
Если после операций с тремя числами уже получилось число больше 24, в четвертой не
используем + и *(экономия времени)
Полученные верные варианты преобразуем в прямую запись..


Ответ 4

Задача тупо переборная. Вот мой вариант реализации. Основной алгоритм:
    public static List GetAll(List array)
    {
        if (array.Count <= 1) return array;
        var result = new List();
        for (int mask = 1; mask < (1 << array.Count) - 1; mask++)
        {
            var xParam = new List();
            var yParam = new List();
            for (int i = 0; i < array.Count; i++) ((mask >> i & 1) == 0 ? xParam
: yParam).Add(array[i]);
            var xResult = GetAll(xParam);
            var yResult = GetAll(yParam);
            foreach (OperatorType operatorType in OperatorType.All) foreach (ICountable
xx in xResult) foreach (ICountable yy in yResult) result.Add(new Expression(xx, yy,
operatorType));
        }
        return result;
    }


Ответ 5

Вариант на питоне с расчетом в обратной польской нотации. Упор в коде на хорошую
читаемость и легкую расширяемость.
# coding=utf-8
from __future__ import print_function
from itertools import permutations, product

class BinaryOperator(object):
    """
    Бинарный оператор
    """

    def __init__(self, text, func, priority=1):
        self.text = text
        self.func = func
        self.priority = priority

    def __call__(self, left, right):
        return self.func(left, right)

    def __str__(self):
        return self.text

class SimpleMachine(object):
    """
    Простейший автомат
    """

    def __init__(self):
        self.reset()

    def reset(self):
        self._stack = []
        self._infix = []

    def infix_add(self, op):
        if isinstance(op, BinaryOperator):
            arg1, arg2 = self._infix.pop(), self._infix.pop()
            to_str = lambda x: '(%s)' % x[0] if x[1] < op.priority else str(x[0])
            self._infix.append(('%s %s %s' % (to_str(arg1), op, to_str(arg2)), op.priority))
        else:
            self._infix.append((op, 10))

    def execute(self, expression):
        try:
            self.reset()
            for op in expression:
                if isinstance(op, BinaryOperator):
                    self._stack.append(op(self._stack.pop(), self._stack.pop()))
                else:
                    self._stack.append(float(op))
                self.infix_add(op)
        except ZeroDivisionError:
            self._stack = []

        return self._stack[-1] if len(self._stack) else None

    @property
    def infix(self):
        return ' '.join([name for name, priority in self._infix])

def expression_generator(all_operands, all_operators):
    """
    Генератор всевозможных выражений
    """

    for lists_operands in permutations(all_operands):
        for lists_operators in product(all_operators, repeat=len(all_operands) - 1):
            result = []
            def gen(stack, operands, operators, expect = 0):
                if not operands and not operators: return result.append(stack)
                if len(operands):
                    gen(stack + [operands[-1]], operands[:-1], operators, expect + 1)
                if expect > 1:
                    gen(stack + [operators[-1]], operands, operators[:-1], expect - 1)

            gen([], lists_operands, lists_operators)
            for expr in result:
                yield expr

OPERANDS = [1, 3, 4, 6]
OPERATORS = (
    BinaryOperator('+', float.__add__, 1),
    BinaryOperator('-', float.__sub__, 1),
    BinaryOperator('*', float.__mul__, 2),
    BinaryOperator('/', float.__div__, 2),
)

if __name__ == '__main__':

    machine = SimpleMachine()
    for expression in expression_generator(OPERANDS, OPERATORS):
        if machine.execute(expression) == 24:
            print('24 =', machine.infix)


Ответ 6

Условие задачи не совсем корректное. Возможно, стоит его поправить, изменив

"Операции и скобки можно использовать любое число раз"

на "Операции и скобки можно использовать любое значимое число раз".
Не то, чтобы я был слоупоком или занудой, но из текущего условия следует такое решение:

Полным перебором найти все комбинации со значимым числом скобок и знаков операций
(или хотя бы одну)
Записать результаты в файл.
Если файл пуст: goto КОНЕЦ
Из файла взять последний результат (пусть это выражение А), заменить его на -(-(А))
и сделать append в файл.
Повторять п.4 пока на жестком диске не кончится место (ну, или пока не надоест :-D)
КОНЕЦ.


Ответ 7

Код на js за который надо сильно пинать :)

    var numbers = [1,3,4,6];
    var symbol = ["+","-","*","/"];
    var MyArray = new Array(0);
    var s = "";

    for (var i=0; i");
        }

        for (var i11=0; i11");

            for (var i12=0; i12");
                } catch (err) {}
            }
        }
    }