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

Содержание:

Введение

В начале XX века алгоритмы стали объектом изучения математики. Стали появляться различные математические уточнения понятия «алгоритм». Возникла такая отрасль математики, как теория алгоритмов. Полученные теорией алгоритмов результаты стали служить теоретическим фундаментом всей компьютерной технологии.

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

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

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

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

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

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

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

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

Цель исследования – изучить основные алгоритмические структуры и их реализацию.

Для достижения цели необходимо решить следующие задачи:

- изучить понятие алгоритма и его свойства;

- рассмотреть виды алгоритмов и способы их описания;

- исследовать основные структуры алгоритмов;

- определить случаи применения и использования алгоритмических структур и их различия.

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

Теоретическую основы курсовой работы составили труды авторов: Аузяк А.Г., Белова М.П., Голицыной О.Л., Ждановой Т.А., Калмыковой Е.А., Коврижных А.Ю., Паклиной В.М., Парфиловой Н.И., Полякова В.И., Рогозина С.А., Семакина И.Г., Трофимова В.В., Фофанова О.Б

Глава 1. Понятие об алгоритмах в программировании

1.1 Понятие алгоритма и его свойства

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

Алгоритм (процедура) – решение задач в виде точных последовательно выполняемых предписаний. [12, с. 4]

Сам термин «алгоритм» связан с именем арабского математика аль-Хорезми, жившего в 783-850гг. «В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком» [13, с. 4]. Им были описаны общие правила выполнения основных арифметических действий в десятичной системе счисления. Эти правила позднее стали называться алгоритмами.

На самых первых ступенях развития математики (Древнего Египта, Вавилона, Греции) стали появляться вычислительные процессы чисто механического характера. Искомые величины различных задач с их помощью вычислялись последовательно по определенным правилам и инструкциям. [4, с. 8]

Поэтому первые алгоритмы в математике – это сложение, вычитание, умножение «столбиком», деление «уголком» многозначных чисел, а также правила алгебраических преобразований и вычислений корней уравнений. [10, с. 7]

Примером алгоритма, который приводит Трофимов В.В., может служить алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух натуральных чисел. Одна из формулировок такого алгоритма, описанная по шагам, выглядит следующим образом:

1. присвоить переменным X и Y значения, НОД которых ищется;
2. если X > Y, то перейти на шаг 5;
3. если X < Y, то перейти на шаг 6;
4. здесь X = Y. Выдать X в качестве результата. Конец работы;
5. заменить пару (X ,Y) парой (X – Y, Y) и вернутся на шаг 2;
6. заменить пару (X ,Y) парой (X, Y - X) и вернутся на шаг 2;

[11, с. 8]

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

Примером формального исполнителя может служить стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе. [13, с. 4]

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

Этап постановки задачи предполагает четкое определение, что именно надо и требуется найти. Важно описать полный набор исходных данных, необходимых для решения задачи. Здесь формируются правила начала и окончания решения задач. Ведется поиск метода решения задачи: метод вычислений, метод перебора вариантов, метод распознавания образов. Выбранный метод является основой для разработки алгоритма, который реализуется с помощью ПК. При разработке исходного алгоритма и даже при выборе модели пользователь, т.е. человек, решающий конкретную задачу, должен иметь представление о математическом обеспечении ПК. [3, с. 5]

Работает компьютер с величинами – различными информационными объектами: числами, символами, кодами и др. Алгоритмы, предназначенные для управления компьютером, называются алгоритмами работы с величинами.

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

Алгоритм решения любой задачи на компьютере может быть одинаков независимо от того, на каком языке программирования будет написана программа. Такой алгоритм будет содержать в себе следующие команды: присвоение, ввод, вывод, обращение к вспомогательному алгоритму, цикл, ветвление. [10, c. 9 – 10]

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

Указанные критерии являются критериями качества алгоритма. Другими критериями выступают адаптируемость алгоритма к различным компьютерам, его простота, изящество и т.д. [2, с. 8]

