Основные алгоритмические структуры

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

К основным алгоритмическим структурам относятся:

а) Следование - это последовательность блоков (или групп блоков) алгоритма. В программе следование представлено в виде последовательного выполнения операций.

б) Цикл До Эта алгоритмическая структура применяется в том случае, когда нужно какие-либо операции исполнить несколько раз до того, как будет истинным определенное условие (см рис 2.1). При этом многократно выполняемая последовательность операций называется телом цикла. Особенностью данного цикла является его обязательное исполнение хотя бы один раз по причине того, что перед первой проверкой условия выхода из цикла будут предварительно выполнены его операторы.

Рис. 2.1. Блок-схема, описывающая алгоритм цикла До

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

При помощи естественного языка цикл До можно представить в виде следующей последовательности операций:

1. Операции начальных присвоений.

2. Операции тела цикла.

3. Если условие выполняется, то переход на 2.

в) Цикл Пока. Этот цикл отличается от цикла До тем, что проверка условия осуществляется перед исполнением операторов тела цикла (см. рис. 2.2). Если же это условие при первой проверке не является истинным, то тело цикла ни разу не выполняется.

Рис.2.2. Блок-схема, описывающая алгоритм цикла Пока

При помощи естественного языка цикл Пока можно представить в виде следующей последовательности операций-

1. Операции начальных присвоений.

2. Если условие выполняется, то переход на 5.

3. Операции тела цикла.

4. Переход на 2

5....

В примере с умножением двух чисел, приведенном выше, использовался цикл Пока.

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

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

При помощи естественного языка разветвление можно представить в виде следующей последовательности операций:

1. Если условие выполняется, то переход на 4.

2. Операции действия 1.

3. Переход на 5.

4. Операции действия 2.

5....

Рис. 2.3. Блок-схема, описывающая алгоритм Разветвления

 

д) Обход . Эта структура является частным случаем разветвления, когда в одной из ветвей нет никаких действий (см. рис. 2.4).

Рис. 2.4. Блок-схема, описывающая алгоритм Обхода

 

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

1. Если условие выполняется, то переход на 3.

2. Операции действия.

3....

е) Множественный выбор . Эта структура является обобщением разветвления, когда необходимо выполнить одно из нескольких действий в зависимости от значения переменной А . Например, при А= 1 выполняется действие В₁ при А = 2 выполняется действие В₂ и так далее (см. рис. 2.5).

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

Рис. 2.5. Блок-схема, описывающая алгоритм Множественного выбора

 

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

 

Примечание:

Давайте попробуем сравнить понятие " алгоритм" с рецептом из кулинарной книги. Предполагается, что рецепт обладает свойством конечности, имеет входные данные (такие, например, как яйца, мука и т. д.) и выходные данные (обед " на скорую руку" и т. п.), но хорошо известно, что ему не хватает определенности. Инструкции из кулинарных рецептов очень часто бывают неопределенными, например: " Добавьте щепотку соли". " Щепотка" определяется как количество, " меньшее чайной ложки", и что такое соль, вероятно, тоже известно всем. Но куда именно нужно добавить соль — сверху? сбоку? Инструкции " Слегка потрясите, пока смесь не станет рассыпчатой" и " Подогрейте коньяк в маленькой кастрюльке" будут вполне понятны опытному повару, но они не годятся для алгоритма. Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер. Тем не менее программист может многому научиться, прочитав хорошую поваренную книгу.

 

 

Примечание:

Итак, давайте в качестве примера разберем алгоритм Евклида. Предположим, что m = 119 и n = 544; начнем с шага 1. Деление m на n в этом случае выполняется просто, даже очень просто, так как частное равно нулю, а остаток — 119. Таким образом, r← 119. Переходим к шагу 2. Поскольку r≠ 0, на этом шаге никакие действия не выполняются. На шаге 3 присваиваем m ← 544, n← 119. Очевидно, что если первоначально m < n, то частное на шаге 1 всегда оказывается равным нулю и в ходе выполнения алгоритма всегда происходит взаимный обмен значений переменных тип, хотя и таким громоздким способом. Поэтому можно добавить дополнительный шаг.

0. [Гарантировать, что m≥ n.] Если m< n, то выполнить взаимный обмен m↔ n.

В результате алгоритм изменится незначительно (разве что увеличится на один шаг), но зато время его выполнения сократится примерно в половине случаев.

