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

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

Алгоритмическая конструкция, которая отображает естественный и последовательный порядок действий, называется следованием. Алгоритмы, использующие исключительно эту конструкцию, именуются линейными алгоритмами. Важность этой конструкции была подчеркнута Э. Дейкстрой в 70-х годах прошлого века, который утверждал, что для записи любого алгоритма достаточно трех основных конструкций: следования, ветвления и повторения.

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

Пример 1: Фрагмент линейного алгоритма. Рассмотрим выполнение фрагмента линейного алгоритма с переменными \( x \), \( y \), \( s \). Исходные значения: \( x = 2 \). Последовательность действий:

• \( y := x \cdot x \) (теперь \( y = 2 \cdot 2 = 4 \));
• \( y := y \cdot x \) (теперь \( y = 4 \cdot 2 = 8 \));
• \( x := y \cdot x \) (теперь \( x = 8 \cdot 2 = 16 \));
• \( x := y \cdot x \) (теперь \( x = 8 \cdot 16 = 128 \));
• \( s := x + y \) (теперь \( s = 128 + 8 = 136 \)).

• \( x := 2 \);
• \( y := x \cdot x \) (\( y = 4 \));
• \( y := y \cdot x \) (\( y = 8 \));
• \( x := y \cdot x \) (\( x = 16 \));
• \( x := y \cdot x \) (\( x = 32 \)); - ошибка в оригинальной таблице на стр. 105. В оригинале: 32. Должно быть: \( x = 8 \cdot 16 = 128 \), но в таблице в шаге 3 \( y = 16 \), \( x = 2 \), в шаге 4 \( y = 16 \), \( x = 32 \).
• \( s := x + y \) (\( s = 32 + 16 = 48 \)). - Если следовать таблице.

Операции с целыми числами

При работе с целыми числами используются операции div (целочисленное деление, или неполное частное) и mod (остаток от деления). Например, \( 5 \text{ div } 2 = 2 \), \( 5 \text{ mod } 2 = 1 \). Эти операции часто используются в задачах, связанных с расчетами (например, при определении минимального количества банкнот для выдачи сдачи).

Ограниченность линейных алгоритмов

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

Виды ошибок в алгоритмах

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

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

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