Какой(-ие) могут быть альтернативные способы решения этой задачи?

Question

[Max Payne]

Внимание! Это НЕ задание, НЕ нужно писать код решающий эту задачу, мне интересны альтернативные ИДЕИ решения задачи, а не их реализация.

Имеется два числа, пускай N и S. S -- стоимость определенного товара, N - количество монет 1...N, то есть 1,2,3...N
В задаче требуется определить каким количеством способов можно купить этот товар, например:

N=3
S=5
Варианты:
2+3=5
________________________
N=4
S=4
Варианты:
1) 4=4
2) 1+3=4

Самое простое решение в лоб - с помощью рекурсии, а какие ещё решения могут быть? Мне, почему-то, очень кажется что это можно решить с помощью формулы, но я не могу сообразить какой.

И ещё раз:

Внимание! Это НЕ задание, НЕ нужно писать код решающий эту задачу, мне интересны альтернативные ИДЕИ решения задачи, а не их реализация.

Answer 1

[Максим Тимофеев]

Я думаю все варианты есть тут: возможные суммы чисел
тут еще очень важно, что в N, если там может быть любое целое число это один вариант. ЕСли дробные, другой. Если там все возможные целые числа, но не более, чем значение S - третий. Насколько я понял вариант третий. То есть надо вычислиnь все возможные комбинации, для получения суммы двух целых чисел, равной S.

Кстати есть классное видео, разбираются математические методы расчета вероятности попадения "счастливого билета" в транспорте. По сути Ваш случай, так как именно идет расчет возможных сумм:
https://www.youtube.com/watch?v=mqnnCdIlBKU (смотреть с 3-й минуты, там много лирики вначале) Не могу сказать, что 1в1 ситуация, но метод вычисления будет такой же.

Comments

[Max Payne]

Не двух, их может быть и 3, и 4, и больше

[Максим Тимофеев]

Arti Markelov, тогда посмотрите видео, там сопоставление суммы трех чисел, в вашем случае просто больше и там две суммы, а у Вас одна из сторон заранее известна.

[longclaps]

Кстати есть классное видео, где Чак Норрис бьётся с Брюсом Ли. К приведенной задаче имеет такое же отношение, как "методы расчета вероятности счастливого билета".

[Максим Тимофеев]

longclaps, Вы видео смотрели? Прежде чем свою тупую аналогию привести?

[longclaps]

Максим Тимофеев, нет, не смотрел, но умею решать такие задачи. А вы?

[Максим Тимофеев]

longclaps, не смотрел, но не одобряю. ЗАЧЕТ
То что Вы предлагаете "динамическое программирование", это концепт, а не решение, а я как раз дал ссылку на реальное решение, при чем как раз с элементами "динамического программирования"

[longclaps]

Максим Тимофеев, (копируя интонацию собеседника) СЛИВ ЗАСЩИТАН

[Максим Тимофеев]

longclaps, Такое ощущение, что Вы просто набором фраз из БД разговариваете, выбирая из в случайном порядке. Вы если считаете себя мега мозгом, Вы решение готовое дайте, лучше, чем то что в видео по ссылке. Отослать человека в поиск или Ваше

Типовой метод решения подобных задач (когда нужно количество способов, но не важны сами способы) - динамическое программировние.

это одно и то же

[longclaps]

Максим Тимофеев, топикстартер просил не давать готовое решение. Передумает - напишу, там ~10 строчек.

[Максим Тимофеев]

longclaps, топикстартер он просил

ИДЕИ решения задачи

А Ваш ответ это как "дядя, я знаю что у Вас сломалось, машина".

[longclaps]

Максим Тимофеев, дядя, я знаю что у Вас сломалось, самолюбие

def solve(n, coins):
    l = [1] + [0] * n
    for c in coins:
        for x in range(n - c, -1, -1):
            l[x + c] += l[x]
    print(l[n])

solve(5, [1, 2, 3, 4, 5])  # 3
solve(25, [1, 2, 4, 8, 16])  # 1 - единственность двичного представления
solve(1000, range(1, 1001))  # 8635565795744155161506

Answer 2

[Griboks]

Я бы использовал комбинаторику.