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

Алгоритмы называют линейными, если они используют только одну базовую алгоритмическую конструкцию — следование. Последовательность выполнения действий в линейном алгоритме не зависит от исходных данных, поскольку все шаги выполняются строго один за другим без каких-либо условий или выбора.

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

• Синтаксические ошибки: Возникают из-за неправильной записи команд, например, из-за опечаток. Эти ошибки обычно легко обнаруживаются системой и могут быть быстро исправлены.
• Логические ошибки: Возникают в логике самого алгоритма. Они приводят либо к отказу выполнения (исполнитель не может выполнить команду), либо к завершению программы, но с результатом, который не соответствует поставленной задаче.

• Из повседневной жизни: Последовательность действий при чистке зубов: взять щетку, нанести пасту, чистить верхние зубы, чистить нижние зубы, ополоснуть рот, помыть щетку.
• Из литературного произведения: Рецепт приготовления блюда, где все шаги выполняются строго по порядку (например, заваривание чая).
• Из любой школьной предметной области: Алгоритм перевода температуры из градусов Цельсия в градусы Кельвина: \( K := C + 273.15 \).

[Изображение узора - две клетки вправо, одна клетка вниз, одна клетка влево, одна клетка вниз. Затем возвращение в исходную точку (ромб в верхнем левом углу). Предполагается, что начальная позиция (ромб) — это верхняя левая клетка поля 3x3, и Робот начинает изнутри этой клетки.]

Алгоритм для Робота:

• использовать Робот
• вправо (переход)
• закрасить
• вправо (переход)
• закрасить
• вниз (переход)
• закрасить
• влево (переход)
• закрасить
• вниз (переход)
• закрасить
• влево (переход)
• вверх (переход)
• влево (переход)
• вверх (переход)
• конец

Восстановим формулу, следуя шагам:

• \( a1 := 1 / x \)
• \( a2 := a1 / x \) (т.е. \( a2 = (1 / x) / x = 1 / x^2 \))
• \( a3 := a2 / x \) (т.е. \( a3 = (1 / x^2) / x = 1 / x^3 \))
• \( a4 := a3 / x \) (т.е. \( a4 = (1 / x^3) / x = 1 / x^4 \))
• \( y := y + a1 \)
• \( y := y + a2 \)
• \( y := y + a3 \)
• \( y := y + a4 \)

Если предположить, что начальное значение \( y \) равно 0, то окончательная формула будет:\[ y = \frac{1}{x} + \frac{1}{x^2} + \frac{1}{x^3} + \frac{1}{x^4} \] (Если же \( y \) имеет начальное значение \( y_0 \), то \( y = y_0 + \frac{1}{x} + \frac{1}{x^2} + \frac{1}{x^3} + \frac{1}{x^4} \)).

Проследим изменение переменной \( y \) при \( x = 1 \):

• Исходное: \( x = 1 \)
• \( y := 2 \cdot x \): \( y = 2 \cdot 1 = 2 \)
• \( y := y + 3 \): \( y = 2 + 3 = 5 \)
• \( y := y \cdot x \): \( y = 5 \cdot 1 = 5 \)
• \( y := y - 4 \): \( y = 5 - 4 = 1 \)
• \( y := y \cdot x \): \( y = 1 \cdot 1 = 1 \)
• \( y := y + 5 \): \( y = 1 + 5 = 6 \)

Окончательное значение переменной \( y \) равно 6.

Восстановим формулу, подставляя каждое действие в предыдущее выражение для \( y \):

• \( y_1 = 2x \)
• \( y_2 = y_1 + 3 = 2x + 3 \)
• \( y_3 = y_2 \cdot x = (2x + 3) \cdot x = 2x^2 + 3x \)
• \( y_4 = y_3 - 4 = 2x^2 + 3x - 4 \)
• \( y_5 = y_4 \cdot x = (2x^2 + 3x - 4) \cdot x = 2x^3 + 3x^2 - 4x \)
• \( y_6 = y_5 + 5 = 2x^3 + 3x^2 - 4x + 5 \)

Итоговая формула: \[ y = 2x^3 + 3x^2 - 4x + 5 \]

Будем переводить последовательно:

• Мили в версты: \( V := M \cdot 1.5 \)
• Версты в сажени: \( S_a := V \cdot 500 \)
• Сажени в аршины: \( A := S_a \cdot 3 \)
• Аршины в дюймы: \( D := A \cdot 28 \)
• Дюймы в миллиметры: \( MM := D \cdot 25.4 \)
• Миллиметры в километры: \( K := MM / 1000000 \)

Итоговый алгоритм для перевода \( M \) миль в \( K \) километров:

• \( K := M \cdot 1.5 \)
• \( K := K \cdot 500 \)
• \( K := K \cdot 3 \)
• \( K := K \cdot 28 \)
• \( K := K \cdot 25.4 \)
• \( K := K / 1000000 \)

Можно также использовать единое выражение: \( K := M \cdot 1.5 \cdot 500 \cdot 3 \cdot 28 \cdot 25.4 / 1000000 \)

Пусть \( x \) — трехзначное число, которое можно представить как \( 100a + 10b + c \), где \( a \), \( b \), \( c \) — его цифры (причем \( a \in \{1..9\}, b, c \in \{0..9\} \)).

• \( a := x \text{ div } 100 \): Получает первую (сотни) цифру числа \( x \).
• \( x \text{ mod } 10 \): Эта операция неверно записана в условии. Должно быть \( x \text{ div } 10 \text{ mod } 10 \) для получения средней цифры. Если следовать алгоритму как есть, то \( b \) будет 0, поскольку \( x \text{ mod } 10 \) — это последняя цифра \( c \), а \( c \text{ div } 10 \) (целочисленное деление) всегда 0. Предположим, что \( b \) вычисляет среднюю цифру, то есть \( b := x \text{ div } 10 \text{ mod } 10 \).
• \( c := x \text{ mod } 10 \): Получает третью (единицы) цифру числа \( x \).
• \( s := a + b + c \): Вычисляет сумму цифр числа \( x \).

Смысл результата \( s \) — это сумма цифр исходного трехзначного числа \( x \).

Проследим изменение переменных. Начальные значения: \( x = 336 \), \( y = 8 \).

1. \( x := x \text{ div } y \): \( x = 336 \text{ div } 8 = 42 \)
2. \( x := x \text{ mod } y \): \( x = 42 \text{ mod } 8 = 2 \)
3. \( y := x \text{ div } y \): \( y = 2 \text{ div } 8 = 0 \)
4. \( y := x \text{ mod } y \): \( y = 2 \text{ mod } 0 \) (Ошибка: деление на ноль! В учебнике, вероятно, предполагалась другая логика или другие команды. Если бы последняя команда была \( y := y \text{ mod } x \), ответ был бы \( y = 0 \text{ mod } 2 = 0 \)).

Если последняя команда не должна вызывать ошибку (например, опечатка в условии):

• Итоговые значения, следуя точному алгоритму (но с ошибкой): \( x = 2 \), \( y \) - не определено (ошибка деления на ноль).
• Если считать, что \( y \) в последней строке должно быть \( x \): \( y := x \text{ mod } x \): \( y = 2 \text{ mod } 2 = 0 \). Тогда \( x = 2 \), \( y = 0 \).

Предположим, что последние две строки перепутаны и должны быть:

• \( y := y \text{ div } x \): \( y = 8 \text{ div } 42 = 0 \)
• \( y := y \text{ mod } x \): \( y = 0 \text{ mod } 42 = 0 \)

Наиболее вероятный ответ, учитывая целочисленную арифметику: \( x = 2 \), \( y = 0 \) (при условии исправления ошибки деления на ноль в последней строке).

Запишем последовательность действий, начиная с числа 4:

• Начальное число: 4
• Команда 1 («Прибавь 2»): \( 4 + 2 = 6 \)
• Команда 2 («Умножь на \( a \)»): \( 6 \cdot a = 6a \)
• Команда 2 («Умножь на \( a \)»): \( 6a \cdot a = 6a^2 \)
• Команда 1 («Прибавь 2»): \( 6a^2 + 2 \)
• Команда 1 («Прибавь 2»): \( 6a^2 + 2 + 2 = 6a^2 + 4 \)

По условию, конечный результат равен 100. Составим и решим уравнение:

Поскольку \( a \) — натуральное число, то \( a = 4 \).