Назовите базовые алгоритмические структуры и поясните их назначение кратко
Обновлено: 30.06.2024
Перечень вопросов, рассматриваемых в теме: алгоритм, блок-схема, следование, линейный алгоритм, ветвление, полная форма ветвления, неполная форма ветвления, разветвляющийся алгоритм, повторение, циклический алгоритм, цикл с предусловием, цикл с постусловием, цикл с параметром, комбинации базовых алгоритмических структур
Глоссарий по теме: следование, ветвление, повторение, цикл с предусловием, цикл с постусловием, цикл с параметром.
Основная литература по теме урока:
Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса
— М.: БИНОМ. Лаборатория знаний, 2017
Дополнительная литература по теме урока:
И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова. Информатика и ИКТ. Профильный уровень: учебник для 11 класса — М.: БИНОМ. Лаборатория знаний, 2012
Теоретический материал для самостоятельного изучения
В 1969 году нидерландский ученый Эдсгер Дийкстра доказал важную теорему. Суть ее в том, что для решения любой логической задачи можно составить алгоритм, используя лишь три алгоритмических структуры: следование, ветвление и повторение. Эти структуры называют базовыми.
Алгоритм реализован через последовательную алгоритмическую структуру, если все команды этого алгоритма выполняются один раз, причем в том порядке, в котором они записаны.
Существуют полная и неполная формы ветвления.
В полной форме если условие выполняется, то алгоритм переходит к выполнению первой серии команд, а если не выполняется — то ко второй.
В неполной форме алгоритм выполняет серию команд только если условие истинно. В противном случае ничего не происходит.
Существует несколько разновидностей циклических алгоритмов.
Первый — цикл с заданным условием продолжения работы (цикл с предусловием или цикл-пока).
Второй — цикл с заданным условием окончания работы (цикл с постусловием или цикл-до).
И третий — цикл с заданным числом повторений (цикл с параметром).
Доказано, что при решении задач можно ограничиться только одним циклом — циклом с предусловием. Но в ряде случаев цикл с постусловием или цикл с параметром делают решение задачи легче.
Примером решения одной и той же задачи с помощью различных циклов может служить задача возведения некоторого числа a в натуральную степень n.
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Естественно, что при таком подходе к алгоритмам изучение основных принципов их конструирования должно начинаться с изучения этих базовых элементов. Для их описания будем использовать язык схем алгоритмов и школьный алгоритмический язык.
| Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл. |
Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.
1. Базовая структура "следование". Образуется последовательностью действий, следующих одно за другим:
| Школьный алгоритмический язык | Язык блок-схем |
| действие 1 действие 2 . . . . . . . . . действие n |
2. Базовая структура "ветвление" . Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах:
3. Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице:
Линейным называется алгоритм, выполнение шагов которого происходит последовательно в порядке возрастания их номеров. В схеме он изображается последовательностью вычислительных блоков и блоков ввода-вывода.
Ветвлением (условием) называется алгоритм, в котором предусмотрено прохождение различных вариантов работы в зависимости от выполнения или не выполнения некоторого условия. В блок-схеме это условие записывается в ромб-блок сравнения.
Различают две формы ветвления:
Конструкция полного ветвления:
Конструкция неполного ветвления:
Алгоритм циклической структуры — алгоритм, в котором предусмотрено выполнение одной и той же последовательности действий.
Циклом называется участок алгоритма, реализующий многократно повторяющиеся при различных значениях параметров однотипные вычисления (например, расчеты по одной и той же формуле), Алгоритм, содержащий цикл, называется циклическим.
Циклический алгоритм позволяет существенно сократить объем программы.
Для организации цикла необходимо предусмотреть:
задание начального значения параметра цикла — переменной, которая будет изменяться при повторениях цикла;
изменение значения этой переменной перед каждым новым повторением цикла;
проверку условия окончания повторений по значению параметра и переход к началу цикла, если повторения не закончены.
Рефераты и конспекты лекций по географии, физике, химии, истории, биологии. Универсальная подготовка к ЕГЭ, ГИА, ЗНО и ДПА!
Базовые структуры алгоритма - это структуры, с помощью которых создается алгоритм для решения определенной задачи. Существуют три основные (базовые) алгоритмические структуры, или три основных типа алгоритмов: линейный, разветвленный и циклический.
Линейный алгоритм (последовательное выполнение, структура следования) - это алгоритм, который обеспечивает получение результата путем однократного выполнения последовательности действий, независимо от входных данных и промежуточных результатов. Действия в таких алгоритмах выполняются последовательно, одна за одной, т.е. линейно.
Разветвленный алгоритм (условие, структура выбора) - в классическом варианте эта структура рассматривается как выбор действий в случае выполнения или невыполнения заданного условия. Ветвления бывают полными и неполными.
Полное ветвление - это ветвление, в котором определенные действия определены и при выполнении, и в случае невыполнения условия. Неполное ветвление - это разветвление, в котором действия определены только при выполнении (или в случае невыполнения) условия.
Циклический алгоритм (цикл, структура повторения) - это алгоритм, в котором предусмотрено повторения некоторой серии команд. С помощью этой структуры описываются однотипные повторяющиеся несколько раз. Такие алгоритмы обеспечивают выполнение длинной последовательности действий, записанных сравнительно короткой последовательностью команд. Именно использование циклов позволяет в полной мере реализовать быстродействие компьютеров.
Основная особенность базовых алгоритмических структур - это их полнота, то есть этих структур достаточно для создания сложного алгоритма.
Читайте также: