Министерство РФ по связи иинформатизации
«Поволжская государственная академия телекоммуникаций и информатики»
Кафедра «программного обеспечения информационных технологий»
КОНТРОЛЬНАЯ РАБОТА ПО КУРСУ:
«Теория вычислительных процессов»
2010
Задание1
Построить базис стандартной схемы;
Реализовать стандартную схему в графовой и линейной формах;
Составить интерпретацию для заданной стандартной схемы;6 Расчет суммы чисел Фибоначчи Расчет суммы первых четырех чисел Фибоначчи
Числа Фибоначчи (Fi) определяются по формулам F0= F1 = 1; Fi = Fi –1 + Fi –2при i = 2, 3,… (каждое очередное число равно сумме двух предыдущих).
Вычислим сумму первых четырёх чисел Фибоначчи, которые непревосходят заданного натурального числа М. Зададим число M = 4.
алгоритм Фибоначчи (аргумент целое М,результат целое S)
дано | M>0
начало цел F0, F1, F2
F0:=1; F1:=1; F2:=2
S:=4 | 4 – сумма первых трех чисел Фибоначчи
начинается пока F2
F0:=F1; F1:=F2; F2:=F0+F1 | серия переприсваиваний
S:=S+F2;
кончается
S:=S–F2 | из S вычитается последнее значение F2,превосходящее M
Конец
Исполнение алгоритма
F0
F1
F2
S
F2 1 1 2 4 + 1 2 3 4+3 + 2 3 5 7+5 − (кц) 12-5=7
Базис класса стандартных схем программ
Полный базис класса стандартных схем состоит из 4-хнепересекающихся, счетных множеств символов и множества операторов — слов,построенных из этих символов.
Множества символов полного базиса:
1. X = {F0, F1, F2, S, M} — множество символов, называемых переменными;
2. Множество функциональных символов; верхний символзадает местность символа; нульместные символы называют константами иобозначают начальными буквами латинского алфавита a, b, c...;
3. Множество предикатных символов; нульместные символыназывают логическими константами;
4. {program,uses, var, begin,end} — множество специальных символов.
Множество операторов включает пять типов:
1. начальный оператор — слово вида start(F0, F1, F2), где F0, F1, F2 — переменные, называемые результатомэтого оператора;
2. заключительный оператор — слово вида stop(S), S — терм; вхождения переменных в терм S называются аргументами этого оператора;
3. операторприсваивания – F0:=1; F1:=1; F2:=2; S:=4; F0:=F1;F1:=F2; F2:=F0+F1;S:=S+F2; S:=S–F2;
4. условный оператор (тест) – логическое выражение; F2
5. оператор петли — односимвольное слово While.
Графовая форма стандартной схемы на рис. 1.
/>
Рис. 1
Линейная форма стандартной схемы
TurboPascal
Program SummaFib;
Uses Crt;
Var M, {zadannoe chislo}
F0, F1, F2, {3 posledovatelnyh chislaFibonachchi}
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 chiselFibonachchi}
Write('Chisla Fibonachchi, neprevoshodyaschie ', M, ' :', F0:4, F1:4);
While F2
begin
F0:=F1; F1:=F2; Write(F1: 4);
F2:=F0+F1; S:=S+F2;
end;
S:=S-F2; {vychitanie iz summyposlednego chisla, kotoroe prevoshodit M}
WriteLn; WriteLn;
WriteLn('OTVET: Summa etih chiselravna = ', 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;
textcolor(6);
write('NAHOZHDENIE DELITELEJ');
gotoxy(2,2);
textcolor(9);
write('Vedite chislo, u kotorogo nadonajti kolichestvo delitelej: ');
readln(x);
textcolor(6);
write ('Deliteli chisla ' ,x, ': ');
for d:=1 to x div 2 do
begin
textcolor(9);
if x mod d=0 then begin
write(d,' ');
inc(y);end;end; {Y:= Y + 1}
writeln(x);
textcolor(5);
write('Kolichestvo delitelej: ' ,y);
readln;
end.
Результат работы PASCAL-программы (рис. 3)
/>
Рис. 3
Задание 3
Разработать алгоритм программы, решающей поставленную задачу;
Составить стандартную схему программы и записать полученнуюпрограмму в линейной форме (рис. 4);
Для каждого оператора программы, записанного в линейной формеопределить слабейшие предусловия.6 Расчет суммы чисел Фибоначчи
/>
Рис. 4
Turbo Pascal
Program SummaFib;
Uses Crt;
Var M, {Zadannoe chislo}
F0, F1, F2, {3 posledovatelnyh chislaFibonachchi}
S: Integer; {Summa chisel Fibonachch}
BEGIN
ClrScr;
Write('Vvedite naturelnoe chislo M:');
ReadLn(M);
F0:=1; F1:=1; F2:=2;
S:=4; {4 — summa pervyh 3-x chiselFibonachchi}
Write('Chisla Fibonachchi, neprevoshodyaschie ', M, ' :', F0:4, F1:4);
While F2
begin
F0:=F1; F1:=F2; Write(F1: 4);
F2:=F0+F1; S:=S+F2;
end;
S:=S-F2; {vychitanie iz summyposlednego chisla, kotoroe prevoshodit M}
WriteLn; WriteLn;
WriteLn('O T V E T: Summa etih chiselravna ', S); ReadLn
END.
Результаты работы Pascal-программы (рис. 5).
/>
Рис. 5
Слабейшие предусловия операторов:
1. начальный оператор — слово вида start (F0, F1, F2), где F0= 1, F1 = 1,
F2 — переменные, называемые результатом этого оператора;
2. заключительный оператор — слово вида stop (S), где S = 2- терм; вхождения переменных в терм S называются аргументами этого оператора;
3. оператор присваивания – F0:=1; F1:=1; F2:=2; S:=4; F0:=F1, где F1=1; F1:=F2, где F2=2; F2:=F0+F1, где F0=1, F1=1; S:=S+F2, где S=4, F2=3; S:=S–F2, где S=4, F2=2;
4. условный оператор (тест) – логическое выражение; F2
M>1;
5. оператор петли — односимвольное слово While.Слабейшее предусловие такое же, как в условном операторе.
Задание 4
Разработать алгоритм программы, решающей поставленную задачу;
Составить стандартную схему программы и записать полученнуюпрограмму в линейной форме (рис. 6);
Используя метод индуктивных утверждений и правила верификацииХоара произвести верификацию программы.6 Расчет произведения чисел Фибоначчи
/>
Рис. 6
Turbo Pascal
Program ProizFib;
Uses Crt;
Var M, {zadannoe chislo }
F0, F1, F2, {tri posledovatelnyhchisla Fibonachchi}
S: Integer; {summa chiselFibonachchi}
R: Real; {proizvedenie chiselFibonachchi}
BEGIN
ClrScr;
Write('Vvedite naturalnoe chislo M:');
ReadLn(M);
F0:=1; F1:=1; F2:=2;
S:=4; {4 — summa pervyh 3-x chiselFibonachchi}
R:=2; {2 — proizvedenie pervyh 3-xchisel Fibonachchi}
Write('Chisla Fibonachchi, neprevoshodyaschie ', M, ' :', F0:4, F1:4);
While F2
begin
F0:=F1; F1:=F2; Write(F1: 4);
F2:=F0+F1; S:=S+F2; R:=R*F2
end;
S:=S-F2; {vychitanie iz summyposlednego chisla, kotoroe prevoshodit M}
R:=R/F2; {Delenie iz proizvedeniyachisla, kotoroe prevoshodit M}
WriteLn; WriteLn;
WriteLn('O T V E T: Summa etih chiselravna: ', S); ReadLn;
WriteLn; WriteLn;
WriteLn('O T V E T: Proizvedenie etixchisel ravno: ', R); ReadLn
END.
Результаты работы Pascal-программы (рис. 7).
/>
Рис. 7
Задание 5
Составить алгоритм выполняемого процесса;
Определить множества условий и событий для процесса;
Построить сеть Петри для моделируемого процесса.6 Работа банкомата в режиме выдачи наличных денежных средств
Условиями для рассматриваемой системы являются:
а) банкомат ждет;
б) запрос поступил и ждет;
в) банкомат обрабатывает запрос;
г) запрос обработан.
Событиями для этой системы являются:
1.Запрос поступил.
2. Банкомат начинает обработку запроса.
3. Банкомат заканчивает обработку запроса.
4. Результат обработки выдаются деньги клиенту.
Для перечисленных событий можно составить следующую таблицуих пред- и постусловий (рис. 8).Событие Предусловия Постусловия
1
2
3
4
нет
а, б
в
г
б
в
г, а
нет
/> />
а /> /> />
Рис. 8
Предусловие выполняется для события 2.