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

• а) Повседневная жизнь: Алгоритм мытья посуды (повторять: взять тарелку, намылить, смыть, поставить сушиться, пока вся грязная посуда не закончится).
• б) Литературное произведение: Алгоритм из сказки «Колобок» (повторять: встретить животное, спеть песенку, убежать, пока не встретится Лиса).
• в) Предметная область (математика): Алгоритм нахождения наибольшего общего делителя (НОД) двух чисел методом Евклида (повторять: заменять большее число разностью чисел, пока числа не станут равны).

Алгоритм использует цикл-ДО с постусловием, то есть тело цикла выполняется, пока условие \( m < 6 \) ложно (пока \( m \ge 6 \)). Начальные значения: \( n = 1 \), \( m = 15 \).

Итоговые значения: \( n = 32 \), \( m = 5 \).

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

• а) Да, согласен. Циклические алгоритмы (конструкция «повторение») позволяют описать многократное повторение большого количества шагов в очень компактной форме. Например, цикл «нц 1000 раз <действие> кц» описывает 1000 выполнений <действия>.
• б) Нет, не совпадают. Краткость алгоритма (в плане записи кода) не всегда означает высокую скорость его выполнения. Циклический алгоритм может быть очень кратким, но содержать большое число итераций, что потребует много времени для выполнения. И наоборот, длинный линейный алгоритм может выполниться быстрее, чем очень короткий алгоритм с вложенными циклами, выполняющими многократные сложные вычисления.

Это задание для цикла-ПОКА, так как размеры области неизвестны.

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

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

алг УгловойОбход
нач
  закрасить
  нц 4 раз 
    нц пока справа свободно
      вправо
      закрасить
    кц
    вправо; вправо
    закрасить
  кц
кон

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

Алгоритм использует цикл-ПОКА или цикл-ДО, последовательно уменьшая число делением на 10 и подсчитывая количество операций. Начальный счетчик цифр \( k = 0 \).

Описание блок-схемы (цикл-ДО):

• Начало
• Ввод числа \( N \).
• Присвоение \( K := 0 \).
• Начало цикла-ДО:
• Тело цикла: \( N := \lfloor N / 10 \rfloor \) (целочисленное деление).
• Тело цикла: \( K := K + 1 \).
• Условие (после): \( N = 0 \).
• Вывод \( K \).
• Конец.

Если используется цикл-ПОКА, то условие будет \( N > 0 \), и цикл может не выполниться, если \( N = 0 \). Для натурального числа \( N \ge 1 \) цикл-ДО (\( N = 0 \)) более естественен, но и цикл-ПОКА (\( N > 0 \)) сработает.

Данная последовательность является арифметической прогрессией с первым членом \( a_1 = 5 \) и разностью \( d = 4 \). Общий член: \( a_i = 5 + ( i - 1 ) \cdot 4 \).

Алгоритм должен суммировать члены, пока сумма \( S \) не достигнет или не превысит 324.

• Начало
• Присвоение: \( S := 0 \) (текущая сумма), \( A := 5 \) (текущий член), \( i := 1 \) (счетчик членов).
• Цикл-ПОКА (\( S < 324 \)):
• Тело цикла: \( S := S + A \).
• Тело цикла: Если \( S \ge 324 \), то прервать цикл.
• Тело цикла: \( A := A + 4 \) (следующий член).
• Тело цикла: \( i := i + 1 \).
• Вывод \( i - 1 \) (количество членов, сумма которых равна или превышает 324).
• Конец

Примечание: Фактически в данном случае сумма 324 будет достигнута ровно на 12-м члене (проверка: \( S_{12} = \frac{12 \cdot ( 2 \cdot 5 + 11 \cdot 4 )}{2} = 6 \cdot ( 10 + 44 ) = 6 \cdot 54 = 324 \)). Алгоритм должен остановиться, когда \( S = 324 \), и вывести \( i \).

Алгоритм использует цикл-ПОКА для нахождения числа лет \( K \).

• Начало
• Присвоение: \( S := 10000 \) (начальная сумма).
• Присвоение: \( K := 0 \) (число лет).
• Цикл-ПОКА (\( S < 20000 \)):
• Тело цикла (увеличение суммы): \( S := S \cdot 1.05 \) ( \( 1 + 5\% = 1 + 0.05 = 1.05 \)).
• Тело цикла (увеличение счетчика лет): \( K := K + 1 \).
• Вывод \( K \).
• Конец

После выполнения цикла \( K \) будет равно минимальному числу лет, за которое сумма достигнет или превысит 20 000 рублей. (Ответ: \( K = 15 \) лет, так как \( 10000 \cdot ( 1.05 )^{14} \approx 19799.31 \), а \( 10000 \cdot ( 1.05 )^{15} \approx 20789.28 \)).

Алгоритм использует цикл-ПОКА, отслеживая количество амеб \( A \) и прошедшее время \( T \).

• Начало
• Ввод требуемого количества амеб \( X \).
• Присвоение: \( A := 1 \) (начальное количество амеб).
• Присвоение: \( T := 0 \) (прошедшее время в часах).
• Цикл-ПОКА (\( A < X \)):
• Тело цикла (удвоение амеб): \( A := A \cdot 2 \).
• Тело цикла (увеличение времени): \( T := T + 3 \).
• Вывод \( T \).
• Конец

Используем цикл с переменной для фиксированного числа повторений \( n=3 \). Начальная численность \( P = 40000 \).

• Начало
• Присвоение: \( P := 40000 \) (начальная численность).
• Цикл-ДЛЯ \( i \) от 1 до 3:
• Тело цикла: \( P := P \cdot 1.05 \).
• Вывод \( P \).
• Конец

Трассировка:

Через 3 года население составит 46 305 человек.

Используем цикл с переменной для фиксированного числа повторений \( n=10 \) (так как деление происходит каждую минуту в течение 10 минут). Начальное количество бактерий \( B = 1 \).

• Начало
• Присвоение: \( B := 1 \) (начальное количество).
• Присвоение: \( T := 0 \) (время в минутах).
• Цикл-ДЛЯ \( i \) от 1 до 10:
• Тело цикла: \( B := B \cdot 2 \) (удвоение количества).
• Тело цикла: \( T := T + 1 \).
• Вывод \( B \).
• Конец

Трассировка: Количество бактерий \( B \) через 10 минут будет \( 1 \cdot 2^{10} = 1024 \).

Алгоритм использует цикл с заданным числом повторений \( k = 6 \). Внутри цикла происходит два смещения. Сначала найдем суммарный вектор смещения \(( \Delta x, \Delta y )\) за одну итерацию:

• \(\Delta x = 4 + ( -2 ) = 2 \)
• \(\Delta y = 6 + ( -4 ) = 2 \)

Итоговое смещение за весь цикл (\( k = 6 \) раз):

• Общее смещение по \( x \): \( 6 \cdot \Delta x = 6 \cdot 2 = 12 \)
• Общее смещение по \( y \): \( 6 \cdot \Delta y = 6 \cdot 2 = 12 \)

Если Чертежник был в \(( x_0, y_0 )\), то он окажется в точке \(( x_0 + 12, y_0 + 12 )\).

Условие возврата в исходную точку означает, что общее смещение \(( \Sigma \Delta x, \Sigma \Delta y )\) равно \(( 0, 0 )\).

1. Суммарный вектор смещения внутри цикла (7 раз):

• Смещение по \( x \) за одну итерацию: \( \Delta x_{\text{цикл}} = 0 + a + 0 + ( -1 ) = a - 1 \)
• Смещение по \( y \) за одну итерацию: \( \Delta y_{\text{цикл}} = 2 + 0 + b + 0 = 2 + b \)

2. Общее смещение за цикл (7 итераций):

• \(\Delta X_{\text{цикл}} = 7 \cdot ( a - 1 ) \)
• \(\Delta Y_{\text{цикл}} = 7 \cdot ( 2 + b ) \)

3. Общее смещение за весь алгоритм:

