Четверг, 13.05.2021, 12:17
Приветствую Вас Гость | RSS | PDA

Всё для студента информата

Полезная информация

Материалы для студента

Всё для студента IT » Материалы для студента » Теория вычислительных процессов

Решение задач по теме "Схемы программ" - рекурсия

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

Похожие статьи:

Не нашли то, что Вам нужно?.. Найдите ответ на форуме!
Категория: Теория вычислительных процессов | Добавил: admin (07.05.2011)
Просмотров: 3046 | Теги: задача, твп
Сообщество
Помощь
Форма входа
Поиск

Студенческий помощник по информатике © 2021
При цитировании материалов данного сайта, обязательна ссылка на источник: ITstudents.ru



>