ГДЗ: Параграф § 1.1 / Информатика 9 класс

Два основных подхода к разработке алгоритмов: метод «сверху вниз» (метод последовательного уточнения) и метод «снизу вверх».

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

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

Вспомогательный алгоритм — это алгоритм, целиком используемый в составе другого алгоритма для решения некоторой подзадачи основной задачи.

Формальные параметры — это имена переменных, которые указываются в определении вспомогательного алгоритма и обозначают исходные данные и/или результаты. Фактические параметры — это конкретные значения или переменные, которые используются в момент вызова вспомогательного алгоритма, замещая формальные параметры.

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

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

Пример из жизни: отражение в двух параллельных зеркалах, где каждое отражение содержит в себе уменьшенное отражение другого зеркала (эффект Дросте).

Назначение вспомогательных алгоритмов:

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

Процесс вызова вспомогательного алгоритма:

1. Формальные входные данные заменяются значениями фактических входных данных.
2. Исполняются команды вспомогательного алгоритма с заданными входными данными.
3. Полученные результаты присваиваются переменным, которые являются именами фактических результатов.
4. Осуществляется переход к следующей команде основного алгоритма.

Сложная задача состоит из большого числа шагов и множества взаимосвязанных деталей. Человеку сложно удержать в уме и спланировать наперёд все элементарные действия, необходимые для решения, особенно если часть действий зависит от промежуточных результатов. Использование метода пошаговой детализации позволяет управлять этой сложностью, фокусируясь сначала на общих этапах, а затем постепенно их уточняя.

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

Связь заключается в использовании принципа пошаговой детализации:

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

Укрупнённые блоки алгоритма:

1. Вычислить сумму ростов учеников \( 9 \text{«А»} \) класса.
2. Вычислить средний рост учеников \( 9 \text{«А»} \) класса (\( H_A = S_A / n \)).
3. Вычислить сумму ростов учеников \( 9 \text{«Б»} \) класса.
4. Вычислить средний рост учеников \( 9 \text{«Б»} \) класса (\( H_Б = S_Б / m \)).
5. Сравнить средний рост классов: \( H_A \) и \( H_Б \).
6. Вывести результат сравнения.

Данный алгоритм \( \text{чертеж} \) является рекурсивным, поскольку он вызывает сам себя (\( \text{чертеж}(a-5) \)).

• Основное действие: В цикле нц 4 раз вперед (a); вправо (90) кц Черепаха рисует квадрат со стороной \( a \).
• Рекурсивный вызов: После рисования квадрата вызывается тот же алгоритм, но с уменьшенным параметром стороны: \( a \) становится \( a-5 \).
• Условие остановки: Рекурсия прекращается, когда \( a < -150 \).

Результат: Черепаха будет последовательно рисовать вложенные квадраты. Каждый следующий квадрат будет иметь сторону на \( 5 \) пикселей меньше предыдущего. Так как поворот между вызовами не предусмотрен, все квадраты будут нарисованы из одной точки и будут сориентированы одинаково, создавая эффект уходящей вглубь перспективы или многослойной рамки.

Если начать с положительного \( a \), например, \( a=100 \), квадраты будут уменьшаться: \( 100, 95, 90, \dots \). Если начать с отрицательного \( a \), например, \( a=-100 \), квадраты будут «расти» в обратную сторону: \( -100, -105, -110, \dots \) (команда вперед (a) будет означать движение назад). При \( a=-150 \) или меньше рекурсия остановится.

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

Вспомогательный алгоритм для закрашивания вертикальной линии вниз:

алг vlinia(цел dlina)

нач

нц dlina раз

закрасить

вниз

кц

вверх

кон

Примечание: В конце vlinia Робот возвращается на одну клетку вверх, чтобы не быть в самой нижней клетке.

Основной алгоритм для варианта 'a' (три вертикальные линии):

использовать Робот

алг нач

vlinia(4) // первая линия

вправо // переход

вправо

vlinia(4) // вторая линия

вправо // переход

вправо

vlinia(4) // третья линия

кон

Блок-схема алгоритма нахождения первого простого делителя (рис. 1.3):

Входное значение: \( n \) (натуральное число, \( n > 1 \)).

Инициализация делителя: \( d = 2 \).

Цикл: повторять, пока остаток от деления \( n \) на \( d \) не равен нулю (\( n \bmod d \neq 0 \)):

• увеличить делитель: \( d = d + 1 \).

Выходное значение: \( d \) (первый простой делитель).

Результаты проверки:

• Для \( n = 121 \): \( d \) будет увеличиваться до \( 11 \). \( 121 \bmod 11 = 0 \). Результат: \( 11 \).
• Для \( n = 135 \): \( d \) будет увеличиваться до \( 3 \), \( 135 \bmod 3 = 0 \). Результат: \( 3 \). В условии задания ошибка, для \( 135 \) первый простой делитель — \( 3 \), а не \( 5 \).
• Для \( n = 847 \): \( d \) будет увеличиваться до \( 7 \). \( 847 \bmod 7 = 0 \). Результат: \( 7 \).

Примечание: В соответствии с логикой алгоритма и математическими правилами, первый простой делитель числа \( 135 \) — это \( 3 \). Число \( 5 \) является вторым простым делителем (после деления \( 135 \) на \( 3 \) получаем \( 45 \), \( 45 \bmod 3 = 0 \), далее \( 15 \bmod 3 = 0 \), и только \( 5 \bmod 5 = 0 \)). Если тест \( 135 \to 5 \) должен быть верным, алгоритм должен быть другим (например, поиск наибольшего простого делителя, или условие теста ошибочно). Если следовать блок-схеме, для \( 135 \) результат будет \( 3 \).