III Алгоритмизация
Изображение алгоритмов
Этапы решения задач с помощью ЭВМ
Решения задачи обработки информации с помощью ЭВМ складывается из нескольких этапов. Обычно выделяют:
- Корректную постановку задачи.
- Выбор метода решения задачи.
- Построение алгоритма реализации выбранного метода решения.
- Кодирование алгоритма для выполнения решения с помощью ЭВМ (написание программы).
- Перевод программы в программу в машинных кодах (трансляция)
- Отладка программы.
- Выполнение расчетов (обработка данных созданной программой)
В этом разделе рассматриваем этап построения алгоритмов.
Основные определения
АЛГОРИТМОМ НАЗЫВАЕТСЯ КОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ТОЧНЫХ ПРЕДПИСАНИЙ, ОДНОЗНАЧНО ОПРЕДЕЛЯЮЩАЯ ПРОЦЕСС ОБРАБОТКИ ДАННЫХ В РЕЗУЛЬТАТЕ РЕШЕНИЯ ЗАДАЧИ.
Программа - это алгоритм, записанный на строгом (однозначном) алгоритмическом языке, который с помощью специальных средств (транслятора) может быть автоматически переведен в программу в машинных кодах.
Основные свойства алгоритмов
Алгоритм должен обладать четырьмя необходимыми свойствами, которые называются основными свойствами алгоритма:
1 - ДИСКРЕТНОСТЬ - представимость алгоритма в виде отдельных шагов, каждый из которых описывает некоторое законченное действие.
2 - КОНЕЧНОСТЬ - достижение поставленной цели за ограниченное число шагов.
3 - ОДНОЗНАЧНОСТЬ - получение одних и тех же результатов при одних и тех же исходных данных, сколько бы раз алгоритм не выполнялся.
4 - МАССОВОСТЬ - применимость алгоритма к некоторому множеству наборов исходных данных.
Способы изображения алгоритмов
Существует три способа изображения (записи) алгоритмов.
Во-первых, алгоритм можно записать на естественном (человеческом) языке. Достоинства этого способа - простота описания (не требуются специальные знания), понятность алгоритма "в общем" в случаях не длинных описаний.
Недостатки – неточность в деталях из-за многозначности человеческих языков, плохая обозримость подробных алгоритмов. Обычно этим способом описания
пользуются для укрупненных (обобщенных) алгоритмов, особенно на функциональном уровне описания.
Во-вторых, его можно записать на формальном (искусственном) однозначном языке (алгоритмическом языке). Достоинствами этого способа являются однозначность и строгость описания, простота последующего создания программы (если для используемого алгоритмического языка есть транслятор - текст алгоритма уже является программой, в противном случае требуется простой перевод на другой алгоритмический язык). Описание алгоритма обычно короче, чем на естественном языке.
Недостатками этого способа являются плохая обозримость больших алгоритмов, сложность описания с требуемой детализацией (подробностью). В процессе построения алгоритма, в нем сложно делать исправления.
Обычно этот способ используют для описания подпрограмм или функций в сборниках алгоритмов.
В-третьих, алгоритм можно записать в условных обозначениях графическим способом. Достоинствами являются возможность описать алгоритм с любой степенью подробности, хорошая наглядность, удобства внесения изменений. В качестве недостатка можно назвать необходимость знать специальные правила графического способа изображения и иметь средства аккуратного выполнения рисунков алгоритма (желательно - автоматизированные средства – графический редактор).
Графический способ
Рассмотрим подробнее графический способ, как наиболее часто используемый.
Так как алгоритм есть последовательность шагов (действий), в его записи нужно изобразить и сами действия и указывать их последовательность. Существует несколько разновидностей графического способа, наиболее распространенным является метод блок-схем. В нем действия изображаются стандартными блоками, а их последовательность - однонаправленными линиями. Существует довольно большой набор различных видов блоков, однако на практике обычно используют не более десятка блоков. Их изображение и назначение представлено в следующей таблице.
Основные элементы блок-схем Таблица 2.
| Обозначение | Наименование | Назначение, примечания |
  
| Процесс | Основной блок обработки данных. В укрупненной блок-схеме - для описания любых процессов, в детальных - для присваивания переменным значений выражений |
| Предопределенный процесс | Обращение (вызов) предопределенных алгоритмов(подпрограмм) Внутри указывается имя п/п. |
 
| Ввод/Вывод | Чтение и запись данных в файлы на магнитных носителях. Часто используется для обозначения только процесса ввода данных с любого устройства ввода |
| Ввод файла | Раньше использовался для ввода данных с перфокарт. Может применяться для любого ввода, в том числе ручного ввода с клавиатуры |
 
| Печатный документ | Применяется для обозначения вывода результатов пользователю на принтер или на дисплей, часто и для вывода на внешнюю память |
  
| Решение | Выбор одного из двух альтернативных путей. Внутри - логическое выражение, у выходов обозначения "да" и "нет" (по истинности и ложности значения) |
   
| Модификатор | Блок, используемый для организации арифметических циклов. Устанавливает начальное значение, модифицирует счетчик цикла, проверяет необходимость выхода |
| Начало алгоритма | Начало программы или подпрограммы (для п/п внутри - имя) |
| Конец алгоритма | Конец программы или выход из подпрограммы (для п/п внутри ставится слово "возврат") |
  
| Межстраничный и внутристраничный соединитель | Передача управления на блок, расположенный на другой или на той же странице. N - номер страницы, n - номер соединителя на странице |
Лекция 13
Правила изображения алгоритмов
Любой алгоритм можно изобразить, используя только блоки "начало", "процесс", "ввод", "вывод" "решение" и "конец", хотя размер блок-схемы при этом может сильно возрасти. Использование модификаторов, переключателей (не показанных в таблице) и особенно предопределенных процессов существенно сокращает блок-схему.
Блоки изображаются в габаритах блока процесс, кроме начала, конца и модификатора, которые имеют половинную высоту. У каждого блока может стоять номер, используемый не для указания последовательности выполнения блоков, а для удобства ссылок на них в пояснениях. Нумерация обычно возрастает сверху вниз и слева направо. Номер ставится либо слева вверху над блоком, либо в разрыве линии контура блока (см. ниже).
 | |
Рисунок 2. Нумерация блоков при изображении алгоритма.
При изображении блоков в алгоритме следует придерживаться следующих правил:
- всякий блок кроме "начала" и "модификатора" имеет только один вход;
- всякий блок, кроме "решения", "модификатора", "переключателя" и "конца" имеет только один выход;
- "решение" имеет один вход и два выхода (по истинности и ложности условия в момент проверки);
- "модификатор" имеет основной вход, основной выход, внутренний вход и выход;
- "переключатель" имеет один вход и несколько выходов.
Линии передачи управления могут соединяться (сливаться) но не могут разъединяться или пересекаться. Для исключения пересечения используются соединители. На линиях могут ставиться стрелки, хотя направления сверху вниз и слева направо обычно не помечаются.
В алгоритмах не должно быть тупиков, зацикливаний, должен быть один вход и один выход. От входа к выходу каждый блок должен принадлежать какому-либо из путей (ветвей алгоритма).