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

 

Алгоритмы, результатами выполнения которых являются числовые величины, будем называть вычислительными алгоритмами. Рассмотрим пример решения следующей математической задачи: даны две простые дроби; получить дробь, являющуюся результатом деления одной на другую.

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

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

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

3. Записать дробь, числителем которой является результат выполнения пункта 1, а знаменателем — результат выполнения пункта 2.

В алгебраической форме это выглядит следующим образом:

 

 

Теперь построим алгоритм деления дробей для компьютера. В этом алгоритме сохраним те же обозначения для переменных, которые использованы в записанной выше формуле. Исходными данными являются целочисленные переменные a, d, c, d. Результатом — также целые величины m и n.

Ниже алгоритм представлен в двух формах: в виде блок-схемы и на Алгоритмическом языке (АЯ).

Раньше прямоугольник в схемах алгоритмов управления мы называли блоком простой команды. Для вычислительных алгоритмов такой простой командой является команда присваивания. Прямоугольник будем называть блоком присваивания, или вычислительным блоком. В форме параллелограмма рисуется блок ввода/вывода. Полученный алгоритм имеет линейную структуру (рис. 2.1).

 

 

В алгоритме на АЯ строка, стоящая после заголовка алгоритма, называется описанием переменных. Служебное слово цел означает целый тип. Величины этого типа могут иметь только целочисленные значения.

Описание переменных имеет вид:

<тип переменных> <список переменных>

Список переменных включает все переменные величины данного типа, обрабатываемые в алгоритме.

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

 

Коротко о главном

 

Основные свойства присваивания:

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

• новое значение, присваиваемое переменной, заменяет ее старое значение;

• присвоенное переменной значение сохраняется в ней вплоть до нового присваивания.

Обмен значениями двух переменных можно производить через третью дополнительную переменную.

Трассировочная таблица используется для «ручного» исполнения алгоритма с целью его проверки.

В алгоритмах на АЯ указываются типы всех переменных. Такое указание называется описанием переменных.

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

 

Вопросы и задания

 

1. Из каких команд составляется линейный вычислительный алгоритм?

2. Что такое трассировка? Как она производится?

3. В каком случае значение переменной считается неопределенным?

4. Что происходит с предыдущим значением переменной после присваивания ей нового значения?

5. Как вы думаете, можно ли использовать в выражении оператора присваивания неопределенную переменную? К каким последствиям это может привести?

6. Напишите на АЯ алгоритм сложения двух простых дробей (без сокращения дроби).

7. Напишите на АЯ алгоритм вычисления у по формуле

у = (1 - х² + 5x ⁴)²,

где x — заданное целое число. Учтите следующие ограничения: 1) в арифметических выражениях можно использовать только операции сложения, вычитания и умножения; 2) каждое выражение может содержать только одну арифметическую операцию. Выполните трассировку алгоритма при x = 2.

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

y = x ⁸; y = x ¹⁰; у = х ¹⁵; у = х ¹⁹.

Постарайтесь использовать минимальное количество дополнительных переменных. Выполните трассировку алгоритмов.

9. Запишите алгоритм циклического обмена значениями трех переменных А, В, С. Схема циклического обмена:

 

 

Например, если до обмена было: А = 1, В = 2, С = 3, то после обмена должно стать: А = 3, В =1,С = 2. Выполните трассировку.

 

ЕК ЦОР: часть 2, глава 6, § 34. ЦОР № 9, 10.

 

§11

Знакомство с языком Паскаль

 

Основные темы параграфа:

■ возникновение и назначение Паскаля;

■ структура программы, на Паскале;

■ операторы ввода, вывода, присваивания;

■ правила записи арифметических выражений;

■ пунктуация Паскаля.