Как составить трассировочную таблицу по блок схеме

Описание алгоритмов с помощью блок-схем.

Для
разработки структуры программы удобнее
пользоваться записью алгоритма в
виде блок-схемы (в
англоязычной литературе используется
термин flow-chart).
Для изображения основных алгоритмических
структур и блоков на блок-схемах
используют специальные графические
символы. Они приведены на рисунке

        
Начало/конец
алгоритма

         

                  
Передача управления

        
Ввод данных

        
Блок вычислений

        
Начало (заголовок)
цикла

       

             
Конец цикла

        
Ветвление

     
Вывод данных

Составим
алгоритм вычисления квадратного корня
из произвольного положительного
вещественного числа х методом
Герона и запишем его на естественном
языке, а также в виде блок-схемы. Метод
основан на многократном применении
формулы:

при

.

Числовая
последовательность 
в
пределе при 
 сходится
к искомому значению. Выполним только 5
итераций метода, считая, что при этом
будет достигнута достаточно хорошая
точность. Обычно десяти итераций метода
Герона более чем достаточно для достижения
хорошей точность расчёта. Оба варианта
записи алгоритма:

1.   Ввести х. 2.   Присвоить  . 3.   Присвоить  . 4.   Присвоить  . 5.   Присвоить  . 6.   Если  , то перейти к шагу 4, иначе напечатать значение  .

         А
теперь займёмся самым любимым занятием
школьников всех времён и народов –
решением квадратного уравнения:

         
.

        
Будем полагать,
что коэффициенты этого
уравнения 
, 
 и 
 представляют
собой вещественные числа. Простейший
случай предполагает, что все коэффициенты
отличны от нуля. В зависимости от знака
дискриминанта квадратного уравнения

         

возможны три
случая:

1.  
Если 
,
то имеются два различных вещественных
корня, которые можно вычислить по
следующим формулам:

,
       
.

2.  
Если 
,
то имеется единственный корень (точнее,
двукратный корень):

.

3.  
Если 
,
то вещественных корней нет.

Блок схема алгоритма
приведена на рисунке:

С
ледует
заметить, что приведённый алгоритм
предназначен для решения узкого класса
задач – квадратных уравнений с «хорошими»
коэффициентами. Если допустить, что
коэффициенты могут принимать произвольные
вещественные значения, есть опасность,
что при определённых значениях
коэффициента (например, 
)
возникает аварийная ситуация (деление
на ноль). Качественный алгоритм и
качественная программа должны быть
устойчивыми, то есть при любых входных
параметрах завершение работы программы
должно быть нормальным, хотя, возможно,
и сопровождаться предупреждающим
сообщением о некорректности входных
данных. Свойством устойчивости обладает
алгоритм решения квадратного уравнения.

Разработанный
программистом алгоритм должен давать
правильный ответ. Проверка алгоритма
может оказаться непростым делом. В
простых случаях такая проверка может
быть выполнена с помощью
заполнения трассировочной
таблицы. Каждый столбец такой
таблицы соответствует определённой
переменной, а каждая строка – одному
шагу алгоритма. Для заполнения таблицы
необходимо шаг за шагом проследить
выполнение алгоритма, записывая в
таблицу текущие значения выбранных для
трассировки переменных. Такой метод
позволяет выявить логические ошибки,
допущенные при составлении или записи
алгоритма, и определить, верен ли
окончательный ответ. Составим в качестве
примера трассировочную таблицу для
алгоритма Герона вычисления квадратного
корня из числа 2.

i	z
0	1,00000
1	1,50000
2	1,41666
3	1,41421
4	1,41421
5	1,41421

         Как
видно из таблицы, уже после третьей
итерации приближенное значение
квадратного корня отличается от точного
1,414213 лишь в шестом знаке после запятой.  

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Слайд 1

Линейные вычислительные алгоритмы. Операция п рисваивание. Трассировочная таблица.

Слайд 2

В линейных алгоритмах присваивание является важнейшей операцией в алгоритмах, работающих с величинами, поговорим о ней более подробно. Переменная величина получает значение в результате присваивания. Присваивание производится компьютером при выполнении одной из двух команд из представленной выше системы команд: команды присваивания или команды ввода. Рассмотрим последовательность выполнения четырех команд присваивания, в которых участвуют две переменные: а и b . В приведенной ниже таблице против каждой команды указываются значения переменных, которые устанавливаются после ее выполнения. Такая таблица называется трассировочной таблицей, а процесс ее заполнения называется трассировкой алгоритма.

Слайд 3

х:= 2 у:=х*х у:=у*у х:=у*х s:= x+y Шаг алгоритма Переменные x y s 1 2 3 4 5 2 2 4 2 32 32 16 16 48 16 – – – – – Вычисления по алгоритму Алгоритм Ответ : s = 48 Прочерк в таблице означает неопределенное значение переменной. Конечные значения, которые получают переменные а и b , соответственно равны 2 и 4 .

Слайд 4

Трассировочная таблица иллюстрирует три основных свойства присваивания. Вот эти свойства: 1) пока переменной не присвоено значение, она остается неопределенной; 2) значение, присвоенное переменной, сохраняется вплоть до выполнения следующего присваивания этой переменной нового значения; 3) новое значение, присвоенное переменной, заменяет ее предыдущее значение.

Слайд 5

Обмен значениями двух переменных Рассмотрим еще один очень полезный алгоритм, с которым при программировании часто приходится встречаться. Даны две переменные величины: X и Y . Требуется произвести между ними обмен значениями. Например, если первоначально было: X = 1; Y = 2 , то после обмена должно стать: X = 2, Y = 1 . Хорошим аналогом для решения такой задачи является следующая: даны два стакана, в первом — молоко, во втором — вода; требуется произвести обмен их содержимым. Всякому ясно, что в этом случае нужен дополнительный, третий, пустой стакан.

Слайд 6

Последовательность действий будет следующей: 1) перелить из 1-го стакана в 3-й; 2) перелить из 2-го стакана в 1-й; 3) перелить из 3-го стакана во 2-й. Цель достигнута! По аналогии для обмена значениями двух переменных нужна третья дополнительная переменная. Назовем ее Z. Тогда задача решается последовательным выполнением трех операторов присваивания (пусть начальные значения 1 и 2 для переменных X и Y задаются вводом):

Слайд 7

В трассировочной таблице выводимые значения выделены жирным шрифтом. Аналогия со стаканами не совсем точна в том смысле, что при переливании из одного стакана в другой первый становится пустым. В результате же присваивания ( Х:=Y ) переменная, стоящая справа ( Y ), сохраняет свое значение. Действительно, в итоге переменные X и Y поменялись значениями. На экран будут выведены значения X и Y: 2,1 .

Слайд 8

Описание линейного вычислительного алгоритма Алгоритмы, результатами выполнения которых являются числовые величины, будем называть вычислительными алгоритмами. Рассмотрим пример решения следующей математической задачи: даны две простые дроби; получить дробь, являющуюся результатом деления одной на другую. В школьном учебнике математики правила деления обыкновенных дробей описаны так: 1. Числитель первой дроби умножить на знаменатель второй. 2. Знаменатель первой дроби умножить на числитель второй. 3. Записать дробь, числителем которой является результат выполнения пункта 1, а знаменателем — результат выполнения пункта 2.

Слайд 9

В алгебраической форме это выглядит следующим образом: Теперь построим алгоритм деления дробей для компьютера. В этом алгоритме сохраним те же обозначения для переменных, которые использованы в записанной выше формуле. Исходными данными являются целочисленные переменные а, b , с, d . Результатом — также целые величины m и n . Ниже алгоритм представлен в двух формах: в виде блок-схемы и на Алгоритмическом языке (АЯ).

Слайд 10

Раньше прямоугольник в схемах алгоритмов управления мы называли блоком простой команды. Для вычислительных алгоритмов такой простой командой является команда присваивания. Прямоугольник будем называть блоком присваивания , или вычислительным блоком . В форме параллелограмма рисуется блок ввода/вывода . Полученный алгоритм имеет линейную структуру.

Слайд 11

В алгоритме на АЯ строка, стоящая после заголовка алгоритма, называется описанием переменных . Служебное слово цел означает целый тип. Величины этого типа могут иметь только целочисленные значения. Описание переменных имеет вид: <тип переменных> <список переменных> Список переменных включает все переменные величины данного типа, обрабатываемые в алгоритме. В блок-схемах типы переменных не указываются, но подразумеваются. Запись алгоритма на АЯ ближе по форме к языкам программирования, чем блок-схемы.

Слайд 12

Коротко о главном Трассировочная таблица пошаговое исполнение команд алгоритма с указанием значений переменных, которые устанавливаются после выполнения команд. Трассировка алгоритма – процесс заполнения трассировочной таблицы Основные свойства присваивания: • значение переменной не определено, если ей не присвоено никакого значения; • новое значение, присваиваемое переменной, заменяет ее старое значение; • присвоенное переменной значение сохраняется в ней вплоть до нового присваивания.

Слайд 13

