Алгоритмы и программы

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

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

Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в IX в. (825 г.) дал правила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом.

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

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

Способы записи алгоритмов

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

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

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

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

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

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

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

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

Приведем пример словесного представления алгоритма на примере нахождения произведения п натуральных чисел (с= п = = 1 х 2 х 3 х 4 х ... х п).

Этот процесс может быть записан в виде следующей системы последовательных указаний (пунктов):

• 1. Полагаем с равным единице и переходим к следующему пункту.
• 2. Полагаем / равным единице и переходим к следующему пункту.
• 3. Полагаем с равным с=сх/ и переходим к следующему указанию.
• 4. Проверяем, равно ли /' числу п. Если / = п, то вычисления прекращаем. Если / < п, то увеличиваем / на единицу и переходим к пункту 3.

Классификация и свойства алгоритмов

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

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

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

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

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

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

Каждая команда алгоритма должна определять однозначное действие исполнителя. Такое свойство алгоритмов называется определенностью (или точностью) алгоритма.

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

Еще одно важное требование, предъявляемое к алгоритмам, — результативность (или конечность) алгоритма. Оно означает, что исполнение алгоритма должно закончиться за конечное число шагов.

Поскольку разработка алгоритмов — процесс творческий, требующий умственных усилий и затрат времени, предпочтительно разрабатывать алгоритмы, обеспечивающие решения всего класса задач данного типа. Например, если составляется алгоритм решения кубического уравнения ах³ + Ьх² + сх + с1 = 0, то он должен быть вариативен, т. е. обеспечивать возможность решения для любых допустимых исходных значений коэффициентов а, Ь, с, с1. Про такой алгоритм говорят, что он удовлетворяет требованию массовости. Свойство массовости не является необходимым свойством алгоритма. Оно, скорее, определяет качество алгоритма; в то же время свойства точности, понятности и конечности являются необходимыми (иначе это не алгоритм).

Запись алгоритмов в виде блок-схем

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

Схема алгоритма — графическое представление алгоритма, дополняемое элементами словесной записи. Каждый пункт алгоритма отображается на схеме некоторой геометрической фигурой или блоком. При этом правило выполнения схем алгоритмов регламентирует ГОСТ 19.002—80 «Единая система программной документации» (табл. 1.28).

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

7 6 5 4 3 2 10

в

7 6 5 4 3 2 10

г

Таблица 1.28. Основные элементы блок-схем

№

Символ

Наименование

Содержание

Размеры

по ГОСТ 19.003—80 (ЕСПД):а = 10,15,20 мм; b = ^, 5а

Блок вычислений

Вычислительные действия или последовательность действий

а

Логический

блок

Выбор направления выполнения алгоритма в зависимости от некоторого условия

Блок ввода-

вывода

данных

• 1. Общие обозначения ввода (вывода) данных (вне зависимости от физического носителя).
• 2. Вывод данных, носителем которых является документ

Начало

(конец)

Начало или конец алгоритма, вход в программу или выход из нее

г = а/4

V-

V_

а/2

Процесс пользователя (подпрограмма)

Вычисление по стандартной программе или подпрограмме

а

Блок

модификации

Функция выполняет действия, изменяющие пункты (например, заголовок цикла) алгоритма

/

V

а

а

7

Соединитель

Указание связи прерванными линиями между потоками информации в пределах одного листа

8

Межстраничное соединение

Указание связи между информацией на разных листах

а/2

0,6 а

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

Это определенный набор блоков и стандартных способов их соединения для выполнения типичных последовательных действий. К основным структурам относятся следующие — линейные, разветвляющиеся, циклические (рис. 1.26).

Рис. 1.26. Примеры структур алгоритмов: а — линейный алгоритм; б — алгоритм с ветвлением; в — алгоритм с циклом

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

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

Примером может являться разветвляющийся алгоритм, изображенный в виде блок-схемы (рис. 1.26, б). Аргументами этого алгоритма являются две переменные А, В, а результатом — переменная X. Если условие А > В истинно, то выполняется операция X := А х В, в противном случае выполняется X := А + В. В результате печатается то значение переменной X, которое она получает при выполнении одной из серий команд.

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

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

Возможен другой случай, когда тело цикла выполняется, по крайней мере, один раз и будет повторяться до тех пор, пока не станет истинным условие. Такая организация цикла, когда его тело расположено перед проверкой условия, носит название цикла с постусловием, или цикла «ДО»/«FOR». Истинность условия в этом случае — условие окончания цикла. Отметим, что возможна ситуация с постусловием и при организации цикла «ПОКА». Итак, цикл «ДО» завершается, когда условие становится истинным, а цикл «ПОКА» — когда становился ложным. Современные языки программирования имеют достаточный набор операторов, реализующих как цикл «ПОКА», так и цикл «ДО».

Рассмотрим пример алгоритма вычисления факториала, изображенный на рис. 1.26 (с циклом «ПОКА»). Переменная N получает значение числа, факториал которого вычисляется. Переменной N, которая в результате выполнения алгоритма должна получить значение факториала, присваивается первоначальное значение 1. Переменной К также присваивается значение 1. Цикл будет выполняться, пока справедливо условие N> К. Тело цикла состоит из двух операций N = N1 х К и К= К + 1.

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

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

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

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

• 1. Дайте классификацию информации.
• 2. Каковы преимущества цифровой информации по отношению к аналоговой?
• 3. Перечислите методы кодирования символов.
• 4. Перечислите методы кодирования численной информации.
• 5. Переведите число 32 451₁₀ в шестнадцатеричную и восьмеричную системы счисления.
• 6. Переведите число 32 451₁₆ в десятичную и восьмеричную системы счисления.
• 7. В чем заключаются особенности двоичной арифметики?
• 8. Подсчитайте произведение 1ГА₁₆ и 2ВС1₆ по модулю 8.
• 9. Подсчитайте сумму 457₈ и 375₈ по модулю 3.
• 10. Перечислите логические элементы ЭВМ.
• 11. Что такое логические узлы ЭВМ?
• 12. Составьте таблицы истинности для левого (-1(А д В)) и правого (-И V -,б) выражений 1-го закона де Моргана. Проверьте их на соответствие.
• 13. Составьте таблицы истинности для левого (-1(А V В)) и правого (-.А V -,б) выражений 2-го закона де Моргана. Проверьте их на соответствие.
• 14. Последний столбец таблицы истинности для двухместных операций, очевидно, может содержать 16 = 2⁴ различных сочетаний «1» и «О». Следовательно, всего может быть определено 16 логических операций над двумя переменными, из которых нами рассмотрены только пять. Составьте таблицу истинности для одной из 9 оставшихся вне рассмотрения функций и попытайтесь построить логическое выражение для этой функции.
• 15. Перечислите базовые структуры алгоритмов и программ.