• Общее смещение по \( X \): \(\Sigma \Delta x = 7 \cdot ( a - 1 ) + ( -7 ) = 0 \)
• Общее смещение по \( Y \): \(\Sigma \Delta y = 7 \cdot ( 2 + b ) + 7 = 0 \)

4. Решение уравнений:

• По оси \( X \): \( 7 \cdot ( a - 1 ) - 7 = 0 \Rightarrow 7 a - 7 - 7 = 0 \Rightarrow 7 a = 14 \Rightarrow a = 2 \)
• По оси \( Y \): \( 7 \cdot ( 2 + b ) + 7 = 0 \Rightarrow 14 + 7 b + 7 = 0 \Rightarrow 7 b = -21 \Rightarrow b = -3 \)

Числа, которые нужно записать: \( a = 2 \), \( b = -3 \).

Предполагаем, что сетка рисуется в первом квадранте, и используется команда «опустить/поднять перо».

• а) Прямоугольная сетка (горизонтальные линии):

Начальная позиция \(( 0, 0 )\). Линии на расстоянии 1 друг от друга, длиной 10.

алг СеткаГоризонтальная
нач
  нц для i от 0 до 10
    сместиться в точку (0, i) ; поднять перо
    опустить перо
    сместиться в точку (10, i)
    поднять перо
  кц
кон

• б) Сетка из наклонных параллельных линий:

Идея: Рисовать линии, которые начинаются на оси Y и заканчиваются на оси X. Длина и угол зависят от шага.

алг СеткаНаклонная
нач
  нц для i от 0 до 10
    сместиться в точку (0, 10 - i) ; поднять перо (начало на Y)
    опустить перо
    сместиться в точку (i, 0) ; конец на X
    поднять перо
  кц
кон

Лабиринт представляет собой коридор, окруженный стенами, с поворотами и выходом справа. Поскольку используются 4 повторения, это означает, что Робот должен совершить 4 поворота (для 4-х сторон квадратного пути).

алг ВыходИзЛабиринта
нач
  нц 4 раз 
    нц пока снизу свободно
      вперед
    кц
    вправо ; поворот на 90 градусов
    вправо
    вправо
    нц пока сверху свободно
      вперед
    кц
  кц
  вправо ; вправо
  нц пока впереди свободно
    вперед
  кц
кон

Примечание: Исполнитель Робот в КуМире имеет ограниченный набор команд (вперед, вправо, влево, закрасить, если ...), и 7 команд в теле цикла, который выполняется 4 раза для выхода из лабиринта, является очень специфическим и сложным условием. Приведенный пример – концептуальный, основанный на движении вдоль стен и поворотах на углах.

Исследование алгоритма:

• Внутренний цикл: «нц 4 раз вперед \(( 50 )\) вправо \(( 90 )\) кц». Этот цикл рисует квадрат со стороной 50, так как 4 повторения и поворот на 90 градусов.
• Внешний цикл: «нц 10 раз ... вправо \(( 36 )\) кц». Этот цикл повторяет рисование квадрата 10 раз, каждый раз поворачивая Черепаху на 36 градусов вокруг центральной точки.
• Результат: В итоге Черепаха рисует 10 квадратов, которые повернуты относительно друг друга на 36 градусов. Поскольку \( 10 \cdot 36^\circ = 360^\circ \), после 10 повторений Черепаха возвращается в исходное положение, формируя узор, похожий на цветок или звезду из 10 квадратов.

Варианты модификации:

• Изменение фигуры: Заменить 4 повторения на другое число, например, «нц 6 раз вперед \(( 40 )\) вправо \(( 60 )\) кц» для рисования треугольника (поворот \( 180 - 60 = 120^\circ \)).
• Изменение количества фигур: Уменьшить или увеличить 10 повторений внешнего цикла, например, на 5 раз. Тогда поворот должен быть \( 360 / 5 = 72^\circ \).
• Создание спирали: Включить изменение размера стороны в тело внешнего цикла, например, «вперед \(( i \cdot 5 )\) вправо \(( 90 )\)» для создания спирального квадрата.
• Сплошное заполнение: Изменить поворот на 10-20 градусов для получения более плотного узора или «заполнения» области.