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

LISP (Лисп). Интерпретируемый язык программирования, созданный в 1960 году Джоном Маккарти. Ориентирован на структуру данных в форме списка и позволяет организовывать эффективную обработку больших объемов текстовой информации;

Delphi (Дельфи) – язык объектно-ориентированного "визуального" программирования. Явился развитием языка Паскаль. При использовании декларативного языка программирования программист указывает исходные информационные структуры, взаимосвязи между ними и то, какими свойствами должен обладать результат. При этом процедуру его получения (то есть алгоритм) программист не строит. В этих языках отсутствует понятие "оператор".^[20]

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

ГЛАВА II. СРАВНИТЕЛЬНЫЙ АНАЛИЗ ТРЕХ ОСНОВОПОЛАГАЮЩИХ СТРУКТУР АЛГОРИТМОВ

Выделяют три основные структуры алгоритмов:

1. Линейная.

2. Разветвляющаяся (альтернатива «если–то–иначе» или «если–то»).

3. Циклическая (повторение).

Линейная структура – является основной. Она означает, что действия выполняются друг за другом. Прямоугольник, показанный на рисунке, может представлять как одну единственную команду, так и множество операторов, необходимых для выполнения сложной обработки данных, где F1 и F2 – некоторые команды для соответствующего исполнителя. Команды записываются с помощью операции присваивания. Присваивание переменной какого-либо значения или присваивание одной переменной значения другой переменной является наиболее часто выполняемым действием в программе, написанной на любом языке программирования. В языке программирования присваивание является операцией и обозначается как «:=». Это означает, что при выполнении этой операции происходит не только присваивание значения определенной переменной, но и возвращается некоторое значение.

---

Разветвляющийся алгоритм – это алгоритм, в котором то или иное действие выполняется после анализа условия. Процесс анализа условия и выбора одной из ветвей на блок-схеме показывают с помощью логического блока. ^[21] Логический блок имеет один вход и два выхода (ветвь «да» и ветвь «нет»). В блок-схемах разветвляющихся алгоритмов всегда есть логический блок. Может оказаться, что для одного из результатов проверки условия ничего предпринимать не надо. В этом случае можно применять только один обрабатывающий блок. Эта структура называется также ЕСЛИ –ТО – ИНАЧЕ. Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран. Для начала нужно понять, что для решения большинства задач, как правило, существует много различных алгоритмов, которые могут отличаться друг от друга по быстродействию, требуемой внутренней и/или внешней памяти, сложности программирования и ряду других критериев. При этом, как правило, не существует алгоритма, который был бы предпочтительнее при любых исходных данных и по всем критериям оценки. Какой из них выбрать для решения конкретной задачи? Этот вопрос очень важен для любого профессионального программиста. Именно поэтому необходимо уже на ранних этапах обучения студентов «программистских» направлений подготовки уделять как можно больше времени вопросам выбора эффективного алгоритма решения задачи. Начинающий программист должен четко понимать, что один из основных этапов решения любой задачи – анализ и выбор алгоритма ее решения. Традиционный способ сравнения эффективности алгоритмов состоит в сопоставлении их порядков сложности.

Человек, автоматическое устройство, компьютер – это разные исполнители алгоритмов. Для того чтобы компьютер мог выполнить алгоритм, его надо написать на понятном компьютеру языке. Компьютер понимает машинный язык. Например, равенство х = у на машинном языке имеет вид: 111101110011110111110101.^[22]

Этот метод применим как к временной, так и пространственной сложности. Порядок сложности алгоритма выражает его эффективность обычно через количество обрабатываемых данных. Однако такой подход к оценке эффективности алгоритмов имеет ряд недостатков. Одним из основных недостатков O-функций является их чрезмерная грубость. Если алгоритм А выполняет некоторую задачу за 0,001×N секунд, в то время как для ее же решения с помощью алгоритма В требуется 1000×N секунд, то алгоритм А в миллион раз быстрее, чем алгоритм В. Тем не менее А и В имеют одну и ту же временную сложность O(N). Следовательно, очень часто необходим более детальный анализ алгоритмов, претендующих на решение одной и той же задачи. В статье рассматривается методика сравнительного анализа различных алгоритмов на примере алгоритмов последовательного поиска. Выбор данной группы алгоритмов основан на том, что последовательный поиск очень часто применяется и в повседневной жизни, он интуитивно понятен и на первый взгляд тривиален. Казалось бы, что можно улучшить в простом последовательном переборе? Но начнем все-таки с того, что знание алгоритмов последовательного поиска профессиональному программисту крайне необходимо. Представьте себе, что необходимо найти книгу в книжном шкафу, расположение книг в котором неизвестно. Так как книгу найти все-таки нужно, то в этом случае очевидный подход – простой последовательный перебор всех находящихся в шкафу книг. Если повезет, вы затра тите только одно сравнение, в худшем случае – N сравнений, где N – количество книг в шкафу. Среднее число сравнений, т. е. если поиск книг будет повторяться многократно, равен N/2. Таким образом, если мы ничего не знаем об организации исходных данных (например, исходные данные могут быть упорядочены), то, скорее всего, без использования последовательного поиска не обойтись. Сформулируем алгоритм более точно. Пусть имеется массив записей с ключами K1, K2, ..., Kn. Необходимо найти запись с заданным ключом K. Тогда традиционный алгоритм последовательного поиска будет включать следующие шаги (алгоритм А).^[23]

---

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

Линейным называется алгоритм, в котором все этапы решения задачи

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

«следование».

Ветвлением называется такая алгоритмическая структура, в которой, в зависимости от истинности условия, выбирается только одно из возможных направлений выполнения алгоритма. Цикл предусматривает многократное повторение действий.^[24]

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

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

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

ГЛАВА III. НЕКОТОРЫЕ ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ РАЗЛИЧНЫХ ТИПОВ АЛГОРИТМОВ

Итак, первым делом мы рассмотрим несколько примеров линейного алгоритма из повседневной жизни. Рассмотрим пример алгоритма на естественном языке:

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

---

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

3. Если d < 0, то напечатать сообщение «Корней нет» и перейти к п.4. Иначе вычислить ????1 = −????+√D 2???? , ????2 = −????−√D 2???? и напечатать значения x1 и x2.

4. Прекратить вычисления.^[25] Или же например рецепт приготовления любого блюда является линейным, например, приготовления бутерброда с маслом, с сыром, салата из моркови, чеснока и майонеза, просто алгоритм открывания замка. Или же пример линейного алгоритма, основанного на литературном произведении:

"Сказка о царе Салтане": алгоритм превращения лебедя в

царевну:

Тут она, взмахнув крылами,

Полетела над волнами

И на берег с высоты

Опустилась в кусты,

Встрепенулась, отряхнулась

И царевной обернулась.

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

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

Рис. 8. Богатырь на распутье.

На камне написано:

«Направо пойдёшь – коня потеряешь, себя спасёшь; налево пойдёшь – себя потеряешь, коня спасёшь; прямо пойдёшь – и себя и коня потеряешь».

Попробуем составить алгоритм действий, который составил автор надписи на камне для путников?

1. Если мы пойдём направо, то потеряем коня. Если же мы не пойдём направо, то у нас остаётся два варианта (мы считаем, что назад возвращаться путник не будет): пойти прямо и налево.
2. В случае, если мы пойдём налево, то потеряем себя, а коня спасём.
3. Если же мы пойдём прямо, то потеряем и себя, и коня.

Блок-схема этого алгоритма выглядит так:

Рис. 9. Блок-схема.^[27]

Далее идут примеры разветвляющегося алгоритма.

Из повседневной жизни любого человека:

Посмотрел в окно. 
Идет дождь – Не идти гулять, остаться дома. 
Не идет дождь - Пойти гулять.

---

Из литературного произведения:

Подъехал богатырь к камню с надписью:
Налево пойдешь - сам пропадешь
Направо пойдешь - коня потеряешь
Прямо пойдешь - и сам пропадешь, и коня потеряешь

Последний пример разветвляющегося алгоритма из геометрии:

Имеются две прямые линии.
Прямые имеют общую точку - прямые пересекаются
Прямые не имеют ни одной общей точки - прямые не пересекаются.

И заключительным будут примеры циклического алгоритма.

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

Рассмотрим пример на составление циклического алгоритма. Мы уже несколько раз обсуждали перевод чисел из десятичной системы в двоичную. Теперь пришло время чётко сформулировать этот алгоритм.

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

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

Решение:

То есть, алгоритм будет выглядеть так:

1. Если число равно 0 или 1, то это и будет его двоичное представление.
2. Если число больше 1, то мы делим его на 2.
3. Полученный остаток от деления записываем в последний разряд двоичного представления числа.
4. Если полученное частное равно 1, то его дописываем в первый разряд двоичного представления числа и прекращаем вычисления.
5. Если же полученное частное больше 1, то мы заменяем исходное число на него и возвращаемся в пункт 2).^[28]

Блок-схема этого алгоритма выглядит следующим образом:^[29]

В сутках 23 часа 56 минут 4 секунды, и они повторяются каждый раз;
Испарение воды: вода-нагрев-испарение-охлаждение-осадки;
Стрелки часов бегут по кругу 24\7 , пока не сядет батарейка.

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

ЗАКЛЮЧЕНИЕ

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

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

---