Как создать функцию, которая получает число, а возвращает список всех возможных перестановок знаков между цифрами, в результате которых выходит 100?
Создать функцию, которая для заданного числа возвращает список всех возможных расстановок знаков арифметических операций и скобок между его цифрами таким образом, чтобы в результате выполнения этих операций в соответствии с правилами получалось число 100. Для упрощения вычислений можно предположить, что первоначальное число передается в функцию в строковом виде. Например, для вызова такой функции со строкой "123456" должен получиться ответ:
["(1 + ((2 + (3 + 4)) * (5 + 6)))",
"(1 + (((2 + 3) + 4) * (5 + 6)))"]
Насколько сложна эта задача и как ее можно реализовать на python?
Ответы (1 шт):
Все-таки я предполагал, что это потребует больших усилий, когда писал комментарий.
opers = ['+', '-', '*']
def all_var(leafes):
global opers
if len(leafes) == 0:
return []
if len(leafes) == 1:
return [leafes]
res = []
for op in opers:
for i in range(len(leafes) - 1):
t = leafes[:i] + [f'({leafes[i]} {op} {leafes[i + 1]})'] + leafes[i + 2:]
res += all_var(t)
return res
s = '123456'
a = list(s)
n = 100
res = set([i[0] for i in all_var(a) if eval(i[0]) == n])
for i in res:
print(i)
Если обратиться к тем самым синтаксическим деревьям, о которых я упоминал в комментарии, то изначально мы имеем 6 листов: 1, 2, 3, 4, 5, 6. Причем операция может быть произведена только между соседними листьями (очевидно, мы не можем сложить 1 и 3, никак не взаимодействуя с двойкой). Это дает возможность для данного набора листьев перебрать все возможные варианты постановки первого знака.
Далее по свойствам синтаксических деревьев, мы можем сказать, будто этих двух выбранных листьев никогда не существовало, а на их месте всегда был результат операции над ними:
1 2 3 4 5 6 -> 1 2 (3 + 4) 5 6 -> 1 2 7 5 6.
Тогда мы получаем новый набор листьев, длина которого на 1 меньше, а значит мы можем использовать рекурсивную функцию перебора.
Разумеется, она очень тяжела по вычислительной сложности (для строки длины 7 уже выполняется секунд 9-10 на моем компьютере), однако она создает все возможные варианты расстановки знаков, насколько я могу судить.