Страницы

Поиск по вопросам

четверг, 18 октября 2018 г.

Получить число 24

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


Ответ

Что-то я ничего, кроме полного перебора не придумал. Вкратце, для всевозможных перестановок данных чисел пытаемся всеми возможными способами расставить скобки и действия между ними. Вот рабочий вариант написаный на 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)))

Комментариев нет:

Отправить комментарий