Раздел 1. Основы алгоритмизации

Понятие алгоритма. Свойства и виды алгоритма

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

п.4. Иначе вычислить 𝑥

= −𝑏+√D, 𝑥

= −𝑏−√D

и напечатать

1

значения x₁ и x₂.

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

2𝑎

2              2𝑎

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

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

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

   да                                 нет

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

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

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

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

Рис. 1.2. Блок-схема линейного алгоритма

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

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

Пусть a, b, c – длины сторон треугольника. Необходимо найти S – площадь треугольника, P – периметр. Для нахождения площади можно воспользоваться формулой Герона:𝑟 = �r(r − a)(r − b)(r − c), где r – полупериметр.

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

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

Внимание! В этих блоках знак «=» означает не математическое равенство, а операцию присваивания. Переменной, стоящей слева от оператора, присваивается значение, указанное справа. Причем это значение может быть уже определено или его необходимо вычислить с помощью выражения. Например, операция r = (a+b+c)/2 – имеет смысл (переменной r присвоить значение (a+b+c)/2), а выражение (a+b+c)/2=r – бессмыслица.

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

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

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

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

Рассмотрим еще один пример разветвленного алгоритма. Даны три числа а, b, с. Найти наибольшее из них.

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

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

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

Существует два типа алгоритмов циклической структуры. На рис.

1.6       изображен цикл с предусловием, а на рис. 1.7 – цикл с постусловием.

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

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

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

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

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

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

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

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

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

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

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

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

1.            Что такое алгоритм? Свойства алгоритма.

2.            Формы   представления   алгоритма.   Перечислить   и   зарисовать блоки алгоритма.

3.            Перечислить виды алгоритма. Примеры.

4.            Что такое цикл? Типы циклов. Привести блок схемы. Назвать отличия.

Скачано с www.znanio.ru