Линейные и разветвляющиеся структуры
Лабораторная работа №5
Линейные алгоритмы
Теоретические основы
В процессе решения задачи с применением компьютера пользователь самостоятельно или с помощью специалистов проходит ряд этапов, которые показаны на рис. 1.
 |
Рис. 1. Этапы решения задачи на ЭВМ
На всех этапах подготовки задачи к решению и при ее решении на ЭВМ необходимо учитывать особенности работы вычислительной техники:
· огромное быстродействие ЭВМ и абсолютная исполнительность;
· ограничения на объемы памяти, которые могут отводиться для записи чисел, переменных и т.п.;
· отсутствие у ЭВМ интуиции и чувства “здравого смысла”;
· способность ЭВМ решать только ту задачу, программу решения которой ей подготовил человек.
На первом этапе формулируются условия задачи (концептуальная модель), например, в словесной форме: функция f(x) должна получить значение, равное единице, если переменная x больше нуля, и ноль, если переменная x принимает другие значения.
Для уяснения “содержания задачи” можно представить ее в графическом виде – отложить на числовой оси точку 0 и отметить значения переменной x, при которых функция f(x) принимает 0 или 1 (рис. 2).
Рис. 2. Графическая интерпретация условий задачи
На втором этапе производится математическая постановка задачи (математическая модель):
· определяются исходные (вводимые) данные и их типы. В нашем случае к исходным данным относится переменная x, которая может принимать целые и вещественные (содержащие дробную часть) значения. В качестве типа для переменной x выбираем вещественный, поскольку данный тип включает в себя и целые значения тоже;
· решение задачи описывается в виде аналитических зависимостей. Для нашей задачи
· определяются конечные (выводимые) данные и их типы. В нашем случае конечными данными (результатом решения) является значение функции f(x) целого типа.
На третьем этапе осуществляется разработка алгоритма. Алгоритмизация выступает как связующее звено между “домашними” этапами решения задачи и непосредственно общением человека с компьютером. Именно на этом этапе начинаются сложности у людей, не имеющих специальной подготовки в области программирования (поэтому значительное внимание при дальнейшем изложении материала будет уделено умению читать и составлять алгоритмы). Алгоритм решения нашей задачи показан на рис. 4.
На четвертом этапе решения задачи алгоритм переводится в программу, записанную на языке высокого уровня. Ниже приводится программа на языке Pascal, которая реализует данный (см. рис. 3) алгоритм.
Pascal:
Program zadacha;
Var x:real; f:integer;
Begin
Read(x); WriteLn(‘x=’,x);
If x>0 Then f:=1
Else f:=0;
WriteLn(‘f=’,f);
End.
На пятом этапе программа вводится в память компьютера, осуществляется ее отладка и решение.
В процентном отношении время, затрачиваемое пользователем на выполнение каждого из этапов при решении задачи с помощью ЭВМ (на выполнение всех этапов – положим 100%), распределяется примерно так, как показано на диаграмме (рис. 4):
 |
