Билет №7
1. Основные алгоритмические структуры: следование, ветвление, цикл. Изображение на блок-схемах. Разбиение задачи на подзадачи. Вспомогательные алгоритмы.
Линейный (последовательный) алгоритм – алгоритм, в котором описание действий выполняется однократно в заданном порядке.
Предположим требуется составить алгоритм вычисления результата выражения:
100+15-40+20
Сложить числа 100 и 15
Из полученной суммы вычесть 40
К результату прибавить 20
Данный алгоритм можно изобразить наглядно. Для этого используются основные составляющие блок-схемы линейного алгоритма:
Начало - начало алгоритма
Х=100+15-40+20 - процесс – выполняется вычисление по 1 или нескольким
действиям
ввести х/ вывести х - ввод/вывод в общем виде
конец - конец алгоритма
Разветвляющийся – алгоритм, в которых в зависимости от условия выполняется либо одна, либо другая последовательность действий.
Б
лок-схема.
+ -
Вот пример использования ветвления в бытовой ситуации.
Если на улице идет
Дождь то надеть сапоги
Иначе надеть туфли
Конец ветвления.
Выйти из дома
Да
нет
На улице идет
дождь
Надеть сапоги
Надеть туфли
Выйти из дома
Если же на ветви (нет) отсутствует последовательность команд, т. е. (серия 2) отсутствует, то такое ветвление называется неполным. Вот пример неполного ветвления из той же бытовой серии:
Да
нет
Если на улице идет дождь
Т
о
взять зонт
Конец ветвления
В
Взять зонт
Выйти из дома
простыми командами являются команды присваивания, ввода и вывода. В качестве условия в ветвлении используется логическое выражение.
Ц иклический – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Блок схема.
+ -
Отметим основное отличительное свойство циклических алгоритмов; количество действий, исполняемы в процессе работы такого алгоритма, может существенно повышать количество команд, составляющих тело цикла.
В блок - схемах алгоритмов (графическом представление алгоритмов) и на учебном алгоритмическом языке цикла пока представляется так:
Да
нет
Пока
на полке есть книги взять книгу с полки
конец цикла
На полке есть
книги?
Всякий алгоритм составляет из простых команд, команд-обращений к вспомогательным алгоритмам и структурных команд.
Вспомогательным алгоритмом называется алгоритм некоторых подзадач по отношению к исходной (основной) задаче. Алгоритм решения основной задачи называется основным алгоритмом. Основные алгоритм содержит команды обращения к вспомогательным алгоритмам. Если составление вспомогательного алгоритма оказывается достаточно сложным, тогда в нем могут быть выделены подзадачи, для которых строятся вспомогательные алгоритмы второго уровня и т.д.
Последовательная детализация –это построение алгоритма “сверху вниз”. Сначала строится основной алгоритм, и в нем записываются обращения к вспомогательным алгоритмам первого уровня. Затем составляются эти вспомогательные алгоритмы, в которых могут быть записаны обращения к вспомогательным алгоритмам второго уровня, и.д. Вспомогательные алгоритмы последнего уровня не содержат обращений к другим вспомогательным алгоритмам.
Последовательность составления алгоритмов - сверху вниз
ОСНОВНОЙ АЛГОРИТМ
ВСПОМ. АЛГОРИТМ 1 ВСПОМ. АЛГ.2 1-Й УРОВЕНЬ
ВСПОМ. АЛГ.1.1 ВСПОМ. АЛГ.1.2 ВСПОМ. АЛГ. 2.1 2-Й УРОВЕНЬ
И Т. Д.
Методы последовательной детализации применяется при любом конструировании сложных объектов. Это естественная логическая последовательность мышления конструктора: постепенное углубление в детали. В нашем случае речь идет тоже о конструировании, но только не технических устройств, а алгоритмов. Достаточно сложный алгоритм другим способом практически построить невозможно. Такая методика позволяет организовать работу коллектива программистов над сложным проектом. Например, руководитель группы строит основной алгоритм, а разработку вспомогательных алгоритмов и составление подпрограмм поручает своим сотрудникам.
Вспомогательные алгоритмы, следовательно, создаются, когда возникает необходимость разбиения задачи на ряд более простых задач или когда есть необходимость многократного использования одного и того же набора действий в одном или разных алгоритмах.
Метод последовательной детализации путем разбиения задачи на подзадачи лежит в основе технологии структурного программирования и широко применяется при использовании структурных языков программирования, таких, как Паскаль или структурные версии Бейсика.
Согласно концепции структурного программирования, вспомогательный алгоритм должен:
Иметь заголовок ( имя ), с помощью которого его можно вызвать (обратится к нему чтобы начать его выполнение) из двух вспомогательных или основного алгоритмов ( это нужно для “состыковки” алгоритмов);
Возвращать управление тому алгоритму, из которого он был вызван, т. е. После выполнения вспомогательного алгоритма должно продолжатся, выполнение вызвавшего его алгоритма с той точки, в которой он был прерван;
иметь возможность вызвать другие алгоритмы;
быть относительно небольшим.
Желательно также, чтобы вспомогательный алгоритм:
имел один вход ( т. е. Его выполнение всегда начиналось в одной точке, независимо от того, откуда и при каких условиях он был выхван0 и один выход. Это гарантирует его замкнутость и упрощает работу с состыкованными алгоритмами;
обладает единственной функцией (например, вычислить недельный заработок сотрудника, напечатать отчет о состоянии оборудования), что служит ключом к хорошо спроектированному итоговому алгоритму? Таким образом, при проектировании основного алгоритма нужно сначала определить необходимый набор функции, а затем разработать вспомогательный алгоритмы.
При составлении и использовании вспомогательных алгоритмов важно знать, что является для них исходными данными (аргументами) и результатами их выполнения. Иногда команды вызова вспомогательного алгоритма содержат указания на имена переменных, значения которых являются для него исходными данными, и имена переменных, значения которых будут являться результатами его выполнения и использоваться в дальнейшем вне его. Иногда результатом выполнения вспомогательного алгоритма может стать значение некоторой сигнальной переменной (флажка), сообщающее, например, об истинности какого-то условия или наличии какого-либо факта, скажем корней уравнения (т. е. Значение флажка может быть равно 1или0). При записи программы для компьютера на языках программирования высокого уровня вспомогательные алгоритмы реализуются в виде программ. Правила обращения к ним и возврата в основную программу определяются конкретным языкам программирования. Программы общего назначения могут объединиться в библиотеки программ (процедур или функций). В языках программирования высокого уровня ветвление реализуется с помощью условного оператора.