Блок-схема алгоритма. Основные алгоритмические конструкции.

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

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

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

 

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

- ввод/вывод данных или результата на экран монитора

 

- процесс - арифметическое выражение или операция присваивания

 

- проверка условия

 

- подпрограмма или ранее созданная программа

 

- вывод на принтер, печать на бумаге.

- циклический процесс. Внутри блока указывается начальное значение переменной цикла, конечное значение переменной цикла и шаг цикла.

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

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

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

Линейные процессы имеют место, например, при вычислении арифметических выражений.

 

Разветвляющийся вычислительный процесс реализуется по одному из нескольких заранее предусмотренных направлений в зависимости от выполнения некоторого условия (логического выражения - ЛВ). Каждое направления вычислений называется ветвью. В любом конкретном случае процесс реализуется только по одной ветви, а выполнение остальных исключается. Ветвящийся процесс, включающий в себя две ветви, называется простым, более двух ветвей — сложным. Сложный ветвящийся процесс можно представить с помощью простых ветвящихся процессов.

Изображение ветвления в виде блок-схемы выглядит следующим образом: (слева – полное ветвление если-то-иначе, справа – неполный вариант ветвления если-то)

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

Для организации цикла необходимо предусмотреть:

задание начального значения параметра цикла – переменной, которая будет изменяться при его повторении;

изменение значения этой переменной перед каждым новым повторением цикла;

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

Цикл называется детерминированным (цикл с параметром), если число повторений тела цикла заранее известно или определено. Цикл называется итерационным (с пред- и постусловием), если число повторений тела цикла заранее неизвестно, а зависит от значений параметров (некоторых переменных), участвующих в вычислениях.

 

Базовые алгоритмы.

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

Пример 1. Заданы три числа. Найти значение наименьшего из них.

Заданные числа обозначим: а, b, с; результирующее наименьшее — min. На Рис 1. представ­лена блок-схема алгоритма решения данной задачи.

Пример 2. Одним из наиболее распространенных алгоритмов, встречающихся в литературе по информатике, является алгоритм Евклида – алгоритм нахождения наибольшего общего делителя двух натуральных чисел m и n (m¹n). Используется цикл с предусловием, в который вложена операция ветвления (Рис. 2).

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

Пример 3. Составим алгоритм вычисления факториала F натурального числа N (N!=1×2×3…×N). Используется цикл со счетчиком i.

Сформулируем правило произведения:

· начальное значение произведения Р=1;

· в теле некоторой циклической конструкции выполнить команду:

Р = Р * <множитель>

Пример 4. Составим алгоритм вычисления суммы N первых натуральных чисел. Используется цикл с предусловием.

 

Сформулируем правило суммирования:

· начальное значение суммы S=0;

· в теле некоторой циклической конструкции выполнить команду:

S = S + <слагаемое>

Подсчет количества элементов. Произведем счет: 1, 2, 3, 4, 5 и т.д., этот процесс является циклическим, так как каждый раз мы со­вершаем одно и то же действие: предыдущее натуральное число уве­личиваем на единицу. Обозначив через К — счетчик искомых эле­ментов, легко получить правило счетчика: К = К + 1 (на очередном шаге цикла). Но при первом подсчете должны получить значение К, равное единице, а до начала счета счетчик должен быть пуст, следо­вательно, начальное значение счетчика равно нулю.

Правило счетчика:

• начальное значение счетчика К = 0;

• в теле некоторой циклической конструкции выполнить команду: К = К + 1.

Пример 5. Задано 20 чисел. Сколько среди них чисел, больших 10?

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

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

 

Рекурсивным называется алгоритм, организованный таким обра­зом, что в процессе выполнения команд на каком-либо шаге он пря­мо или косвенно обращается сам к себе.