Recur7. Описать рекурсивную функцию Combin2(N, K) целого типа, находящую C(N, K) — число сочетаний из N элементов по K — с помощью рекуррентного соотношения:
\(C(N, 0) = C(N, N) = 1,\)
\(C(N, K) = C(N - 1, K) + C(N - 1, K - 1) \text{ при } 0 < K < N.\)
Параметры функции — целые числа; \(N > 0, 0 \leq K \leq N\). Считать, что параметр N не превосходит 20. Для уменьшения количества рекурсивных вызовов по сравнению с функцией Combin1 (см. задание Recur6) описать вспомогательный двумерный массив для хранения уже вычисленных чисел C(N, K) и обращаться к нему при выполнении функции Combin2. С помощью функции Combin2 найти числа C(N, K) для данного значения N и пяти различных значений K.

Решение на Python 3:

import random
import numpy
from scipy.special import comb

def Combin2(N,K):
    if K == 0:
        Arr[N][0] = 1
        return 1
    if N == K:
        Arr[N][K] = 1
        return 1
    if Arr[N-1][K] != 0:
        a = Arr[N-1][K]
        #print("a = ", a)
    else:
        a = Combin2(N-1,K)
    if Arr[N-1][K-1] != 0:
        b = Arr[N-1][K-1]
        #print("b = ", b)
    else:
        b = Combin2(N-1,K-1)
    y = a + b
    Arr[N][K] = y
    return y

#for i in range(5):
N = random.randrange(1,20)
print("n = ",N)
K = random.randrange(0,N)
print("k = ",K)
#Arr = [[None for x in range(K+1)] for y in range(N+1)]
Arr = numpy.zeros((N+1,K+1))
Arr.astype(int)
print(Arr)
y = Combin2(N,K)
print(Arr)
print("n Choose k: ", y)
print("SciPy => n Choose k: ", comb(N,K))