У вас есть девять цифр:
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-ов и кодирования операций с помощью символов.
👉 Это не оптимальное решение. Пишите свое решение в комментариях👇
@python_job_interview