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

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

Рассмотрим пример. В школьном учебнике математики правила деления обыкновенных дробей описаны так:

1) числитель первой дроби умножить на знаменатель второй дроби;

2) знаменатель первой дроби умножить на числитель второй дроби;

3) записать дробь, числитель которой есть результат выполнения пункта 1, а знаменатель – результат выполнения пункта 2. В алгебраической форме это выглядит следующим образом:

Построим алгоритм деления дробей для ЭВМ. В этом алгоритме сохраним те же обозначения для переменных, которые использованы в записанной выше формуле. Исходными данными являются целочисленные переменные а, b, с, d. Результатом – также целые величины. Блок-схема и текст алгоритма на учебном алгоритмическом языке приведены ниже.

Формат команды присваивания следующий:

Переменная := выражение.

Знак «:=» нужно читать как «присвоить».

Команда присваивания обозначает следующие действия, выполняемые компьютером.

1. Вычисляется выражение.

2. Полученное значение присваивается переменной.

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

В описаниях алгоритмов необязательно соблюдать строгие правила в записи выражений. Их можно писать в обычной математической форме. Это еще не язык программирования со строгим синтаксисом.

В приведенном алгоритме присутствует команда ввода:

ввод a,b,c,d.

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

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

вывод m,n.

С помощью этой команды результаты выводятся на экран или на устройство печати на бумагу.

Рассмотрим последовательное выполнение четырех команд присваивания, в которых участвуют две переменные величины а и b.

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

Таблица 3.14

Значения переменных

Этот пример иллюстрирует три основных свойства команды присваивания:

- пока переменной не присвоено значение, она остается неопределенной;

- значение, присвоенное переменной, сохраняется в ней вплоть до выполнения следующей команды присваивания этой переменной;

- новое значение, присваиваемое переменной, заменяет ее предыдущее значение.

Рассмотрим один алгоритм, который приходится часто использовать при программировании. Даны две величины: X и Y. Требуется произвести между ними обмен значениями. Например, если первоначально было Х = 1, Y = 2, то после обмена должно стать: Х = 2, Y = 1.

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

- перелить из первого стакана в третий;

- перелить из второго в первый;

- перелить из третьего во второй.

По аналогии для обмена значениями двух переменных нужна третья дополнительная переменная. Назовем ее Z. Тогда задача обмена решается последовательнымвыполнением трех команд присваивания (табл. 3.15):

Таблица 3.15

Решение задачи обмена

Аналогия со стаканами не совсем точна в том смысле, что при переливании из одного стакана в другой первый становится пустым. В результате же присваивания (Х: = Y) переменная, стоящая справа (Y), сохраняет свое значение.

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

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