Таким образом, алгоритм в работе компьютера, как определяет его Белов М.В., представляет собой «точное предписание, т.е. набор операций и правил их чередования, при помощи которого, начиная с некоторых исходных данных, можно решить задачу фиксированного типа. Команда алгоритма – предписание о выполнении отдельного законченного действия исполнителя». [3, с. 5]

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

Основными свойствами алгоритмов являются:

- дискретность (прерывность, раздельность) указывает на то, что алгоритм должен представлять процесс решения задачи как последовательное исполнение простых (или ранее определенных) шагов (этапов).

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

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

- результативность (или конечность) означает приведение к решению задачи за конечное число шагов;

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

По поводу свойства «конечность» Трофимов В.В. пишет о ее неоднозначности. Кроме того, что алгоритм должен заканчиваться за конечное число шагов. Алгоритм состоит также из отдельных элементарных шагов, или действий, причем конечно множество различных шагов, из которых строится алгоритм.

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

И такое свойство как эффективность. Оно говорит о том, что одну и ту же задачу можно решить по-разному и за разное время с различными затратами памяти. Это свойство характеризуется минимальным числом шагов алгоритма, точностью решения, минимальными затратами других ресурсов. [11, с. 9]

Не совсем правильно применять к понятию «алгоритм» понятие «свойства», как полагает Аузяк А.Г., т.к. свойства присущи какому-нибудь веществу. Алгоритм же искусственная конструкция. И чтобы благодаря алгоритму можно было достичь определенных целей, его надо строить по определенным правилам – правилам построения алгоритма. [13, c. 6]

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

Например, при решении квадратного уравнения ax² + bx + c = 0 исходными данными являются коэффициенты a, b, c, результатами – корни уравнений x_1, x₂, а промежуточными данными – дискриминант уравнения D = b² – 4ac. [10, с. 7]

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

Третьим правилом является дискретность. Алгоритм состоит из отдельных шагов (действий, операций, команд). Множество шагов конечно.

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

Пятым правилом является сходимость или результативность. После конечного числа шагов алгоритм должен завершать работу. При этом необходимо указать, что считать результатом работы алгоритма. [13, с. 7]

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

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

Полное понимание алгоритма происходит благодаря его свойствам или по-другому правила построения алгоритма.

1.2 Виды алгоритмов и способы их описания

Виды алгоритмов как логико-математических средств отражают также компоненты человеческой деятельности, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения и определения действий исполнителей подразделяют на:

- механические алгоритмы, или детерминированные, жесткие (например, алгоритм работы машины, двигателя и т.п.);

- гибкие алгоритмы, например стохастические, т.е. вероятностные и эвристические. [3, с. 6]

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

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

Особенностью эвристического алгоритма (значение от греческого слова «эврика» - «я нашел») является то, что программа действий алгоритма не дает достижения однозначного определенного конечного результата из-за не обозначенной всей последовательности действий и не выявленных действий исполнителя.

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

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

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

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

Эквивалентными будут являться такие алгоритмы, результаты которых для одних и тех же исходных данных будут одинаковыми. [3, с. 7]

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

- множество допустимых исходных данных одного из них является множеством допустимых исходных данных и другого; из применимости одного алгоритма к каким-либо исходным данным следует применимость и другого алгоритма к этим данным;

- применение этих алгоритмов к одним и тем же исходным данным дает одинаковые результаты.

Пример таких алгоритмов. Допустим надо подсчитать общую сумму чисел, приведенных в табл. 1. Эквивалентными будут алгоритмы подсчета общей суммы по строкам: 5 + 1 + 3 + 8 + 10 + 9 + 6 + 1 + 5 + 10 + 1 + 1 = 60, и по столбцам: 5 + 10 + 5 + 1 + 9 + 10 + 3 + 6 + 1 + 8 + 1 + 1 = 60. Заметим, что для данной таблицы считать проще по столбцам. [14, с. 17]

Таблица 1. Целые числа

5	1	3	8
10	9	6	1
5	10	1	1

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

Также выделяют такие виды алгоритмов как:

- линейный, представленный набором команд (указаний), которые выполняются последовательно во времени друг за другом;

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

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

- цикл программы представлен последовательностью команд (серия, тело цикла), выполняемых многократно (для новых исходных данных) до того момента, как будут удовлетворены некоторые условия;

- вспомогательный или подчиненный. Под ним понимается алгоритм, который был ранее разработан и целиком используется при алгоритмизации конкретной задачи. Иногда при наличии одинаковых последовательных указаний для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм. [1, c. 5]

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

Согласно первому типу понятие алгоритма связано с традиционными понятиями математики такими, как вычисления и числовые функции.

По второму типу представление об алгоритме основывается как о детерминированном устройстве, которое выполняет простые операции в каждый отдельный момент. Такое представление обеспечивает однозначность алгоритма и элементарность его шагов. Также данное представление соответствует идеологии построения компьютеров. Основной теоретической моделью этого типа, созданной в 1930-х гг. английским математиком Аланом Тьюрингом, является машина Тьюринга. [11, с. 10]

Модель третьего типа состоит в преобразовании слов в произвольных алфавитах. Элементарными операциями в них являются подстановки, замена части слова (под словом понимается последовательность символов алфавита) другим словом. Такой тип обладает преимуществом в максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной (необязательно числовой) природы. Примерами моделей данного типа служат канонические системы американского математика Эмиля Л. Поста и нормальные алгоритмы, которые были введены советским математиком А.А. Марковым.

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

Характер языка описания определятся тем, для какого исполнителя предназначен алгоритм. Возможности исполнителя алгоритмов определяют уровень используемых языковых средств, т. е. степень детализации и формализации предписаний в алгоритмической записи. [14, с. 17]

Если исполнителем будет человек, запись может быть не полностью формализована, на первое место выдвигаются понятность и наглядность. Для записи таких алгоритмов может быть использован естественный язык. В этом случае можно использовать словесную форму записи или схемы алгоритмов.

Для записи алгоритмов, предназначенных для исполнителей‑автоматов, необходима строгая формализация, поэтому в таких случаях применяют формальные специальные языки. То есть если задача решается с помощью ЭВМ, то алгоритм решения задачи должен быть записан в понятной для машины форме, а именно в виде программы. Преимущество формального способа записи состоит в том, что он дает возможность изучать алгоритмы как математические объекты; при этом формальное описание алгоритма служит основой, позволяющей интеллектуально охватить этот алгоритм.

Часто встречаются такие формы представления алгоритмов как:

- словесная – записывается на естественном языке;

- графическая – с помощью блок-схемы;

- псевдокоды – полуформализованные описания алгоритмов на некотором условном алгоритмическом языке, которые включают в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др. [6, с. 6]

Некоторые авторы выделяют отдельно среди форм представления алгоритмов - программную, представленную текстами на языках программирования.

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

Однако словесная форма имеет ряд недостатков:

- строго не формализуема;

- страдает многословностью записей;

- допускает неоднозначность толкования отдельных предписаний.

Эта форма обычно используется на начальных стадиях разработки алгоритма. [9, с. 7]

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

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

Рассмотрим пример алгоритма на естественном языке:

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

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

3. Если d < 0, то напечатать сообщение «Корней нет» и перейти к п. 4. Иначе вычислить 𝑥₁ = (−𝑏+√D) / 2𝑎 , 𝑥₂ = (−𝑏−√D) / 2𝑎 и напечатать значения x₁ и x₂.

4. Прекратить вычисления. [6, с. 7]

Еще примером данного способа описания алгоритма является алгоритм нахождения максимального из двух значений:

- определим форматы переменных X, Y, M, где X и Y – значения для сравнения, M – переменная для хранения максимального значения;