Вернемся к шагу 1. Находим, что , поэтому r← 68. В результате на шаге 2 снова не выполняются никакие действия, а на шаге З присваиваем m← 119, n← 68. В следующих циклах сначала получаем r← 51 и m ← 68, n← 51, а затем — r← 17 и m← 51, n ← 17. Наконец, в результате деления 51 на 17 получаем r← 0. Таким образом, на шаге 2 выполнение алгоритма прекращается. Наибольший общий делитель 119 и 544 равен 17.

 

 

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

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

 

Примечание:

В качестве примера давайте исследуем с этой точки зрения алгоритм Евклида. Предположим, нам нужно решить следующую задачу: " Пусть задано значение n, а m может быть любым целым положительным числом. Тогда чему равно среднее число Т_n выполнений шага 1 алгоритма Евклида? ". Прежде всего необходимо убедиться в том, что задача имеет смысл, поскольку нам предстоит найти среднее при бесконечно большом количестве значений m,. Но совершенно очевидно, что после первого выполнения шага 1 значение будет иметь только остаток от деления m на n. Поэтому все, что мы должны сделать для нахождения значения Т_n, — это испытать алгоритм для m = 1, m = 2, ..., m = n, подсчитать суммарное число выполнений шага 1 и разделить его на n.

А теперь рассмотрим еще один важный вопрос, касающийся поведения Т_n как функции от n: можно ли ее аппроксимировать, например, функцией или На самом деле это чрезвычайно сложная и интересная математическая проблема, которая еще не решена окончательно; более подробно она будет рассмотрена в разделе 4.5.3. Можно доказать, что при больших значениях n Т_n ведет себя, как функция (12(ln2)/π ²) ln n, т. е. она пропорциональна натуральному логарифму n. Заметим, что коэффициент пропорциональности нельзя просто взять и угадать; чтобы определить его, нужно затратить определенные усилия.

 

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

Примечание:

До сих пор наше обсуждение алгоритмов носило достаточно общий характер, Кратко опишем метод, с помощью которого понятие алгоритма можно строго обосновать в терминах математической теории множеств. Формально определим метод вычислений как четверку (Q, I, Ω, f), где Q — это множество, содержащее подмножества I и Ω, а f — функция, переводящая множество Q в себя. Кроме того, f оставляет неподвижными точки множества Ω, т. е. f(q) равно q для всех элементов q из множества Ω. Эти четыре элемента, Q, I, Ω, f, представляют соответственно состояния вычисления, ввод, вывод и правило вычислений. Каждое входное значение х из множества I определяет вычисляемую последовательность x₀, x₁, x₂, … следующим образом:

x₀ = x и х_k+1=f(x_k) для k≥ 0 (l)

Говорят, что вычисляемая последовательность заканчивается через k шагов, если k — это наименьшее целое число, для которого х_k принадлежит Ω, и что она дает выходное значение х_k для заданного х. (Заметим, что если х_k принадлежит Ω, то и х_k+1 принадлежит Ω, так как в этом случае х_k+1=х_k) Некоторые вычисляемые последовательности могут никогда не заканчиваться, но алгоритм — это метод вычислений, который заканчивается через конечное число шагов для всех х из I.

Например, алгоритм Евклида в этих терминах можно формализовать следующим образом. Пусть элементами множества Q будут все величины (n), все упорядоченные пары (m, n) и все упорядоченные четверки (m, n, r, 1), (m, n, r, 2) и (m, n, p, 3), где m, n и р — это целые положительные числа, а r — неотрицательное целое число. Пусть I — это подмножество всех пар (m, n), а Ω — подмножество всех величин (n). Определим функцию f следующим образом:

f((m, n))=(m, n, 0, l); f((n)) = (n);

f((m, n, r, 1)) = (m, n, остаток от деления m на n, 2);

f((m, n, r, 2)) = (n), если r = 0, (m, n, r, 3) в противном случае;

f((m, n, p, 3)) = (n, p, p, 1).

Соответствие между данной записью и алгоритмом Евклида очевидно.

