Как расставить операторы чтобы получилось максимальное число?
Идея усложнить задачу. Первоначальное условие: вводятся три числа: a, b, c. Нужно расставить операторы (+ / * и скобки - ** не используем) так, чтобы получилось максимальное число. То есть, банально выбрать максимум из нескольких комбинаций: a + b * c; a * (b + c); a * b * c; (a + b) * c; a + b + c а также a * b + c.
Что если сделать условие этой зада более универсальным? То есть, для разного количества введенных чисел. А также, автоматически перебирать все комбинации операторов. Ведь даже для трех чисел пришлось несколько раз перепроверять все ли возможные варианты задействованы. Решение вышло также, мягко говоря, не очень изящным. Для четырех-пяти это будет еще более-менее посильно сделать вручную, но дальше начинается темный лес. Возможно ли решить задачу в новой формулировке? Как это сделать:
- максимально кратко
- максимально понятно (даже для новичка, забегающего немного вперед в учебе).
Ответы (1 шт):
Как расставить знаки операций и скобки всеми возможными способами? Если число одно, то оно и результат. Если чисел больше, то разбиваем список чисел всеми возможными способами на две части. Для обеих частей рекурсивно находим значения, пробуем их сложить и умножить. Это всё.
Ниже код, в котором главное - простота. Он сносно работает для десяти чисел. Если нужно больше, поиск можно оптимизировать, и довольно существенно.
def values(args, i1, i2):
if i1 + 1 == i2:
yield args[i1]
for i in range(i1 + 1, i2):
for lhs in values(args, i1, i):
for rhs in values(args, i, i2):
yield lhs + rhs
yield lhs * rhs
def main():
args = [float(w) for w in input().split()]
print(max(values(args, 0, len(args))))
main()
$ echo 1 2 3 4 5 6 7 8 9 10 | python max-expr.py 5443200.0 $ echo -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 | python max-expr.py 3628800.0