1) Составить рекурсивную схему (РС) в линейной форме.
RS: F(i, k); F(i, k) = if (i=0) then (Q(i, k) and M(i, k)) else P(i, k);
Q(i, k)= if (not (c[i] in diapazon)) then print:=false else T(i, k);
T(i, k)=if (c[u - 1] = c[u]) then print:=false;
M(i, k)= if print then W(c[i]);
P(i, k)= (if num-i>=0) then B(num, k);
B(i, k)=find(num-i,i,len+1).
2) Указать интерпретацию PC и представить протокол выполнения программы.
- Область интерпретации D ⊆ N - подмножество множества натуральных (целых неотрицательных) чисел.
I(u) = 1, I(i) = 1, I(diapazon) = [1..n], I(n) = 8, I(y) – число различных представлений заданного натурального N в виде суммы не менее двух попарно различных положительных слагаемых.I(find) – функция для подсчёта количества различных представлений заданного натурального N в виде суммы не менее двух попарно различных положительных слагаемых.I(print) – условие вывода на экранI(C[i])= C[i] – массив для хранения разложения
Протокол выполнения программы (S, I) конечен, результат:
4 3 1
5 2 1
5 3
6 2
7 1
Результат=5.
Протокол выполнения программы для N=20:
Протокол выполнения программы для N=20:
6 5 4 3 2
7 5 4 3 1
7 6 4 2 1
7 6 4 3
7 6 5 2
8 5 4 2 1
8 5 4 3
8 6 3 2 1
8 6 4 2
8 6 5 1
8 7 3 2
8 7 4 1
8 7 5
9 5 3 2 1
9 5 4 2
9 6 3 2
9 6 4 1
9 6 5
9 7 3 1
9 7 4
9 8 2 1
9 8 3
10 4 3 2 1
10 5 3 2
10 5 4 1
10 6 3 1
10 6 4
10 7 2 1
10 7 3
10 8 2
10 9 1
11 4 3 2
11 5 3 1
11 5 4
11 6 2 1
11 6 3
11 7 2
11 8 1
11 9
12 4 3 1
12 5 2 1
12 5 3
12 6 2
12 7 1
12 8
13 4 2 1
13 4 3
13 5 2
13 6 1
13 7
14 3 2 1
14 4 2
14 5 1
14 6
15 3 2
15 4 1
15 5
16 3 1
16 4
17 2 1
17 3
18 2
19 1
Похожие статьи:
|
