Краткое содержание: Параграф § 1.1 / Информатика 9 класс

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

Процесс конструирования (разработки) алгоритма для решения сложной задачи обычно включает ее разбиение на более простые подзадачи. Для решения таких подзадач используются вспомогательные алгоритмы. В разделе рассматриваются два основных метода разработки алгоритмов:

• Метод разработки «сверху вниз», также известный как метод последовательного уточнения или метод пошаговой детализации.
• Метод разработки «снизу вверх».

Метод «сверху вниз» — это процесс последовательного уточнения алгоритма. На первом этапе предполагается наличие «совершенного» исполнителя, который «все знает и все умеет», и определяется постановка задачи. Если исполнитель не может выполнить заданное предписание, оно представляется в виде совокупности более простых команд. Задача разбивается на части, решение каждой из которых формулируется в виде отдельной команды. Если и эти команды выходят за пределы возможностей исполнителя, они снова уточняются в виде более простых предписаний. Процесс продолжается до тех пор, пока все предписания не станут понятны исполнителю. Объединение полученных предписаний дает требуемый алгоритм.

Метод «снизу вверх» предполагает, что сначала разрабатывается множество небольших вспомогательных алгоритмов (библиотека), которые могут быть использованы для решения задач определенного класса. После этого разрабатывается основной алгоритм, содержащий обращения к алгоритмам из библиотеки.

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

Для записи алгоритмов используются базовые алгоритмические конструкции:

• Следование (линейный алгоритм): последовательное выполнение команд друг за другом.
• Ветвление: организация действий в зависимости от условия (команды если <условие> то <команда 1> иначе <команда 2> все).
• Цикл: многократное повторение последовательности команд. В учебнике рассматриваются два типа циклов:
  • Цикл с заданным числом повторений (нц k раз <последовательность команд> кц).
  • Цикл с условием (нц пока <условие> <последовательность команд> кц).

Вспомогательные алгоритмы и рекурсия

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

Процесс вызова вспомогательного алгоритма состоит из нескольких шагов: 1) формальные входные данные заменяются значениями фактических входных данных; 2) для заданных входных данных исполняются команды вспомогательного алгоритма; 3) полученные результаты присваиваются переменным, обозначенным как фактические результаты; 4) осуществляется переход к следующей команде основного алгоритма.

Локальные переменные — это имена и типы переменных, объявленные как формальные параметры внутри вспомогательного алгоритма и невидимые в основном алгоритме. При необходимости работы с переменными как в основном, так и во вспомогательном алгоритмах, они объявляются как глобальные.

Рекурсивный алгоритм — это алгоритм, в котором прямо или косвенно содержится ссылка (вызов) на него самого как на вспомогательный алгоритм. Примерами рекурсивных алгоритмов являются вычисление степени числа \( a^n \) и построение фрактальной фигуры, такой как снежинка Коха.

Исполнители и их системы команд

В качестве примеров формальных исполнителей рассматриваются:

• Исполнитель Робот, действующий на клетчатом поле с возможными стенами. Его команды включают перемещение (вверх, вниз, вправо, влево), закрашивание клетки (закрасить) и проверку условий (сверху свободно, снизу стена, клетка закрашена и т.д.).
• Исполнитель Черепаха, который перемещается по экрану компьютера в квадратном окне со стороной \( 500 \) пикселей и может рисовать кончиком хвоста. Его система команд включает: поднять хвост, опустить хвост, вперед (n), назад (n), вправо (m), влево (m), где \( n \) — это количество шагов, а \( m \) — угол поворота в градусах.