В этой формулировке понятия " алгоритм" не содержится ограничение, касающееся эффективности, о котором упоминалось ранее. Например, Q может быть множеством бесконечных последовательностей, которые нельзя вычислить с помощью карандаша и бумаги, а f может включать операции, которые простой смертный сможет выполнить не всегда. Если мы хотим ограничить понятие " алгоритм" таким образом, чтобы в нем могли содержаться только элементарные операции, то введем ограничения на элементы Q, I, Ω и f, например, следующим образом. Пусть А — это ограниченное множество букв, а А*—множество всех строк, определенных на множестве А (т. е. множество всех упорядоченных последовательностей x₁x₂... х_n, где n≥ 0 и x_j принадлежит А для 1≤ j≤ n). Идея заключается в следующем: закодировать состояния вычисления таким образом, чтобы они были представлены строками из множества А*. Теперь пусть N — целое неотрицательное число, a. Q — множество всех пар (σ, j), где а принадлежит A*, a j — целое число, 0 ≤ j ≤ N. Пусть I — подмножество пар из Q, для которых j = 0, а Ω — подмножество пар из Q, для которых j = N. Если Θ и σ — строки из А*, то мы будем говорить, что Θ входит в σ, если σ имеет вид α Θ ω, где α и ω — некоторые строки. И в завершение определим функцию f с помощью строк Θ _j, φ _j и целых чисел a_j, b_j, 0≤ j≤ N следующим образом:

f(σ, j] = (σ, a_j), если Θ _j не входит в σ

f(σ, j) = (α φ _j ω, b_j), если α является самой короткой строкой, для которой σ =α Θ _j ω

f(σ, N) = ((T, N)..(3)

Метод вычислений, удовлетворяющий этому определению, безусловно, является эффективным. Кроме того, опыт показывает, что в таком виде можно представить любую задачу, которая решается с помощью карандаша и бумаги. Существует также много других по сути эквивалентных способов формулировки понятия эффективного метода вычислений (например, с помощью машины Тьюринга). Приведенная выше формулировка практически совпадает с той, которую дал А. А. Марков (Markov) в своей книге Теория алгоритмов [Труды АН СССР, Ин-т математики.—1954.—42.—376 с.], а впоследствии исправил и расширил Н. М. Нагорный (Nagorny) (M.: Наука, 1984).

 

 

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

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

Исполнитель - человек или автомат (например, компьютер), который умеет выполнять определенный конечный набор действий;

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

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

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

Программа - алгоритм, записанный в форме, воспринимаемой вычислительной машиной. [ ГОСТ 19.004-80].

Таким образом, программы нужны для выполнения компьютером какого-либо задания. Любые действия, выполняемые компьютером в программах, производятся над некоторыми объектами. По изменению состояния этих объектов можно судить о результатах данного действия. Одним из важнейших объектов в программе является переменная.

 

Пятый этап — ввод программы и исходных данных в ЭВМ. Программа и исходные данные вводятся в ЭВМ с клавиатуры с помощью редактора текстов, и для постоянного хранения осуществляется их запись на гибкий или жесткий маг­нитный диск.

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

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

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

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

Седьмой этап — исполнение отлаженной программы и анализ результа­тов. На этом этапе программист запускает программу и задает исходные данные, требуемые по условию задачи.

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

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

КАК ВЫЗВАТЬ ПРОГРАММУ?

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

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

ЯЗЫКИ ПРОГРАММИРОВАНИЯ

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

Современные компьютеры не настолько совершенны, чтобы понимать про­граммы, записанные на каком-либо употребляемом человеком языке — русском, английском, японском. Команды, предназначенные для ЭВМ, необходимо запи­сывать в понятной ей форме. С этой целью применяются языки программирования — искусственные языки, алфавит, словарный запас и структура которых удобны человеку и понятны компьютеру.

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

Исходя из этого все языки программирования делятся на языки низкого, высо­кого и сверхвысокого уровня.

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

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

Более многочисленную группу составляют языки программирования высокого уровня, средства которых допускают описание задачи в наглядном, легко воспри­нимаемом виде. Отличительной особенностью этих языков является их ориентация не на систему команд той или иной ЭВМ, а на систему операторов, характерных для записи определенного класса алгоритмов. К языкам программирования этого типа относятся: Бейсик, Фортран, Алгол, Паскаль, Си. Программа на языках высо­кого уровня записывается системой обозначений, близкой человеку (например, фиксированным набором слов английского языка, имеющих строго определенное назначение). Программу на языке высокого уровня проще понять и значительно легче отладить.

К языкам программирования сверхвысокого уровня можно отнести Алгол-68, при разработке которого сделана попытка формализовать описание языка, привед­шая к появлению абстрактной и конкретной программ. Абстрактная программа создается программистом, конкретная — выводится из первой. Предполагается, что при таком подходе принципиально невозможно породить неверную синтакси­чески (а в идеале и семантически) конкретную программу. Язык АРL относят к языкам сверхвысокого уровня за счет введения сверхмощных операций и операто­ров. Запись программ на таком языке получается компактной.

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

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: