ЛЕКЦИЯ № 1. Алгоритмы и алгоритмизация.

Цель лекции: Знакомство с понятием алгоритма и возможностью его изображения в виде блок схемы Приобретение навыков построения алгоритмов линейной и разветвляющейся структуры.

 

1.1. Понятие алгоритма. Способы описания.

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

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

определенностью или детерминированностью - применение алгоритма к одним и тем же исходным данным должно приводить к одному и тому же результату;

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

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

Разработка алгоритма решения задачи является очень ответственным этапом при подготовке задачи к решению на ЭВМ. Ошибки, допущенные на этапе разработки алгоритма, приведут к тому, что написанная по этому алгоритму программа будет неработоспособной, т. е. не позволит получить правильный результат.

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

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

Словесная запись алгоритма представляет собой перечисление простейших действий (арифметических, логических и др.), которые нужно выполнить для получения результата, в той последовательности, в какой они должны выполняться.

Пример. Составить алгоритм вычисления значения функции, заданной графиком (рис. 1), для любого заданного значения аргумента

Рисунок 1.1

Значение функции определяется следующим образом:

 

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

1. Ввести в память ЭВМ значение аргумента х.

2. Проверить справедливость неравенства х < 1. Если условие х < 1 выполняется, то перейти к шагу 3, если не выполняется (х ≥1), то перейти к шагу 4.

3. Вычислить значение у = 2 и перейти к шагу 5.

4. Вычислить значение у = - х + 3 и перейти к шагу 5.

5.Напечатать значение результата у.

6.Прекратить вычисления.

 

1.2.Описание алгоритмов в виде блок-схем.

Для разработки структуры программы удобнее пользоваться записью алгоритма в виде блок-схемы (в англоязычной литературе используется термин flowchart). Для изображения основных алгоритмических структур и блоков на блок-схемах используют специальные графические символы.

Описание алгоритмов в виде блок-схем является наиболее наглядным способом представления алгоритмов. Алгоритм при этом изображается в виде последовательности блоков, предписывающих выполнение отдельных функций, и связей между ними. Внутри блоков помещается информация, поясняющая выполняемые ими действия. Каждый блок снабжается номером, который размещается в разрыве контура блока в левой верхней его части. Конфигурация и размеры блоков, а также порядок построения схем определяют ГОСТ 19.002—80 и 19.003—80.

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

Размер а должен выбираться из ряда 10.15, 20,... мм, размер b равен 1,5а. В схемах алгоритмов, не являющихся документацией, обычно увеличивают ширину блоков (размер b) для удобства записи информации.

 

Таблица 1.1

Название блока	Обозначение (ГОСТ 19.003-80)	Выполняемая функция
Процесс		Вычислительное действие или последовательность действий
Решение		Проверка условия и выбор направления хода вычислительного процесса
Модификация		Начало цикла с параметром
Предопределенный процесс		Использование ранее созданных и отдельно описанных алгоритмов
Ввод-вывод		Ввод или вывод данных
Документ		Вывод данных на печатающее устройство
Соединитель		Указание связи между прерванными линиями потока
Соединитель		Указание связи между прерванными линиями потока
Пуск, останов		Начало, конец, останов, вход и выход в отдельно описанных алгоритмах и подпрограммах
Комментарий		Пояснения, содержание подпрограмм, формулы

 

1.3. Базовые структуры алгоритмов.

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

 

Базовая структура следование. Образуется из последовательности действий, следующих одно за другим.

 

Рисунок 1.2 - Базовая структура следование

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

Пример. Пусть требуется определить величину Z=E^Y, где Y=SIN(X). Результат вывести на печать.

 

Рисунок 1.3-Строго упорядоченная линейная последовательность

 

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

Рассмотрим другой случай линейной последовательности операторов. Требуется вычислить значение функции

 

Введем следующие обозначения:

 

X=r²; Y=sin α; Z=cosα; a=XYZ; b=Y+Z.

 

Величины r и α являются исходными данными задачи.

Для расчета f вначале необходимо определить величины X, Y и Z, причем безразлично в какой последовательности, затем следует рассчитать значения a и b также в любом порядке и, наконец, определить значение функции f. Таким образом, операторы по вычислению значений X, Y и Z, также как и операторы вычисления значений a и b, между собой независимы, но вычисление X, Y и Z должно предшествовать вычислению значений a и b. В этом случае имеет место частично упорядоченная линейная последовательность операторов.

 

Рисунок1.4- Частично упорядоченная линейная последовательность

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

Структура ветвление существует в трех основных вариантах:

· если-то;

· если-то-иначе;

· выбор.

Рисунок 1.5- Вариант если-то (или неполная развилка)

Пример. Дано действительное число x. Если оно четное, то заменить его на 0, иначе ничего не делать. . Рисунок1.6- Пример алгоритма

Рисунок 1.7- Вариант если-то-иначе (или полная развилка)

Пример. Даны два числа а и b. Большее из них возвести в квадрат       Рисунок 1.8- Пример алгоритма

Пример. Составить алгоритм вычисления функции:       Рисунок 1.9- Пример алгоритма

 

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

В общем случае количество ветвей может быть больше двух.

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

 

Рисунок 1.10- Алгоритм вычисления корней квадратного уравнения