Найти тему
10,2 тыс подписчиков

📌 Задача


У вас есть девять цифр: 1, 2, …, 9. Именно в таком порядке. Вы можете вставлять между ними знаки «+», «-» или ничего. У вас будут получаться выражения вида 123+45-6+7+89. Найдите все из них, которые равны 100.

def all_combinations(a):
if len(a) <= 1:
yield a
else:
head = ''
tail = list(a)
while len(tail) > 0:
head += tail.pop(0)
for s in all_combinations(tail):
yield [head] + s

def all_signs(n):
if n == 0:
yield ()
else:
for tail in all_signs(n-1):
for s in '+-':
yield (s,) + tail

def perform_operations(nums, signs):
nums = list(map(int, nums))
result = nums.pop(0)
n = 1
for s in signs:
if s == '+':
result += nums.pop(0)
if s == '-':
result -= nums.pop(0)
n += 1
return result

for numbers in all_combinations(tuple(map(str, range(1, 10)))):
#print(numbers)
for signs in all_signs(len(numbers) - 1):
#print(signs)
summ = perform_operations(numbers, signs)
if summ == 100:
print(
''.join(map(
lambda x: ''.join(x),
zip(numbers, signs)))
+ numbers[-1])

Три функции:

- all_combinations — итератор, который выдает все числа для операций (в терминах задачи: вставляет пустые места);
- all_signs — выдаёт все возможные сочетания знаков + и - заданной длинны (для единообразия, это тоже итератор с рекурсией);
- perform_operations — выполняет операции.

Здесь просится решение, избавленное от if-ов и кодирования операций с помощью символов.

👉 Это не оптимальное решение. Пишите свое решение в комментариях👇

@machinelearning
1 минута
426 читали