Меню

Уроки 17 22 2 4 Основные алгоритмические конструкции

Анализ программ с помощью трассировочных таблиц

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

Используются трассировочные таблицы двух видов:

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

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

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

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

Из таблицы видно, что в результате работы переменные приняли значения: а = 2 и b = 4.

Пример 4. Определим значение переменной s, полученное в результате выполнения следующей программы:

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

Источник

Уроки 17 — 22 § 2.4. Основные алгоритмические конструкции

• следование
• ветвление
• повторение
• линейные алгоритмы
• разветвляющиеся алгоритмы
• циклические алгоритмы

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

Эдсгер Вибе Дейкстра (1930-2002) — выдающийся нидерландский учёный, идеи которого оказали огромное влияние на развитие компьютерной индустрии.

2.4.1. Следование

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

Графическое представление алгоритмической конструкции «следование» приведено на рис. 2.8.

Рис. 2.8. Алгоритмическая конструкция «следование»

Пример 1. Линейный алгоритм приготовления отвара шиповника.

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

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

Пример 3. Дан фрагмент линейного алгоритма:

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

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

Пример 4. Некоторый исполнитель может выполнять над целыми числами кроме операций сложения, вычитания, умножения и деления ещё две операции: с помощью операции div вычисляется целое частное, с помощью операции mod — остаток.

Например: 5 div 2 = 2; 5 mod 2 = 1; 2 div 5 = 0; 2 mod 5 = 2 .

Покажем, как с помощью этих операций можно реализовать алгоритм работы кассира, выдающего покупателю сдачу (s) наименьшим количеством банкнот по 500 (k500), 100 (k100), 50 (k50) и 10 (k10) рублей.

Исполните алгоритм для s = 745 и s = 1864. Составьте соответствующие таблицы значений переменных.

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

2.4.2. Ветвление

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

Блок-схема ветвления представлена на рис. 2.9. Каждая ветвь может быть любой степени сложности (рис. 2.9, а), а может вообще не содержать предписаний (рис. 2.9, б).

Рис. 2.9. Структура «ветвление»: а — полная форма ветвления; б — неполная форма ветвления

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

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

А В — А больше В;
А>=В — А больше или равно В;
А<>B — А не равно В.

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

Пример 7. Алгоритм вычисления функции f(x) = |x| для произвольного числа х.

Обратите внимание на второй блок этой блок-схемы . В нём представлены имена и типы величин (данных), обрабатываемых в алгоритме.

Условия, состоящие из одной операции сравнения, называются простыми. В качестве условий при организации ветвлений можно использовать и составные условия. Составные условия получаются из простых с помощью логических связок and (и), or (или), not (не) : and означает одновременное выполнение всех условий, or — выполнение хотя бы одного условия, a not означает отрицание условия, записанного за словом not .

Пример 8. Алгоритм определения принадлежности точки х отрезку [ а, b ]. Если точка х принадлежит данному отрезку, то выводится ответ ДА , в противном случае — НЕТ .

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

Пример 9. Алгоритм, в котором переменной У присваивается значение большей из трёх величин А, В и С.

Пусть А = 10, В = 30 и С = 20. Тогда процесс выполнения алгоритма можно представить в следующей таблице:

Пример 10. Алгоритм решения линейного уравнения ax + b = 0.

Пример 11. Исполнитель Робот может выполнять ту или иную последовательность действий в зависимости от выполнения следующих простых условий:

Также Робот может действовать в зависимости от выполнения составных условий.

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

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

2.4.3. Повторение

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

В зависимости от способа организации повторений различают три типа циклов:

Читайте также:  Анализ аудитории блогера и е интересов в Instagram

1) цикл с заданным условием продолжения работы;
2) цикл с заданным условием окончания работы;
3) цикл с заданным числом повторений.

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

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

На алгоритмическом языке эта конструкция записывается так:

