Файл: Алгоритмизация как обязательный этап разработки программы.pdf

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

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

2 Понятие алгоритма. Свойства и виды алгоритмов

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

Алгоритм — понятное и точное предписание(указание) исполнителю совершить определенную последовательность действий для достижения поставленной цели за конечное число шагов.^[5]1

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

1. Алгоритм должен работать за конечное количество времени. Если ваш алгоритм не может разобраться с проблемой, для которой он был создан, за конечное количество времени, то он бесполезен.
2. Он должен иметь чётко определённые инструкции. Каждый шаг алгоритма должен быть точно определён. Инструкции должны быть однозначны для каждого случая.
3. Он должен быть пригодным к использованию. Алгоритм должен решать проблему, для решения которой он был написан.

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

1. Дискретность — это разделение выполнения решения задачи на отдельные операции(выполняемые исполнителем по определенным командам). Анализ различных примеров алгоритмов показывает, что запись алгоритма распадается на отдельные указания исполнителю выполнить некоторое законченное действие. Каждое такое указание называется командой. Команды алгоритма выполняются одна за другой. После каждого шага исполнения алгоритма точно известно, какая команда должна выполнятся следующей.
2. Элементарность (понятность) — каждый шаг алгоритма должен быть простым, чтобы исполнитель мог выполнить его одним действием.
3. Определенность (детерминированность, точность) — свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускал произвольной трактовки. Также строго должен быть определен порядок выполнения отдельных шагов. Алгоритм не должен быть рассчитан на принятие каких-либо самостоятельных решений исполнителем, не предусмотренных составленным алгоритмом.
4. Массовость — алгоритм решения задачи разрабатывается в общем виде, т.е. гарантируется применимость алгоритма ко всем задачам рассматриваемого типа, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется «область применимости алгоритма».
5. Результативность — свойство, подразумевающее, что любой алгоритм должен завершаться после конечного числа шагов, с указанием того, что считать результатом. Цель выполнения любого алгоритма состоит в получении конкретного результата, который имеет определенное отношение к исходным данным.^[6]2

---

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

1. Линейный
2. Ветвящийся
3. Циклический

В алгоритмах линейной структуры действия выполняются последовательно друг за другом.^[7]1

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

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

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

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

Цикл с предусловием.

В данной циклической структуре сначала проверяется значение условного выражения (условие) перед выполнением очередного шага цикла. Если значение условного выражения истинно, исполняется тело цикла. После чего управление вновь передается проверке условия и т.д. Эти действия повторяются до тех пор, пока условное выражение не примет значение ЛОЖЬ. При первом же несоблюдении условия цикл завершается. Количество шагов цикла заранее не определено и зависит от входных данных задачи. Особенностью цикла с предусловием является то, что если изначально условное выражение ложно, то тело цикла не выполнится ни разу.

---

Цикл с постусловием.

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

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

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

Алгоритмы существуют не сами по себе. Они предназначены для определенного исполнителя (человека, робота, компьютера, языка программирования и т.д.). В связи с этим способы записи алгоритмов могут быть различны. Наиболее распространенными являются 3 типа записи алгоритмов:

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

Примером вербальной записи алгоритма может являться рецепт приготовления шарлотки:

Продукты:

• сахар — 1 стакан;
• мука — 1 стакан;
• яйца — 3 штуки;
• разрыхлитель для теста — ½ ч.л.;
• яблоки — 2 штуки;
• масло сливочное — для смазывания формы.

---

Способ приготовления:

• Сахар смешать с яйцами с помощью венчика или миксера, добавить муку и разрыхлитель. Тщательно перемешать до растворения сахара.
• Тем временем форму для запекания смазать маслом. Яблоки очистить от кожи и нарезать дольками.
• Выложить яблоки в форму и залить получившимся тестом.
• Духовку разогреть до 180-200 градусов. Поставить шарлотку с яблоками запекать до готовности.

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

• Графический — алгоритм описывается с помощью набора графических изображений (блок-схем). Описание алгоритма с помощью блок схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Написание алгоритмов с помощью блок-схем регламентируется ГОСТом. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость» алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур. Так же к графической записи алгоритма относят запись алгоритма с использованием диаграммы Нэсси Шнейдермана. Диаграмма Нэсси-Шнейдермана была предложена в сочетании со структурным программированием как средство борьбы с проблемой "клубка спагетти", присущей схемам алгоритмов. Эта диаграмма, бесспорно, заменяет одномерное представление вложенных операторов двумерным. Тем не менее, по мере роста сложности программного кода появляются проблемы отображения, поскольку элементы диаграммы быстро становятся все меньше и меньше.^[8]3

Можно выделить несколько «типичных» действий (этапов), которые в различной последовательности выполняются при решении задач:

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

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

---

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

В качестве примера используем самую простую программу, которую пишут новички на их первом языке программирования — данная программа выводит надпись «Hello, World»:

#include <iostream>

#include <cstdlib>

using namespace std;

int main()

{

cout << "Hello, world!" << endl;

system("pause");

return 0;

}

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

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

для j от 1 до n-1

для i от 1 до n-j

если aᵢ < aᵢ₊₁ поменять их местами

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

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

Алгоритмизация – как ключевой этап программирования

Программа – это запись алгоритма на языке программирования, приводящая к конечному результату за конечное число шагов. Программа – это детальное и законченное описание алгоритма средствами языка программирования.^[9]1

---