Понятие алгоритма, свойства и виды алгоритмов. Построение блок-схем

Практическое занятие 1

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

Термин «алгоритм» происходит от латинской формы имени среднеазиатского математика Аль-Хорезми – Algorithmi. Алгоритм является одним из основных понятий информатики и математики.

К основным свойствам алгоритмов относятся:

1) дискретность (прерывность,раздельность) –алгоритм долженпредставлять процесс решения задачи как последовательное исполнение простых (или ранее определенных) шагов (этапов);

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

3) результативность (или конечность) –алгоритм долженприводить к решению задачи за конечное число шагов;

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

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

• словесная –записывается на естественном языке;

• графическая –с помощью блок-схемы;

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

 

Рассмотрим пример алгоритма на естественном языке:

1. Ввести в компьютер числовые значения переменных а, b и с.

2. Вычислить дискриминант по формуле d = b² - 4ас.

3. Если d < 0, то напечатать сообщение «Корней нет» и перейти к

п.4. Иначе вычислить значения x₁ и x₂.

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

 

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

Блок начала-конца алгоритма.Надпись в блоке: «начало»(«конец»).

 

 

Блок ввода-вывода данных.Надпись в блоке:слово«ввод»(«вывод» или «печать») и список вводимых (выводимых) переменных.

 

Блок решения или действия. Надпись в блоке:конкретнаяоперация или группа операций.

 

Условный блок. Надпись в блоке: проверяемое условие.

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

В качестве примера приведем блок-схему алгоритма решения уравнения, описанного выше.

 

Рис. 1. Блок-схема алгоритма решения квадратного уравнения

 

Виды алгоритма:

 

1. Линейный алгоритм. В котором все операции выполняютсяпоследовательно одна за другой.

 

 

Рис. 2.

Рассмотрим пример линейного алгоритма.

 

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

 

Пусть a, b, c – длины сторон треугольника. Необходимо найти S –площадь треугольника, P –периметр.

 

Входные данные: a, b, c. Выходные данные: S, P.

 

Блок-схема алгоритма представлена на рис. 3.

 

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

 

с помощью выражения. Например, операция r = (a+b+c)/2 – имеет смысл (переменной r присвоить значение (a+b+c)/2), а выражение

(a+b+c)/2=r –бессмыслица.

 

 

Рис. 3. Пример линейного алгоритма

 

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

 

В блок-схемах разветвленные алгоритмы изображаются так, как показано на рис. 1.4.

 

Рис. 4. Полный и неполный разветвленный алгоритм

 

В качестве примера разветвленного алгоритма можно рассмотреть блок-схему алгоритма решения квадратного уравнения (см. рис. 1).

 

Рассмотрим еще один пример разветвленного алгоритма.

 

Даны три числа а, b, с. Найти наибольшее из них.

 

Блок-схема алгоритма представлена на рис. 5.

 

 

 

Рис. 5. Алгоритм поиска наибольшего из трех чисел

 

3. Циклический алгоритм. Циклом называют повторениеодних и тех же действий (шагов). Последовательность

 

действий, которые повторяются в цикле, называют телом цикла.

 

Существует два типа алгоритмов циклической структуры. На рис. 6 изображен цикл с предусловием, а на рис. 7 – цикл с постусловием.

 

Эти циклы взаимозаменяемы и обладают некоторыми отличиями:

 

• в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием – после тела цикла;

• в цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу;

• в цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием – условие выхода из цикла.

 

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

 

Обязательные блоки для организации цикла:

 

1. Установка начального значения параметра цикла.

 

2. Проверка условия достижения конечного значения параметра цикла.

 

3. Изменение параметра цикла.

 

Рассмотрим пример циклического алгоритма (рис. 8).

 

 

Рис. 8. Пример циклического алгоритма

 

Поделиться:

Воспользуйтесь поиском по сайту: