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

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

Содержание:

Введение

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

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

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

Вся информация в данной курсовой взята из надежных источников таких как: «Основы алгоритмизации и программирования» Г.Р. Кадырова (Ульяновский государственный университет); «Основы алгоритмизации в информационных системах» М.П. Белов(Северо-западный государственный заочный технический университет); «Программирование и основы алгоритмизации» А.Г. Аузяк, Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин (Казанский национальный исследовательский технический университет им. А.Н. Туполева – КАИ).

Глава 1 Алгоритм. Общие понятия

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

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

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

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

Алгоритм - это точное, сформулированное на определенном языке, конечное описание того или иного способа действия, основанного на применении исполнимых элементарных однозначно трактуемых шагов. [2]

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

Термин алгоритм происходит от имени узбекского ученого IX в. Аль-Хорезми, который в своем труде «Арифметический трактат», переведенном в XII в. с арабского на латынь, изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Эти правила и называют алгоритмами.

1.2 Свойства алгоритмов

Алгоритмы обладают целым рядом свойств:

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

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

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

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

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

1.3 Основные характеристики алгоритмов

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

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

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

Для сложных задач эта характеристика имеет большое значение, т.к. ее изменение значительно сильнее влияет на время решения, чем изменение быстродействия ПК.

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

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

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

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

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

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

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

К средствам описания алгоритмов относятся следующие основные способы их представления: словесный; графический; псевдокоды; программный.

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

Словесный способ записи алгоритмов представляет собой последовательное описание основных этапов обработки данных и задается в произвольном изложении на естественном языке. [3] Данный способ получил значительно меньшее распространение из-за его многословности и отсутствия наглядности.

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

Определим форматы переменных x, y, z, где x и y – значения для сравнения, z – переменная для хранения максимального значения;

Получим два значения чисел x и y для сравнения;

Сравним x и y.

Если x меньше y, значит большее число y.

Поместим в переменную z значение y.

Если x не меньше (больше) y, значит большее число x.

Поместим в переменную z значение x.

Такой способ записи удобно использовать на начальном этапе алгоритмизации задачи. К недостаткам словесного способа записи можно отнести следующее:

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

Поэтому словесный способ записи алгоритмов не имеет широкого распространения.

1.4.2. Графический способ описания алгоритмов

Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. Иначе такой способ называют блок-схемой.

Блок-схемой называется наглядное графическое изображение алгоритма, когда отдельные его этапы изображаются при помощи различных геометрических фигур – блоков, а связи между этапами (последовательность выполнения этапов) указываются при помощи стрелок, соединяющих эти фигуры. [1] В блок-схеме каждому типу действия соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. [3] Для начертания этих схем используется набор символов, определяемых ГОСТ 19.701-90 (ИСО 5807 – 85) [4] «Единая система программной документации». В таблице 1 приведены наиболее часто употребляемые символы.

Символ «Процесс» применяется для обозначения одного или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединить в один блок. Представление отдельных операций достаточно свободно. Например, для обозначения вычислений можно использовать математические выражения, для пересылок данных – стрелки, для других действий – пояснения на естественном языке. В зависимости от уровня детализации схемы пояснения на естественном языке могут быть более или менее подробными. Метод блок-схем, так же как и алгоритмический язык(псевдокод), независим от специфики языков программирования, поэтому в описаниях операторов не следует использовать резервированные слова и символы языков программирования, а также применять имена данных, образованные в соответствии с синтаксическими правилами этих языков.

Символ «Решение» используется для обозначения переходов управления по условию. В каждом блоке решения должны быть указаны вопрос, решение, условие или сравнение, которые он определяет. Стрелки, выходящие из блока решения, должны быть помечены соответствующими ответами (например, ДА, НЕТ), так чтобы были учтены все возможные ответы.

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

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

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

Символ «Документ» предназначен для ввода – вывода данных, носителем которых служит бумага.

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

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

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

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

1.4.2.1 Графические способы описания алгоритмов работы информационных систем (промышленных систем)

