§ 10. Линейные вычислительные алгоритмы

Определения и обозначения

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

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

Присваивание — команда, которая вычисляет выражение и записывает полученное значение в переменную. Обычно сначала указывают имя переменной, а затем выражение, например s = v * t. Команда нужна, чтобы сохранить результат и при необходимости использовать его дальше.

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

Как это устроено

Решение вычислительной задачи начинают с определения исходных данных, результата и связи между ними. Это нужно, чтобы понять, какие величины известны, что требуется найти и какой формулой они связаны. Например, для площади прямоугольника известны длины сторон, а искомый результат получают их умножением. После такого разбора проще выбрать нужные переменные и не включать в программу лишние действия.

Затем команды располагают в порядке выполнения. Это важно, потому что более позднее вычисление может зависеть от значения, полученного раньше. Если команда использует промежуточный результат, её ставят после команды, которая этот результат вычисляет. Так программа проходит задачу от исходных данных к ответу, не пытаясь использовать значение, которого ещё нет.

В команде присваивания сначала вычисляют выражение справа от знака, а затем записывают результат в переменную слева. Например, при v = 4 и t = 3 команда s = v * t сначала даёт число 12, после чего s получает это значение. Такой порядок объясняет, почему присваивание нельзя понимать как обычное математическое равенство: переменная слева может получить новое значение.

Промежуточные результаты сохраняют в переменных, когда они нужны в следующих вычислениях. Это позволяет разделить сложную формулу на понятные шаги и не выполнять одни и те же действия повторно. Например, сначала можно найти путь s, а следующей командой использовать s для вычисления другого показателя. Имена переменных подсказывают, что именно хранится в каждой из них.

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

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

Таблица показывает общий ход решения: сначала программа получает исходные значения, затем обрабатывает их и в конце выдаёт ответ. Проверяя алгоритм, сравнивай его команды с этими этапами. Если результат выводится до вычисления или исходных данных не хватает, порядок нужно исправить.

Разбор задач

Задача 1. Составить алгоритм вычисления периметра прямоугольника по заданным длинам сторон a и b. Периметр — сумма длин всех четырёх сторон, то есть две длины a и две длины b. Поэтому формулу можно записать как P = 2 * (a + b), а скобки показывают, что сначала складываются стороны разной длины.

1. Ввести значения a и b, потому что это исходные данные задачи.
2. Вычислить P = 2 * (a + b) и сохранить результат в переменной P.
3. Вывести P, чтобы пользователь получил периметр.

Ответ: последовательность команд — ввод a, b; P = 2 * (a + b); вывод P. Скобки не дают случайно умножить на 2 только одно из слагаемых.

Задача 2. Вычислить y = 3x² − 2x + 1 при заданном x. Формулу надо превратить в команды, сохранив порядок действий: сначала степени и умножение, затем сложение и вычитание. В записи программы умножение указывают явно, поэтому произведения 3x² и 2x записываются как 3 * x * x и 2 * x.

1. Ввести x — без его значения вычислить выражение нельзя.
2. Вычислить y = 3 * x * x − 2 * x + 1, соблюдая порядок операций.
3. Вывести y, чтобы получить значение выражения для введённого x.

Ответ: команды: ввод x; y = 3 * x * x − 2 * x + 1; вывод y. Если в используемом языке программирования есть оператор возведения в степень, можно применить его, но смысл порядка вычислений должен сохраниться.

Задача 3. По начальной скорости v и времени t найти путь при равномерном движении, а затем среднюю скорость на этом пути. Сначала используем формулу s = v * t. Для среднего значения скорости путь нужно разделить на время движения, поэтому следующим шагом будет w = s / t; предполагается, что t не равно нулю.

1. Ввести начальную скорость v и время t.
2. Вычислить s = v * t и сохранить найденный путь.
3. Вычислить w = s / t, используя уже полученное значение s, затем вывести s и w.

Ответ: при t ≠ 0 средняя скорость w равна v, поскольку (v * t) / t = v. Здесь важно сначала найти s: иначе следующая команда использовала бы ещё не вычисленный результат.

Типичные ошибки

Математическое равенство принимают за команду присваивания. В математике равенство утверждает, что две части имеют одинаковые значения, а команда присваивания вычисляет правую часть и меняет значение переменной слева. Путаница возникает из-за похожей записи. Проверь себя: можно ли объяснить, какое значение будет сохранено и в какой переменной?

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

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

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

Связь с другими темами

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

Что запомнить

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