- получим два значения чисел X и Y для сравнения;

- сравним X и Y.

- если X меньше Y, значит большее число Y.

- Поместим в переменную M значение Y.

- Если X не меньше (больше) Y, значит большее число X.

- Поместим в переменную M значение X. [13, с. 9]

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

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

Типы графических обозначений, элементы блок-схем изображаются следующим образом:

- начало (конец) алгоритма

- блок ввода-вывода данных

- блок вычислений. Процесс (действия или серия действий)

- логический блок, в котором направление потока информации выбирается в зависимости от некоторого условия. Решение.

- процесс пользователя (подпрограмма)

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

- соединитель, используется для указания связи между потоками информации в пределах одного листа

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

Начало и конец алгоритма обозначают с помощью одноименных символов (рис. 1.1). Шаг алгоритма, связанный с присвоением нового значения некоторой переменной, преобразованием некоторого значения с целью получения другого значения, изображается символом «процесс». Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий изображается символом «решение» [11, с. 12]

Следующим описанием алгоритма является «песевдокод». Он представляет собой пошагово-словесную запись алгоритма по определенным правилам или соглашениям. Здесь используют общепринятую математическую символику и конструкцию. Псевдокод является промежуточной позицией между естественным и формальным языками.

Часто программистам требуется создать описание алгоритма, которое будет предназначаться только для человека. Такие описания не являются программами, но имеют более четкую структуру в отличии от обычного текса. Сочетание естественного языка и структур языка программирования делает описанный алгоритм доступным и также информативным. Такие описания способствуют проведению высокоуровневого анализа структуры данных или алгоритма. [2, с. 12]

Например, алгоритм умножения двух чисел можно записать с помощью псевдокода:

1. Ввод a, b.
2. P=a b.
3. Вывод Р.
4. Конец.

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

Основные служебные слова этого языка представлены в табл. 2. [9, с. 7 – 8]

Таблица 2. Служебные слова школьного алгоритмического языка

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

Пример записи алгоритма на школьном языке АЯ:

алг Сумма квадратов (арг цел n, рез цел S)

дано | n > 0

надо | S = 1*1 + 2*2 + 3*3 + ... + n*n

нач цел i

ввод n; S:=0

нц для i от1 доn S:=S + i*i

кц

вывод "S = ", S

кон

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

Относительно понятия алгоритма различают три типа алгоритмических моделей.

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

Глава 2. Структуры алгоритмов

2.1 Основные алгоритмические конструкции

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

- линейная или последовательная;

- разветвляющаяся;

- циклическая.

Особенность базовых структур состоит в том, что они имеют один вход и один выход.

Алгоритмы линейной структуры представлены последовательным выполнением действий одно за другим (рис. 1 [6, с. 9]).

Рисунок 1. Блок-схема линейного алгоритма

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

Пример линейного алгоритма.

Даны длины трех сторон треугольников – a, b, c. Необходимо вычислить площадь – S, и периметр треугольника – P. Для нахождения площади можно воспользоваться формулой Герона: 𝑟 = 􀶥r(r − a)(r − b)(r − c), где r – полупериметр. Входные данные: a, b, c. Выходные данные: S, P.

Алгоритм представлен в виде блок-схемы на рис. 2 [6 с. 9 – 10].

Рисунок 2. Пример линейного алгоритма

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

Переменной, которая стоит слева от оператора, присваивается значение, указанное справа. Данное значение может быть или определено, или его нужно вычислить с помощью выражения. Как пример, операция r = (a+b+c)/2 – имеет смысл (переменной r присвоить значение (a+b+c)/2), а выражение (a+b+c)/2 = r – бессмыслица.

Разветвленная структура отличается тем, что в зависимости от выполнения или невыполнения какого-либо условия производятся различные последовательности действий. При этом последовательность таких действий называется ветвью алгоритма. На рис. 3 представлены алгоритмы полной и неполной разветвленной структуры [6, с. 10].

Рисунок 3. Полный и неполный разветвленный алгоритм

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

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

Таким образом, различают два вида условий: простые и составные. Простое условие – это выражение, которое состоит из двух арифметических выражений или двух текстовых величин. При этом они связаны знаками: < (меньше), > (больше), >= (больше или равно), = (равно), о (не равно).

Составное условие строятся из двух или более простых выражений, которые связаны логическими операциями: И, ИЛИ, НЕ.

В качестве примера разветвленного алгоритма можно рассмотреть блок-схему алгоритма решения квадратного уравнения (Рис. 4 [1, c. 6]).

Рисунок 4. Блок-схема алгоритма решения квадратного уравнения

Можно рассмотреть и такой пример.

Необходимо упорядочить три числа: a, b, c по возрастанию таким образом, чтобы переменной a соответствовало самое маленькое число, b – среднее, c – самое большое.

Чтобы решить данную задачу, используют метод перестановок, благодаря которому последовательно сравниваются значения переменных а < b, затем а < c, потом b < c.

Если выполняется первое условие: а < b, то происходит переход к следующему условию: а < c. Если нет, то происходит перестановка значений соответствующих переменных, и после этого осуществляется переход к следующему условию.

В связи с тем, что в ПК каждая величина храниться в отдельной ячейке памяти, то нельзя сделать перестановку a = b; b = a. Иначе в обоих переменных a и b окажется значение b. Чтобы осуществить перестановку двух переменных a и b используют вспомогательную переменную h. И перестановка будет иметь следующий вид: h = a, a = b, b = h. (рис. 5) [5].

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

Для алгоритма циклической структуры характерно выполнение повторяющейся последовательности действий, которая называется телом цикла, в зависимости от выполнения или невыполнения какого-либо условия. [7, с. 23]

Существует вложенный цикл, который находится внутри тела другого цикла. И итерационный цикл, число повторений которого не задается, а определяется в ходе выполнения цикла. Одно повторение называется итерацией. [11, с. 13]

Различают алгоритмы циклической структуры трех типов. На рис. 6 изображен цикл с предусловием, а на рис. 7 – цикл с постусловием [6, с. 11 – 12]. Данные циклы взаимосвязаны, но и имеют некоторые отличия:

- в цикле с предусловием - условия проверяются до тела цикла

в цикле с постусловием – после тела цикла;

- в цикле с предусловием – тело цикла может не выполняться ни разу

в цикле с постусловием - тело цикла выполняться хотя бы один раз;

- в цикле с предусловием – проверяются условия продолжения цикла

в цикле с постусловием – проверяются условия выхода из цикла.

Рисунок 6. Алгоритм циклической структуры с предусловием

Рисунок 7. Алгоритм циклической структуры с постусловием

И третий тип алгоритма циклической структуры – цикл с параметром. В таком цикле число повторений цикла однозначно определено и задается с помощью начального, конечного значений параметра и шагом его значения (рис. 8). [9, с. 17]

Рисунок 8. Цикл с параметром

Цикл с параметром выполняется следующим образом:

1. параметр цикла принимает начальное значение;

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

3. параметр цикла изменяется на единицу или на заданный шаг;

4. переход к пункту 2.

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

Обязательные блоки для организации цикла:

1. Установка начального значения параметра цикла.
2. Изменять переменную перед каждым новым повторением цикла.
3. Проверка условия достижения конечного значения параметра

цикла.

1. Изменение параметра цикла, т.е. переходить к его началу, если он не закончен, или выходить из него по окончании.

Последние три функции выполняются многократно.

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

Для построения разветвляющихся и циклических структур алгоритма в алгоритмическом языке используются составные операторы такие, как операторы ветвления и цикла.

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

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

Для структуры ветвления существует четыре основных варианта записи:

если – то;

если – то – иначе;

выбор;

выбор – иначе.

