Главная Учебники - Разные Лекции (разные) - часть 32
Министерство РФ по связи и информатизации
«Поволжская государственная академия телекоммуникаций и информатики» Кафедра «программного обеспечения информационных технологий
» ПО КУРСУ: «Теория вычислительных процессов» 2010 Задание 1
Построить базис стандартной схемы; Реализовать стандартную схему в графовой и линейной формах; Составить интерпретацию для заданной стандартной схемы; Числа Фибоначчи (Fi
) определяются по формулам F0
= F1
= 1; Fi
= Fi –1
+ Fi –2
при i = 2, 3, ... (каждое очередное число равно сумме двух предыдущих). Вычислим сумму первых четырёх чисел Фибоначчи, которые не превосходят заданного натурального числа М. Зададим число M = 4. дано
| 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 Конец
Исполнение алгоритма Базис класса стандартных схем программ
Полный базис класса стандартных схем
состоит из 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
<=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 Рис. 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 nado najti 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); Для каждого оператора программы, записанного в линейной форме определить слабейшие предусловия. Рис. 4 Turbo Pascal
Program SummaFib;
Uses Crt;
Var M, {Zadannoe chislo}
F0, F1, F2, {3 posledovatelnyh chisla Fibonachchi}
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 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('O T V E T: Summa etih chisel ravna ', 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, где F2
=2, M>1; 5. оператор петли
- односимвольное слово While
. Слабейшее предусловие такое же, как в условном операторе
. Задание 4
Разработать алгоритм программы, решающей поставленную задачу; Составить стандартную схему программы и записать полученную программу в линейной форме (рис. 6); Используя метод индуктивных утверждений и правила верификации Хоара произвести верификацию программы. Рис. 6 Turbo Pascal
Program ProizFib;
Uses Crt;
Var M, {zadannoe chislo }
F0, F1, F2, {tri posledovatelnyh chisla Fibonachchi}
S : Integer; {summa chisel Fibonachchi}
R : Real; {proizvedenie chisel Fibonachchi}
BEGIN
ClrScr;
Write('Vvedite naturalnoe chislo M: ');
ReadLn(M);
F0:=1; F1:=1; F2:=2;
S:=4; {4 - summa pervyh 3-x chisel Fibonachchi}
R:=2; {2 - proizvedenie pervyh 3-x 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; R:=R*F2
end;
S:=S-F2; {vychitanie iz summy poslednego chisla, kotoroe prevoshodit M}
R:=R/F2; {Delenie iz proizvedeniya chisla, kotoroe prevoshodit M}
WriteLn; WriteLn;
WriteLn('O T V E T: Summa etih chisel ravna: ', S); ReadLn;
WriteLn; WriteLn;
WriteLn('O T V E T: Proizvedenie etix chisel ravno: ', R); ReadLn
END
.
Результаты работы Pascal-программы (рис. 7). Рис. 7 Задание 5
Составить алгоритм выполняемого процесса; Определить множества условий и событий для процесса; Построить сеть Петри для моделируемого процесса. Условиями для рассматриваемой системы являются: а) банкомат ждет; б) запрос поступил и ждет; в) банкомат обрабатывает запрос; г) запрос обработан. Событиями для этой системы являются: 1.Запрос поступил. 2. Банкомат начинает обработку запроса. 3. Банкомат заканчивает обработку запроса. 4. Результат обработки выдаются деньги клиенту. Для перечисленных событий можно составить следующую таблицу их пред- и постусловий (рис. 8). 1 2 3 4 нет а, б в г б в г, а нет Рис. 8
|