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

ВВЕДЕНИЕ

Понятие алгоритм появилось в средних веках, и его авторство приписывают математику Муххамеду бен Аль-Хорезми. Считается, что звучание слова алгоритм - это результат произношения слова Аль-Хорезми. Первоначально термин алгоритм применяли только к выполнению арифметичес­ких действий над десятичными числами [4]. В дальнейшем это понятие получило более широкое применение, и, в общем смысле, алгоритм представляет собой некоторую, однозначно определенную последовательность действий, предназначенную исполнителю для решения поставленной задачи за обозримый промежуток времени. Алгоритмы используются людьми повсеместно, и практически каждый из нас знаком с ними. Например, рецепт яблочного пирога - это линейный алгоритм. Исполнителем этого алгоритма является человек. Но термин "алгоритмическая конструкция" уже ассоциируется с вычислительной техникой. В качестве исполнителя такого алгоритма, как правило, выступает электронное вычислительное устройство.

Цель работы. Рассмотреть основные структуры алгоритмов и на практических примерах провести их сравнительный анализ.

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

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

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

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

Дискретность – это свойство подразумевает, что алгоритм делится на простые шаги [3,4].

Массовость – это свойство показывает, что алгоритм представляет собой универсальную последовательность действий, которая применяется для решения всех задач данного типа [3,4].

Определенность – это свойство ал­горитма свидетельствует, что шаги инструкции алгоритма должны быть однозначны и не допускать двусмысленности [3,4].

Результативность – свойство состоит в том, что алгоритм должен завершаться за конечное число шагов [3,4].

Формальность – это свойство указывает, что инструкции алгоритма должны быть понятны любому исполнителю, для которого они предназначены [3,4].

Разработка алгоритма предшествует кодированию программы на языке программирования и представляет собой очень сложный процесс. Качество разработки алгоритма существенно влияет на эффективность написанной на его основе программы. Существуют уникальные алгоритмы для решения математических задач. Например, алгоритм Евклида для поиска наибольшего общего делителя двух чисел [1, 3]. Этот алгоритм очень эффективный и требует достаточно небольшого числа операций для решения поставленной задачи. Но таких алгоритмов очень мало и, как правило, они носят имена своих создателей.

На второй ступени по качеству разработки находятся алгоритмы, описанные в открытой печати, предназначенные для решения стандартных типовых задач, которые приходится решать программистам. Это такие задачи, как сортировка массивов (пузырьковая сортировка), поиск наикратчайшего пути (задача коммивояжера), быстрый поиск и многие другие [1, 3]. Эти стандартные алгоритмы тоже очень эффективны, так как в их создании участвовали группы специалистов, обладающие высокой квалификацией. Библиотека таких алгоритмов опубликована в известном труде "Искусство программирования" Дональда Кнута [1].

В практике специалиста по информационным системам могут встречаться задачи, для решения которых стандартных алгоритмов не существует, поэтому ему самостоятельно придется их разрабатывать. Любые сложные алгоритмы состоят из простых структур - алгоритмических конструкций. Основные алгоритмические конструкции представляют собой базовые кирпичики, из которых строятся большие алгоритмы. Сочетание базовых конструкций позволяет задать сложную цепочку действий для решения поставленной задачи. Основные алгоритмические конструкции подразделяются на 3 типа: линейные структуры, разветвляющиеся структуры и циклические [2-4]. Все они будут рассмотрены в данной курсовой работе.

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

1.1. Способы описания алгоритмов

Распространены четыре основные способа описания алгоритмов: словесное описание, псевдокод, блок-схема и программа [4].

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

Псевдокод — это язык описания алгоритма, который включает набор команд, представленных на естественном, ча­стично формализованном языке. На псевдокоде удобно разрабатывать алгоритмы, используя основные алгоритмические конструкции. Поэтому описанные на псевдокоде алгоритмы удобны для кодирования на языках программирования. Единого стандарта для псевдокода не разработано, поэтому на практике можно встретить различные его варианты [3,4].

Блок-схема — это язык описания алгоритмов с помощью геометрических фигур, соединенных линиями, показывающими порядок выполнения команд алгоритма. Этот способ представления алгоритма очень наглядный и, как правило, используется в отчётах и презентациях [3,4].

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

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

1.2. Применение линейных алгоритмов

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

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

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

Блок схема алгоритма приведена на рисунке 1

Рисунок 1 – Блок-схема алгоритма сложения двух чисел

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

Начало алгоритма

Ввод двух чисел а, b.

Вычислить сумму S = а + b.

Вывод S.

Конец алгоритма.

Пример. Составить компьютерную программу для вычисления общей поверхности и объема конуса. Заданы значения радиуса основания R и длины образующей L.

Решение.

Общая площадь поверхности вычисляется по формуле:

S = R² + RL.

Объем конуса вычисляется по формуле:

,

где H - высота конуса, определяемая по формуле:

.

Блок схема алгоритма представлена на рисунке 2.

Рисунок 2 - Блок-схема линейного алгоритма вычисления общей поверхности и объема конуса

Словесное описание алгоритма. На первом этапе работы алгоритма вводятся исходные значения: длина образующей (L) и радиус окружности (R). Затем следуют три вычислительные формулы, в которых последовательно вычисляются высота конуса (Н), площадь его поверхности (S) и объем (V). Завершается алгоритм выводом на экран вычисленных величин: площади S и объема V.

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

Program SandV;

Var

L, R, H, S, T, V : real;

{Основной код программы}

Begin

{Ввод исходных данных}

ReadLn(R); ReadLn(L);

{Основные вычисления}

H : = Sqrt(L*L-R*R);

S : = PI*Sqr(R) +PI*R*L;

V := PI* Sqr(R)*H/3;

{Вывод результатов}

WriteLn('V=', V:8:4);

WriteLn('S=' , S:8:4);

End.

В код добавлены комментарии, которые делают понятными все этапы работы алгоритма. Добавление комментариев - это один из важных элементов представления алгоритмов на языке программирования.

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

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

2. Разветвляющиеся алгоритмы

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

2.1. Способы построения разветвляющегося алгоритма

Порядок выполнения разветвляющийся конструкции следующий. На первом этапе проверяется истинность логического выражения, которое представляет собой условие. Если условие выполняется (истинно), то реализуется оператор 1, иначе (ложь) - оператор 2 [2].

Рисунок 3 - Блок-схема оператора ветвления, предусматривающего выполнения двух операторов

Разветвляющейся конструкции на языке программирования ставится в соответствие оператор условного перехода, который на языке высокого уровня Паскаль имеет вид [2]:

if логическое выражение then

Оператор 1

else

Оператор 2

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

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

if x>0 then

y:=x+4

else

y:=x*5;

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

Рисунок 4 - Блок-схема оператора ветвления, предусматривающего выполнения одного оператора

На языке программирования Паскаль разветвляющаяся конструкция, предусматривающая выполнение одного оператора, имеет вид [2]:

if логическое выражение then Оператор 1;

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

if x>10 then y:=x+7;

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

Пример. Даны три числа a, b, c. Найти наибольшее их этих трех чисел.

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