Обмен значениями двух переменных можно производить через третью дополнительную переменную . Трассировочная таблица используется для «ручного» исполнения алгоритма с целью его проверки . В алгоритмах на АЯ указываются типы всех переменных . Такое указание называется описанием переменных . Числовые величины, принимающие только целочисленные значения, описываются с помощью служебного слова цел (целый).

Слайд 14

1) A : =1 B: =2 A: =A+B B: =2*A Задание. Постройте трассировочные таблицы для следующих алгоритмов: 2) A : =1 B: =2 C: =A A: =B B: =C 3) A: =1 B: =2 A: =A+B B: =A-B A: =A-B

1.

Домашняя работа №1
построение таблицы трассировки для
ветвящегося процесса

2.

Вложенные операторы условия :
домашняя работа №1
Задание:
Для заданного варианта (номер варианта – две последние цифры шифра студента
(номер студенческого билета))
• построить блок-схему и программу на языке Си (С++) (с использованием программы
afce .exe);
• осуществить запуск полученной программы в среде программирования;
• осуществить пошаговое ее выполнение, протоколируя в таблице трассировке
промежуточные результаты.

3.

Пример задания
Файл:
Задание на ДР_1 (ветвление).txt

4.

Методика выполнения
Задание представлено в виде неструктурированного кода на алгоритмическом языке. В ходе
выполнения задание необходимо:
1. Открыть файл задания и найти свой вариант. Скопировать задание в отчёт (doc-файл).
2. Сделать дополнительную копию задания в отчете. Представить задание в виде
структурного кода, отступом отразив вложенность конструкций.
3. Запустить программу редактора блок-схем (afce.exe), прилагаемую вместе с заданием.
4.
5.
6.
7.
8.
Выбрать язык программирования Си.
Построить блок-схему в соответствии с заданием на шаге 2
Сохранить изображение блок-схемы как растровую картинку.
Вставить растровое изображение в отчет (или на шаге 4 с номерами блоков)
Пронумеровать каждый блок блок-схемы.
Из редактора блок-схем скопировать исходный код в среду программирования.
Дополнить программу в соответствии с синтаксисом языка программирования Си (С++).
Запустить программу в среде программирования, сделать скриншот исходника и
результатов запуска, вставить полученное изображение в отчет.
Построить в отчете таблицу трассировки.
Сравнить результат таблицы трассировки с результатом работы программы. Сделать
вывод.

5.

Пример выполнения (шаг 1)
1. Открыть файл задания и найти свой вариант. Скопировать задание в
отчёт (doc-файл).

6.

Пример выполнения (шаг 1)
1. Открыть файл задания и найти свой вариант. Скопировать задание в
отчёт (doc-файл).

7.

Пример выполнения (шаг 2)
2. Сделать дополнительную копию задания в отчете. Представить задание
в виде структурного кода, отступом отразив вложенность конструкций.
(… открыт блокнот)

8.

Пример выполнения (шаг 2)
2. Сделать дополнительную копию задания в отчете. Представить задание
в виде структурного кода, отступом отразив вложенность конструкций.

9.

Пример выполнения (шаг 3)
3. Запустить программу редактора блок-схем, прилагаемую вместе с заданием.
Выбрать нужный язык программирования (1). Затем начать построение блок-схемы в
соответствии с заданием, выбирая нужные элементы (2) и выбирая точки их
расположения (3). После окончания построения выбрать масштаб (4) так, чтобы блоксхема уместилась на листе формата А4.

10.

Пример выполнения (шаг 3)
3. Результат
построения
блок-схемы:

11.

Пример выполнения (шаг 3)
3. Результат
построения
блок-схемы:

12.

Пример выполнения (шаг 3)
3. Результат
построения
блок-схемы:

13.

Пример выполнения (шаг 3)
3. Вставить
растровое
изображение в
отчет

14.

Пример выполнения (шаг 4)
4. Пронумеровать каждый блок блок-схемы.

15.

Пример выполнения (шаг 5)
5. Из редактора блок-схем скопировать исходный код в среду программирования.
Дополнить программу в соответствии с синтаксисом языка программирования Си
(С++).
.

16.

Пример выполнения (шаг 5)
5. Из редактора блок-схем скопировать исходный код в среду программирования.
Дополнить программу в соответствии с синтаксисом языка программирования Си
(С++).
.

17.

Пример выполнения (шаг 5)
5. Из редактора блок-схем скопировать исходный код в среду программирования.
Дополнить программу в соответствии с синтаксисом языка программирования Си
(С++).
.

18.

Пример выполнения (шаг 5)
5. Из редактора блок-схем скопировать исходный код в среду программирования.
Дополнить программу в соответствии с синтаксисом языка программирования Си
(С++).

