-
Notifications
You must be signed in to change notification settings - Fork 0
/
1-3-15.py
40 lines (37 loc) · 2.24 KB
/
1-3-15.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
'''
https://stepik.org/lesson/24459/step/15?unit=6764
Сочетанием из 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
'''
n, k = map(int, input().split())
def fun (n, k):
if k == 0:
return 1
elif k > n:
return 0
else:
return fun(n - 1, k) + fun(n - 1, k - 1)
print(fun(n, k))