Оператор выбора будет использоваться в случаях, если необходимо выбрать альтернативу их трех возможностей и более. [3, с. 31]

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

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

Особенности применения алгоритмических структур

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

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

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

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

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

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

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

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

Например, необходимо найти объем цилиндра [3, с. 47]. Для решения используется линейная структура алгоритма:

алг Объем цилиндра (арг вещ r, h, рез вещ v)

нач

вещ pi = 3.1415926

ввод r, h

v = 2* pi* r* r* h

вывод v

кон

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

Алгоритмы разветвляющейся или циклической структуры используются при решении задач, где необходимо проанализировать условия, и только потом следующее действие выполняется. Это более сложные задачи. В их структуре обязательно присутствует логический блок. В разветвляющемся алгоритме логический блок имеет один вход и два выхода: ветвь «да» и ветвь «нет» [8, с. 14]. А для задач, где необходимо получить решение путем подбора верного значения (истины), путем команд повторения, используется циклический алгоритм.

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

Для ее решения используют метод алгоритма Евклида. Идея этого метода основана на том, что НОД А и В есть также и НОД (А - В), то есть последовательное вычитание из большего числа меньшего до тех пор, пока числа не сравняются, должно привести к исходному значению НОД.

На естественном языке алгоритм Евклида выглядит следующим образом:

1. Рассмотреть А как первое число, В как второе. Перейти к пункту 2.
2. Сравнить первое и второе число. Если они равны, перейти к пункту 5. Если нет, перейти к пункту 3.
3. Если первое число меньше второго, то поменять их местами. Перейти к пункту 4.
4. Вычесть из первого числа второе и рассмотреть полученную разность как первое число. Перейти к пункту 2.
5. Рассмотреть перовое число как результат. Закончить выполнение алгоритма.

Структура алгоритма в виде блок-схемы изображена на рис. 9 [4, с. 18].

Рисунок 9. Блок-схема алгоритма Евклида

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

Допустим ситуацию, перед выходным днем папа сказал своему сыну: «Давай спланируем свой завтрашний день. Если будет хорошая погода, то проведем день в лесу. Если же погода будет плохая, то сначала займемся уборкой квартиры, а во второй половине дня сходим в зоопарк». Что получится на выходе блок-схемы (рис. 10) [1, с. 18], если:

а) погода хорошая;

б) погода плохая?

Для определения результата воспользуемся трассировочными таблицами (а, б):

а) погода хорошая:

Шаг	1
Исходные значения	Погода хорошая
Результат выполнения	Прогулка в лесу
Вывод значений	Прогулка в лесу

б) погода плохая:

Шаг	1
Исходные значения	Погода плохая
Результат выполнения	Уборка квартиры Поход в зоопарк
Вывод значений	Поход в зоопарк

Рисунок 10. Пример разветвляющегося алгоритма

Наиболее простым способом отслеживания действий, предписанных алгоритмом, является его пошаговое исполнение.

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

1) пошаговое выполнения каждого действия с записью результата в строку таблицы;

2) выполнение группы действий с записью результатов в одну строку для всей группы.

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

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

Необходимо поменять значение двух переменных А и В. команды и результаты выполнения заносятся в таблицу (табл. 3)

Таблица 3. Трассировочная таблица

команда	А	Б
А: = 3	3
В: = 5		5
А: = В	5
В: = А		5
результат	5	5

По результату задачи видно, что она не решена, т.к. значение 3, находящееся в переменной А, утеряно. Его необходимо сохранить, а затем присваивать переменной А значение переменной В. Для временного хранения нужного значения вводится дополнительная переменная С, она называется буферной (табл. 4).

Таблица 4. Трассировочная таблица с дополнительной переменной

команда	А	Б	С
А: = 3	3
В: = 5		5
С: = А			3
А: = В	5
В: = С		3
результат	5	3

Теперь требуемый результат получен.

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

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

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

Заключение

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

Алгоритм – это строго определенная последовательность действий, определяющих процесс перехода от исходных данных к искомому результату.

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

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