К графическим способам описания алгоритмов работы информационных систем (промышленных систем) относятся также:

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

-Структурные схемы (рис. 2.a) и сигнальные графы (рис. 2.б). Применяются для изображения структуры и описания функционирования преимущественно непрерывных систем. Переход от одной формы описания к другой очень прост. Передаточные функции (передачи) F отдельных функциональных блоков записываются в структурной схеме внутри соответствующих прямоугольников, а в направленном графе – на его ветвях (ребрах). Переменным (сигналам) x в структурной схеме соответствуют линии, соединяющие блоки, а в графе – его узлы (вершины). Автоматные графы (рис. 3). Применяются для описания дискретных состояний системы и возможных переходов между ними. Узлы изображают различные возможные состояния q, а ветви со стрелками – переходы. Рядом с каждой ветвью записывается условие B, которое вызывает переход между соответствующими состояниями. Сети Петри (рис. 4). Сети Петри являются направленными графами с двумя видами узлов, а именно с узлами для изображения состояний q (кружки) и узлами для изображения переходов (вертикальные штрихи) между состояниями. Переход осуществляется, если состояния, находящиеся перед символом перехода, помечены и наступает событие, вызывающее переход. Например, имеет место переход от q к q, q и q, если имеется q и выполнено условие В1.

- Сети Петри особенно удобны для изображения параллельно происходящих взаимосвязанных процессов.

-Графы последовательного выполнения программы. Пригодны для записи задач управления и для описания поведения релейных систем управления. Изображают зависящую от каких-либо условий последовательность состояний системы q. Положение (0 или 1) конкретных функциональных элементов (Q1, Q2, Y1, Y2, Y3), соответствующие некоторым характерным состояниям системы, указываются в отдельной таблице. В приведенном примере (рис. 5): как только S1 = 1, система совершает переход из состояния q в q; если S2 = 1, то осуществляет переход в состояние q, для S2 = 0 – в состояние q и т.д.

- Схемы работы (рис. 6). Очень удобно использовать для описания линейно протекающих процессов и работы соответствующих систем управления. Изображается зависящая от появления определенных событий последовательность отдельных шагов или состояний процесса (q, q, q, …). Пример: сигнал ″Пуск″ и сигнал ″закрыть заслонку″ начинают первый шаг процесса (например, наполнение мешалки). Как только поступают информационные сигналы 1, 2, 3 (двигатель А включен, вентиль 1 открыть, время ожидания истекло), следует шаг процесса 2 и т.д.

1.4.3. Псевдокоды

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

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

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

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

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

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

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

Синтаксические конструкции языка подразделяются на два типа (см. рис. 7): описания данных (величин) и операторов (команд).

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

1.4.4. Программный способ представления

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

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

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

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

По этому критерию можно выделить следующие уровни языков программирования: машинные; машинно-ориентированные (языки ассемблера);
машинно-независимые (языки высокого уровня).

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

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

Языки высокого уровня делятся на:

- процедурные (алгоритмические) (Basic, Pascal, С и др.), которые предназначены для однозначного описания алгоритмов; для решения задачи процедурные языки требуют в той или иной форме явно выписать процедуру ее решения;

- логические (Prolog, Lisp и др.), которые ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное
описание задачи с тем, чтобы решение следовало из составленного описания;

