Написать алгоритм, который используя числа 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)))
Комментариев нет:
Отправить комментарий