Recur7. Описать рекурсивную функцию CombiN_2($$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)$$ при $$0<K<N$$. Параметры функции — целые числа; $$N>0$$, $$0 \le K \le N$$. Считать, что параметр $$N$$ не превосходит $$20$$. Для уменьшения количества рекурсивных вызовов по сравнению с функцией CombiN_1 (см. задание Recur6) описать вспомогательный двумерный массив для хранения уже вычисленных чисел $$C(N, K)$$и обращаться к нему при выполнении функции CombiN_2. С помощью функции CombiN_2 найти числа $$C(N, K)$$для данного значения $$N$$ и пяти различных значений $$K$$.
Решение:
|
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 |
Memory = [] def CombiN_2(N,K): global Memory CombiN_2_1 = 0 CombiN_2_2 = 0 if (K==0) or (K==N): temp=1 else: if Memory[N-1][K]>0: CombiN_2_1 = Memory[N-1][K] else: CombiN_2_1 = CombiN_2(N-1,K) if Memory[N-1][K-1]>0: CombiN_2_2 = Memory[N-1][K-1] else: CombiN_2_2 = CombiN_2(N-1,K-1) temp = CombiN_2_1+CombiN_2_2 Memory[N][K]=temp return temp for i in range(20): Memory.append([]) for i2 in range(20): Memory[i].append(0) N = int(input('N : ')) for i in range (5): K = int(input('K : ')) print(CombiN_2(N,K)) |
Другие задачи из раздела Recur можно посмотреть здесь.
Комментарии: