Методические материалы по информатике

Алгоритмы

Алгоритм – точная конечная последовательность команд, приводящая от исходных данных к искомому результату за конечное число шагов. (Слово происходит от имени великого математика IX в. Мухаммеда ибн Мусы аль-Хорезми.)

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

Классификация алгоритмов

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

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

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

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

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

Позволяет описать действия, которые выполняются в зависимости от условия. В простей­шем случае, это ответ на вопрос «Да» или «Нет». Во всех языках программирования эта возможность реализована при помощи оператора ветвления If...[Else]...EndIf.
Может иметь как полную форму, когда действия описаны для обеих ветвей, так и частичную, когда действия производяться только для положительного либо, наоборот, только для отрицательного ответа.

Циклический алгоритм

Циклический алгоритм может иметь несколько вариантов.
• «Для» (For) служит для проведения определенного количества итераций (повторов).
• «Пока» (While|Until) выполняется до тех пор, пока соблюдается определенное условие.
• «Неопределенный цикл» (Do) выполняется бесконечно или пока внутри его тела не выполнится команда принудительного завершения цикла. Чаще всего задается с условием.

В некоторых языках программирования могут использоваться специализированные циклы: для обхода всех элементов набора объектов (For Each) или для просмотра всех записей в таблице базы данных (Scan).
Во всех случаях построения циклического алгоритма нужно внимательно следить за тем, чтобы при его выполнении происходило корректное завершение. Одна из наиболее распространенных ошибок – создание бесконечного цикла, который не завершается никогда.

Вспомогательный алгоритм (подпрограмма)

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

Свойства алгоритмов

• Дискретность. Алгоритм должен быть разделен на простейшие (элементарные) шаги.
• Понятность. Выполняемые действия должны быть понятны исполнителю алгоритма, то есть входить в систему команд исполнителя (СКИ).
• Определенность. Каждое действие должно быть сформулировано так, чтобы не оставалось возможности для произвольных дополнительных рассуждений или вопросов. В результате алгоритм может выполняться механически.
• Результативность. Исполнение алгоритма обязательно должно приводить к конечному результату, соответствующему поставленной цели.
• Массовость (универсальность). Одно из наиболее важных свойств, указывающее на то, что алгоритм должен быть применим к решению некоторого класса задач, различающихся лишь исходными данными.
• Выполнимость. Результат должен быть достигнут за конечное количество шагов.

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

• Словесно-пошаговый.
• Учебный алгоритмический язык.
• Язык программирования.
• Блок-схема.
• Таблица.

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

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

Обозначения в блок-схемах

Оформление блок-схем должно производиться с соблюдением правил ГОСТа.

Вопросы и задачи

1. Найти гипотенузу прямоугольного треугольника по двум известным катетам.
2. Найти катет прямоугольного треугольника по известным гипотенузе и второму катету.
3. Построить алгоритм нахождения всех натуральных решений уравнения y = x², для y < 100.
4. Построить алгоритм нахождения всех натуральных решений уравнения y = x³, для y < 100.