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

Глава 6. Понятие алгоритма и его основные формы

Алгоритм и его свойства

Слово "АЛГОРИТМ", как известно, происходит от видоизменённого имени древнего гениального арабского учёного Аль Хорезми. Поначалу дадим нестрогое, простейшее определение понятия "алгоритм":

АЛГОРИТМ – это некая система предписаний (инструкций), обязательно ведущих к достижению некоторого желаемого результата.

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

Иногда алгоритм предельно прост и выполняется рефлекторно. Например, человек прикоснулся к раскалённому предмету. Он сразу отдёргивает руку и дует на неё или подставляет под холодную воду. Рука спасена.

Ещё один простой пример. Если горит красный сигнал светофора, то переходить улицу нельзя, и мы стоим. Цвет сменился на жёлтый, а затем на зелёный – мы начинаем и совершаем переход.

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

Приведём несколько "академичный" пример алгоритма. Допустим, проводится тестирование. Вместе с вопросом испытуемому предлагается ряд ответов, из которых только один правильный. Алгоритм поведения человека в данном случае сильно зависит от степени его подготовки. Если он хорошо представляет себе проблему, то сразу указывает верный ответ. Если – не очень, то обычно применяется следующий алгоритм: исходя от противного, отбрасываются заведомо негодные ответы, в сузившемся круге поиска легче догадаться, что правильно, а что – нет. Наконец, крайний случай – не готов! Тогда алгоритма просто нет – наугад!

И таких примеров из обычной повседневной жизни можно привести великое множество.

Теперь уточним определение алгоритма:

АЛГОРИТМ – это конечная последовательность простейших формул и логических правил, чётко и недвусмысленно определяющих весь ход решения какой-либо задачи, который состоит в упорядоченном выполнении различных операций над данными с целью получения искомого ответа (результата) за к о н е ч н о е число шагов.

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

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

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

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

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

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

5. Массовость. Предполагается, что алгоритм разрабатывается в общем виде, т. е. он может быть пригоден для решения не одной, а некоторого класса задач определённого типа. При этом они могут различаться лишь значениями исходных данных. Например, алгоритм расчёта стоимости партии товаров (в отличие от величины получаемого при этом результата!) с учётом назначенной для него скидки не зависит от значений цены единицы товара, его количества и процента скидки. Аналогично, алгоритм расчёта заработной платы для бригады работников одинаков для любого их количества и сумм, начисленных каждому из них.

Отсутствие или неполнота любого из этих свойств лишает алгоритм совершенства и возможности его успешной автоматической реализации.

Формы представления алгоритма

Алгоритм как набор инструкций может быть представлен в разных формах:

а) словесной,

б) словесно-формульной,

в) в виде псевдокода,

г) графической,

д) программной (с помощью операторов или команд).

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

Словесно-формульная запись сочетает в себе применение конструкций естественного языка и понятных математических обозначений. Например, чтобы описать алгоритм вычисления выражения Y = x² + x при х=3,5, нужно

Ø придать переменной х значение 3,5;

Ø вычислить выражение x²;

Ø вычислить сумму x² + x

Ø записать вычисленное значение вместо Y.

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

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

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

Начало

2. Дано Сч=1, Y= 0(Сч – переменная для подсчёта количества чисел х,

Y – переменная-накопитель суммы значений х)

3. Ввод значения х

4. Если Сч > 10 перейти к пункту 7

Иначе выполнить

Y = Y + x (увеличить значение Y на величину x)

5. Выполнить Сч = Сч + 1 (увеличить значение Сч на 1)

6. Перейти к пункту 4

7. Вывод на печать значения Y

Конец

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

Псевдокод легко воспринимается человеком, но абсолютно непригоден для написания реальной программы, "понятной" для ЭВМ. Кроме того, если алгоритм достаточно сложен, то ПСК теряет свою наглядность.

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

Кроме того, (что очень важно!) блок-схема не зависит от языка программирования, на котором будет реализован алгоритм. Поэтому она доступна для понимания любым человеком, знакомым с применяемыми в ней обозначениями, но вовсе не владеющим программированием. Вот как выглядит алгоритм нахождения суммы десяти (10) произвольных чисел в виде блок-схемы:

Начало

Сч = 1 Y = 0

Нет

Да

Сч > 10

х

 

 

Y = Y + x

 

Конец

 

Рис. 6.1. Графическая форма циклического алгоритма

Условные обозначения, применяемые при составлении блок-схем алгоритмов, и правила их выполнения определены в ГОСТ 19.701-90 (ИСО 5807-85) «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

ПРИМЕЧАНИЕ 1: подробности о назначении отдельных фигур в блок схеме и приёмах их отображения см. в Приложении 1 "Графическая схема алгоритмов (ГСА)".

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

Алгоритм, описываемый в операторах, может понять только специалист в области программирования, но компьютеру он по-прежнему «непонятен». Для этого он должен быть "переведён" на язык машинныхкоманд специальной программой-транслятором. Алгоритм в командах компьютер уже умеет «распознавать» и выполнять. Здесь, наконец, можно уже говорить о программе для компьютера.

ПРОГРАММА – это последовательность недвусмысленных инструкций (операторов или команд), которую компьютер чётко выполняет одну за другой до тех пор, пока не дойдёт до оператора «конец».