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

Алгоритмы работы с величинами

Компьютер как исполнитель алгоритмов

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

Компьютер-исполнитель работает с определенными данными по определенной программе. Данные - это множество величин.

Величины: константы и переменные

Компьютер работает с информацией, хранящейся в его памяти. Отдельный информационный объект (число, символ, строка, таблица и пр.) называется величиной.

Всякая обрабатываемая программой величина занимает свое место (поле) в памяти ЭВМ. Значение величины - это информация, хранимая в этом поле памяти.

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

Числовые величины в программировании, так же как и математические величины, делятся на переменные и константы (постоянные). Например, в формуле (а² - 2аb + b²) а, b - переменные, 2 - константа.

Константы записываются в алгоритмах своими десятичными значениями, например: 23, 3.5, 34. Значение константы хранится в выделенной под нее ячейке памяти и остается неизменным в течение работы программы.

Переменные в программировании, как и в математике, обозначаются символическими именами. Эти имена называют идентификаторами (от глагола "идентифицировать", что значит "обозначать", "символизировать"). Идентификатор может быть одной буквой, множеством букв, сочетанием букв и цифр и Т. д. Примеры идентификаторов: А, X, ВЗ, prim, r25 и т. п.

Система команд

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

Независимо от того, на каком языке программирования будет написана программа, алгоритм работы с величинами составляется из следующих команд:

- присваивание;

- ввод;

- вывод;

- обращение к вспомогательному алгоритму;

- цикл;

- ветвление.

Команда присваивания

Команда присваивания - одна из основных команд в алгоритмах работы с величинами. Записывать ее мы будем так:

<переменная> := < выражение>

Значок ":=" читается "присвоить". Например:

Z :=X + Y

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

Если до выполнения этой команды содержимое ячеек, соответствующих переменным X, Y, Z, было таким:

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

Прочерк в ячейке Z обозначает, что начальное число в ней может быть любым. Оно не имеет значения для результата данной команды.

Если слева от знака присваивания стоит числовая переменная, а справа - математическое выражение, то такую команду называют арифметической командой присваивания, а выражение - арифметическим.

В частном случае арифметическое выражение может быть представлено одной переменной или одной константой. Например:

Х:= 5

Y:=X

Команда ввода

Значения переменных, являющихся исходными данными решаемой задачи, как правило, задаются вводом.

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

ввод <список переменных>.

Например:

ввод А, В, С

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

Вот схема выполнения приведенной выше команды.

1. Память до выполнения команды:

2. Процессор компьютера получил команду ввод А, B, С, прервал свою работу и ждет действий пользователя.

3. Пользователь набирает на клавиатуре:

1 3 5

и нажимает клавишу <ВВОД> (<Еnter>).

4. Память после выполнения команды:

5. Процессор переходит к выполнению следующей команды программы.

При выполнении пункта 3 вводимые числа должны быть отделены друг от друга какими-нибудь разделителями. Обычно это пробелы.

Из сказанного выше можно сделать вывод:

Переменные величины получают конкретные значения в результате выполнения команды присваивания или команды ввода.

Если переменной величине не присвоено никакого значения (или не введено), то она является неопределенной. Иначе говоря, ничего нельзя сказать, какое значение имеет эта переменная.

Команда вывода

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

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

вывод <список вывода>

Например:

вывод X1, Х2

По этой команде значения переменных X1 и Х2 будут вынесены на устройство вывода (чаще всего это экран).

О других командах, применяемых в вычислительных алгоритмах, вы узнаете позже.

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

1. Что такое величина? Чем отличаются переменные и постоянные величины?

2. Чем определяется значение величины?

3. Какие существуют основные типы величин в программировании?

4. Как записывается команда присваивания?

5. Что такое ввод? Как записывается команда ввода?

6. Что такое вывод? Как записывается команда вывода?

7. В схематическом виде (как это сделано в параграфе) отразите изменения значений в ячейках, соответствующих переменным А и В, в ходе последовательного выполнения команд присваивания:

8. Вместо многоточия впишите в алгоритм несколько команд присваивания, в результате чего должен получиться алгоритм возведения в 4-ю степень введенного числа (дополнительные переменные, кроме А, не использовать):

ввод А . . . вывод А

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

Присваивание; свойства присваивания

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

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

Присваивание производится компьютером при выполнении одной из двух команд из представленной выше системы: команды присваивания или команды ввода.

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

Прочерк в таблице обозначает неопределенное значение переменной. Конечные значения, которые получают переменные а и b, соответственно равны 2 и 4.

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

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

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

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

Обмен значениями двух переменных

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

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

1) перелить из 1-го в 3-й;

2) перелить из 2-го в 1-й;

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

Цель достигнута!

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

Действительно, в итоге переменные X и Y поменялись значениями. На экран будут выведены значения X и У в таком порядке: 2, 1. В трассировочной таблице выводимые значения выделены жирным шрифтом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7. Напишите на АЯ алгоритм вычисления y по формуле y = (1 - х² + 5х⁴)², где х - заданное целое число. Учтите следующие ограничения: 1) в арифметических выражениях можно использовать только операции сложения, вычитания и умножения; 2) выражение может содержать только одну арифметическую операцию. Выполните трассировку алгоритма при х = 2.

8. Пользуясь ограничениями предыдущей задачи, напишите наиболее короткие алгоритмы вычисления выражений:y = х⁸ ; y = х¹⁰ ; y = х¹⁵ ; y = х¹⁹ .

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