19.

Пример выполнения (шаг 5)
5. Из редактора блок-схем скопировать исходный код в среду программирования.
Дополнить программу в соответствии с синтаксисом языка программирования Си
(С++).

20.

Пример выполнения (шаг 5)
5. Из редактора блок-схем скопировать исходный код в среду программирования.
Дополнить программу в соответствии с синтаксисом языка программирования Си
(С++).

21.

Пример выполнения (шаг 5)
5. Из редактора блок-схем скопировать исходный код в среду программирования.
Дополнить программу в соответствии с синтаксисом языка программирования Си
(С++).

22.

Пример выполнения (шаг 6)
5. Из редактора блок-схем скопировать исходный код в среду программирования.
Дополнить программу в соответствии с синтаксисом языка программирования Си
(С++).

23.

Пример выполнения (шаг 6)
6. Из редактора блок-схем скопировать исходный код в среду программирования.
Дополнить программу в соответствии с синтаксисом языка программирования Си
(С++).

24.

Пример выполнения (шаг 7)
7. Построить в отчете таблицу трассировки.
Таблица трассировки представляет собой таблицу, каждая строка которой соответствует
выполнению отдельного оператора программы (или блока блок-схемы) или его части на очередном
шаге выполнения алгоритма.
В таблице выделяют область протокола выполнения команды и область данных.
Область
данных
Область команд
№
шага
№
блока
Оператор
(операция)
Результат
A
Переменная
B
C
D

25.

Пример выполнения (шаг 7)
7. Построить в отчете таблицу трассировки.
Таблица трассировки представляет собой таблицу, каждая строка которой соответствует выполнению отдельного
оператора программы (или блока блок-схемы) или его части на очередном шаге выполнения алгоритма.
В таблице выделяют область протокола выполнения команды и область данных.
Область протокола выполнения команд состоит из
• № шага – порядковый номер шага вычислительного процесса
в соответствии с фактической очередностью выполнения
команд алгоритма
• № блока – идентификатор оператора в коде (например, номер
строки программы или номер блока блок-схемы)
• Оператор – фактически выполняемая операция
вычислительного процесса без учета текущего значения
операндов
• Результат – процесс вычисления значения, которое будет
определено как результат выполнения команды
В области данных таблицы трассировки для каждой
переменной из алгоритма определен столбец,
соответствующий содержимому ячейки памяти
переменной
Область
данных
Область команд
№
шага
№
блока
Оператор
(операция)
Результат
A
Переменная
B
C
D

26.

Пример выполнения (шаг 7)
7. Построение таблицы трассировки.
№
№
шага блока
1
1
Оператор
(операция)
Начало
Переменная
Результат
A
B
C
D

27.

Пример выполнения (шаг 7)
7. Построение таблицы трассировки.
№
№
шага блока
Переменная
Оператор
(операция)
1
1
Начало
2
2
3
3
4
4
Присваивание:
А=5
Присваивание:
B=19
Присваивание:
С = -40
D= 16
Результат
A
А <- 5
B <- 19
C <- -40
D <- 16
B
C
D
5
19
-40
16

28.

Пример выполнения (шаг 7)
7. Построение таблицы трассировки.
№
№
шага блока
1
1
Начало
2
2
3
3
4
4
Присваивание:
А=5
Присваивание:
B=19
Присваивание:
С = -40
D= 16
Проверка: D > B
5
5
Переменная
Оператор
(операция)
Результат
A
А <- 5
B <- 19
C <- -40
D <- 16
B
C
D
5
19
-40
16

29.

Пример выполнения (шаг 7)
7. Построение таблицы трассировки.
№
№
шага блока
1
1
Начало
2
2
3
3
4
4
Присваивание:
А=5
Присваивание:
B=19
Присваивание:
С = -40
D= 16
Проверка: D > B
5
5
Переменная
Оператор
(операция)
Результат
A
А <- 5
C
D
5
B <- 19
C <- -40
D <- 16
16 > 19
B
19
-40
16
–> НЕТ

30.

Пример выполнения (шаг 7)
7. Построение таблицы трассировки.
№
№
шага блока
1
1
Начало
2
2
3
3
4
4
Присваивание:
А=5
Присваивание:
B=19
Присваивание:
С = -40
D= 16
Проверка: D > B
Проверка:
(A > C) xor (B > A)
5
6
5
11
Переменная
Оператор
(операция)
Результат
A
А <- 5
C
D
5
B <- 19
C <- -40
D <- 16
16 > 19
B
19
-40
16
–> НЕТ
(5 > -40) xor (19 > 5) =
Да xor да –> НЕТ

