Печать
Категория: Recur
Просмотров: 1599

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))