Информатика на пять О нас
 Добавить в избранное
5byte.ru
 Теория
 8 класс
 9 класс
 10 класс
 11 класс
Задания
 8 класс
 9 класс
 10 класс
 11 класс
Книги
Тесты
ЕГЭ
Turbo Pascal 7
 Описание
 Задачи
HTML
Рефераты

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

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

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

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

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

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

Команда а b
а:= 1 1 -
b:= 2 х а 1 2
а:= b 2 2
b:= a + b 2 4

Прочерк в таблице обозначает неопределенное значение переменной. Конечные значения, которые получают переменные а и 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 Z
ввод X, Y 1 2 -
Z:=X 1 2 1
Х:=Y 2 2 1
Y:=Z 2 1 1
вывод X, У 2 1 1

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

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

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

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

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

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

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

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

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



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

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

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

алг Деление дробей
цел а, Ь, с, d, m, n
нач ввод а, Ь, с, d
     m:=a х d
     n:=b х c
     вывод m,n
кон

Рис. 3.5. Алгоритм деления дробей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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





 У Вас есть материал пишите нам
 
    Copyright © 2008    
  Top.Mail.Ru