31.

Пример выполнения (шаг 7)
7. Построение таблицы трассировки.
№
№
шага блока
1
1
Начало
2
2
3
3
4
4
Присваивание:
А=5
Присваивание:
B=19
Присваивание:
С = -40
D= 16
Проверка: D > B
Проверка:
(A > C) xor (B > A)
5
6
5
11
Переменная
Оператор
(операция)
Результат
A
А <- 5
C
D
5
B <- 19
C <- -40
D <- 16
16 > 19
B
19
-40
16
–> НЕТ
(5 > -40) xor (19 > 5) =
Да xor да –> НЕТ

32.

Пример выполнения (шаг 7)
7. Построение таблицы трассировки.
№
№
шага блока
Переменная
Оператор
(операция)
Результат
A
1
1
Начало
2
2
А <- 5
3
3
4
4
Присваивание:
А=5
Присваивание:
B=19
Присваивание:
С = -40
D= 16
16 > 19
5
5
Проверка: D > B
6
11
Проверка:
(A > C) xor (B > A)
7
14
Присваивание:
C=(C mod B) +1
B
C
D
5
B <- 19
19
C <- -40
D <- 16
-40
16
–> НЕТ
(5 > -40) xor (19 > 5) =
Да xor да –> НЕТ
C <- ( -40 mod 19 ) +1 = -2 + 1 =
-1
-1

33.

Пример выполнения (шаг 7)
7. Построение таблицы трассировки.
№
№
шага блока
Переменная
Оператор
(операция)
Результат
A
1
1
Начало
2
2
А <- 5
3
3
4
4
Присваивание:
А=5
Присваивание:
B=19
Присваивание:
С = -40
D= 16
16 > 19
5
5
Проверка: D > B
6
11
Проверка:
(A > C) xor (B > A)
7
8
14
15
Присваивание:
C=(C mod B) +1
Присваивание:
A = (D – A) mod 5
B
C
D
5
B <- 19
19
C <- -40
D <- 16
-40
16
–> НЕТ
(5 > -40) xor (19 > 5) =
Да xor да –> НЕТ
C <- ( -40 mod 19 ) +1 = -2 + 1 =
-1
A <- (16 -5) mod 5 = 11 mod 5
=1
-1
1

34.

Пример выполнения (шаг 7)
7. Построение таблицы трассировки.
№
№
шага блока
Переменная
Оператор
(операция)
Результат
A
1
1
Начало
2
2
А <- 5
3
3
4
4
Присваивание:
А=5
Присваивание:
B=19
Присваивание:
С = -40
D= 16
16 > 19
5
5
Проверка: D > B
6
11
Проверка:
(A > C) xor (B > A)
7
8
14
15
Присваивание:
C=(C mod B) +1
Присваивание:
A = (D – A) mod 5
9
16
Печать: A, B, C, D
10
17
Конец
B
C
D
5
B <- 19
19
C <- -40
D <- 16
-40
16
–> НЕТ
(5 > -40) xor (19 > 5) =
Да xor да –> НЕТ
C <- ( -40 mod 19 ) +1 = -2 + 1 =
-1
A <- (16 -5) mod 5 = 11 mod 5
=1
Печать: 1 19 -1 16
-1
1

35.

Пример выполнения (шаг 8)
8. Сравнение результатов
№
№
шага блока
Переменная
Оператор
(операция)
Результат
A
1
1
Начало
2
2
А <- 5
3
3
4
4
Присваивание:
А=5
Присваивание:
B=19
Присваивание:
С = -40
D= 16
16 > 19
5
5
Проверка: D > B
6
11
Проверка:
(A > C) xor (B > A)
7
8
14
15
Присваивание:
C=(C mod B) +1
Присваивание:
A = (D – A) mod 5
9
16
Печать: A, B, C, D
10
17
Конец
B
C
D
5
B <- 19
19
C <- -40
D <- 16
-40
16
–> НЕТ
(5 > -40) xor (19 > 5) =
Да xor да –> НЕТ
C <- ( -40 mod 19 ) +1 = -2 + 1 =
-1
A <- (16 -5) mod 5 = 11 mod 5
=1
Печать: 1 19 -1 16
-1
1

36.

Пример выполнения (шаг 9)
9. Печать отчета
БУМАЖНЫЙ отчет:
• Титульник отчета
• Задание с номером варианта
• Структурированное представление задания
• Блок-схема с номерами блоков
• Скриншот исходника в среде
программирования с результатом работы
программы
• Таблица трассировки
• Выводы
• Источники (литература)