Мисюткин. Методичка по алгоритмитизации

Подождите немного. Документ загружается.

Введение

Решение любой задачи осуществляется по определенному плану,

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

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

выполнение которых приводит задачу к решению.

На практике существенное значение имеет то, чтобы создаваемый

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

1. Детерминированность (или другими словами определенность,

однозначность) – четкость и ясность всех предписаний алгоритма.

2. Результативность – способность алгоритма приводить к решению

задачи за определенное число шагов.

3. Массовость (или универсальность) – применимость алгоритма к

решению задач определенного класса.

Разработка алгоритма является наиболее ответственным и творческим

этапом в разработке программы, так как именно от него зависит, правильно

ли решается задача в целом.

1. Способы записи алгоритма

В настоящее время на различных этапах формализации и постановки

задачи используется три основных способа описания алгоритмов:

 словесно – формульный;

 схема алгоритма (другие названия: блок – схема, графическая схема

алгоритма);

 запись в виде программы.

Перед тем как записать алгоритм в виде программы, его, как правило,

представляют в виде схемы алгоритма. А не наоборот, как пытаются

сделать многие начинающие! Схема алгоритма, если она правильно

составлена, способствует правильному и более быстрому написанию

программы!

Правила выполнения схем алгоритмов регламентированы ГОСТ 19.701

– 90 (ИСО 5807 – 85) [1], входящего в единую систему программной

документации (ЕСПД) под названием "Схемы алгоритмов, программ, данных

и систем. Условные обозначения и правила выполнения". Согласно этому

стандарту схем а алгоритма – это графическое представление метода

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

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

1) символов процесса, указывающих фактические операции обработки

данных (включая символы, определяющие путь, которого следует

придерживаться с учетом логических условий);

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

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

чтения схемы.

Обозначение наиболее часто употребляемых символов и описание

отображаемых ими действий приведено в таблице1.

Таблица1.

Название символа Обозначение Значение

Терминатор

Начало или конец схемы

программы

Данные

Ввод или вывод данных;

носитель данных не определен

Процесс

Обработка данных любого вида,

приводящее к изменению

значения, формы или

размещения информации

Предопределенный

процесс

Использование подпрограммы

(или модуля)

Решение

Проверка условия и выбор

одного из нескольких

альтернативных выходов

Подготовка

Модификация команды, группы

команд, индексного регистра

(создание цикла)

Линия

Отображает поток данных и

управления. При

необходимости могут быть

добавлены стрелки - указатели

Соединитель

Обрыв линии и продолжение ее

в другом месте.

Соответствующие символы –

соединители должны иметь

одно и то же уникальное

обозначение.

Название символа Обозначение Значение

Комментарий

Пояснения к выполняемым

действиям. Располагается около

ограничивающей фигуры

(символа или блока символов,

обведенных пунктирной

линией)

Символы могут быть вычерчены в любой ориентации, но, по -

возможности, предпочтительной является горизонтальная ориентация.

Текст, необходимый для понимания функции данного символа, следует

помещать внутри данного символа и записывать слева направо и сверху вниз

независимо от направления потока. Если объем текста превышает размеры

символа, нужно использовать символ комментария. В схемах может

использоваться идентификатор символов (например, в виде номера),

которым можно воспользоваться в справочных целях в других элементах

документации (или для ссылки на символ). Идентификатор символа должен

располагаться слева над символом.

Правила выполнения соединений. Потоки данных или потоки

управления в схемах показываются линиями. Направление потока слева

направо и сверху вниз считается стандартным. Если необходимо внести

большую ясность в схему (например, при соединениях), на линиях

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

то стрелки должны указывать это направление.

В схемах следует избегать пересечения линий. Пересекающиеся линии

не имеют логической связи между собой, поэтому изменения направления

потока в точках пересечения не допускаются. Две или более входящие линии

могут объединяться в одну исходящую.

Линии в схемах должны подходить к символу либо слева, либо сверху,

а исходить либо справа, либо снизу. Линии должны быть направлены к

центру символа. При необходимости линии в схемах нужно разрывать во

избежание излишних пересечений или слишком длинных линий, а также,

если схема состоит из нескольких страниц. Соединитель в начале разрыва

называется внешним соединителем, а соединитель в конце разрыва –

внутренним соединителем. Совместно с символом комментария можно

указать, с какой страницы, или на какую страницу схемы совершается

переход.

Примеры:

Внешний соединитель Внутренний соединитель

Несколько выходов из символа можно показывать:

 несколькими линиями отданного символа к другим символам;

 одной линией от данного символа, которая затем разветвляется в

соответствующее число линий.

Примеры:

Каждый выход из символа нужно пометить значениями

соответствующих условий, чтобы показать логический путь, который он

представляет, с тем, чтобы эти условия и соответствующие ссылки были

идентифицированы.

Примеры:

Со стр.1

К стр.5

При всем разнообразии структур алгоритмов можно выделить четыре

типовых структуры (рис.1.1), из которых как из кирпичиков, можно

построить здание алгоритма любой сложности: следование, ветвлени е ,

цикл и выбор.

а) б) в)

Рис. 1.1. Типовые структуры алгоритмов: а) - следование; б, в) – ветвление

(полное и неполное).

Да Нет

A>B D=?

=-1

Другое

Да Нет

а) б)

Рис.1.2. Типовые структуры алгоритмов: а) – цикл с предусловием; б) – цикл

с постусловием.

Рис.1.3. Типовая структура выбор.

Типовые структуры хороши тем, что все они имеют одну точку входа и

одну точку выхода. Это упрощает просмотр и понимание алгоритма и

сокращает количество возможных ошибок, сделанных при составлении

схемы и время на их поиск. Типовые структуры могут быть вложенными

друг в друга, например, символ, входящий в структуру следование может

включать в себя структуры ветвление или цикл, а каждая из ветвей структур

ветвление или выбор может содержать структуры следование, цикл или еще

одно ветвление и выбор.

2. Типы алгоритмов

На основе перечисленных в разделе 1 структур строятся следующие

типы алгоритмов:

 линейный (на основе структуры следование); характеризуется

тем, что все действия, определяемые символами, входящими в

схему, выполняются последовательно, в порядке их написания;

селектор

 разветвляющийся (на основе структур ветвление и выбор):

характеризуется тем, что в ходе выполнения, решение задачи идет

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

зависит от выполнения заданного условия:

 циклический (на основе структуры цикл): характеризуется

многократным повторением определенной группы действий.

В последующих разделах на конкретных примерах рассматриваются

все вышеперечисленные типы алгоритмов.

Сразу же оговоримся, что в рассмотренных примерах исходные данные

задаются корректно, т.е. например, если в расчете функции (пример 5.1)

используется ln(x), то значение x будет задано большим, чем 0, т.к. в

противном случае произойдет ошибка вычисления (логарифм для х≤0 не

существует). Поэтому схема алгоритма проверки условия х>0 не

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

проверять все вводимые значения на предмет: допустимы ли они или нет.

3. Линейные алгоритмы

Пример 3.1. Вычислить значение функции

















zxeb

при известных значениях x, y и z.

Решение. Исходными данными для расчета

являются значения x, y и z. Их значения нужно

ввести с какого – либо устройства. Значение b

становится известными только после расчета по

формуле. Тогда, чтобы оно стало известно нам, его

нужно вывести на устройство вывода.

Схема алгоритма представлена на рис. 3.1.

Рис.3.1. Схема алгоритма к примеру 3.1.

Замечание. Алгоритм предусматривает вывод не только полученного

результата, но и всех введенных исходных данных. Это следует делать всегда

по двум причинам:

начало

Ввод

x,y,z

















zxeb

конец

Вывод

x,y,z,b

 Появляется возможность контроля правильности ввода данных;

 Если результат выводится в виде распечатки на принтер, всегда

можно видеть, при каких исходных данных он получен

Пример 3.2. Вычислить высоту и площадь равнобедренного

треугольника с основанием а и углом при основании



Решение. Высоту h и площадь S такого треугольника можно рассчитать

по следующим формулам

Stg







Следовательно, исходными данными,

которые нужно ввести, являются

здесь значения а и



, а результатами,

подлежащими выводу – h и s. Схема

алгоритма представлена на рис. 3.2.

Рис. 3.2. Схема алгоритма к примеру 3.2.

4. Разветвляющийся алгоритм



 

начало

Ввод

а и 



h 

конец

Вывод



,h,s





Пример 4.1. Даны численные значения двух величин a и b. Если

b=0, то найти наименьшее из a или b; если b <0, то найти наибольшее из a

или b. В противном случае, каждое значение увеличить на 20%.

Решение. Нахождение наименьшего (наибольшего) из двух чисел

осуществим их простым сравнением a<b (или a>b), причем для упрощения

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

за минимальное. Схема алгоритма приводится на рис.4.1.

Рис.4.1. Схема алгоритма примера 4.1.

Замечание . Для выбора направления решения по условиям b=0, b<0 и

b>0 вместо структуры "ветвление" можно было воспользоваться структурой

"выбор".

Пример 4.2. Вычислить функцию

вывод

да

начало

да нет

a<b

b=0

b<0

вывод

a>b

вывод

a=1,2·a

b=1,2·b

конец

нет

да

нет

да

вывод

а,b

ввод a,b

вывод a,b

нет

















)3( sin

)2( 1000,lg

)1( 10,

случаяхостальныхвx

xеслиx



Кроме значения функции вывести номер формулы, по которой

производился расчет.

Решение. Обозначим номер формулы, по которой производился расчет

через n. В схеме алгоритма предусмотрим присваивание n значения 1,2 или

3, в зависимости от того, по какой формуле производился расчет. Выбор

расчетной формулы проведем на основе следующего анализа:

Схема алгоритма представлена на рис.4.2

5. Циклические алгоритмы

5.1. Организация циклов с предусловием и постусловием

Как уже отмечалось в разделе 2, в типовую структуру цикл входит две

разновидности: цикл с предусловием и цикл с постусловием. Обе они

реализуются одним и тем же набором символов (рис.5.1.), которые

выполняют следующие действия:

 – задание начального значения параметру цикла;

 – проверка условия: для а) – возможности выполнения

цикла; для б) – возможности выхода из цикла;

 – рабочая часть цикла (тело цикла);

 – блок модификации (изменения) параметра цикла; если

этот блок в схеме будет пропущен, то, как правило,

возникает ситуация, когда цикл будет выполняться

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

неизменным. Говорят, что в этом случае имеет место

бесконечный цикл.

Как видно из приведенных схем, в случае а) сначала проверяется

условие: можно ли выполнить цикл, и, если ответ положительный, то цикл

выполняется. В случае б) сначала выполняется цикл, а затем проверяется

условие: можно ли выйти из цикла, и, если ответ положительный, то работа

цикла завершается.

(3) (1)

(2)

1000

+

-