Линейные и разветвляющиеся алгоритмы

Содержание: 

  1.  Данные. Понятие типа данных
  2. ЭВМ – исполнитель алгоритмов
  3.  Линейные алгоритмы
  4.  Разветвляющиеся алгоритмы

Данные. Понятие типа данных

Алгоритм, реализующий решение некоторой конкретной задачи, всегда работает с данными. Данные – это любая информация, представленная в формализованном виде и пригодная для обработки алгоритмом.

Данные, известные перед выполнением алгоритма, являются начальными, исходными (входными) данными. Результат решения задачи – это конечные, выходные данные (результаты).

Данные делятся на переменные и константы.

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

Константы – это данные, значения которых не меняются в процессе выполнения алгоритма.

 Например:

вычислить площадь круга по формуле S=пR2

В данном алгоритме необходимо объявить две переменные:

  •  переменная R, в которую будет заноситься значение радиуса окружности
  •  переменная S, в которую будет заноситься значение площади круга

Константой является число п.

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

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

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

  •  множество допустимых значений;
  •  множество допустимых операций;
  •  форма внутреннего представления.

Типы констант определяются по контексту, т.е. по форме записи в тексте. А типы переменных устанавливаются в описаниях переменных.

Тип

Значения

Операции

Внутр.представление

Целый

Целые положительные и отрицательные числа.

Примеры: 23, -12, 387

Арифметические операции с целыми числами: +, -, *, целое деление и остаток от деления. Операции отношений (<, >, = и др.).

Формат с фиксированной точкой

Вещественный

Любые (целые и дробные) числа.

Примеры: 2,5; -0,01; 45,0; 3,6*109

Арифметические операции с целыми числами: +, -, *, /

Операции отношений.

Формат с плавающей точкой

Логический

True(истина)

False(ложь)

Логические операции: И(and), ИЛИ(or), НЕ(not).

Операции отношений.

1 бит:

1 – true;

0 — false

Символьный

Любые символы компьютерного алфавита.

Примеры: ‘a’, ‘5’, ‘+’, ‘$’

Операции отношений.

Коды таблицы символьной кодировки. 1 символ – 1 байт.

Есть еще один вариант классификации данных – классификация по структуре. Данные делятся напростые и структурированные. Для простых величин (их еще называют скалярными) справедливо утверждение: одна величина – одно значение; для структурированных: одна величина – множество значений. К структурированным величинам относятся массивы, строки, множества и т.д.

 ЭВМ – исполнитель алгоритмов

Всякий алгоритм (программа) составляется для конкретного исполнителя в рамках его системы команд. Естественно, что, говоря о программировании, мы имеем в виду, что исполнителем является компьютер. Точнее говоря, исполнителем является комплекс ЭВМ + Система программирования (СП). Программист составляет программу на том языке, на который ориентирована СП.

Независимо от того, на каком языке программирования будет написана программа, алгоритм решения любой задачи на ЭВМ может быть составлен из команд:

  •  присваивания;
  •  ввода;
  •  вывода;
  •  обращения к вспомогательному алгоритму;
  •  цикла;
  •  ветвления.

 Линейные алгоритмы

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

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

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


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

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

Присваивание – это операция, которая значение выражения, стоящее справа от символа «=» запоминает в переменной или элементе массива, стоящем слева. При присваивании происходит преобразование типов данных, если они не совпадают.

Присваивание может осуществляться двумя способами:

  •  с помощью команды присваивания
  •  с помощью команды ввода

Например: вычислить дробь 123

Исходные данные: целочисленные переменные a, b, c, d.

Результат: также целые величины m и n.


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

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

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

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

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

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

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

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

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

Команда

a

b

a := 1

1

b := 2 * a

1

2

a := b

2

2

b := a + b

2

4

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

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

Разветвляющиеся алгоритмы

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

Каждое из возможных направлений дальнейших действий называется ветвью.

В блок-схемах разветвление реализуется специальным блоком «Решение». Этот блок предусматривает возможность двух выходов. В самом блоке «Решение» записывается логическое условие, от выполнения которого зависят дальнейшие действия.

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


Различают несколько видов разветвляющихся алгоритмов:

1. «Обход» — такое разветвление, когда одна из ветвей не содержит ни одного оператора, т.е. как бы обходит несколько действий другой ветви:


2.  «Разветвление» — такой тип разветвления, когда в каждой из ветвей содержится некоторый набор действий:

3. «Множественный выбор» — особый тип разветвления, когда каждая из нескольких ветвей содержит некоторый набор действий. Выбор направления зависит от значения некоторого выражения:


Контрольные вопросы

1. Какой алгоритм называется линейным?

2. Какой алгоритм называется разветвляющимся?

3. Перечислите виды разветвляющихся алгоритмов.