Базис стандартной и рекурсивной схемы. Верификация программы

Министерство РФ по связи и информатизации

«Поволжская государственная академия телекоммуникаций и информатики»

Кафедра «программного обеспечения информационных технологий »

КОНТРОЛЬНАЯ РАБОТА ПО КУРСУ:

«Теория вычислительных процессов»

2010

Задание 1

Построить базис стандартной схемы;

Реализовать стандартную схему в графовой и линейной формах;

Составить интерпретацию для заданной стандартной схемы;

6

Расчет суммы чисел Фибоначчи

Расчет суммы первых четырех чисел Фибоначчи

Числа Фибоначчи (F_i ) определяются по формулам F₀ = F₁ = 1; F_i = F_{i –1} + F_{i –2} при i = 2, 3, ... (каждое очередное число равно сумме двух предыдущих).

Вычислим сумму первых четырёх чисел Фибоначчи, которые не превосходят заданного натурального числа М. Зададим число M = 4.

алгоритм Фибоначчи (аргумент целое М, результат целое S)

дано | M>0

начало цел F0, F1, F2

F0:=1; F1:=1; F2:=2

S:=4 | 4 – сумма первых трех чисел Фибоначчи

начинается пока F2<=M

F0:=F1; F1:=F2; F2:=F0+F1 | серия переприсваиваний

S:=S+F2;

кончается

S:=S–F2 | из S вычитается последнее значение F2, превосходящее M

Конец

Исполнение алгоритма

F0	F1	F2	S	F2<M
1	1	2	4	+
1	2	3	4+3	+
2	3	5	7+5	− (кц)
12-5=7

Базис класса стандартных схем программ

Полный базис класса стандартных схем состоит из 4-х непересекающихся, счетных множеств символов и множества операторов - слов, построенных из этих символов.

Множества символов полного базиса:

1. X = {F₀ , F₁ , F₂ , S, M} - множество символов, называемых переменными ;

2. Множество функциональных символов ; верхний символ задает местность символа ; нульместные символы называют константами и обозначают начальными буквами латинского алфавита a, b, c...;

3. Множество предикатных символов ; нульместные символы называют логическими константами;

4. {program, uses, var, begin, end} - множество специальных символов.

Множество операторов включает пять типов:

1. начальный оператор - слово вида start(F₀ , F₁ , F₂ ), где F₀ , F₁ , F₂ - переменные, называемые результатом этого оператора;

2. заключительный оператор - слово вида stop(S), S - терм; вхождения переменных в терм S называются аргументами этого оператора;

3. оператор присваивания – F₀ :=1; F₁ :=1; F₂ :=2; S:=4; F₀ :=F₁ ; F₁ :=F₂ ; F₂ :=F₀ +F₁ ; S:=S+F₂ ; S:=S–F₂ ;

4. условный оператор (тест) – логическое выражение; F₂ <=M;

5. оператор петли - односимвольное слово While .

Графовая форма стандартной схемы на рис. 1.

Рис. 1

Линейная форма стандартной схемы

Turbo Pascal

Program SummaFib;

Uses Crt;

Var M, {zadannoe chislo}

F0, F1, F2, {3 posledovatelnyh chisla Fibonachchi}

S : Integer; {summa chisel Fibonachi}

BEGIN

ClrScr;

Write('Vvedite naturalnoe M : ');

ReadLn(M);

F0:=1; F1:=1; F2:=2;

S:=4; {4 - summa pervih 3-h chisel Fibonachchi}

Write('Chisla Fibonachchi, ne prevoshodyaschie ', M, ' :', F0:4, F1:4);

While F2<=M do

begin

F0:=F1; F1:=F2; Write(F1 : 4);

F2:=F0+F1; S:=S+F2;

end;

S:=S-F2; {vychitanie iz summy poslednego chisla, kotoroe prevoshodit M}

WriteLn; WriteLn;

WriteLn('OTVET: Summa etih chisel ravna = ', S); ReadLn

END

Задание 2

Построить базис рекурсивной схемы;

Составить интерпретацию для заданной рекурсивной схемы (рис. 2);

Составить протокол выполнения программы;

6

Составить рекурсивную программу-функцию подсчета количества всех положительных делителей натурального числа n.

Рассчитать количество делителей для числа 10.

Рис. 2

TURBO PASCAL

program Chislo;

uses crt;

type r=array[1..10] of integer;

var

d,x:integer;

a:r;

y:integer;

begin

clrscr;

y:=1;

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать