Понятие о типах алгоритмических структур

Кон

Кц

Пример записи алгоритма на школьном АЯ

Способы записи (отображения) алгоритмов

Словесная — описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Пример. Алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

Алгоритм:

· задать два числа;

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

· определить большее из чисел;

· заменить большее из чисел разностью большего и меньшего из чисел;

· повторить алгоритм с шага 2.

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

Словесный способ не имеет широкого распространения по следующим причинам:

· такие описания строго не формализуемы;

· страдают многословностью записей;

· допускают неоднозначность толкования отдельных предписаний.

Графическая — изображение алгоритма графическими символами по ГОСТ 19.701 – 90.

· Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.

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

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

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

Примером псевдокода может являться школьный алгоритмический язык в русской нотации, описанный в 1991 г. А. Г. Кушниренко учебнике «Основы информатики и вычислительной техники».

алг Сумма квадратов (арг цел n, рез цел S)

дано | n > 0

надо | S = 1*1 + 2*2 + 3*3 +... + n*n

нач цел i

ввод n; S:=0

нц для i от 1 до n

S:=S+i*i

вывод «S =», S

Программная — запись алгоритма в виде текста на выбранном языке программирования.

1.4 Основные блоки используемые при отображении схем программ (алгоритмов) по ГОСТ 19.701 – 90

Согласно ГОСТ 19.701 – 90 схемы программ отображают последовательность операций в программе. Схема программы состоит из:

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

2) линейных символов, указывающих поток управления;

3) специальных символов, используемых для облегчения написания и чтения схемы.

При изображении блоков необходимо учитывать, что основанием большинства блоков является прямоугольник с условными размерами сторон a и b, как представлено на рисунке 1.1.

Рисунок 1.1 — Основание блоков

Размер а выбирается начиная с 10 мм с шагом в 5 мм, при этом сторона b = 1,5·a, например, для рисования в тетеради удобно использовать блоки размером a равным 10 мм, тогда b равно 15 мм (две клетки в высоту, три в длину).

Исключением являются блоки: «Терминатор», высота которого равна 0,5·a, при длине b, и «Соединитель», диаметр которого равен 0,5·a.

Таблица 1 — Обозначение основных блоков по ГОСТ 19.701 – 90

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

1. Базовая структура «Следование»

На рисунке 1.2 представлена базовая алгоритмическая структура — «Следование». Действия выполняются исполнителем последовательно, одно за другим. Алгоритм, в котором команды выполняются одна за другой, называется линейным алгоритмом.

Рисунок 1.2 — Пример алгоритма программы с линейной структурой

2. Базовая структура «Ветвление»

На рисунке 1.3 представлены варианты базовой алгоритмической структуры —«Ветвление». При использовании базовой структуры «Ветвление» одна или другая последовательность команд выполняется в зависимости от истинности условия. Алгоритм, содержащий к базовую структуру ветвление, называется разветвляющимся.

Рисунок 1.3 — Пример программы содержащей ветвления
а) Содержащий выбор из двух возможностей (оператор if)
б) Содержащей множественный выбор (оператор switch)

3. Структура с циклом

На рисунке 1.4 представлены варианты алгоритмической структуры содержащей циклы. При этом, алгоритм, предусматривающий многократное повторение одного и того же действия над новыми данными, называется циклическим, а повторяющаяся серия команд называется телом цикла.

Разновидности циклов:

1. Цикл с предусловием;

2. Цикл цикл с постусловием;

3. Цикл с постоянным шагом (со счетчиком, арифметический).

Рисунок 1.4 — Пример программы содержащей циклы

а) Цикл с предусловием (условие проверяется перед выполнением тела цикла)

б) Цикл с постусловием (условие проверяется после выполнения тела цикла)

в) Цикл с постоянным шагом (оператор for)

Дата добавления: 2014-10-17