Дана последовательность чисел. Например: 2 9 3 6 3 8 1 10 6 7.
Нужно узнать: сколькими способами можно образовать число, большее 8.
Правильные ответ - 42, но я никак не могу понять как его добиться.
Подскажите формулу или толкните в нужном направлении.
Не уверен, что правильно понял задачу, поскольку у меня на данной последовательности чисел 42 не получается. Но ответ на всякий случай напишу.
Общая идея моего алгоритма состоит в том, чтобы пройти в цикле всю последовательность, уходя в рекурсию на её оставшуюся часть всякий раз, когда текущий элемент не завершает собой очередную комбинацию. Если же текущий элемент оказывается завершающим, то к промежуточному итогу прибавляется единица. Каждый рекурсивный вызов возвращает свой промежуточный итог, который прибавляется к промежуточному итогу более высокого уровня. И в конце объединение промежуточных итогов первого уровня даёт общее количество комбинаций.
На Python'е это выглядит вот так:
#!/usr/bin/python
numbers = [2, 9, 3, 6, 3, 8, 1, 10, 6, 7]
def combinations(selected=[], nexts=numbers):
subtotal = 0
for i, n in enumerate(nexts):
if sum(selected) + n > 8:
# print selected+[n]
subtotal += 1
else:
subtotal += combinations(selected+[n], nexts[i+1:])
return subtotal
print combinations()