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

Информатика. 10 класс (Повышенный уровень)

§ 3. Основные алгоритмические конструкции

3.1. Алгоритмические конструкции

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

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

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

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

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

Пример 3.1. Блок-схемы алгоритмических конструкций.

1. Цикл с параметром (значение параметра изменяется от 1 до N):

2. Цикл с предусловием:

3. Цикл с постусловием:

Источник

Занятие 5. Алгоритмическая конструкция следование

Алгоритм и программа

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

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

налево, налево, налево, шагни, шагни, налево, шагни, шагни, налево, шагни, шагни, налево, шагни, шагни.

Л, Л, Л, Ш, Ш, Л, Ш, Ш, Л, Ш, Ш, Л, Ш, Ш.

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

Рис. 5.1. Запись алгоритма в виде графической схемы.

Все три приведенные записи алгоритма верны, но ни одна из них не может быть использована в среде ГРИС Букашка для того, чтобы исполнитель нарисовал квадрат. Для практического использования алгоритма придётся написать программу, реализующую алгоритм в соответствии с правилами языка программирования, который принят в среде ГРИС. Это было сделано на предыдущем занятии.

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

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

Пример программы

Источник

§ 3.4. Основные алгоритмические конструкции

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

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

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

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

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

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

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

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

х:=2
у:=х*х
У:=У*У
х:=у*х
s:=х+у

Выясним, какое значение получит переменная 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) рублей.

k500:=s div 500
s:=s mod 500
klOO:=s div 100
s:=s mod 100
k50:=s div 50
s:=s mod 50
klO:=s div 10

Ознакомьтесь с модулем для коллективной работы «Линейные алгоритмы» (http://school-collection.edu.ru/). Совместно с товарищами постарайтесь составить алгоритмы для имеющихся в модуле задач. Пройдите тестирование.

3.4.2. Ветвление

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

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

Полная форма ветвления:

Сокращённая форма ветвления:

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

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

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

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

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

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

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

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

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

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

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

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

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

Ознакомьтесь с модулем для коллективной работы «Алгоритмы с ветвящейся структурой» (http://school-collection.edu.ru/). Совместно с товарищами постарайтесь составить алгоритмы для имеющихся в модуле задач. Пройдите тестирование.

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

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

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

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

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

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

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

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

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

вправо
закрась

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

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

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

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

Ознакомьтесь с модулем для коллективной работы «Циклические алгоритмы с предусловием» (http://school-collection.edu.ru/). Совместно с товарищами постарайтесь составить алгоритмы для имеющихся в модуле задач. Пройдите тестирование:

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

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

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

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

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

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

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

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

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

Ознакомьтесь с модулем для коллективной работы «Циклические алгоритмы с постусловием» (http://school-collection.edu.ru/). Совместно с товарищами постарайтесь составить алгоритмы для имеющихся в модуле задач. Пройдите тестирование.

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

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

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

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

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

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

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

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

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

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

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

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

Пример 21. В некотором населённом пункте N домов. Известно, сколько людей проживает в каждом из домов. Составим алгоритм подсчёта жителей населённого пункта.

Исходные данные (количество жильцов) представим с помощью линейной таблицы А, содержащей N элементов: А[1] — количество жильцов дома 1, А[2] — количество жильцов дома 2, A[N] — количество жильцов дома N. В общем случае A[i] — количество жильцов дома i, где i принимает все значения от 1 до n (i = 1,n). Результат работы алгоритма обозначим через s.

Ознакомьтесь с модулем для коллективной работы «Циклические алгоритмы с параметром» (http://school-collection.edu.ru/). Совместно с товарищами постарайтесь составить алгоритмы для имеющихся в модуле задач. Пройдите тестирование.

Самое главное

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

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

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

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

Источник

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

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

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

Графическое представление алгоритмической конструкции «следование» приведено на рис. 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. Составьте соответствующие таблицы значений переменных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) цикл с заданным условием окончания работы;

3) цикл с заданным числом повторений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 15. Алгоритм по выучиванию наизусть четверостишия:

нц прочитать четверостишие по книге 1 раз рассказать четверостишие

кц при не сделал ошибку

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

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

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

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

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

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

нц для i от i1 до i2 шаг R

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

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

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

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

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

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

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

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

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

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

Источник