Лекция

Тема: «Понятие алгоритма. Изображение алгоритма в виде блок-схемы»

План

1. Понятие алгоритма

2. Изображение алгоритма в виде блок-схемы

3. Основные структуры алгоритмов

4. Упражнения

1. Понятие алгоритма

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

Разработать алгоритм решения задачи означает разбить задачу на последовательно выполняемые шаги (этапы), причем результаты выполнения предыдущих этапов могут использоваться при выполнении последующих. При этом должны быть четко указаны как содержание каждого этапа, так и порядок выполнения этапов. Отдельный этап (шаг) алгоритма представляет собой либо другую, более простую задачу, алгоритм решения которой разработан ранее, либо должен быть достаточно простым и понятным без пояснений.

Четко сформулированная последовательность правил, описывающих этот процесс, и является алгоритмом.

Если алгоритм разработан, то его можно вручить для выполнения человеку (и вообще любому исполнителю, в том числе и ЭВМ), не знакомому с решаемой задачей, и, точно следуя правилам алгоритма, этот человек (или другой исполнитель) получит ее решение. Пример решения квадратного уравнения

Алгоритм обладает следующими основными свойствами, раскрывающими его определение:

1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов). При этом для выполнения каждого шага (этапа) алгоритма требуется некоторый конечный отрезок времени. То есть преобразование исходных данных в результат осуществляется во времени дискретно.

2. Определенность (или детерминированность). Это свойство состоит в том, что каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

3. Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.

4. Массовость. Это свойство состоит в том, что алгоритм решения задачи разрабатывается в общем виде, т. е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. (В отдельных случаях исходные данные могут отсутствовать.)

5. Правильность. Способность алгоритма давать правильные результаты при решении поставленных задач

Чтобы разработать алгоритм, нужно хорошо представить себе ход решения задачи. При этом полезно решить задачу самому (на бумаге) для каких-либо наборов данных, не требующих громоздких вычислений, запоминая выполняемые действия, так, чтобы далее эти действия формализовать, т. е. записать в виде последовательности четких правил.

Понятия алгоритма и программы разграничены не очень четко. Обычно программой называют окончательный вариант алгоритма решения задачи, ориентированный на конкретного исполнителя.

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

Разработанный алгоритм можно зафиксировать несколькими способами:

· ·  на естественном языке (предыдущий пример);

· ·  в виде блок-схемы (см. ниже);

· ·  на специальном языке для записи алгоритмов (алгоритмическом языке).

2. Изображение алгоритма в виде блок-схемы

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

Существует Государственный стандарт (ГОСТ), определяющий правила выполнения схем и обозначения для отдельных операций процесса обработки данных. Блок-схемы строятся по определенным правилам и включают в себя геометрические фигуры (блочные символы) соединенные между собой стрелками (линиями), указывающими порядок выполнения операций. Блочные символы стандартизированы и различаются по типу выполняемых действий (ГОСТ 19.002-80 и 19.003-80, международные стандарты ISO 2636-73 или ISO 1028-73). ГОСТом, помимо типов фигур, предписываются также определенные размеры их сторон, одинаковые размеры блоков. Этих требований необходимо придерживаться при оформлении окончательной документации. На промежуточных этапах разработки алгоритма придерживаться этих требований ГОСТа не обязательно. Приведем наиболее употребительные блоки блок-схем:

Наименование	Обозначение	Функция
Процесс		Выполнение операции или группы операций, в результате которых изменяются значение, форма представления или расположение данных
Решение		Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий
Модификация		Выполнение операций, меняющих команды, или группы команд, меняющих программу
Предопределенный процесс		Использование ранее созданных и отдельно описанных алгоритмов и программ
Ввод-вывод		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов (вывод)
Линия потока		Указание последовательности обработки символов
Соединитель		Указание на наличие связи между прерванными линиями потока, связывающими символы
Пуск-останов		Начало и конец выполнения программы
Межстраничный соединитель		Указание на наличие связи между разъединенными частями схемы, расположенных на разных листах

Рассмотрим более подробно применение основных графических элементов блок-схемы.

В схеме начало и завершение алгоритма, а также вход и выход из вспомогательных алгоритмов отмечаются, соответственно, блочными символами начала и конца.

