Основы алгоритмизации

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

Существуют различные способы записи алгоритмов. Основными среди них являются:

•  словесные;

•  графические;

•  на алгоритмических языках.

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

Словесное описание. Самой простой является запись алгоритма в виде набора высказываний на обычном разговорном языке. Словес­ное описание имеет минимум ограничений и является наименее фор­мализованным. Однако все разговорные языки обладают неоднознач­ностью, поэтому могут возникнуть различные толкования текста ал­горитма, заданного таким образом. Алгоритм в словесной форме может оказаться очень объёмным и трудным для восприятия.

Пример 1. Словесное описание алгоритма нахождения наиболь­шего общего делителя (НОД) пары целых чисел (алгоритм Евклида).

Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы X и У. Запишите первое из заданных чисел в стол­бец X, а второе — в столбец У. Если данные числа не равны, замените большее из них на результат вычитания из большего числа меньшего. Повторяйте такие замены до тех пор, пока числа не окажутся равны­ми, после чего число из столбца X считайте искомым результатом.

Построчная запись. Это запись на естественном языке, но с соблю­дением некоторых дополнительных правил:

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

Кроме слов естественного языка предписания могут содержать ма­тематические выражения и формулы.

Пример 2. Построчная запись алгоритма Евклида.

  1. Обозначить первое из заданных чисел X, второе — У.
  2. Если X = У, то перейти к п. 8.
  3. Если X > У, то перейти к п. 4, иначе перейти к п. 6.
  4. Заменить X на X - У.
  5. Перейти к п. 2.
  6. Заменить У на У - X.
  7. Перейти к п. 2.
  8. Считать X искомым результатом.

Построчная запись алгоритма позволяет избежать ряда неопре­делённостей; её восприятие не требует дополнительных знаний. Вместе с тем использование построчной записи требует от человека большого внимания.

Блок-схемы

Наилучшей наглядностью обладают графические способы записи алгоритмов. Самый распространённый среди них — блок-схема.

Блок-схема представляет собой графический документ, дающий представление о порядке работы алгоритма. Здесь предписания изо­бражаются с помощью различных геометрических фигур, а последо­вательность выполнения шагов указывается с помощью линий, со­единяющих эти фигуры. Направления линий связи слева направо и сверху вниз считаются стандартными, и линии связи изображаются без стрелок, в противоположном случае — со стрелками.

Рассмотрим некоторые условные обозначения, применяемые в блок-схемах.

Выполнение алгоритма всегда начинается с блока начала и окан­чивается при переходе на блок конца (рис. 3.2, а). Из начального бло­ка выходит одна линия связи; в конечный блок входит одна линия связи.

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

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

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

Комментарии (рис. 3.2, г) используются для добавления поясни­тельных записей, делающих блок-схему более понятной.

Пример 3. Запись алгоритма Евклида с помощью блок-схемы (рис. 3.3)

Алгоритмические

языки

Алгоритмические языки — формальные языки, предназначенные для записи алгоритмов. Каждый из них характеризуется:

  • алфавитом — набором используемых символов;
  • синтаксисом — системой правил, по которым из символов алфави­та образуются правильные конструкции языка;
  • семантикой — системой правил, строго определяющей смысл и способ употребления конструкций языка.

Класс алгоритмических языков очень широк. При изучении курса информатики в школах используются различные версии школьного (учебного) алгоритмического языка.

Школьный алгоритмический язык.

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

В общем виде программу на школьном алгоритмическом языке можно представить так:

  • алг <название алгоритма>
  • нач
  •       <Последовательность команд>
  • кон

Пример 4. Алгоритм, позволяющий из полного сосуда ёмкостью 12 л отлить половину, пользуясь двумя пустыми сосудами ёмкостью 8 и 5 л.

  • алг переливания
  • нач
  •        наполнить сосуд ёмкостью 8 л из сосуда ёмкостью 12 л
  •        наполнить сосуд ёмкостью 5 л из сосуда ёмкостью 8 л
  •        вылить всё из сосуда ёмкостью 5 л в сосуд ёмкостью 12 л
  •        вылить всё из сосуда ёмкостью 8 л в сосуд ёмкостью 5 л
  •        наполнить сосуд ёмкостью 8 л из сосуда ёмкостью 12 л
  •        долить из сосуда ёмкостью 8 л сосуд ёмкостью 5 л
  •        вылить всё из сосуда ёмкостью 5 л в сосуд ёмкостью 12 л
  • кон