Реализуйте программу, которая для заданных n и k вычисляет C(n, k)

Сочетанием из n элементов по k называется подмножество этих n элементов размера k.
Два сочетания называются различными, если одно из сочетаний содержит элемент, который не содержит другое.
Числом сочетаний из n по k называется количество различных сочетаний из n по k. Обозначим это число за C(n, k).

Пример:
Пусть n = 3, т. е. есть три элемента (1, 2, 3). Пусть k = 2.
Все различные сочетания из 3 элементов по 2: (1, 2), (1, 3), (2, 3).
Различных сочетаний три, поэтому C(3, 2) = 3.

Несложно понять, что C(n, 0) = 1, так как из n элементов выбрать 0 можно единственным образом, а именно, ничего не выбрать.
Также несложно понять, что если k > n, то C(n, k) = 0, так как невозможно, например, из трех элементов выбрать пять.

Для вычисления C(n, k) в других случаях используется следующая рекуррентная формула:
C(n, k) = C(n - 1, k) + C(n - 1, k - 1).

Реализуйте программу, которая для заданных n и k вычисляет C(n, k).

Вашей программе на вход подается строка, содержащая два целых числа n и k (1 ≤ n ≤ 10, 0 ≤ k ≤ 10).
Ваша программа должна вывести единственное число: C(n, k).

Примечание:
Считать два числа n и k вы можете, например, следующим образом:

n, k = map(int, input().split())
Sample Input 1:

3 2
Sample Output 1:

3
Sample Input 2:

10 5
Sample Output 2:

252
Напишите программу. Тестируется через stdin → stdout

0

1

0

3

биномиальный коэффициент..., метод является новым в Python версии 3.8. круто))

0

Сообщение от charitonov круто))

наверное, но твое решение наиболее подходит к условию задачи)).

Добавлено через 2 минуты
да, рекурсия в питоне имеет хвостатость?

0

тогда уж ДП, а не рекурсия.

1

Сообщение от eaa ДП

если наш гений Arsegg поддержал, вероятность высока)). ДП - это данных переплет))?

0

0

Arsegg, ну, тут даже постановка задачи рекурсивная! зачем плодить, что-то еще.
в питоне рекурсия, как и в java, съест память?

0

Aviz__, тем, что рекурсия убивает производительность программы в ноль (до экспоненты), если не использовать мемоизацию + память на стек вызовов (логарифм). Точную асимптотику, думаю, Ув. eaa напишет.

Добавлено через 11 минут
Например, если навесить декоратор на функцию Ув. charitonov functools.lru_cache, то значение функции C(50, 10) еще можно дождаться, пока Python не свалится со StackOverflow.

2

2

Сообщение от Arsegg память на стек вызовов

на плюсах и чистом С это делается, так называемой хвостатой рекурсией.

0

Aviz__, зависит от компилятора и настроек компиляции. Он может и не оптимизировать хвостовую рекурсию. При проектировании приложения я бы сильно на эту фичу не рассчитывал.

0

Arsegg, на хабре, давно читал статью, про то, что хвостатая в java не возможна принципиально. ко python я обратил снова (с тех первых пор он сильно изменился) свой взор недавно, поэтому и спросил, к случаю)).

0

Нативно Python эту фичу не поддерживает, хотя некоторые адепты уже написали батарейки под это дело: tco (https://stackoverflow.com/a/18506625).

1

0