Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Понятие об алгоритмах).pdf

Эвристический алгоритм (от греческого слова “эврика”) – это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и прошлом опыте решения сходных задач.

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

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

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

Цикл программы – последовательность команд (серия, тело цикла), которая

может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.

Вспомогательный (подчиненный) алгоритм (процедура) – алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.

В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм [1, с. 7-9].

1.5. Методы изображения алгоритмов

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

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

графическая (изображения из графических символов);

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

программная (тексты на языках программирования).

Словесное описание алгоритма

Данный способ получил значительно меньшее распространение из-за его

многословности и отсутствия наглядности.

Рассмотрим пример на алгоритме нахождение максимального из двух значений:

Определим форматы переменных X, Y, M, где X и Y – значения для сравнения, M – переменная для хранения максимального значения;

получим два значения чисел X и Y для сравнения;

сравним X и Y.

если X меньше Y, значит большее число Y.

Поместим в переменную M значение Y.

Если X не меньше (больше) Y, значит большее число X.

Поместим в переменную M значение X [1, с. 9].

Рассмотрим еще пример алгоритма (вычисление корней квадратного уравнения) на естественном языке:

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

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

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

п.4. Иначе вычислить ????₁ =(−????+√D)/2????, ????₂ =(−????−√D)/2???? и напечатать

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

4. Прекратить вычисления [3, с. 7].

Уточним понятие словесного представления алгоритма на примере нахождения факториала числа n (c=n!), т.е. вычисления по формуле с=1*2*3*4…n:

1. Полагаем с равным 1 и переходим к следующему пункту.
2. Полагаем i равным 1 и переходим к следующему пункту.
3. Полагаем с=i*c и переходим к следующему пункту.
4. Проверяем, равно ли число i числу n. Если равно, то вычисления прекращаем. Если i<n, то увеличиваем i на 1 и переходим к пункту 3 [2, с. 8-9].

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

такие описания строго не формализуемы;

страдают многословностью записей;

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

Блок-схема алгоритма

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

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

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

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

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

Блок-схемы алгоритмов удобно использовать для объяснения работы уже готового алгоритма, при этом в качестве блоков берутся действительно блоки алгоритма, работа которых не требует пояснений. Блок-схема алгоритма должна служить для упрощения изображения алгоритма, а не для усложнения [1, с. 10].

Вспомним основные условные обозначения, используемые при графической записи алгоритма [1, с. 11]:

Рис.1. Основные условные графические обозначения [1, с. 11]

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

уравнения, описанного выше [3, с. 8]:

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

Псевдокод

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

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

В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций [1, с. 11-12].

Программное представление алгоритма

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

Однако на практике в качестве исполнителей алгоритмов используются

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

Следовательно, язык для записи алгоритмов должен быть формализован.

Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера [1, с. 12].

1.6. Классификация алгоритмов. Базовые структуры.

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

К основным структурам относятся следующие: линейные (рис 3, а), разветвляющиеся (рис 3, б), циклические (рис 3, в, г) [2, с. 13-14].

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

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

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

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

Примером может являться разветвляющийся алгоритм, изображенный на рисунке 4, б.

Циклическим называется алгоритм, в котором некоторая часть операций выполняется многократно (тело цикла). Однако, слово многократно, не значит бесконечно.

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

Возможен другой случай, когда тело цикла выполняется хотя бы один раз, и будет выполняться до тех пор, пока не станет истинным условие. Такая организация цикла, когда тело цикла расположено до проверки условия, носит название цикл с постусловием [2, с. 14-16].

Пример цикла пока изображен на рисунке 4, в [2, с. 16].

Рис.4. Примеры структур алгоритмов

Глава 2. Основные структуры алгоритмов и их примеры

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

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

последовательно одна за другой (рис. 5) [3, с. 9].

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

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

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

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

Для нахождения площади можно воспользоваться формулой Герона:

S = (r(r − a)(r − b)(r − c))^1/2,

где r – полупериметр.

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

Блок-схема алгоритма представлена на рис. 6 [3, с. 9-10].

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

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

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

Он включает последовательное выполнение следующих этапов:

ввод исходных данных в память ЭВМ;

вычисление искомых величин по формулам;

вывод результатов из памяти ЭВМ на информационный носитель.

Пример. Составить алгоритм вычисления площади круга по формуле

S= πR². Решение показано на рис. 7 [1, с. 15]

Рис.7. Вычисление площади круга

2.2 Разветвленный алгоритм

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