Раскрывают понятие алгоритма его свойства. Ими являются: дискретность (прерывность, раздельность), определенность, результативность (конечность), массовость, элементарность или понятность, эффективность.

Решение задач на компьютере проходи определенные этапы:

- постановка задачи;

- математическая формализация;

- построение алгоритма;

- составление программы на языке программирования;

- отладка и тестирование программы.

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

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

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

Алгоритмы, представленные в виде блок-схем, это более наглядный и универсальный способ. Блок – это геометрическая фигура, которая изображает конкретную операцию, а стрелки показывают порядок выполнения этапов.

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

Линейный алгоритм – это алгоритм, в котором действия выполняются только один раз и строго в том порядке, в котором они записаны. В основном они используются при вычислении площадей фигур в математике.

Разветвляющийся алгоритм – это алгоритм, в котором то или иное действие выполняется после анализа условия. В структуре такого алгоритма есть две ветви «да» и «нет».

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

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

Список использованных источников

1. Алгоритмы. Основные алгоритмические конструкции [Текст]: сб. задач / сост. С.А. Рогозин. – Челябинск: Изд-во Челяб. гос. пед. ун-та, 2008. – 42 с.
2. Алгоритмы и структуры данных: учебное пособие / О.Б. Фофанов; Томский политехнический университет. – Томск: Изд-во Томского политехнического университета, 2014 – 126 с.
3. Белов М.П. Основы алгоритмизации в информационных системах: Учеб. пособие. – СПб.: СЗТУ, 2003. – 85 с.
4. Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования: учеб. пособие. – 3-е изд., испр. и доп. – М.: ФОРУМ, 2008. – 432 с.
5. Калмыкова Е. А.. Информатика. - 2012. [Электронный ресурс] URL // https://lawbooks.news/informatika_960/informatika501.html
6. Основы алгоритмизации и программирования: учебное пособие /

Г. Р. Кадырова. – Ульяновск: УлГТУ, 2014. – 95 с.

1. Основы алгоритмизации и программирования: практикум: [учеб.-метод. пособие]. В 2 ч. Ч. 1. Задачи и упражнения / А. Ю. Коврижных, Е. А . Конончук, Г. Е . Л узина ; М-во образования и науки Рос. Федерации, Урал. федер. ун-т. — Екатеринбург : Изд‑во Урал. ун-та, 2016. — 52 с.

8. Основы алгоритмизации и программирования: учеб. пособие / Т.А. Жданова, Ю.С. Бузыкова. – Хабаровск : Изд-во Тихоокеан. гос. ун-та, 2011. – 56 с.

9. Основы алгоритмизации и программирования: учебное пособие / В. М. Паклина, Е. М. Паклина. Екатеринбург: УрФУ, 2010. – 92 с.

10. Основы алгоритмизации и программирования: учебник для студ. учреждений сред. проф. образования / И.Г. Семакин, А.П. Шестаков. – 3-е изд., стер. – М.: Издательский центр «Академия», 2012. – 400 с.

11. Основы алгоритмизации и программирования: учебник для СПО / В.В. Трофимов, Т.А. Павловская; под ред. В.В. Трофимова. – М.: Издательство Юрайт, 2018. – 137 с.

12. Поляков В.И., Скорубский В.И. основы теории алгоритмов. – СПб: СПб НИУ ИТМО, 2012. – 51 с.

13. Программирование и основы алгоритмизации: Для инженерных специальностей технических университетов и вузов. /А.Г. Аузяк, Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин. Казань: Изд-во Казанского национального исследовательского технического ун-та - КАИ, 2013, 153 с.

14. Программирование. Основы алгоритмизации и программирования: учебник для студ. учреждений высш. проф. образования / Н. И. Парфилова, А. Н. Пылькин, Б. Г. Трусов; под ред. Б. Г. Трусова. — М.: Издательский центр «Академия», 2012. — 240 с.