Выполняется цикл-ПОКА следующим образом: 1) проверяется условие (вычисляется значение логического выражения); 2) если условие удовлетворяется (Да), то выполняется тело цикла и снова осуществляется переход к проверке условия; если же условие не удовлетворяется, то выполнение цикла заканчивается. Возможны случаи, когда тело цикла не будет выполнено ни разу.

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

Пример 13. Правее Робота (клетка со звёздочкой) расположен коридор неизвестной длины. Необходимо, чтобы Робот закрасил все клетки этого коридора.

Пока будет выполняться условие справа свободно , Роботу следует выполнять команды:

Соответствующий алгоритм для Робота будет иметь вид:

нц пока справа свободно
вправо
закрась
кц

Пример 14. Требуется, не пользуясь операцией деления, получить частное q и остаток r от деления натурального числа х на натуральное число у .

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

Исполним этот алгоритм для х = 23 и у = 5 .

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

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

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

На алгоритмическом языке эта конструкция записывается так:

Выполняется цикл-ДО следующим образом: 1) выполняется тело цикла; 2) проверяется условие (вычисляется значение логического выражения); если условие не удовлетворяется («Нет»), то снова выполняется тело цикла и осуществляется переход к проверке условия; если же условие удовлетворяется, то выполнение цикла заканчивается. В любом случае тело цикла будет выполнено хотя бы один раз.

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

Пример 16. Вычислим значение переменной b согласно следующему алгоритму:

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

Пример 17. Спортсмен приступает к тренировкам по следующему графику: в первый день он должен пробежать 10 км; каждый следующий день следует увеличивать дистанцию на 10% от нормы предыдущего дня. Как только дневная норма достигнет или превысит 25 км, необходимо прекратить её увеличение и далее пробегать ежедневно ровно 25 км. Начиная с какого дня спортсмен будет пробегать 25 км?

Пусть х — количество километров, которое спортсмен пробежит в некоторый i -й день. Тогда в следующий (i + 1) -й день он пробежит х + 0,1x : километров ( 0,1x — это 10% от х ).

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

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

Рис. 2.12. Цикл с параметром

На алгоритмическом языке эта конструкция записывается так:

В цикле-ДЛЯ всегда есть параметр цикла — величина целого типа, изменяющаяся в ходе выполнения цикла от своего начального значения i1 до конечного значения i2 с шагом R.

Выполняется цикл-ДЛЯ следующим образом: 1) параметру цикла присваивается начальное значение; 2) параметр цикла сравнивается с конечным значением; если параметр цикла не превышает конечное значение, то выполняется тело цикла, увеличивается значение параметра цикла на шаг и снова осуществляется проверка параметра цикла; если же параметр цикла превышает конечное значение, то выполнение цикла заканчивается.

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

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

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

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

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

Исполним этот алгоритм для a = 4 и n = 3.

Пример 20. Для исполнителя Робот цикл с известным числом повторений реализуется с помощью следующей конструкции:

Так, если правее Робота не встретится препятствий, то, выполнив приведённый ниже алгоритм, он переместится на пять клеток вправо и закрасит эти клетки:

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

САМОЕ ГЛАВНОЕ

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

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

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

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

1) цикл с заданным условием продолжения работы;
2) цикл с заданным условием окончания работы;
3) цикл с заданным числом повторений.

Вопросы и задания

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

2. Какие алгоритмы называются линейными?

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

а) из повседневной жизни;
б) из литературного произведения;
в) из любой предметной области, изучаемой в школе.

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

Читайте также:  Ключевой элемент таблицы субд

5. По алгоритму восстановите формулу.

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

Источник



Реализация алгоритмов в электронных таблицах

Реализацию алгоритма вычислительной задачи в электронных таблицах Excel возможно, так как они выполняют необходимые требования, предъявляемые к среде реализации алгоритма [Глущенко Ю. В. Обоснование использования языка программирования в учебном процессе (в печати)].

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

  1. Составление спецификаций переменных заданного алгоритма в виде таблицы, в столбцах которой будут Имя переменной в алгоритме, назначение, тип, диапазон, адрес в Excel, вид реализации.
  2. Разработка таблиц ВводаИнформации.
  3. Разработка таблицы подзадачи ОбработкаИнформации.
  4. Разработка таблицы ВыводаРезультата.
  5. Тестирование построенных таблиц.

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

ЗАДАЧА. Задан алгоритм в виде:

НАЧАЛО_АЛГОРИТМА

  1. Ввести значения сторон треугольника а, в, с.
  2. Вычислить значение полупериметра р = (а+в+с)/2
  3. Вычислить площадь треугольника S=(p*(p-а)*(р-в)*(р-с)).
  4. Вывести значение S.

Реализовать вычисления по заданному алгоритму в Excel.

1. Спецификация переменных исходного алгоритма:

2. Разработка таблицы ВводаИнформации

Таблица ВводаИнформации должна содержать значения переменных входного потока. Ее реализация показана на Рис. 1.

3. Разработка таблицы подзадачи ОбработкаИнформации

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

4. Разработка таблицы ВыводаРезультатов

Таблица ВыводаРезультатов должна содержать значения переменных выходного потока. Ее реализация показана на Рис. 1.

5. Тестирование разработанных таблиц

Для тестирования полученных таблиц строим таблицу теста по следующему шаблону:

№ п/п. Имя Назначение Значение/результат
1 А Входной поток 1 3 1
2 В 1 4 1
3 С 4 5 2
4 Р Промежуточные 3 6 2
5 S Выходной поток Ошибка 6

Задачи для самостоятельной работы можно найти в Приложении 1.

Алгоритм ветвления

ЗАДАЧА. Задан алгоритм в виде:

НАЧАЛО_АЛГОРИТМА

  1. Ввести значение переменной Х.
  2. ЕСЛИ Х не больше 0, ТО Y:=Х*Х, ИНАЧЕ Y:=Х+1.
  3. Вывести значение переменной Y.

Реализовать вычисления по заданному алгоритму в Excel.

1. Спецификация переменных исходного алгоритма:

№ п/п. Имя переменной в алгоритме. Назна-чение Тип Диа-пазон Адрес Реализация
Переменные входного потока
1 Х Входной поток вещ ± B3
Переменные блока обработки информации
2 Y вычисление вещ ± Е3
Переменные выходного потока.
2 Y Выходной поток вещ ± Е3

2. Разработка таблицы ВводаИнформации

Таблица ВводаИнформации должна содержать значения переменных входного потока. В нашем случае значение X. Ее реализация показана на Рис. 2.

3, 4. Разработка таблицы подзадачи ОбработкаИнформации.

В данной задаче можно (и нужно) объединить задачи ОбработкиИнфориации и ВыводаРезультатов, построив только таблицу ВыводаРезультатов. Ее реализация показана на Рис. 2.

5. Тестирование разработанной таблицы.

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

  • слева от ветвления,
  • в точке ветвления,
  • справа от точки ветвления.

Значения берутся так, чтобы просто было проверить результат. Поэтому построим таблицу тестирования в виде:

Имя переменной ЗНАЧЕНИЕ/РЕЗУЛЬТАТ
Слева от точки ветвления В точке ветвления Справа от точки ветвления
X -5 2
Y 25 3

Задачи для самостоятельной работы можно найти в Приложении 2.

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

ЗАДАЧА. Задан алгоритм в виде:

НАЧАЛО_АЛГОРИТМА

  • Ввести значение целочисленной переменной 1 I то идти на п.4
  • Вывести значение S <Вывод результата>.

Реализовать вычисления по заданному алгоритму в Excel.

1. Спецификация переменных исходного алгоритма:

№ п/п. Имя переменной в алгоритме. Назначение Тип Диапазон Адрес Реализация
Переменные входного потока
1 N ПВхП ц 1..10 B3
Индекс цикла
1 i индекс ц 1..N А10:A50
5 S ПВхдП ц
Переменные выходного потока.
5 S ПВхдП ц

2. Разработка таблицы ВводаИнформации

Таблица ВводаИнформации должна содержать значения переменных входного потока. В нашем случае значение N. Ее реализация показана на Рис. 3.

3. Разработка таблицы подзадачи ОбработкаИнформации

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

  • Построение столбца индексов цикла.
  • Построение столбца элементов массива.

ЗАДАЧА №1 ПОСТРОЕНИЕ СТОЛБЦА ИНДЕКСА ЦИКЛА.

Данную задачу сформулируем в виде:

Построить столбец значений индекса цикла в интервале [1..N (задано)]. При этом с изменением значения N в ячейке В3 должно изменяться и количество значений индекса цикла в расчетной таблице.
Эта задача решается в столбце А начиная со строки №10.

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

ПЕРВАЯ ЗАДАЧА РЕШЕНА

ЗАДАЧА №2. ПОСТРОЕНИЕ СТОЛБЦА ЭЛЕМЕНТОВ ЦИКЛА.

Здесь под элементом цикла будем понимать текущее значение S, зависящее от значения индекса цикла.
Сформулируем задачу в следующем виде:
Для каждого значения индекса цикла определить текущее значение S.
Столбец В дает нам текущие значения S=f( ), при этом протяжка формулы в столбце В должна быть не меньше протяжки в столбце А.

ВТОРАЯ ЗАДАЧА РЕШЕНА.

4. Разработка таблицы подзадачи ВыводРезультатов

Для решения данной задачи следует понять, что выходным значением S будет наибольшее из значений в ячейках В [10…]. Конечное значение интервала в В определяется протяжкой формул в задачах №№1, 2. Пусть формулы протянули до строки №50. Естественно, наибольшим S будет для наибольшего значения индекса цикла, так как на каждом шаге прибавляется число большее 1.
Следовательно, в ячейку Е3 необходимо ввести формулу

И если помнить, что значение пустой ячейки Excel воспринимает как «0», то…

ТРЕТЬЯ ЗАДАЧА РЕШЕНА.

5. Тестирование полученных таблиц

Для тестирования полученной таблицы строим таблицу теста по следующему шаблону:

№ п/п. Имя назначение Значение/результат
1 N Вход 1 5 7 9 10
2 S Выход 1 15 28 45 55

Задачи для самостоятельной работы можно найти в Приложении 3.

Источник

Блок-схемы алгоритмов. ГОСТ. Примеры

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

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

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

Содержание:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нужны ли блок-схемы? Альтернативы

Частные конторы никакие блок-схемы не используют, в книжках по алгоритмам [6] вместо них применяют словесное описание (псевдокод) как более краткую форму. Возможно блок-схемы применяют на государственных предприятиях, которые должны оформлять документацию согласно требованиям ЕСПД, но есть сомнения — даже для регистрации программы в Государственном реестре программ для ЭВМ никаких блок-схем не требуется.

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

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

Появляются подозрения, что система образования прогнила и отстала лет на 20, однако аналогичная проблема наблюдается и за рубежом. Международный стандарт ISO 5807:1985 мало чем отличается от ГОСТ 19.701-90, более нового стандарта за рубежом нет. Там же производится множество программ для выполнения этих самых схем — Dia, MS Visio, yEd, …, а значит списывать их не собираются. Вместо блок-схем иногда применяют диаграммы деятельности UML [6], однако удобнее они оказываются, разве что при изображении параллельных алгоритмов.

Периодически поднимается вопрос о том, что ни блок-схемы, ни UML не нужны, да и документация тоже не нужна. Об этом твердят программисты, придерживающиеся методологии экстремального программирования (XP) [7], ходя даже в их кругу нет единого мнения.

В ряде случаев, программирование невозможно без рисования блок-схем, т.к. это один процесс — существуют визуальные языки программирования, такие как ДРАКОН [8], кроме того, блок-схемы используются для верификации алгоритмов (формального доказательства их корректности) методом индуктивных утверждений Флойда [9].

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

Источник