Рис. 4. Распределение времени на решение задачи
Из диаграммы видно, что больше всего времени, как правило, требуется на выполнение этапа отладки и решения. Это связано с тем, что здесь устраняются ошибки, допущенные пользователем на всех предыдущих этапах решения задачи. Не очень страшно, если это ошибки синтаксиса или семантики, – они достаточно легко устранимы. Гораздо хуже наличие алгоритмических ошибок, выявить которые значительно труднее, а для их устранения иногда проще разработать новый алгоритм и написать новую программу, чем исправить существующую.
Алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных к искомому результату.
Само слово “алгоритм” происходит от латинской формы написания имени великого математика IX века Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом и понимали только правила выполнения четырех арифметических действий над многозначными числами, а в дальнейшем это понятие стало использоваться для обозначения последовательности действий, приводящих к решению поставленной задачи. Сейчас с помощью алгоритмов решаются не только вычислительные, но и многие другие задачи.
Качество алгоритма определяется его свойствами (характеристиками). К основным свойствам алгоритма относятся:
1. Массовость. Предполагается, что алгоритм может быть пригоден для решения всех задач данного типа. Например, алгоритм для решения системы линейных алгебраических уравнений должен быть применим к системе, состоящей из произвольного числа уравнений.
2. Результативность. Это свойство означает, что алгоритм должен приводить к получению результата за конечное число шагов.
3. Определенность. Предписания, входящие в алгоритм, должны быть точными и понятными. Эта характеристика обеспечивает однозначность результата вычислительного процесса при заданных исходных данных.
4. Дискретность. Это свойство означает, что описываемый алгоритмом процесс и сам алгоритм могут быть разбиты на отдельные элементарные этапы, возможность выполнения которых на ЭВМ у пользователя не вызывает сомнений.
Можно сказать, что алгоритм – это задание, которое нужно исполнить. Утверждения и вопросы могут быть использованы в алгоритмах только как подчиненные предложения в составе предписания.
Наиболее простой и универсальной формой представления алгоритма является словесное описание, которое содержит записанную на естественном языке (точнее, на подмножестве естественного языка) последовательность предписаний. Выполнение алгоритма предполагается в естественной последовательности, то есть в порядке записи. При необходимости изменить порядок выполнения предписаний в явной форме указывается, какое предписание надлежит выполнить следующим. Если необходимо такой алгоритм записать на бланке, то рекомендуется придерживаться следующих правил, облегчающих переход от алгоритма к программе:
1. Каждое предписание записывается с новой строки.
2. После предписания ставится точка с запятой.
3. Если предписание не поместилось в одной строке, то его можно продолжить на следующей строке без каких-либо знаков переноса.
Такую словесную запись алгоритма называют псевдокодом (ПСК), подчеркивая этим ее промежуточное положение между нашей естественной речью и понятным для компьютера языком программ. Достоинством псевдокодов является их универсальность, а к недостаткам можно отнести малую наглядность записи.
Наглядностью обладает другая форма записи – графическая схема алгоритмов (ГСА) или блок-схема. Такая схема представляет собой графический документ, который дает представление о порядке работы алгоритма. Здесь предписания имеют вид различных геометрических фигур, а последовательность выполнения операций отображается с помощью линий, соединяющих эти фигуры. Условные обозначения, применяемые при составлении граф-схем алгоритмов, и правила выполнения определены в ГОСТ 19.701-90 (ИСО 5807-85) “Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения”.
В табл. 1 приведены наименования, обозначения и определения отображаемых функций для символов, используемых при описании программ и алгоритмов.
Таблица 1
Описание символов, используемых в ГСА
| Наименование | Обозначение | Функции |
Данные
| Символ отображает данные, носитель данных не определен. Используется для обозначения операций ввода и вывода данных | |
Процесс
| Символ отображает функцию обработки данных любого вида (выполнение определенной операции или группы операций, приводящее к изменению значения, формы или размещения информации). Используется для обозначения операций присваивания | |
Предопре-деленный
процесс
| Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов, которые определены в другом месте (в подпрограмме, модуле). Используется для обозначения неэлементарных блоков | |
Подготовка
| Символ отображает модификацию команды или группы команд с целью воздействия на некоторую последующую функцию (установка переключателя, модификация индексного регистра или инициализация программы). Может быть использован для обозначения заголовка цикла |
| Наименование | Обозначение | Функции |
Решение
| Символ отображает решение или функцию переключательного типа, имеющую один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа. Соответствующие результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути. Используется для обозначения оператора условного перехода или оператора варианта | |
Граница цикла
| Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа в начале или в конце в зависимости от типа цикла | |
Соединитель
| Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и то же уникальное обозначение | |
Терминатор
| Символ отображает выход во внешнюю среду и вход из внешней среды. Используется для обозначения начала или окончания алгоритма | |
Линия
| Символ отображает поток данных или управления. Направления справа налево и снизу вверх обозначаются стрелками. Используется для соедине-ния символов в алгоритме | |
 Параллельные действия
| Символ отображает синхронизацию двух или более параллельных операций | |
Пунктирная линия
| Символ отображает альтернативную связь между двумя или более символами. Кроме того, символ используется для обведения аннотированного участка при записи комментариев | |
Комментарий
| Символ используется для добавления описательных комментариев или пояснительных записей с целью объясне-ний или примечаний. Пунктирные линии в символе комментария связаны с соответствующим символом или могут обводить группу символов. Текст комментариев или примечаний должен быть помещен около ограничивающей фигуры | |
| Наименование | Обозначение | Функции |
Пропуск
| . . . | Символ (три точки) используют в схемах для отображения пропуска символа или группы символов, в которых не определены ни тип, ни число символов. Символ используется только в символах линий или между ними. Он применяется главным образом в схемах, изображающих общие решения с неизвестным числом повторений |
Символы могут быть вычерчены в любой ориентации, но предпочтительной является горизонтальная ориентация. Внутрь символа помещают обозначения или описания операций. Направления линий связи слева направо и сверху вниз считаются стандартными, и линии связи изображаются без стрелок, в противоположном случае – со стрелками. В операционные блоки (процесс, ввод-вывод и подпрограмма) входит и из них исходит только одна линия связи. В блок проверки условий (ветвление) входит одна, а выходит не менее двух линий, около которых записываются результаты проверки условий. Из начальной вершины исходит одна линия связи, в конечную вершину также входит одна линия связи. Линии могут соединяться одна с другой, но не могут разветвляться. Символы ГСА могут быть отмечены идентификаторами или порядковыми номерами. Идентификатор представляет собой букву или букву с цифрой и должен располагаться слева над символом.
Внутри соединителей ставятся номера (координаты) блоков, к которым или от которых идут линии связи. Вместо номера (координат) может быть поставлен некоторый (один и тот же в обоих соединениях) идентификатор (см. рис. 4).
 |
Рис. 4. Применение соединителей
Недостатком графических схем алгоритмов является громоздкость. Для решения специальных задач, например проектирования вычислительных устройств, применяются другие способы задания алгоритмов, такие, как логические (операторные) и матричные схемы. Их достоинствами являются компактность и простота дальнейшей формализации, а недостатком – малая наглядность.
 |
1. Начало;
2. Список данных:
a, b, c – целый;
x – вещественный;
3. Ввод(a, b, c);
4. Вывод(a, b, c);
5. Если (a>b) То
6. x:=2×a – 3×c;
Иначе
7. x:=2×b + 3×c;
Конец-Если 5;
8. x:= x + c;
9. Вывод(x);
10. Конец.
Исходные данные: 5, 4, 1
Рис. 5. Пример алгоритма
Теория структурного программирования доказывает, что алгоритм любой степени сложности можно построить с помощью основного базового набора структур:
· последовательная (линейная) структура (рис. 6, а);
· ветвящаяся структура (рис. 6, б);
· циклическая структура (рис. 6, в).
 |
