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

155
25 декабря 2019, 16:50

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

Answer 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)))
Answer 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;
Answer 3

Надо написать работающий вариант или описание сойдет?

Если сойдет:

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

Answer 4

Задача тупо переборная. Вот мой вариант реализации. Основной алгоритм:

    public static List<ICountable> GetAll(List<ICountable> array)
    {
        if (array.Count <= 1) return array;
        var result = new List<ICountable>();
        for (int mask = 1; mask < (1 << array.Count) - 1; mask++)
        {
            var xParam = new List<ICountable>();
            var yParam = new List<ICountable>();
            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;
    }
Answer 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)
Answer 6

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

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

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

Не то, чтобы я был слоупоком или занудой, но из текущего условия следует такое решение:

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

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

    var numbers = [1,3,4,6];
    var symbol = ["+","-","*","/"];
    var MyArray = new Array(0);
    var s = "";
    for (var i=0; i<numbers.length; i++) {
        s=s+numbers[i];
        for (var i2=0; i2<symbol.length; i2++) {
            s=s+symbol[i2];
            for (var i3=0; i3<numbers.length; i3++) {
                if (s.indexOf(numbers[i3]+'', 0) != -1) continue;
                s=s+numbers[i3];
                for (var i4=0; i4<symbol.length; i4++) {
                    s=s+symbol[i4];
                    for (var i5=0; i5<numbers.length; i5++) {
                        if (s.indexOf(numbers[i5]+'', 0) != -1) continue;
                        s=s+numbers[i5];
                        for (var i6=0; i6<symbol.length; i6++) {
                            s=s+symbol[i6];
                            for (var i7=0; i7<numbers.length; i7++) {
                                if (s.indexOf(numbers[i7]+'', 0) != -1) continue;
                                s=s+numbers[i7];
                                MyArray.push(s);
                                s = s.slice(0,6);
                            }
                            s = s.slice(0,5);
                        }
                        s = s.slice(0,4);
                    }
                    s = s.slice(0,3);
                }
                s = s.slice(0,2);
            }
            s = s.slice(0,1);
        }
        s = "";
    }
    var skobkyDvoynue = [
        [0, 3],
        [2, 5],
        [4, 7]
    ];
    var skobkyTroynie = [
        [0, 5],
        [2, 7]
    ];
    var skobkyDvoynue2_1 = [
        [1, 4],
        [3, 6],
        [5, 8]
    ];
    for (var i8=0; i8<MyArray.length; i8++) {
        if (eval(MyArray[i8]) == 24)
            document.write(MyArray[i8]+'='+eval(MyArray[i8])+"<br \>");
        for (var i10=0; i10<skobkyDvoynue.length; i10++) {
            var arr = MyArray[i8].split('');
            arr.splice(skobkyDvoynue[i10][0], 0, '(');
            arr.splice(skobkyDvoynue[i10][1]+1, 0, ')');
            if (eval(arr.join('')) == 24) document.write(arr.join('')+'='+eval(arr.join(''))+"<br \>");
        }
        for (var i11=0; i11<skobkyTroynie.length; i11++) {
            var arr2 = MyArray[i8].split('');
            arr2.splice(skobkyTroynie[i11][0], 0, '(');
            arr2.splice(skobkyTroynie[i11][1]+1, 0, ')');
            if (eval(arr2.join('')) == 24) document.write(arr2.join('')+'='+eval(arr2.join(''))+"<br \>");
            for (var i12=0; i12<skobkyDvoynue2_1.length; i12++) {
                var arr3 = (arr2.join('')).split('');
                arr3.splice(skobkyDvoynue2_1[i12][0], 0, '(');
                arr3.splice(skobkyDvoynue2_1[i12][1]+1, 0, ')');
                try {
                    if (eval(arr3.join('')) == 24) document.write(arr3.join('')+'='+eval(arr3.join(''))+"<br \>");
                } catch (err) {}
            }
        }
    }
READ ALSO
SharedPreferences настройки приложения

SharedPreferences настройки приложения

Как организовать в настройках приложения функцию скрыть/показать textviewПытался с помощью SharedPreferences, но так и понял

144
Почему приложение вылетает [закрыт]

Почему приложение вылетает [закрыт]

Хотите улучшить этот вопрос? Update the question so it's on-topic for Stack Overflow на русском

151
Оптимизировать код методов Java

Оптимизировать код методов Java

Есть такая задача: найти максимальную последовательность единиц в матрицеПоследовательность может быть как горизонтальной так и вертикальной

118
Для чего сравнивать this и любой Object o?

Для чего сравнивать this и любой Object o?

Для чего сравнивать this, и любой Object o? В каких случая они могут оказаться равными?

121