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 36 37 |
program Recur7; var N,K,i,i2:integer; Memory:array[1..20,1..20] of integer; Function CombiN_2(N,K:integer):integer; var CombiN_2_1,CombiN_2_2:integer; begin if (K=0) or (K=N) then result:=1 else begin if Memory[N-1,K]>0 then CombiN_2_1:=Memory[N-1,K] else CombiN_2_1:=CombiN_2(N-1,K); if Memory[N-1,K-1]>0 then CombiN_2_2:=Memory[N-1,K-1] else CombiN_2_2:=CombiN_2(N-1,K-1); result:=CombiN_2_1+CombiN_2_2; end; Memory[N,K]:=result; end; begin for i:=1 to 20 do for i2:=1 to 20 do Memory[i,i2]:=0; Write('N: '); Readln(N); for i:=1 to 5 do begin Write('K: '); Readln(K); Writeln(CombiN_2(N,K)); end; end. |
Другие задачи из раздела Recur можно посмотреть здесь.
Комментарии: