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

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

дискретностью, массовостью, определенностью, результативностью, формальностью.

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

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

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

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

1.2.Способы описания (виды) алгоритмов.

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

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

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

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

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

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

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

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

В таблице приведены наиболее часто употребляемые символы.

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

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

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

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

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

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

Разработка блок-схемы алгоритма решения задачи

Цель работы : изучение графического способа описания алгоритма решения задачи.

Задачи работы :

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

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

1.1. Порядок выполнения работы

Изучите теоретические сведения по теме данного раздела (п. 1.2)

Ознакомьтесь с постановкой задачи (п. 1.3). Вариант задания соответствует вашему номеру в списке группы.

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

Ответьте на контрольные вопросы.

Подготовьте отчет о выполнении практической работы, который должен содержать:

титульный лист;

цель практической работы;

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

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

ответы на контрольные вопросы;

выводы по практической работе.

1.2. Общие сведения

Одним из наиболее трудоемких этапов решения задачи на ЭВМ является разработка алгоритма.

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

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

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

массовость – пригодность для задач данного типа при исходных данных, принадлежащих заданному подмножеству;

результативность – реализуемый вычислительный процесс выполняется за конечное число этапов с выдачей осмысленного результата;

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

Выделяют следующие типы вычислительных процессов :

Линейный вычислительный процесс.

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

Разветвленный вычислительный процесс.

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

Циклический вычислительный процесс

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

В свою очередь, существуют также несколько типов циклического вычислительного процесса , а именно:

Счетные циклы (циклы с заданным количеством повторений) – ­­ это циклические процессы, для которых количество повторений известно.

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

Поисковые циклы – это циклические процессы, из которых возможны два варианта выхода:

Выход по завершению процесса;

Досрочный выход по какому-либо дополнительному условию.

По типу вычислительного процесса, реализуемого алгоритмом, различают:

Алгоритмы линейной структуры;

Алгоритмы разветвленной структуры;

Алгоритмы циклической структуры.

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

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

Словесный (записи на естественном языке);

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

Графический (изображение схем и графических символов);

Программный (тексты на языках программирования).

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

Пример 1.1.

Алгоритм сложения двух чисел (a и b).

Спросить, чему равно число a.

Спросить, чему равно число b.

Сложить a и b, результат присвоить с.

Сообщить результат с.

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

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

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

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

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

Блок-схема алгоритма – это графическое представление хода решения задачи. Блок-схема состоит из блоков, соединенных линиями, а блоки изображаются в виде геометрических фигур, называемых символами. Внутри символов записываются указания о выполняемых блоком функциях – формулы, текст, логические выражения. Вид символов и правила выполнения блок-схем стандартизированы – ГОСТ 19.701-90 содержит перечень символов, их наименования, отображаемые функции, формы и размеры, а также правила выполнения схем. При разработке алгоритма каждое действие обозначают соответствующим блоком, показывая их последовательность линиями со стрелками на конце. Названия, обозначения и назначение элементов блок-схем приводится на рис. 1.1.

Рисунок 1.1 – Основные блоки

Следует упомянуть некоторые основные правила выполнения блок-схем, которыми надлежит руководствоваться при графическом описании алгоритмов. Начало алгоритмов отмечается символом "Терминатор", из которого выходит одна линия. В нем записывается слово "Пуск" ("Начало"). Конец алгоритма отмечается этим же символом, в котором записывается слово "Останов" ("Конец"). В этом случае данный символ не имеет ни одной выходной линии, а на него может замыкаться одна или более линий. Символ “Процесс” может иметь одну или несколько входных линий и только одну выходную. Внутри символа может быть записано несколько предписаний – в этом случае они выполняются в порядке записи. Представление отдельных операций достаточно свободно. Для обозначения вычислений можно использовать математические выражения, для пересылки данных – стрелки, для других действий – пояснения на естественном языке, например, А: = Х + 4; i: = i + 1, ––> B.

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

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

следование - обозначает последовательное выполнение действий (рис. 1.2, а);

ветвление - соответствует выбору одного из двух вариантов действий (рис. 1.2, б);

цикл-пока - определяет повторение действий, пока не будет нарушено условие, выполнение которого проверяется в начале цикла (рис. 1.2, в).

Рисунок 1.2 – Базовые алгоритмические структуры

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

выбор - выбор одного варианта из нескольких в зависимости от значения некоторой величины (рис. 1.3, а, б);

цикл-до - повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (рис. 1.3, в, г);

цикл с заданным числом повторений (счетный цикл ) – повторение некоторых действий указанное число раз (рис. 1.3, д, е).

Рисунок 1.3 – Реализация дополнительных алгоритмических структур

через базовые структуры

Рассмотрим примеры графического описания алгоритмов различных типов: линейного, разветвляющегося, циклического и комбинированного (рис. 1.4 – 1.7).

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

Алгоритм вычисления значения выражения K=3b+6а (рис. 1.4) .

Рисунок 1.4 – Пример блок-схемы линейного алгоритма

Пример 1.3. Разветвляющийся алгоритм.

Алгоритм, определяющий, пройдет ли график функции y=3x+4 через точку с координатами x1,y1 (рис. 1.5).

Рисунок 1.5 – Пример блок-схемы разветвляющегося алгоритма

Пример 1.4. Циклический алгоритм.

Алгоритм, определяющий факториал натурального числа n (рис. 1.6):

n ! = 1*2*3*….*(n -1)* n

5!=1*2*3*4*5=120

Рисунок 1.6 – Пример блок-схемы циклического алгоритма

Пример 1.5. Комбинированный алгоритм.

Необходимо определить наибольший общий делитель двух натуральных чисел А и В.

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

Пример (а): А=225, В=125. Применяя алгоритм Евклида, получаем для А и В наибольший общий делитель, равный 25.

Пример (б): А=13, В=4. В этом случае наибольший общий делитель А и В равен 1.

				B
		50-25=25

Блок-схема алгоритма Евклида для нахождения наибольшего общего делителя двух натуральных чисел показана на рис. 1.7.

Рисунок 1.7 – Пример блок-схемы комбинированного алгоритма

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

Пример 1.6. Описание алгоритма Евклида на псевдокоде .

Алгоритм Евклида:

Ввести А,В

цикл-пока А ≠ В

если А > В

то А:= А - В

иначе В:= В - А

все - если

все-цикл

Вывести А

Конец алгоритма.

Таблица 1.1 – Пример псевдокода для записи базовых алгоритмических структур

Структура	Псевдокод	Структура	Псевдокод
Следование			Выбор
			Все-выбор
Ветвление	Если	заданным количеством повторений	Для =
	иначе
	Все - если		Все-цикл
Цикл-пока	Цикл-пока		Выполнять
	Все-цикл

1.3. Задачи для составления блок-схем алгоритмов

Дано целое число m>1.

Получить наименьшее целое k, при котором 4 k >m.

Вычислить произведение

Дано целое число n.

Получить наименьшее число вида 2 r , превосходящее n (r - натуральное).

Даны целые числа n, k (n  k  0).

Вычислить.

Дано натуральное число n и действительное число a.

Вычислить произведение .

Дано натуральное число n.

Вычислить сумму .

Даны действительное число х и натуральное число n.

Вычислить, не используя операцию возведения в степень.

Дано натуральное число n.

Вычислить сумму:

Даны действительные числа x и a, натуральное n.

Вычислить:

Вычислить:

Даны натуральные числа n, m. Получить сумму m последних цифр числа n.

Пусть n- натуральное число. Вычислить сумму.

Дано натуральное число n.

Вычислить сумму:

Контрольные вопросы

Дайте определение алгоритма.

Перечислите основные свойства алгоритмов и раскройте их сущность.

Как подразделяются алгоритмы по типу реализуемого вычислительного процесса?

Какие способы описания алгоритмов вам известны?

Что понимается под графическим способом описания алгоритмов? В чем состоит преимущество данного способа перед словесным описанием алгоритма?

Курсовая работа >> Информатика

Весов ребер оставного дерева. 2.4 Блок -схема Рисунок 7 – Блок -схема алгоритма решения задачи 2.5 Обоснование выбора языка программирования Турбо... , интегрированную среду, намного ускоряющую процесс разработки программ. Этот программный продукт прошел...

1. Алгоритмы и основы программирования

   Практическая работа >> Информатика, программирование

   Составление программ решения различных задач на электронных вычислительных машинах; наука, занимающаяся разработкой методов... . Блок -схема данного линейного алгоритма показана на рисунке 4. Пример 1. Вычислить при x=2,3 В общем случае, алгоритм решения ...

2. Построение блок схем алгоритмов . Алгоритмические языки высокого уровня

   Реферат >> Информатика

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

3. Системное и программное обеспечение

   Реферат >> Информатика

   ... : Разработка блок схемы алгоритма решения задачи по контролю знаний слушателей ФПК. ОписаниеФФффуввыа блоков схемы алгоритма решения задачи . Блок 1 ... – ввести имя (обозначение) задачи , ввести...

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

Алгоритм и алгоритмизация

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

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

Элементы блок-схем

Блок-схема алгоритма программы представляет собой последовательность графических символов, предписывающих выполнение конкретных операций, а также связей между ними. Внутри каждого такого изображения указывается информация о задаче, подлежащей выполнению. Размеры и конфигурация графических символов, а также порядок оформления последовательностей регламентированы ГОСТ 19003-80 и ГОСТ 19002-80.

Рассмотрим основные элементы блок-схемы алгоритма (на фото предоставлены примеры их начертания).

1. Процесс - вычислительное действие либо последовательность таких действий.

2. Решение - проверка заданного условия.

3. Модификация - заголовок цикла.

4. Предопределенный процесс - обращение к процедуре.

5. Документ - печать и вывод данных.

6. Перфокарта - ввод информации.

7. Ввод/Вывод - Ввод/Вывод данных.

8. Соединитель - разрыв линий потока.

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

10. Комментарий - используют для размещения пояснительных надписей.

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

12. Слияние - соединение потоков.

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

Правила начертания

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

Переменные, константы и ячейки памяти

Для лучшего понимания принципа действия алгоритма можно рассмотреть простейший автомат. В его состав входят память, состоящая из ячеек; записывающая/считывающая головка; процессор. В чем заключается принцип работы такого устройства? Головка, получив приказ от процессора, осуществляет запись данных в ячейку либо производит считывание константы. В простейшем случае это будет арифметическое число. Кроме того, константами могут быть строки символов и др. Под переменной понимается ячейка памяти, в которой хранится информация. За время выполнения алгоритма в такой ячейке могут быть записаны различные данные. На этом принципе построены персональные компьютеры и прочая электроника. Алгоритм выполнения какой-либо задачи является набором команд для считывания или записи информации в эти ячейки памяти.

Массивы

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

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

Линейные алгоритмы

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

Разветвляющиеся алгоритмы

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

Блок-схемы алгоритмов: примеры

Рассмотрим, каким образом функционирует разветвленный алгоритм. В качестве примера возьмем функцию: z = y/x. Из условия видно, что данное уравнение обладает одним ограничением - на нуль делить нельзя. Так что необходимо исключить данное решение и предупредить пользователя о возникшей ошибке. Сначала составляется блок-схема алгоритма. Она будет состоять из семи блоков. Первый графический символ - «Начало», второй - «Ввод», здесь следует задать значения Х и Y. Затем следует блок «Решение», в нем проводится проверка условия: Х=0. В данном случае автомат проводит сверку с ячейкой константой, если вводимое значение совпадет с ней, то решение алгоритма пойдет по ветви «Да». В таком случае управление передается четвертому блоку, и автомат выдает «ошибку», работа заканчивается в седьмом символе «Конец». Если результат проверки отрицательный, тогда в пятом графическом символе осуществляется процесс деления и определяется значение Z. В шестом блоке выводится результат на экран.

Циклические алгоритмы

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

Пример решения разветвляющегося алгоритма

Рассмотрим пример, в котором дана блок-схема алгоритма с наперед неизвестным количеством проходов. Для этого следует решить задачу - указать наименьшее число членов ряда сумма которых превышает число К. Такая блок-схема алгоритма состоит из восьми символов. Вначале вводим значение числа К (№2). Затем в блоке 3 переменная П получает значение «единица», это значит, что с него начнется отсчет натуральных чисел. А накопительная сумма С в начале получает значение «нуль». Далее управление передается в пятый блок, где происходит выполнение команды: С=С+П. То есть происходит суммирование значений ячеек С и П, и результат перезаписывается в С. После сложения первого члена данной последовательности в блоке №6 осуществляется проверка условия - не превышает ли сумма заданное число К? Если условие не выполнено, тогда управление передается четвертому блоку, где к переменной П прибавляется единица и осуществляется переход снова к блоку №5. Данная процедура будет происходить до тех пор, пока не выполнится условие: С>К, то есть накапливаемая сумма превысит заданное значение. Переменная П является счетчиком цикла. Далее происходит переход к блоку №7, где отпечатываются результаты работы.

Алгоритмы, содержащие структуры вложенных циклов

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

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

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

Декомпозиция алгоритма

Под этим термином понимают разложение общей схемы алгоритма на вспомогательные (функции и процедуры) и головной. Этот метод весьма прост, когда алгоритм задан блок-схемой - сначала из него вычленяют участки, отвечающие за основную работу. Наиболее сложные этапы оформляются как функции и процедуры верхнего уровня. Далее их делят на элементарные участки низкого уровня. Здесь работает принцип «от сложного к простому». Это проводится до тех пор, пока алгоритм не будет разобран на Обычно решение декомпозиции последовательности состоит из трех главных этапов: ввода данных, вывода отсортированного массива. Первый и последний этапы вследствие их элементарности не нуждаются в разложении, поэтому их выполняют в головном алгоритме. А вот второй является весьма сложным самостоятельным фрагментом вычислений, поэтому его обычно выводят в отдельный блок. Этапы сортировки, в свою очередь, делятся на две части: установления необходимости проведения процедуры (N-1)-кратного прохода по заданному массиву и нахождения наименьшего элемента в рассматриваемом фрагменте массива с последующей перестановкой его с начальным элементом участка. Так как последний этап неоднократно повторяется, то его оформляют как отдельную процедуру.

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

На территории Российской Федерации действует единая система программной документации (ЕСПД) , частью которой является Государственный стандарт — ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем» . Не смотря на то, что описанные в стандарте обозначения могут использоваться для изображения схем ресурсов системы, схем взаимодействия программ и т.п., в настоящей статье описана лишь разработка схем алгоритмов программ.

Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985 .

Элементы блок-схем алгоритмов

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

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

Терминатор начала и конца работы функции	Терминатором начинается и заканчивается любая функция. Тип возвращаемого значения и аргументов функции обычно указывается в комментариях к блоку терминатора.
Операции ввода и вывода данных	В ГОСТ определено множество символов ввода/вывода, например вывод на магнитные ленты, дисплеи и т.п. Если источник данных не принципиален, обычно используется символ параллелограмма. Подробности ввода/вывода могут быть указаны в комментариях.
Выполнение операций над данными	В блоке операций обычно размещают одно или несколько (ГОСТ не запрещает) операций присваивания, не требующих вызова внешних функций.
Блок, иллюстрирующий ветвление алгоритма	Блок в виде ромба имеет один вход и несколько подписанных выходов. В случае, если блок имеет 2 выхода (соответствует оператору ветвления), на них подписывается результат сравнения — «да/нет». Если из блока выходит большее число линий (оператор выбора), внутри него записывается имя переменной, а на выходящих дугах — значения этой переменной.
Вызов внешней процедуры	Вызов внешних процедур и функций помещается в прямоугольник с дополнительными вертикальными линиями.
Начало и конец цикла	Символы начала и конца цикла содержат имя и условие. Условие может отсутствовать в одном из символов пары. Расположение условия, определяет тип оператора, соответствующего символам на языке высокого уровня — оператор с предусловием (while) или постусловием (do … while).
Подготовка данных	Символ «подготовка данных» в произвольной форме (в ГОСТ нет ни пояснений, ни примеров), задает входные значения. Используется обычно для задания циклов со счетчиком.
Соединитель	В случае, если блок-схема не умещается на лист, используется символ соединителя, отражающий переход потока управления между листами. Символ может использоваться и на одном листе, если по каким-либо причинам тянуть линию не удобно.
Комментарий	Комментарий может быть соединен как с одним блоком, так и группой. Группа блоков выделяется на схеме пунктирной линией.

Примеры блок-схем

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

Сортировка вставками

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

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

Блок-схема алгоритма сортировки вставками

В приведенной блок-схеме для организации цикла используется символ ветвления. В главном цикле (i < n) перебираются элементы необработанной части массива. Если все элементы обработаны — алгоритм завершает работу, в противном случае выполняется поиск позиции для вставки i-того элемента. Искомая позиция будет сохранена в переменной j в результате выполнения внутреннего цикла, осуществляющем сдвиг элементов до тех пор, пока не будет найден элемент, значение которого меньше i-того .

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

Сортировка пузырьком

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

Блок-схема алгоритма сортировки пузырьком

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

Сортировка выбором

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

Блок-схема сортировки выбором

На блок-схеме приведен пример использования блока «подготовка», а также показано, что в ряде случаев можно описывать алгоритм более «укрупнённо» (не вдаваясь в детали). К сортировке выбором не имеют отношения детали реализации поиска индекса минимального элемента массива , поэтому они могут быть описаны символом вызова внешней процедуры. Если блок-схема алгоритма внешней процедуры отсутствует, не помешает написать к символу вызова комментарий, исключением могут быть функции с говорящими названиями типа swap, sort , … .

На блоге можно найти другие примеры блок-схем :

Часть студентов традиционно пытается рисовать блок-схемы в Microsoft Word , но это оказывается сложно и не удобно. Например, в MS Word нет стандартного блока для терминатора начала и конца алгоритма (прямоугольник со скругленными краями, а не овал). Наиболее удобными, на мой взгляд, являются утилиты MS Visio и yEd , обе они позволяют гораздо больше, чем строить блок-схемы (например рисовать диаграммы UML), но первая является платной и работает только под Windows, вторая бесплатная и кроссплатфомренная. Все блок-схемы в этой статье выполнены с использованием yEd.

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

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

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

Элементы блок-схемы

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

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

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

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

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

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

Особенности применения блок-схем

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

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