Эти блоки в отличие от большинства других имеют один вход или один выход, отмечающие как бы начало и конец пути обработки информации. Каждая схема обязательно должна начинаться и заканчиваться этими символами.

Следующие блочные символы в виде параллелограмма используют для обозначения операций ввода-вывода данных

Блок, отражающий вычислительный процесс, применяют для обозначения операции (или группы операций), изменяющей значение, форму представления или размещения данных.

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

Логический блочный символ, обозначающий решение, используют для выбора направления выполнения алгоритма в зависимости от некоторого условия (условий).

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

Из блока проверки условия может выходить два или три информационных потока, что отличает его от других блочных символов, имеющих не более одного выхода. Выходящие из блока линии должны снабжаться условиями, порождающими то или иное направление исполнения алгоритма (например, «да» или «нет», <0, =0 или >0, + или -и т. д.).

Блочный символ модификации символизирует начало циклических вычислений (заголовок цикла), для управления которыми он используется.

Внутри блока указываются переменная цикла и параметры, характеризующие закон ее изменения, например, i = х1,хт, dx, где i – переменная цикла, х1 и хn – начальное и конечное значения переменной цикла, dx – шаг ее изменения (переменная цикла изменяется от до х1 до хn с шагом dx). Если шаг равен 1, то dx можно не указывать.

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

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

В блочный символ вписывают номера блоков, в которые вычислительный процесс передается или из которых он поступил. Так, верхний соединитель указывает, что вычислительный процесс передается на вход блока 15, а нижний – что вычислительный процесс поступил с выхода блока 10.

Если же линии соединяют блоки, расположенные на разных страницах, то используется символ межстраничного соединителя, в который вписывают не только номера блоков, но и номера страниц.

Изображенный межстраничный соединитель означает, что вычислительный процесс передается на вход блока 23, расположенного на странице 10. Нижний межстраничный соединитель означает, что информация передана с выхода блока 12, расположенного на странице 6 (то есть сначала указывается номер страницы, а под ним номер блока, на который передается или с которого принимается управление).

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

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

При создании блок-схем используют следующие правила:

· ·        линии потока проводят параллельно внешним краям рамки листа. Допускается пересечение их или изгиб под углом 90°. Направление линий потока сверху вниз и слева направо принимают за основное: если линии потока основного направления не имеют изломов, то это направление стрелками можно не обозначать. В остальных случаях направление линий потока обозначать стрелкой обязательно;

· ·        схема является самым наглядным и простым способом представления алгоритма. В ней четко прослеживаются порядок выполнения действий, потоки информации и пути их следования. Линии по отношению к блокам могут быть входящими и выходящими. Количество входящих линий для всех блоков не ограничено – их может быть одна, две, три и более. Выходящая же линия для большинства блоков может быть только одна (исключение – блоки проверки условия);

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

· ·        внутри блоков и рядом с ними делаются записи, уточняющие выполняемые функции. Эти записи могут быть представлены в любой удобной для разработчика форме. Они не имеют каких-либо существенных ограничений (на язык, обозначения, символы и др.), однако должны быть понятны всем, кто будет пользоваться алгоритмом. Единственное ограничение накладывается на последовательность записей – они должны читаться (использоваться при работе алгоритма) слева направо и сверху вниз независимо от направления потоков информации;

· ·        в схеме алгоритма все линии от блока начала до блока конца не должны иметь разрывов, не помеченных соединителями. Все линии, указывающие на последовательность выполнения действий, должны быть замкнутыми;

· ·        в схеме должны четко прослеживаться потоки информации;

· ·        блоки следует размещать таким образом, чтобы избегать пересечения линий. При передаче управления в схеме снизу вверх или справа налево линии обязательно помечают стрелками;

· ·        не допускается передача управления «в никуда». Источник и получатель должны быть четко обозначены.

3. Основные структуры алгоритмов

Основные структуры алгоритмов – это ограниченный набор блоков и стандартных способов их соединения для выполнения типичных последовательностей действий.

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

К основным структурам относятся:

        1. Следование (линейный). Последовательное размещение блоков и групп блоков. В программе реализуется последовательным размещением операторов.

2. Разветвление. Применяется, когда в зависимости от условия нужно выполнить либо одно, либо другое действие. Действие 1 или действие 2 может в свою очередь содержать несколько этапов

3. Обход. Частный случай разветвления, когда одна ветвь не содержит никаких действий.

            4. Множественный выбор. Является обобщением разветвления, когда в зависимости от значения переменной (I) выполняется одно из нескольких действий. При I=1 выполняется действие S1, при I=2 – действие S2 и т. д.

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

Счетчик цикла (i) принимает начальное значение (а). Значение счетчика цикла сравнивается с конечным значением (b). Если счетчик меньше либо равен конечному значению, то выполняется тело цикла, счетчик увеличивается на шаг (с) и снова происходит сравнение счетчика с конечным значением. Такие операции повторяются до тех пор, пока значение счетчика не превысит конечное значение. (В таких циклах допускается и уменьшение счетчика. В этом случае начальное значение должно быть больше либо равно конечному, а шаг отрицательным. Выполнение цикла выполняется до тех пор, пока значение счетчика не станет меньше конечного значения).

6.   Цикл с предусловием. Применяется при необходимости выполнить какие-либо вычисления несколько раз при неизвестном заранее количестве повторов. В этом случае цикл повторяется до выполнения некоторого условия. В таких циклах вначале задаются некоторые начальные параметры, затем проверяется некоторое условие. Если оно выполняется, то выполняется тело цикла, и условие проверяется снова. Цикл повторяется до тех пор, пока выполняется условие

            7. Цикл с постусловием. Особенность этого цикла в том, что он всегда выполняется хотя бы один раз, так как первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено.

            Особенностью всех приведенных структур является то, что они имеют один вход и один выход, и их можно соединять друг с другом в любой последовательности. В частности, каждая структура может содержать любую другую структуру в качестве одного из блоков.

Обычно при составлении схемы блоки размещаются друг под другом в порядке их выполнения. Возврат назад осуществляется только на циклах. Это дает простую и наглядную структуру алгоритма, по которой далее легко составить программу.

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

В некоторых случаях стремление, во что бы то ни стало, остаться в рамках структурного подхода приводит к необоснованному усложнению программы и потере ее наглядности и естественности. 

4. Упражнения

1. Разделить число n на число m

2. Составить блок-схему нахождения площади трапеции

3. Выбрать максимальное из двух чисел

4. Найти максимальное из трех чисел

5. Задано число x. Найти значение функции у.

6. Заданы 3 числа: х, y, p. Если р < 0, тогда вычислить переменную t как разность x и у, в противном случае как сумму.

7. Заданы 3 числа: x, y, z. Если х < 0, тогда переменную р посчитать как мах из y и z, если х ≥ 0, то р как min из y и z.

8. Вычислить значение функции:

9. Составить блок-схему решения квадратного уравнения: ax² + bx + с = 0; 

D = b² - 4ac

10. Вычислить

11. Найти значение функции:

12. Найти значение функции:

13. Определить, чему равна функция Y = x + z, где 

14. Найти значение функции

15. Найти значение функции вида:

16. Найти сумму ряда с заданной точностью E:

Решить задачу с предусловием и постусловием

17. Составить алгоритм нахождения факториала числа: Y = n!

18. Затабулировать значение функции Y = sin(x) на отрезке [0, 6.28] с шагом ∆x = 0.3

19. На основе этой задачи просуммировать те элементы функции, значение которых < 0,5.

Вопросы для самоконтроля

1. Что такое алгоритм? Назовите его свойства.

2. Что такое алгоритмизация?

3. Способы составления алгоритмов (три)?

4. Что такое схема?

5. Назовите основные блоки блок-схем и их назначение.

6. Назовите основные правила, которыми пользуются при создании блок-схем.

7. Какие основные структуры алгоритмов вы знаете?

8.  Дайте характеристику алгоритма следования.

9. Дайте характеристику алгоритма разветвления.

10. Расскажите об алгоритме множественного выбора.

11. Охарактеризуйте алгоритм циклов с известным количеством повторений.

12. Дайте характеристику алгоритма циклов с неизвестным количеством повторений.