- объектно-ориентированные (Object Pascal, C++, Java и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над ними. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути, описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.

Подведем итоги по данной главе. Алгоритм – это точная, понятная последовательность действий. Он имеет 5 основных свойств таких, как определенность, массовость, результативность, понятность и дискретность; и 2 характеристики: временная и объемная. Алгоритм имеет 4 способа описания: словесный, графический, псевдокоды и программный.

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

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

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

Ввод исходных данный в память ЭВМ;
Вычисление искомых величин по формулам;
Вывод результатов из памяти ЭВМ на информационный носитель.

Стандартная блок-схема линейного алгоритма приводится на рис. 8 (вычисление суммы двух чисел — А и В).

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

Циклический алгоритм– алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. Группа команд(операторов), выполняющихся одна за другой, называется серией. Серия может состоять из одного оператора. Пример циклического алгоритма приведен на рис. 10.

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

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

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

Структура ветвление существует в четырех основных вариантах [1] (см. табл. 3): если – то; если – то – иначе; выбор; выбор – иначе.

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

Различия в исполнении этих конструкций вытекают из свойств ветвления.

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

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

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

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

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

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

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

Существует два типа алгоритмов циклической структуры: цикл с предусловием и цикл с постусловием. [1]

Эти циклы взаимозаменяемы и обладают некоторыми отличиями:

• в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием – после тела цикла;

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

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

2.1 Операторы управления

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

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

• условные операторы, к которым относятся оператор условия if и оператор выбора switch;

• операторы цикла (for, while, do while);

• операторы перехода (break, continue, return, goto);

•другие операторы (оператор "выражение", пустой оператор).

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

Оператор if имеет следующую общую форму записи: if (логическое выражение) оператор A; [else(иначе) оператор B;].

Иногда алгоритм задачи содержит ряд альтернативных решений, причем некоторую переменную надо проверять отдельно для каждого постоянного целого значения, которое она может принимать. В зависимости от результатов этой проверки должны выполняться различные действия. Оператор switch производит сопоставление значения с множеством констант. Структура switch, состоящая из ряда меток case и необязательной метки default(умолчание), имеет следующий вид:

switch (выражение выбора)

{

case значение 1:

оператор 1;

break;

Оператор break применяется для выхода из оператора switch и вызывает передачу управления на первый оператор после структуры switch. Константы в вариантах case должны быть различными, и если проверяемое значение не совпадает ни с одной из констант, выбирается вариант default. После каждой метки case может быть предусмотрено одно или несколько действий, при этом в последнем случае операторы не нужно заключать в скобки.

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

Оператор for повторяет блок рабочих операторов указанное число раз и имеет следующую структуру:

for(имя переменной = начальное значение; конечное значение; приращение) оператор, где

• имя переменной - имя управляющей переменной, используемой как счетчик цикла;

• начальное значение - начальное значение управляющей переменной;

• конечное значение - конечное значение управляющей переменной;

• приращение - шаг изменения значения управляющей переменной;

• оператор - один или несколько рабочих операторов, образующих тело цикла.

Операторы break и continue изменяют поток управления. Когда оператор break выполняется в структурах while, for, do/while или switch, происходит немедленный выход из структуры. Программа продолжает выполнение с первого оператора после структуры. Обычное назначение оператора break - досрочно прерывать цикл или пропустить оставшуюся часть структуры switch.

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

Глава 3 Примеры использования алгоритмов

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

Пример 1. (Линейный)

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

ввод r

P:= 2*π*r;

S:= π*r²;

V:= (4/3)*π*r²;

Ввод r

вывод P, S, V

P:= 2πr

Блок-схема 1

Вывод P, S, V

V:= (4/3)πr²

S:= πr²

Пример 2.(Линейный)

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

ввод a, b

c:= ;

Ввод a, b

P:= a+b+c;

S:= (a*b)/2;

c:=

вывод P, S

Блок-схема 2

Вывод P, S

S:= (a*b)/2

P:= a+b+c

Пример 3.(Разветвляющийся)

Определить, имеется ли среди заданных целых чисел a, b , c хотя бы одно четное.

ввод a, b , c

если a mod 2 = 0

Ввод a, b, c

то вывод «есть четное число»

иначе если b mod 2 = 0

a mod 2 = 0

то вывод «есть четное число»

да

иначе если c mod 2 = 0

нет

то вывод «есть четное число»

да

b mod 2 = 0

иначе вывод «четных чисел нет»

нет

c mod 2 = 0

Блок-схема 3

нет

да

Вывод «есть четное число»

Вывод «четных чисел нет»

Пример 4.(Разветвляющийся)

Из трех заданных чисел x, y, z выберите те, которые принадлежат отрезку [a;b].

Ввод a, b, x , y, z

Если a<=x<=b

Ввод a, b, x, y, z

То вывод x;

Если a<=y<=b

да

a<=x<=b

То вывод y;

Вывод x

Если a<=z<=b

нет

a<=y<=b

То вывод z;

да

Конец.

Вывод y

нет

да

Блок-схема 4

Вывод z

a<=z<=b

Пример 5.(Циклический)

Вычислить значение функции z=x*y при условии, что одна из переменных x меняется в каждом цикле на 1, а y не меняется и может быть любым целым числом.

Ввод x, y, n

Нц

Ввод x, y, n

Пока i:=1; n

z:=x*y;

i:= 1; n

x:=x+1;

вывод z

z:=x*y

кц

x:=x+1

конец

Вывод z

Блок-схема 5

Пример 6.(Циклический)

Посчитать сумму всех положительных и произведение отрицательных элементов массива A[n].

Ввод n

Нц

i:=1 до n

ввод A[i]

кц

A[i]

s1:=0;

s2:=1;

i:=1 до n

нц

i:=1 до n

нет

да

A[i]>0

если A[i]>0 то

s1:= s1+A[i]

s1:=s1+A[i]

s2:=s2*A[i]

иначе s2:= s2*A[i]

кц

Вывод s1, s2

вывод s1, s2

конец

Блок-схема 6

Заключение

Подведем итоги по проделанной работе.

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

Существует 5 основных свойств алгоритма:

Определенность;
Массовость;
Результативность;
Понятность;
Дискретность.

Алгоритм имеет временные и объемные характеристики. Временные определяют длительность решения и временные сложности, а объемные определяют информационные сложности.

Существует 4 способа описания алгоритма:

Словесный;
Графический;
Псевдокоды;
Программный.

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

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

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

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

Алгоритм имеет 3 базовые структуры: линейная, разветвляющаяся, циклическая.

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

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

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

Библиография

1. Основы алгоритмизации и программирования: учебное пособие / Г. Р. Кадырова. – Ульяновск: УлГТУ, 2014. – 95 с..

Основы алгоритмизации и программирования. Курс лекций.
Белов П.М. Основы алгоритмизации в информационных системах: Учебн. Пособие.- Спб.: СЗТУ, 2003. – 85с..
ГОСТ 19.701-90 (ИСО 5807 – 85) «Единая система программной документации».
Программирование и основы алгоритмизации: Для инженерных специальностей технических университетов и вузов. /А.Г. Аузяк, Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин. Казань: Изд-во Казанского национального исследовательского технического ун-та - КАИ, 2013, 153 с.

Приложения

Таблица

Название символа	Обозначение	Пояснение
1	2	3
Процесс		Вычислительное действие или последовательность вычислительных действий
Решение		Проверка условий
Модификация		Начало цикла
Предопределенный процесс		Вычисления по подпрограмме, стандартной подпрограмме
Документ		Вывод, печать результатов на бумаге
Ввод-вывод		Ввод – вывод данных в общем виде
Соединитель		Разрыв линий потока
Пуск, останов		Начало, конец, останов, вход и выход в подпрограммах
Комментарий		Пояснения, содержание подпрограмм, формулы

Направление включения

А4

А3

А2

А1

Направление выключения

А5

Рис. 1

Рис. 4

Рис. 3

Рис. 2

-1

Время ожидания 240 с

Двигатель Б включен

Время ожидания 10 с

Вентиль 1 открыт

Двигатель А включен

Закрыть защитную решетку

Пуск вручную

q2 Перемешивание

q1 Наполнение

q0 Исходное состояние

Рис. 6

Рис. 5

0 1 0 1 0

1 0 1 0 0

0 0 0 0 0

Q1 Q2 Y1 Y2 Y3

Таблица 2

Основные ключевые слова

Дополнительные ключевые слова

Алг (алгоритм) рез (результат)

Нач (начало) кон (конеч)

Арг (аргумент) знач (значение)

Тип

Вещ (вещественный) цел(целый)

Лит (литерный) таб (таблица)

Сим (символьный)

Не то если и

все или выбор иначе

Нц (начало цикла) кц (конец цикла)

от до шаг для

пока :=(оператор присваивания)

при да нет

Запись

Истина

Лог (логический)

Ложь

Массив

Множество

Функция

Дано

Надо

Ввод

Вывод

Утв (утверждение)

Средства алгоритмического описания

Выражения

Рис. 7

Тип логический

Тип литерный

Тип натуральный

Тип вещественный

Тип целый

Указатели функции

Отношения

Логические

Арифметические

Массивы (таблицы)

Функции

Переменные

Константы

Знаки действий над величинами

Величины (данные)

Символические имена

Ключевые слова

Элемента синтаксических Конструкций языка

Повторение с параметром

Повторение

Выбор

Ветвление

Серия

Вызов вспомогательного алгоритма

Выдача результата рез

Задание значения арг

Присваивание

Составные

Комментарий

Простые

Оператор (команда)

Начало

Рис. 8

Конец

Ввод A, B

Вывод X

X:= A*B

Начало

Нет

Да

Рис. 9

Конец

Вывод X

X:= A+B

X:= A*B

Ввод

Начало

Рис. 10

N!:= N!*K

K:= K+1

Конец

Вывод N!

K < N

K:= 1, N!:= 1

Ввод N

Таблица 3

Алгоритмический язык

Схема алгоритма

если - то

если условие

то действия

все

да

Условие

нет

Действия

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

Если условие

То действия 1

Иначе действия 2

Все

нет

да

Действия 2

Действия 1

Условие

Выбор

При условие 1: действия 1

При условие 2: действия 2

…

При условие n: действия n

Все

нет

да

Действия n

Условие n

Условие 1

Условие 2

Действия 2

Действия 1

Продолжение таблицы на стр. 40

Продолжение таблицы 3

Выбор - иначе

Выбор

При условие 1: действия 1

При условие 2: действия 2

…

При условие n: действия n

Иначе действия n+1

Все

нет

Действия n+1

нет

да

Действия n

Условие n

Условие 1

Условие 2

Действия 2

Действия 1

Примеры команды если

Если x > 0

То y:= tg(x)

Все

нет

да

y:= tg(x)

x > 0

Если a > b

То a:= 5*a; b:= 1

Иначе b:= 4*b + 1

все

нет

да

a:=5*a; b:=1

b:=4*b+1

a > b

Продолжение таблицы на стр. 41

Продолжение таблицы 3

Выбор

При n = 1: y:= tg(x)

При n = 2: y:= ctg(x)

При n = 3: y:= 10

Все

нет

да

y:= 10

n = 3

нет

да

n = 1

n = 2

y:= ctg(x)

y:= tg(x)

Выбор

При a > 5: i:= a - 1

При a = 0: j:= a + 1

Иначе i:= 5; j:= 5

все

нет

i:=5; j:=5

нет

да

a > 5

a = 0

j:= a + 1

i:= a - 1

Цикл типа пока

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

Нц пока условие

Тело цикла (последовательность действий)

Кц

да

Тело цикла

Условие

Продолжение таблицы на стр. 42

Продолжение таблицы 3

Цикл типа для

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

Нц для i от i1 до i2

Тело цикла (последовательность действий)

кц

нет

i= i1, i2

да

Тело цикла

Примеры команд пока и для

i:= 1; S:= 0

нц пока i <= 10

S:= S + A[i]

i:= i +1

кц

нет

да

i:= i+1

S:= S + A[i]

i <= 10

Нц для i от 1 до 8

X[i]:= i*i

Y[i]:=X[i]/8

кц

i= 1, 8

нет

да

Y[i]:=X[i]/8

X[i]:= i*i