Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования ( Три ключевых структуры алгоритма ).pdf
Добавлен: 31.03.2023
Просмотров: 108
Скачиваний: 1
ВВЕДЕНИЕ
Одним из основополагающих определений и понятий в информатике, алгоритмизации и программирования является понятие алгоритма.
Алгоритмом называют определенную последовательность команд, в результате исполнения которых человек или электронно-вычислительная машина (ЭВМ) имеет возможность решить поставленную перед ним задачу.
Цель данной работы – обзор основных структур алгоритмов, их сравнительный анализ и подробное изучение, включая примеры их использования. В данной курсовой работе будут рассматриваться три основные главы:
1. Три ключевых структуры алгоритма.
2. Сравнительный анализ трех основополагающих структур алгоритмов.
3. Некоторые примеры использования различных типов алгоритмов.
В каждой главе, соответственно, будут рассматриваться несколько подглав, о которых мы поговорим ниже.
Первая глава охватывает три основные структуры алгоритма, такие как линейный алгоритм, циклический алгоритм и разветвляющийся алгоритм. Здесь же мы рассмотрим общие черты и свойства, присущие всем алгоритмам, а именно: дискретность, детерминированность (однозначность), результативность (конечность), массовость. Каждый тип алгоритма будет подробно рассмотрен и разобран, с приведением соответствующих примеров, схем и картинок.
Вторая глава включает в себя одну из самых главных частей – нахождение особенностей каждого алгоритма, их схожесть и исключительные свойства. Анализируя три основные структуры алгоритмов, мы можем выявить для себя и дальнейшей работы наиболее подходящую структуру. Именно, в связи с этим данный этап является неотъемлемой частью основ алгоритмизации и программирования.
В третьей и последней главе соответственно будут приведены примеры использования всех трех типов структур алгоритмов, которые были указаны ранее. Эти примеры будут подкреплены нужными таблицами, схемами и картинками.
Выводом из данной курсовой работы будет являться заключение, после которого будет следовать библиография, т. е. список использованной литературы в дополнение с приложением.
ГЛАВА I. ТРИ КЛЮЧЕВЫХ СТРУКТУРЫ АЛГОРИТМА
Перед тем как перейти к разбору трех основных структур алгоритмов, мы рассмотрим пять свойств, которые так или иначе относятся к каждому из этих типов, а именно: дискретность, массовость, детерминированность (однозначность), результативность (оно же и конечность).
Для начала рассмотрим дискретность. Дискретность (от лат. discretus — разделённый, прерывистый. Дискретность — всеобщее свойство материи. Например, механические часы, передвигают минутную стрелку дискретно на 1/60 часть окружности) — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.[1]
Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
В данном абзаце мы обсудим такое важное свойство как массовость. Свойство алгоритма «Массовость» — алгоритм решения задачи разрабатывается в общем виде, то есть он должен быть применим для некоторого класса задач, различающихся только исходными данными. При
этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Теперь мы перенесемся к следующему свойству, такому как детерминированность. Детерминированность (определенность, точность, однозначность). Это свойство заключается в том, что при задании одних и тех же исходных данных несколько раз алгоритм будет выполняться абсолютно одинаково и всегда будет получен один и тот же результат. Свойство детерминированности проявляется также и в том, что на каждом шаге выполнения алгоритма всегда точно известно, что делать дальше, а каждое действие однозначно понятно исполнителю и не может быть истолковано неопределенно. Благодаря этому свойству выполнение алгоритма носит механический характер.
К трем вышеперечисленным свойствам так же добавляется результативность. Результативность Завершение алгоритма определёнными результатами.[2] Так же результативность - означает, что выполнение алгоритма обязательно должно привести к решению поставленной задачи, либо к сообщению о том, что при заданных исходных величинах задачу решить невозможно. Алгоритмический процесс не может обрываться безрезультатно.
1.1 Линейный алгоритм
Компьютерная программа является алгоритмом действий для процессора компьютера, а сам процессор – исполнителем данного алгоритма.
Сама по себе компьютерная программа является общим алгоритмом, который в свою очередь разделяется на отдельные составные части, на отдельные алгоритмы, которые принято называть алгоритмическими структурами, хотя не будет ошибочно, если называть такие структуры просто алгоритмами. Владея навыками в применении алгоритмических структур, программист как бы строит программу в целом, как здание из отдельных кирпичиков.
В процессе создания и использования языков программирования были реализованы многие виды алгоритмических структур, как говорится – на все случаи жизни. В зависимости от характера логического условия процесс может состоять из двух и более ветвей. В любой конкретный момент реализации данной структуры осуществляется обработка только по одной из ветвей, а выполнение операций по другим ветвям исключается[3]. На сегодняшний день, в любом современном языке, на основании имеющегося арсенала алгоритмов, можно оформить практически любое поведение процессора по желанию программиста, другими словами – написать абсолютно любую программу.
Не смотря на множество возможностей создания огромного количества самых сложных программ, большое количество языков программирования, различных требований к созданию компьютерных программ, алгоритмических структур всего несколько. Грамотно осознав и накопив опыт по работе с этим количеством алгоритмов, можно смело приступать к созданию компьютерной программы. Причем даже не столь важно, какой язык программирования использовать, синтаксис языка (его ключевые слова и правила оформления) всегда можно посмотреть в нужном справочнике, а вот общий алгоритм вашей собственной программы, принципы и пути взаимосвязей между алгоритмическими структурами в ней известны только вам, как автору, и никто вам здесь не помощник, ни справочники, ни база данных Интернета, только вы сами и ваши знания. Еще одно доказательство тому, что не существует программ с абсолютно одинаковым алгоритмом. Если сравнить между собой две одинаковые на первый взгляд программы, которые выполняют одни и те задачи, выполнены по одному и тому же заказу (техническому заданию - ТЗ), на входе получают одни и те же данные, а на выходе выдают одинаковые результаты, то все равно их внутренний алгоритм, внутреннее содержимое будет разное и зависеть оно будет только от индивидуальных особенностей автора-программиста[4]. Из чего можно сделать вывод, что создание программы для компьютера – это глубоко творческий процесс. Также как два художника срисовывая в природе одну и ту же лесную опушку, никогда не нарисуют одинаково.
Итак, как уже говорилось, существует несколько видов алгоритмических структур, которые существуют почти во всех языках программирования, кроме нескольких узконаправленных:
1. Линейный алгоритм;
2. Разветвленный алгоритм (ветвление);
3. Алгоритмическая структура «Выбор»;
4. Алгоритмическая структура «Цикл» (циклический алгоритм).
Язык Visual Basic не исключение, как член группы высокоуровневых языков программирования, в нем присутствуют все четыре вида алгоритмических структур. Рассмотрим подробнее самый простой вид алгоритма – линейный алгоритм.
Линейным называется алгоритм, в котором команды выполняются последовательно одна за другой.
Не зря линейный алгоритм называют еще и элементарным – в нем абсолютно все команды для процессора расписаны последовательно, а значит, и выполняются также – одна за другой, по линейке, без отклонений, без условий. Такие команды называют еще серией команд.
Давайте вспомним примеры.
Пример с «Калькулятором» – программой, которая умела суммировать цифры и состояла лишь из поля ввода для переменной a, поля ввода для переменной b, кнопки «+», кнопки «=» и поля вывода результата. Или пример с выполнением домашнего задания, по информатике домашнее задание мы выполняли последовательно, у нас все для этого было: учебник по информатике, записи лекций с уроков, знания, вопросы домашнего задания и так далее.
Такая программа бы являлась самой простой, потому что построена она на самом простом алгоритме – линейном, других возможностей, кроме суммирования, она бы не имела. То есть процессор, после загрузки вел себя строго линейно – ожидал ввода первой цифры, потом второй, суммировал и выдавал какой-то результат[5]. Мы не предоставили возможности процессору повести себя как-то иначе. А что если бы наш «Калькулятор» умел бы не только суммировать, но и делить, например, a на b. Из правил арифметики мы знаем, что деление на 0 невозможно, но получилось бы так, что пользователь нашей программы в качестве делителя ввел ноль. Математическая операция невозможна, процессор бы вернул ошибку, а программа – неприятное сообщение. Как быть в этом случае? На это и существуют более «продвинутые» алгоритмические структуры, о которых мы поведем речь в следующих статьях. Может сложиться мнение, что линейный алгоритм неудобен и не стоит его использовать, владея знаниями по другим алгоритмам. Но это в корне неверный вывод – написать программу, не используя линейный алгоритм невозможно. Он составляет костяк программы, ее основу, в внутри него, там где это необходимо, производят вставки других алгоритмических структур.
Прежде чем, приступить к написанию программы, чтобы сделать алгоритм более наглядным и лучше отследить моменты дискретизации и детерминированности, часто используют блок-схемы.[6] Это графическое изображение, где в виде различных геометрических фигур описывают элементы будущей программы. Причем за определенными фигурами закреплены конкретные элементы, например, серию команд (линейный алгоритм) принято обозначать в виде прямоугольника, внутри которого описывается сама последовательность действий. Фигурой эллипса (прямоугольника с закругленными углами) обозначают начало и конец программы. Стрелками указывают направление действия программы. Существуют специальные ГОСТы, где перечислены все возможные фигуры, используемые для этих целей: ГОСТ 19.701-90, ГОСТ 19.002-80, ГОСТ 19.003-80.
Попробуем изобразить «Калькулятор» из нашего прошлого примера в виде блок-схемы:
Упрощенная блок-схема линейного алгоритма
У нас получилась довольно простая блок-схема всего из трех геометрических фигур, где во внутрь прямоугольника мы образно поместили серию команд. Такая схема является приблизительной и не отражает сущности программы и ее составных частей, даже на уровне линейного алгоритма. Попробуем усложнить блок-схему этого же примера, используя более широкий диапазон фигур:[7]
Более сложная схема линейного алгоритма
Как мы видим из этого рисунка, для каждого действия существует определенная фигура: для ввода-вывода – параллелограмм, для сохранения данных в неавтономную (энергозависимую память) – прямоугольник с закругленными боками. Этот наш пример можно было бы усложнять, приводить к более профессиональному виду и далее, но на данном этапе работы, примем такой вариант, как наиболее правильный.[8]
Итак, подведем итоги:
1. Компьютерная программа – общий алгоритм для процессора, который состоит из отдельных блоков – алгоритмических структур;
2. Алгоритмических структур известное количество, правильное и рациональное использование которых позволяет реализовать любые, самые сложные маневры при написании программы;
3. Создание программы – творческий процесс. Это – продукт, созданный индивидуально каждым программистом, основываясь на его знаниях, умениях, навыках и опыте работы;
4. Самое сложное в программировании – целенаправленное и осознанное использование алгоритмических структур;
5. Линейный алгоритм самый простой и не позволяет реализовать элементы программы в зависимости от условий, однако на нем базируется остов всей программы. Это как цемент в строительстве стены – его не видно в готовом объекте, но без него стена ссыпалась бы в песок, камни и другие строительные составляющие;
6. В целях визуального представления связки элементов программы используются графические блок-схемы. Прежде чем приступить к написанию кода программы, желательно составить такую схему – она поможет в дальнейшем не ошибиться и не запутаться.
1.2 Разветвляющийся алгоритм
Разветвляющийся алгоритм - алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.[9]