![](/stc/img/evkova.png)
ОСНОВНЫЕ СТРУКТУРЫ АЛГОРИТМОВ (Сравнительный анализ и примеры использования структур алгоритмов)
Содержание:
Введение
Алгоритмические конструкции возникают в любой социальной сфере жизни человека. Алгоритмическое мышление является важным аспектом, ведь с помощью алгоритмов можно организовывать и описывать мыслительную деятельность и практически любые процессы, будь то приготовление кулинарного блюда по рецепту или решение математической задачи.
Изучению алгоритмизации и программированию необходимо уделять пристальное внимание в связи с тем, что это самое удобное средство для развития логики и мышления человека. Однако, тема алгоритмизации и, в частности, сравнительного анализа структур алгоритмов, имеет некоторые трудности при изучении параметров самого анализа, так как в широком доступе нет научных работ, относящихся к данному вопросу. Нами был изучен большой массив информации. Используемые источники и литература представляют в основном базовые знания по алгоритмизации и не дают более детальных знаний, необходимых для проработки вопроса сравнительного анализа структур алгоритмов. Существует большой массив информации по сравнительному анализу отдельных алгоритмов, например, анализ алгоритмов поиска и т.п., но параметров сравнительного анализа именно структур алгоритмов не было найдено. Все выше сказанное дает нам основание говорить об актуальности выбора темы нашей работы.
Целью исследования является выделение общего между структурами алгоритмов и проведение их сравнительного анализа. Для достижения поставленной цели были сформулированы следующие задачи:
1. Сформулировать понятие «алгоритм» и его свойства, а также представить способы записи алгоритмов;
2. Обозначить классификацию структур алгоритмов: линейную, разветвляющую и циклическую;
3. Выделить общие параметры структур алгоритмов и провести сравнительный анализ на основе примеров.
Задачи данной темы будут исследованы и представлены в нашей работе в трех главах, каждая из которых логически закончена и включена в процесс по реализации нашей цели.
1. Алгоритм и его свойства, способы записи
1.1. Алгоритм и его свойства
Алгоритм относится к основным базовым понятиям математики и информатики. Вся наша жизнь так или иначе связана с разнообразными алгоритмами. Само понятие алгоритм в современном мире прочно входит в наш обиход, это понятие уверенно шагнуло и в разговорную речь. Появляется все больше понятий слова алгоритм «Алгоритм поведения» или «Алгоритм успеха» которые не редко можно услышать по телевизору или в прессе, но в основном алгоритмы применяются к вычислительным и управляющим процессам.
Очень часто в роли исполнителей выступают ЭВМ и прочие вычислительные устройства, но алгоритмы необязательно относятся только к компьютерам, так, например, четко описанный рецепт приготовления кулинарных блюд тоже является алгоритмом, но в роли исполнительного устройства выступает человек, который по описанному алгоритму может приготовить блюдо. Также в роли исполнителя может быть некий механизм или машина, например, дверной замок тоже является исполнительным механизмом, ключ в данном случае выступает в роли алгоритма.
Многие правила, всевозможные инструкции и прочее также можно отнести к алгоритмам в которых содержатся четкие указания к действиям. К таким инструкциям можно отнести, например, «инструкции по оказанию первой неотложной медицинской помощи, правила пожарной безопасности, правила поведения на водоемах и т.д.». В частых случаях несоблюдении этих правил «алгоритмов» может привести к печальным последствиям.
Алгоритм – четкое описание последовательности действий, которые необходимо выполнить для получения результата [4, с.6]. Непосредственно термин «алгоритм» происходит от имени Хорезмского математика-ученого Аль-Хорезми – Algorithmi жившего в VIII – XI веках н.э., внесший немалый вклад в алгебру, геометрию и прочие науки.
Данное выше определение алгоритма нельзя считать строгим - не вполне ясно, что такое «точное предписание» или «последовательность действий, обеспечивающая получение требуемого результата». Поэтому обычно формулируют несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций [8, с.5].
Порядок действий считается алгоритмом в том случае, если он обладает определёнными свойствами [3, с.8].
Правила выполнения арифметических операций или геометрических построений представляют собой алгоритмы. При этом остается без ответа вопрос, чем же отличается понятие алгоритма от таких понятий, как «метод», «способ», «правило». Можно даже встретить утверждение, что слова «алгоритм», «способ», «правило» выражают одно и тоже (т.е. являются синонимами), хотя такое утверждение, очевидно, противоречит «свойствам алгоритма».
Само выражение «свойства алгоритма» не совсем корректно. Свойствами обладают объективно существующие реальности. Можно говорить, например, о свойствах какого-либо вещества. Алгоритм – искусственная конструкция, которую мы сооружаем для достижения определенных целей. Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. Поэтому нужно говорить все же не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму [8, с.6].
К различным алгоритмам в разных явных и не явных формах предъявляются следующие требования:
- конечность
- определенность
- дискретность
- массовость
- эффективность
1) Конечность алгоритма или результативность. Означает, что алгоритм должен иметь возможность своего завершения после определенного количества шагов, как и каждое его действие.
Это требование происходит из теории вычислений, которая пытается провести грань между правильными и неправильными алгоритмами. Алгоритм считают правильным, если на любом допустимом входе он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. Неправильный алгоритм для некоторого входа может вовсе не остановиться или дать неправильный результат [7, с.42].
Но иногда на практике есть случаи, когда используются бесконечные «цикличные» процессы, например, поддержание заданной температуры в бойлере или холостого хода в автомобиле.
Часто термин алгоритм неформально используется по отношению к этапам решения, не всегда приводящим к конечному результату. Примером служит известный школьный алгоритм деления в столбик, который не дает конечного результата в процессе деления на 1 и 3.
2) Определенность алгоритма каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче [8, с.5].
Для исключения неоднозначности разработаны определённые методы для записи алгоритмов для примера можно привести запись в виде блок-схем которая записывается специальными пиктограммами. Каждый такой блок указывает на четкое выполняемое действие.
Другим методом записи алгоритмов является формально определенный язык, в котором каждое утверждение имеет однозначно четкий смысл. Для работы алгоритмов на ЭВМ применяют языки программирования.
3) Дискретность (прерывность, раздельность) - выполнение команд алгоритма последовательно, с точной фиксацией моментов окончания выполнения одной команды и начала выполнения следующей, т. е. алгоритм должен содержать последовательность указаний (команд), каждое из которых приводит к выполнению в исполнителе одного шага (действия) [2, с.8]. Для каждого шага алгоритма требуется конечный отрезок времени, в котором будет выполнен этот шаг с последующим преобразованием входных данных в результат. То есть преобразование данных в алгоритме осуществляется во времени дискретно.
4) Массовость. Алгоритм разрабатывается в общем виде так, чтобы его можно было применять для класса задач, различающихся только исходными данными. При этом исходные данные выбираются из некоторой области, которая называется областью применяемости алгоритма [3, с.9]. Например, можно взять алгоритм вычисления площади круга по формуле S=πR2, где R будет является входными данными, а S преобразованными выходными.
Но не все математические задачи можно решить с помощью алгоритмов, такие задачи, которые не имеют общего решения называются алгоритмически не разрешимыми.
5) Эффективность алгоритма. Алгоритм, который выполняет действие за меньшее число шагов признается более эффективным [7, с.43].
Очевидно, что при выборе алгоритмов нужно учитывать не только их характеристики качества, но и способ реализации алгоритма. Например, многие итерационные алгоритмы удобны для ПК, но слишком трудоемки для человека. Тип используемой ПК также может влиять на выбор алгоритма (иногда имеет место и обратный вариант, когда сначала определяется алгоритм и лишь затем способ реализации) [2, с.10].
Это свойство, которое связано непосредственно с вычислительными ресурсами, используемыми алгоритмом. Для достижения максимальной эффективности алгоритма мы хотим минимизировать использование ресурсов. Однако различные ресурсы такие как (память и время) нельзя сравнивать напрямую. Считать какой алгоритм эффективен в нашем случае будет зависит от того, что нам нужно, либо использование минимального количества памяти, либо выполнение алгоритма за минимальное время или другие меры эффективности.
1.2. Способы записи алгоритмов
Для строгого задания различных структур данных и алгоритмов их обработки требуется иметь такую систему формальных обозначений и правил, чтобы смысл всякого используемого предписания трактовался точно и однозначно [2, с.10].
Алгоритм является абстракцией и поэтому один и тот же алгоритм можно представить многими способами. Если с алгоритмом работает человек, то это может быть традиционный язык (русский, английский), язык картинок и пиктограмм, а также математические формулы [7, с.43].
В настоящее время распространены следующие формы представления алгоритмов:
- словесная
- графическая;
- псевдокоды;
- программная.
Словесный способ является наиболее понятным для человека, благодаря этому каждый шаг алгоритма может понять любой исполнитель.
Данный способ получил значительно меньшее распространение из-за его многословности и отсутствия наглядности [8, с.9].
Примером может служить алгоритм задачи про волка, козу и капусту:
Дано:
Человеку, находящемуся на берегу реки, нужно переправить на противоположный берег волка, козу и капусту. В лодку человек может одновременно только одного «пассажира». Нельзя оставить вместе волка с козой и козу с капустой.
1. Переправить козу
2. Возвратиться самому
3. Переправить волка
4. Возвратиться с козой
5. Переправить капусту
6. Возвратиться
7. Переправить козу
Есть еще формально-словесный способ записи, это форма записи алгоритмов, которая представляет собой инструкцию. Она обязательно включает в себя математические символы, присутствует словесное объяснение. Это позволяет увеличить круг решаемых задач.
Примером может служить алгоритм вычисления площади треугольника по формуле Герона:
1. Задать численные значения a, b, c.
2. Вычислить p по формуле:
p = (a + b + c)/2.
3. Вычислить S по формуле:
S = √p(p - a)(p - b)(p - c)
4. Вывести результат.
Графический способ записи (изображения из графических символов или блок-схем).
Графический способ описания алгоритма иначе называют блок-схемой. В блок-схемах используются геометрические фигуры, каждая из которых изображает какую-либо операцию или действие, а также этап процесса решения задачи. Каждая фигура называется блоком. Порядок выполнения этапов показывается стрелками, соединяющими блоки. Блоки необходимо размещать сверху вниз или слева направо в порядке их выполнения [3, с.10].
Классические действия алгоритма изображаются следующими геометрическими фигурами по ГОСТ 19.701–90 (ИСО 58-7 85) [1] «Единая система программной документации», согласно которому каждой группе действий ставится в соответствие блок особой формы.
Блок-начала-конца алгоритма. Надпись в блоке: «Начало» («Конец»).
Блок ввода-вывода данных. Надпись в блоке: слово «ввод» («вывод» или «печать») и список вводимых (выводимых) переменных.
Блок схема процесс. Надпись в блоке: конкретная операция или группа операций.
Условный блок. Надпись в блоке: проверяемое условие.
В результате проверки условия осуществляется выбор одного из возможных путей (ветвей) вычислительного процесса. Если условие выполняется, то следующим выполняется этап по ветви «да», если условие не выполняется, то выполняется этап по ветви «нет».
В качестве примера приведем схему алгоритма (рис. 1) на языке блок-схем нахождения максимального из двух чисел.
рис 1.
Запись на псевдокоде (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.).
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языками [8, с.11]. Псевдокод обычно опускает детали, несущественные для понимая алгоритма человеком, такими деталями могут быть описания переменных, подпрограммы и т.д. Псевдокод используется для демонстрации того, как компьютерный алгоритм может и должен работать. Программисты часто используют псевдокод в качестве промежуточного этапа в программировании, между стадией планирования и стадией написания работающего кода. Хороший псевдокод может превратиться в комментарии к финальной версии программы и будет помогать программисту исправлять ошибки в будущем или корректировать код.
Для примера приведем листинг алгоритма на псевдокоде АЯ (школьный алгоритмический язык) для нахождения площади круга по радиусу.
алг нахождение площади круга по радиусу (арг вещ π, R, рез вещ S)
нач
ввод R
если R <=0 то вывод ‘значение должно быть положительным’
иначе
S:=3.14*(r*r)
вывод ‘площадь круга ’, R
кон
Программная запись алгоритма (тексты на языках программирования).
При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм.
Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем [8, с.12]. Следовательно, язык для записи алгоритмов должен быть формализован [2, с.25].
Как мы знаем любой алгоритм — это последовательность предписанных действий, выполнив которые за конечное число шагов можно прийти от исходных данных к искомому результату. Таким образом, алгоритм должен быть записан на промежуточном языке понятным компьютеру, с точными и однозначными правилами и отличном от естественного языка и языка блок-схем. Такой язык принято называть языком программирования, а запись алгоритма на этом языке – программой для компьютера. К алгоритмическим языкам относится машинный язык (система команд) и языки программирования. На данный момент в мире существует сотни языков программирования реально используемых на практике. Выделим некоторые из них: Java, Python, Ruby, PHP, C++, C#.
Примером записи алгоритма на языке программирования может служить листинг программы на языке С#.
using System;
namespace primer
{
// Программа демонстрации записи на языке программирования.
// Сравнение двух чисел и вывода в консоль максимального из них.
class Program
{
static void Main(string[] args)
{
// Объявляем переменные
int a = 0;
int b = 0;
int m = 0;
// Запрашиваем данные у пользователя
Console.WriteLine(" Введите первое число");
a = Convert.ToInt32(Console.ReadLine());
Console.WriteLine(" Введите второе число");
b = Convert.ToInt32(Console.ReadLine());
//Блок решения
if (a == b)
{
Console.WriteLine(" Числа {0} и {1} равны ", a, b);
}
else
{
if (a>b)
{
m = a;
}
if (a<b)
{
m = b;
}
Console.WriteLine(" Число {0} большee",m);
}
Console.WriteLine("\n Нажмите любую клавишу");
Console.ReadLine(); // Ожидание нажатия клавиши для завершения программы
}
}
}
Из вышеизложенного мы понимаем, что алгоритмы применяются практически в каждой сфере деятельности человека. Большинство алгоритмов уже созданы и типизированы, нам остается только правильно их применять на практике. При разработке нового алгоритма перед нами стоит задача составить алгоритм по существу, а все остальное, это перевод алгоритма с одного языка на другой.
2. Классификация основных структур алгоритма
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл [2, с.31].
В данном разделе более подробно рассмотрим вопросы основных структур алгоритмов и примеры их построения.
2.1 Линейная структура алгоритма
Алгоритм линейной структуры – алгоритм, в котором все действия выполняются последовательно друг за другом [6, с.5]. Все этапы действий в алгоритме выполняются в том порядке, в котором они записаны. Структура содержит в себе последовательное выполнение этапов:
- ввод исходных данных;
- вычисление искомых величин по формулам;
- вывод результатов;
2.2 Разветвляющиеся структуры алгоритмов
Разветвляющийся алгоритм описывает вычислительный процесс, реализация которого происходит по одному из нескольких заранее предусмотренных направлений [5, с.5]. Направление, по которому следует вычислительный процесс, называется ветвью процесса. Выбор определенного направления происходит в зависимости от полученных результатов заданного логического условия заданного в блоке ветвления. Результатами вычисления логического условия являются значения: «истина» (да), если происходит соответствие условию, и «ложь» (нет), когда условие не выполняется. Логические условия в структурах ветвления бывают простые и сложные. В простых условиях применяют две переменных, два числа или два арифметических выражения. Например x>y; x+y=5; a*b = b*a. Сложные условия представляют последовательность простых условий, объединённых знаками логических операций. Например: x>y И a>b. Структуру ветвления можно записать четырьмя основными вариантами:
- если – то
В структуре выполняется проверка условия, при логическом «истина» выполняется блок «действие», иначе блок пропускается. (рис. 2)
- если-то-иначе
В этой структуре после проверки условия при истинном значении выполняется первый блок действия, иначе при ложном значении выполняется второй блок действия. (рис. 3)
- выбор
Эта конструкция алгоритма применяется для реализации множественного ветвления. Поэтапно проверяются условия и при истинном значении выполняется действие, если условие не выполнено в структуре выбора, ни какое действие не выполняется. (рис. 4)
- выбор – иначе
Конструкция выбор – иначе (рис.5) аналогична предыдущей конструкции (рис. 4), единственное тут добавлен блок действия, который выполняется если ни одно условие не выполнено. (рис. 5)
2.3 Циклические структуры алгоритмов
Циклом называют повторение одних и тех же действий (шагов). Последовательность действий, которые повторяются в цикле, называют телом цикла [4, с.11]. Циклический алгоритм описывает вычислительный процесс, этапы которого повторяются многократно. Различают простые циклы, не содержащие внутри себя других циклов, и сложные (вложенные), содержащие несколько циклов. В зависимости от ограничения числа повторений выделяют циклы с известным числом повторений и циклы, число повторений которых заранее неизвестно [5, с.6].
Также циклом называется любая многократно выполняемая инструкция, организованная разными способами. Каждое выполнение тела цикла называется итерацией. Циклы различаются на циклы с предусловием, циклы с постусловием и безусловные циклы.
Циклы до (цикл с предусловием, рис. 6) – повторение до выполнения условия окончания цикла. В этой структуре тело цикла может не выполнится ни разу, условие проверяется еще до начала обработки тела цикла.
Пример использования на (рис. 7).
Циклы пока (циклы с постусловием, рис. 8) – в этой структуре минимум один раз выполняется тело цикла. Условие проверяется после первого выполнения тела цикла и контролирует выход из него.
Пример использования на рисунке 9.
Циклы для (безусловные циклы, рис. 10) или цикл с параметром. Эти циклы имеют в своем составе три обязательных элемента:
- Начальное значение, которое называется параметром цикла
- Значение, при котором цикл завершится
- Шаг цикла
На каждом этапе проверяется параметр цикла, если стартовое условие больше конечного, то цикл завершает работу. Иначе к стартовому значению прибавляем величину шага и цикл повторяется. Следует понимать, что любой безусловный цикл можно заменить на цикл с предусловием или постусловием. Пример безусловного цикла на (рис. 11).
В теле любого цикла могут находится операторы другого цикла, в таком случае цикл содержащий в себе другой цикл называют внешним, а цикл находящийся в теле первого - внутренним (вложенным). В общем такая структура построения цикла называется сложными или вложенными циклами. Правила организации внешнего и внутреннего цикла такое же, как и правила простого цикла. При построении сложных циклов следует обратить внимание на одно условие, все операторы внутреннего цикла должны располагаться в теле внешнего цикла.
При составлении циклических алгоритмов нужно придерживаться нескольких правил:
- Для окончания цикла, необходимо чтобы содержимое тела цикла влияло на пост- или предусловие, если условия не будут соблюдены мы получим бесконечный цикл. Но для некоторых задач такие циклы применяются, примером может служить контроль температуры в водогрейном котле.
- Переменные, передаваемые в цикл, должны обеспечивать хотя бы одно его выполнение.
Таким образом, мы выделили основные структуры алгоритмов, правила их записи и структурного построения. В исследовании наглядно показаны основные примеры построения структур алгоритмов, которые можно применять для разного круга задач. Алгоритмы показаны в порядке возрастания сложности и большую часть задач можно решить комбинацией базовых структур.
3. Сравнительный анализ и примеры использования структур алгоритмов
В этой части мы разберем примеры построения алгоритмов на основе ключевых структур и проведем сравнительный анализ структур.
Все базовые структуры алгоритмов линейные, ветвления и цикла объединяет одно свойство, все они обязательно имеют один вход и один выход.
Рассмотрим самую простую структуру - линейную.
В линейной структуре все блоки выполняются строго один за другим и никак иначе. Такая структура подходит нам для решения большинства задач, где не требуется принимать логическое решение и выполнять многократные действия. Для примера возьмем алгоритм вычисления площади круга по формуле S=π*R2, где S это вычисляемая площадь, а R это задаваемый радиус окружности. Словесно этот алгоритм будет выглядеть следующим образом:
1. Введем радиус R
2. Вычислим площадь по формуле S=π*R2
3. Выведем значение S
Данный алгоритм больше подходит для описания выполнения задачи на ЭВМ, но для записи такого алгоритма в компьютер нужно использовать специальные языки, которые понимает ЭВМ, языки программирования.
Приведем реализацию этой программы на языке C#, критерием выбора данного языка было то, что синтаксис и семантика языка схожа с такими популярными языками как С++ и JavaScript и переход от одного языка к другому не составляет особого труда, также с помощью данных языков решается широкий спектр задач.
static void Main(string[] args)
{
double S,R;
Console.WriteLine(" Введите радиус R");
R = double.Parse(Console.ReadLine());
S = 3.14 * (R * R);
Console.WriteLine("Площадь круга радиусом " + R + " = " + S);
Console.ReadLine();
}
Данный пример показывает нам, как работает линейная структура. Структура может содержать некоторое количество блоков ввода, вывода информации и блоки решения, но в итоговом варианте такой алгоритм должен быть конечен и приводил к искомому результату. Для алгоритмов, требующих принятия решения, например, логическое сравнение, линейная структура уже не подходит, для этого будем использовать структуру выбора.
Структура выбора (структура ветвления) предназначена для разделения алгоритма на заранее предусмотренные направления, зависящие от входных данных, в конечном итоге каждый из путей ведет к общему выходу.
Приведем пример алгоритма если – то в словесном виде.
1. Вводим число X
2. Сравниваем введенное число X
3. Если число X < 10 выводим “Число X меньше 10”
На языке блок-схем это выглядит так:
Это минимальная конструкция структуры ветвления если - то.
С помощью структуры ветвления и линейной структуры можно реализовать практически любые алгоритмы, но чем сложнее алгоритм, тем более объемными они будут и плохо читаемыми. На практике часто встречаются задачи, когда нужно выбрать не одно из двух, а одно из трех или более путей ветвления. Такую структуру называют выбором варианта, ее также можно построить из линейных и ветвящихся структур.
Даже очень простые расчеты могут поставить человека в тупик, если их надо повторить тысячи раз, а повторять операции миллионы раз человек совершенно не способен. Лучшие качества компьютеров проявляются не тогда, когда они рассчитывают значения сложных выражений, а когда многократно, с незначительными изменениями, повторяют сравнительно простые операции. С необходимостью повторяющихся действий человек сталкивается постоянно. Перечень повторяющихся действий называют телом цикла. Разберем пример на основе линейной структуры: нам надо сложить введенное число само на себя десять раз, для этого составим словесный алгоритм.
1. Вводим число X
3. X=X+X
4. X=X+X
5. X=X+X
6. X=X+X
7. X=X+X
8. X=X+X
9. X=X+X
10. X=X+X
11. X=X+X
12. Вывести полученное число X
Как видим алгоритм получается очень объемным, а если такую операцию нужно будет провести скажем тысячи раз. Расписать такой алгоритм будет очень сложно. Для облегчения и наглядного представления повторяющихся действий существует структура цикл. Как в алгоритме с циклом будет выглядеть предыдущий пример, мы покажем на примере цикла с параметром, так как нам известно количество повторений.
1. Задаем число Х
2. Задаем параметр цикла начальное значение i=1, конечное значение i=10, шаг 1, при значении i=10 переход к п. 5
3. Вычисляем X=X+X
4. Переход к п.2
5. Выводим число X
На языке блок схемы это выглядит так:
В итоге объём алгоритма сократился в два раза, повторяющиеся действия сложения числа на само себя вложено в цикл. Хотя стоит понимать, что это не увеличило скорость выполнения алгоритма, так как приходится еще считать параметры цикла и проверять их, а это дополнительные элементарные операции, но чтение алгоритма структура цикла облегчает в разы.
Также циклы используются в алгоритмах поиска и сортировки без которых процесс описания алгоритма занял бы очень много места и времени. Конечно, если это не слишком маленькие значения, до сотни значений еще можно описать, но, если это несколько сотен, тысяч, или даже миллионов, алгоритм поиска не по одному списку или массиву, а по нескольким десяткам, тысячам, структуры циклов в данном случае как никак идеально походит нам, в отличие от линейной структуры.
Сама структура цикла по сути ничего не представляет без линейных блоков или блоков ветвления, поэтому циклы используются совместно с линейными и ветвящимися структурами. Простой пример использования цикла без операторов внутри, это цикл с параметром, можно использовать как таймер, но к сожалению современные системы работают очень быстро и значения параметра цикла будет очень большим, не всегда можно точно вычислить какой параметр нужен, например, для задержки в 1 секунду. Для таких случаев есть специальные операторы в программировании.
Рассмотрим пример математической задачи на нахождение корней уравнения ax2+bx+c=0 (a ≠0), в данном алгоритме нам потребуется один блок ветвления для проверки условия дискриминанта (D>=0), полностью выполнить линейной структурой мы его сможем только в том случае, если после вычислении дискриминанта мы получим положительное значение, либо ноль.
Так как заранее мы не можем знать какие будут входные данные, будет использоваться структура ветвления совместно с линейной структурой. Словесно алгоритм будет выглядеть так:
1. Ввести числа a, b, c
2. Вычислить дискриминант по формуле D=b2-4ac
3. Проверяем условие, если D ≤ 0, то перейти к п. 5
4. Решения нет, перейти к п. 7
5. Провести вычисления по формулам x1=(-b- √D)/(2a), x2=(-b+√D)/(2a)
6. Вывести x1, x2
7. Конец.
Блок-схемой алгоритм выглядит так:
Здесь показан общий алгоритм решения квадратных уравнение, применена линейная структура и структура ветвления. Конечно алгоритм можно еще усовершенствовать, ввести еще один блок для проверки равенства дискриминанта нулю, при таком значении нет смысла вычислять две формулы так-как корень будет один (x1=x2), и можно вычислить по одной из приведенных формул.
Таким образом, мы можем сказать, что простые математические функции можно выполнить с помощью линейных структур. Объемные повторяющиеся линейные вычисления легко сокращаются за счет внедрения циклов. Структуры ветвления нужны нам для организации логического выбора, путем комбинации разных вариаций основных структур, можно создавать любые алгоритмы любой сложности. Это относится как к алгоритмам в нашей повседневной жизни, так и к алгоритмам в компьютерных системах и не только. Все базовые структуры имеют ряд схожих особенностей к ним относятся:
- Обязательные блоки начала и конца
- Хотя-бы один блок структуры
- Входные данные
- Обработанные выходные данные
Из сказанного можно сделать вывод, что не обязательно знать все, алгоритмы, но нужно уметь их выводить, как математик выводит формулы, видеть их, понимать. Понимание алгоритмов помогает нам решать сложные задачи, как в повседневной жизни, так и при решении задач в программировании.
Заключение
Изучив тему алгоритмизации и сравнительного анализа структур алгоритмов, мы приходим к следующим выводам:
1. Алгоритмы применяются повсеместно и входят в каждую сферу деятельности нашей жизни. Большинство алгоритмов уже созданы и типизированы, нам остается только правильно их применять на практике.
2. При разработке нового алгоритма перед нами стоит задача составить алгоритм по существу, а все остальное, это перевод алгоритма с одного языка на другой.
3. В исследовании мы сформулировали следующие свойства алгоритмов:
- конечность алгоритма или результативность
- определенность алгоритма
- дискретность (прерывность, раздельность)
- массовость
- эффективность алгоритма.
4. Способы записи алгоритмов можно представить, как:
- словесный способ
- графический способ записи
- запись на псевдокоде
- программная запись алгоритма.
5. Структура алгоритмов состоит из трех комбинаций: линейная, разветвляющаяся и циклическая.
Алгоритм линейной структуры – последовательное выполнение этапов алгоритма: ввод данных, вычисление искомых величин и вывод данных.
Разветвляющийся алгоритм описывает вычислительный процесс, реализация которого происходит по одному из нескольких заранее заданных направлений.
Циклом называется любая многократно выполняемая инструкция, организованная разными способами. Каждое выполнение тела цикла называется итерацией. Циклы различаются на циклы с предусловием, циклы с постусловием и безусловные циклы.
6. Таким образом, изучив и проанализировав основные структуры алгоритмов, мы можем сказать, что простые математические функции можно выполнить с помощью линейных структур. Объемные повторяющиеся линейные вычисления легко сокращаются за счет внедрения циклов. Структуры ветвления нужны нам для организации логического выбора, путем комбинации разных вариаций основных структур, можно создавать любые алгоритмы любой сложности. Это относится как к алгоритмам в нашей повседневной жизни, так и к алгоритмам в компьютерных системах и не только.
7. Все базовые структуры имеют ряд схожих особенностей к ним относятся:
- Обязательные блоки начала и конца
- Хотя-бы один блок структуры
- Входные данные
- Обработанные выходные данные
Все вышесказанное помогает нам понять, что не обязательно знать все, алгоритмы, но нужно уметь их выводить, так как будто математик выводит формулу, видеть их и понимать. Понимание алгоритмов помогает нам решать сложные задачи, как в повседневной жизни, так и при решении задач в программировании.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ
Источники:
1. ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации». Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения.
Литература:
2. Белов М.П. Основы алгоритмизации в информационных системах: Учеб. Пособие. - СПб.: СЗТУ,2003. - 85 с.
3. Жданова, Ю.С. Основы алгоритмизации и программирования: учеб. пособие /Т.А. Жданова, Ю.С. Бузыкова. – Хабаровск: Изд-во Тихоокеан. гос.ун-та, 2011. – 56 с.
4. Кадырова, Г.Р. Основы алгоритмизации и программирования: учебное пособие / Г. Р. Кадырова. – Ульяновск: УлГТУ, 2014. – 95 с.
5. Макаров В.Л. Программирование и основы алгоритмизации: Учеб. пособие –СПб.: СЗТУ,2003. - 110 с.
6. Основы алгоритмизации и программирования: Метод. указ. / Сост.: И.П. Рак, А.В. Терехов, А.В. Селезнев. Тамбов: Изд-во Тамб. гос. техн. ун-та, 2004. - 24 с.
7. Основы алгоритмизации и программирования. Курс лекций. URL: http://lib.ssga.ru/fulltext/UMK/исходные%20для%20Кацко/заменить%20полностью/Информатика/лекции/13%20Основы%20алгоритмизации%20и%20программирования.pdf (Дата обращения: 15.06.18).
8. Программирование и основы алгоритмизации: Для инженерных специальностей технических университетов и вузов. /А.Г. Аузяк, Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин. Казань: Изд-во Казанского национального исследовательского технического ун-та - КАИ, 2013. - 153 с.
- Роль мотивации в поведении организации (Методологические основы мотивации)
- Процессы принятия решений в организации (Функции управленческих решений)
- Технология работы службы питания в гостиницах (на примере гостиницы «Марриотт Тверская Москва»)
- Технология обслуживания постоянных гостей. Программы лояльности в гостинице
- Организация бухгалтерского учета на предприятии
- Денежная система: понятие, элементы и их содержание, механизм функционирования (Теоретическое обоснование денежной системы)
- Современные языки программирования
- Персонал как ключевой фактор предоставления качественной гостиничной услуги
- Правовое регулирование рекламной деятельности в РФ
- Анализ денежных средств предприятия (Теоретические основы организации учета денежных средств)
- Административные барьеры входа на РФ рынках
- Роль мотивации в поведении организации (Механизм мотивации и стимулирования труда персонала в современных условиях)