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

Основные данные о работе

Версия шаблона	1.1
Филиал	Абаканский
Вид работы
Название дисциплины	Информационные технологии в менеджменте
Тема	Линейные вычислительные алгоритмы
Фамилия студента	Василян
Имя студента	Анна
Отчество студента	Гегамовна
№ контракта	1020011400309001

 

Содержание

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

Основная часть

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

 

Линейный  алгоритм – это алгоритм, в котором  команды выполняются последовательно  одна за другой, в порядке их записи.

Команда следования состоит только из простых команд. На рисунке простые  команды имеют условное обозначение S1 и S2. Из команд следования образуются линейные алгоритмы. Примером линейного алгоритма будет нахождение суммы двух чисел, введенных с клавиатур.  

-- С ветвлением:

Команда ветвления -- это составная команда алгоритма, в которой в зависимости от условия Р выполняется или одно S1, или другое S2 действие. Из команд следования и команд ветвления составляются разветвляющиеся алгоритмы (алгоритмы ветвления). Примером разветвляющегося алгоритма будет нахождение большего из двух чисел, введенных с клавиатуры.

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

-- С повторением: 

Команда повторения -- это составная команда алгоритма, в которой в зависимости от условия Р возможно многократное выполнение действия S. Из команд следования и команд повторения составляются циклические алгоритмы (алгоритмы повторения). На рисунке представлена команда повторения с предусловием. Называется она так потому, что вначале проверяется условие, а уже затем выполняется действие. Причем действие выполняется, пока условие соблюдается.

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

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

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

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

Рассмотрим последовательность выполнения четырех команд присваивания, в которых  участвуют две переменные а и 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Свойства команды присваивания: 
1.    пока переменной не присвоено значение, она остается неопределенной; 
2.    значение, присвоенное переменной, сохраняется в ней вплоть до выполнения следующей команды присваивания этой переменной; 
3.    новое значение, присваиваемое переменной, заменяет ее предыдущее значение.

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

Команда ввода на АЯ записывается:

ввод a,b,c,d

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

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

вывод m,n

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

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