Рис. 6. Базовый набор структур
Поскольку каждая типовая структура имеет 1 вход и 1 выход, то любой операционный блок может быть, в свою очередь, представлен в виде последовательности любых базовых структур (в общем случае с любой глубиной вложения). Эта возможность и обеспечивает, в конечном счете, построение алгоритмов любой степени сложности только из основных базовых структур.
Линейные и разветвляющиеся структуры
Наиболее простыми для понимания и использования являются линейные структуры. Первоначально с их помощью можно описать любой вычислительный процесс. Предписания, которые обычно содержит такой алгоритм, представлены на рис. 7.
Предписание “Список данных” содержит сведения об именах и типах данных, обрабатываемых в этом алгоритме. Пред-писание “Ввод(исходные данные)” определяет, какие исходные данные и в каком порядке должны быть введены в ЭВМ. Предписание “Вывод (исходные данные)” позволяет проконтролировать правильность ввода информации. Предписания 5 и 6 позволяют получить требуемые результаты и выдать их пользователю. Рассматриваемый алгоритм относится к линейным.
Линейным называется алгоритм (фрагмент алгоритма, см. рис. 3, а), в котором отдельные предписания выполняются в естественном порядке (в порядке записи) независимо от значений исходных данных и промежуточных результатов.
Линейной, например, является последовательность вычислений по какой-либо формуле с помощью карманного калькулятора. Более подробно следует рассмотреть запись математических формул в виде конструкции
X:=A;
которая читается следующим образом: “Переменной X присвоить значение, равное A”. В этой формуле X – переменная; A может быть любым, сколь угодно сложным математическим выражением. В процессе решения задачи на ЭВМ выражение A вычисляется, и его значение присваивается содержимому ячейки памяти, отведенной для хранения переменной X. При этом переменная X теряет свое значение и приобретает новое. Таким образом, символ “:=” употребляется при изображении алгоритмов в значении “присвоить”. Как следствие этого, бессмысленное, с точки зрения алгебры, выражение
X:= X+5;
является широко распространенным в программировании и означает, что к текущему значению переменной X добавляется число 5, после чего X теряет свое старое значение и приобретает новое, которое на 5 больше предыдущего.
Линейные фрагменты используются на первых этапах детализации задачи. Однако только в редких случаях все предписания такого алгоритма являются элементарными. Так, например, предписание 5 на рис. 7 не является элементарным и требует дальнейшей детализации. Поэтому назначение блока 5 предусматривает сверху свободное место для записи координат блока, в котором будет раскрываться смысл детализируемого участка.
Анализ алгоритмов заключается в исследовании процессов, происходящих в ходе решения задачи на ЭВМ, и является одним из способов поиска и устранения ошибок в алгоритме.
Основным инструментом анализа алгоритмов служит таблица значений, заголовок которой показан на рис. 8.
 |
Заполнение таблицы производится последовательно, по мере имитации выполнения алгоритма в компьютере:
1. При появлении в алгоритме имени переменной оно записывается в столбец «Память», имитируя выделение в ЭВМ соответствующей ячейки памяти с таким же именем.
2. Первое значение, которое получит переменная, записывается в столбец «Память» в выделенную для нее строку. Например, если переменная А получает значение 5, то в строке А следует записать: А=5.
3. Каждое новое значение переменной записывается в строке с ее именем через запятую. Например, если переменная а получает новое значение 7, то в строке А запись будет иметь вид: А=5,7. Следует помнить, что в памяти компьютера новое значение переменной будет записано на место старого.
4. Столбцы «Условие» и «Вывод» заполняются по мере появления соответствующих предписаний в алгоритме.
Пример 1. Определить, что будет выведено на печать в результате выполнения следующего алгоритма, если при вводе переменные получили значения: A=2.5; B=0.5.
1. Начало;
2. Ввод (A,B);
3. X:=A–B;
4. Y:=A+B;
5. Z:=YX;
6. 
;
7. Вывод(A,B,X,Y,Z);
8. Конец.
Алгоритм решения задачи представлен в виде псевдокодов и содержит 8 строк. В вычислительном процессе используются пять переменных: A,B,X,Y,Z. Команда Начало означает, что процессор ЭВМ приступил к решению данной задачи. Оператор Ввод(A,B) позволяет записать в ячейку памяти A число 2.5, а в ячейку B – число 0.5. В третьей строке алгоритма записана операция присваивания X:=A–B. В ЭВМ она реализуется следующим образом: содержимое ячеек A и B направляется в процессор, где выполняется операция вычитания. Результат выполнения этой операции (2) записывается в ячейку X. Оператор присваивания Y:=A+B реализуется аналогично: содержимое ячеек A и B снова направляется в процессор, результат операции сложения (3) записывается в ячейку Y. После выполнения пятой операции в ячейку Z будет записано число 9. При выполнении шестой операции в процессор направляются числа из ячеек A и Z (2.5 и 9). Затем в соответствии с правилами приоритета выполняются операции, стоящие в правой части оператора присваивания: умножение, вычитание, вычисление квадратного корня, сложение, деление. Полученный результат (0.4) записывается в ячейку Z вместо старого значения (9).
Оператор Вывод(X,Y,Z) позволяет вывести значения переменных X, Y и Z на экран дисплея или принтер.
Команда Конец означает, что процессор ЭВМ завершил решение задачи.
Таблица значений, заполненная в ходе анализа алгоритма задачи 1, будет иметь вид, показанный в табл. 1.
Таблица 1
Таблица значений
 |
Синтез линейных алгоритмов
Пример 2. Разработать алгоритм для вычисления и печати значения функции Y, заданной формулой:
.
В алгоритме предусмотреть ввод аргумента X и вывод на печать введенной информации и результатов решения.
При анализе данной задачи на содержательном уровне определяется ее сущность, возможность решения на ЭВМ. При необходимости на задачу могут быть наложены определенные допущения и ограничения.
Составление математической модели целесообразно начать с определения переменных и констант, которые должны быть введены в машину в качестве исходных данных. Затем пользователь должен определить, какие переменные и в каком виде необходимо получить в качестве результатов решения. Далее необходимо подобрать математические зависимости, которые позволяют преобразовать исходные данные в конечные результаты. В рассматриваемой задаче математическую модель можно записать следующим образом:
Ввод: X.
Расчет: 
.
Вывод: X, Y.
Следует обратить внимание на то, что математическое выражение для расчета переменной Y содержит три повторяющихся фрагмента X2+1. В результате выделения этого фрагмента в промежуточную переменную не только сокращается запись соответствующего оператора присваивания, но и уменьшается расчет примерно на 100 коротких машинных операций.
Алгоритм должен содержать оператор Список данных. Этот оператор обеспечивает резервирование необходимого количества ячеек памяти машины. В нем указываются имена переменных и их атрибуты. После оператора Ввод целесообразно поставить оператор вывода всех вводимых переменных и констант. Это позволяет избежать ошибок ввода, связанных с ошибками набора и преобразования информации в машинные коды.
Алгоритм решения задачи в виде псевдокодов будет иметь следующий вид:
1. Начало;
2. Список данных: X,Y,Z – вещ.;
3. Ввод(X);
4. Вывод(X);
5. Z:=X 2+1;
6. Y:=eZ +cos(Z)+ln(Z);
7. Вывод(Y);
8. Конец.
Решение задач
ЗАДАЧА 1. Определить, что выводится на печать в результате выполнения следующего алгоритма:
1. Начало;
2. Список данных: A,X,Y,Z – цел.; B – вещ.;
3. A:=5;
4. X:=A–1;
5. Y:= 
;
6. Z:=AY 
;
7. B:=(Z + X)/ 
8. Вывод(B);
9. Конец.
РЕШЕНИЕ
Составить таблицу значений:
| Память | Условие | Вывод |
ЗАДАЧА 2. Определить, что будет выведено на печать в результате выполнения алгоритма, схема которого имеет вид:
 |
РЕШЕНИЕ
Составить таблицу значений:
| Память | Условие | Вывод |
ЗАДАЧА 3. Определить, что выводится на печать в результате выполнения следующего алгоритма, если входной поток имеет вид: 2.5 0.5.
1. Начало;
2. Список данных: A,B,X,Y,Z – вещ.;
3. Ввод(A,B);
4. Вывод(A,B);
5. X:=A–B;
6. Y:=A+B;
7. Z:=YX;
8. 
;
9. Вывод(X,Y,Z);
10.Конец.
РЕШЕНИЕ:
Составить таблицу значений:
| Память | Условие | Вывод |
ЗАДАЧА 4. Разработать алгоритм для вычисления и печати значения функции Y, заданной формулой:
ЗАДАЧА 5. Известно, что система уравнений:
A1 × X+B1 × Y=C1;
A2 × X+B2 × Y= C2,
имеет решение: 
Разработать алгоритм для вычисления и печати значений X и Y по известным численным значениям коэффициентов A1, B1, C1, A2, B2, C2, являющихся исходными (вводимыми) данными.
Дата добавления: 2019-01-14; просмотров: 795; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!