Основные алгоритмические конструкции
Следование
Следование — алгоритмическая конструкция, отображающая естественный, последовательный порядок действий. Алгоритмы, в которых используется только структура «следование», называются линейными алгоритмами.
Графическое представление алгоритмической конструкции «следование» приведено на рисунке:
Пример 1. Линейный алгоритм приготовления отвара шиповника.
Обратите внимание, что многие из предписаний этого алгоритма могут потребовать детализации — представления в виде некоторой совокупности более мелких предписаний.
Пример 2. У исполнителя Робот есть четыре команды перемещения (вверх, вниз, влево и вправо), при выполнении каждой из них Робот перемещается на одну клетку в соответствующем направлении. По команде закрасить Робот закрашивает клетку, в которой он находится. Запишем линейный алгоритм, исполняя который Робот нарисует на клетчатом поле следующий узор и вернётся в исходное положение:
- алг узор
- нач
- закрасить
- вправо
- вправо
- закрасить
- вниз
- влево
- закрасить
- вверх
- влево
- кон
Пример3. Дан фрагмент линейного алгоритма:
x:=2
y:=x⋅x
y:=y⋅y
x:=y⋅x
s:=x+y
Выясним, какое значение получит переменная s после выполнения этого фрагмента алгоритма. Для этого составим таблицу значений переменных, задействованных в алгоритме:
С помощью операции div вычисляется целое частное, с помощью операции mod — остаток.
Ветвление
Ветвление — алгоритмическая конструкция, в которой, в зависимости от результата проверки условия («да» или «нет»), предусмотрен выбор одной из двух последовательностей действий (ветвей).
Алгоритмы, в основе которых лежит структура «ветвления», называют разветвляющимися.
Блок-схемы ветвления представлены на рисунках.
Полная форма ветвления
На алгоритмическом языке команда ветвления записывается так:
Пример 4.
Неполная форма ветвления
На алгоритмическом языке команда ветвления записывается так:
Пример 5.
Для записи условий, в зависимости от результатов проверки которых выбирается та или иная последовательность действий, используются операции сравнения:
A<B − А меньше В;
A<=B − А меньше или равно В;
A=B − А равно В;
A>B − А больше В;
A>=B − А больше или равно В;
A<>B − А не равно В.
Здесь буквы A и B можно заменять на любые переменные, числа и арифметические выражения. Приведённые операции сравнения допускаются и для символьных переменных.
Пример 6.
Алгоритм вычисления функции y(x)=|x| для произвольного числа x.
Обрати внимание на второй блок этой блок-схемы. В нём представлены имена и типы величин (данных), обрабатываемых в алгоритме.
Условия, состоящие из одной операции сравнения, называются простыми. В качестве условий при организации ветвлений можно использовать и составные условия.
Составные условия получаются из простых с помощью логических связок and (и), or (или), not (не): and означает одновременное выполнение всех условий, or — выполнение хотя бы одного условия, а not означает отрицание условия, записанного за словом not.
Пример 7.
Алгоритм определения принадлежности точки x отрезку [a;b]. Если точка x принадлежит данному отрезку, то выводится ответ ДА, в противном случае — НЕТ.
Существует достаточно много ситуаций, в которых приходится выбирать не из двух, а из трёх и более вариантов. Есть разные способы построения соответствующих алгоритмов. Один из них составить комбинацию из нескольких ветвлений.
Пример 8.
Алгоритм, в котором переменной Y присваивается значение большей из трёх величин A, B и C.
Пусть A=10, B=30 и C=20. Тогда процесс выполнения алгоритма можно представить в следующей таблице:
Ответ: Y=30.
Пример 9.
Алгоритм решения линейного уравнения ax+b=0.
Повторение
Повторение — алгоритмическая конструкция, представляющая собой последовательность действий, выполняемых многократно.
Алгоритмы, содержащие конструкцию повторения, называют циклическими или циклами.
Последовательность действий, многократно повторяющаяся в процессе выполнения цикла, называется телом цикла.
В зависимости от способа организации повторений различают три типа циклов:
- цикл с заданным условием продолжения работы;
- цикл с заданным условием окончания работы;
- цикл с заданным числом повторений.
Цикл с заданным условием продолжения работы ( цикл - ПОКА, цикл с предусловием)
Логика работы этой конструкции описывается схемой, показанной на рисунке.
На алгоритмическом языке эта конструкция записывается так:
Выполняется цикл-ПОКА следующим образом:
- проверяется условие (вычисляется значение логического выражения);
- если условие удовлетворяется (Да), то выполняется тело цикла и снова осуществляется переход к проверке условия;
- если же условие не удовлетворяется, то выполнение цикла заканчивается.
Возможны случаи, когда тело цикла не будет выполнено ни разу.
Пример 10.
Алгоритм, по которому из всех имеющихся кирпичей отбираются целые кирпичи и складываются в машину.
Пример 11.
Правее Робота расположен коридор неизвестной длины. Необходимо, чтобы Робот закрасил все клетки этого коридора.
Пример 12.
Требуется, не пользуясь операцией деления, получить частное q и остаток r от деления натурального числа x на натуральное число y.
Представим операцию деления как последовательные вычитания делителя из делимого. Причём вычитать будем до тех пор, пока результат вычитания не станет меньше вычитаемого (делителя). В этом случае количество вычитаний будет равно частному от деления q, а последняя разность — остатку от деления r.
Цикл с заданным условиемокончания работы (цикл-ДО, цикл с постусловием) Логика работы этой конструкции описывается схемой, показанной на рисунке.
На алгоритмическом языке эта конструкция записывается так:
Выполняется цикл-ДО следующим образом:
- выполняется тело цикла;
- проверяется условие (вычисляется значение логического выражения); если условие не удовлетворяется («Нет»), то снова выполняется тело цикла и осуществляется переход к проверке условия;
- если же условие удовлетворяется, то выполнение цикла заканчивается.
В любом случае тело цикла будет выполнено хотя бы один раз.
Пример 13.
Алгоритм по выучиванию наизусть четверостишия.
Пример 14.
Вычислим значение переменной b согласно следующему алгоритму:
Составим таблицу значений переменных, задействованных в алгоритме:
Пример 15.
Спортсмен приступает к тренировкам по следующему графику: в первый день он должен пробежать 10 км; каждый следующий день следует увеличивать дистанцию на 10 от нормы предыдущего дня. Как только дневная норма достигнет или превысит 25 км, необходимо прекратить её увеличение и далее пробегать ежедневно ровно25 км. Начиная с какого дня спортсмен будет пробегать 25 км?
Пусть x — количество километров, которое спортсмен пробежит в некоторый i-й день. Тогда в следующий (i+1)-й день он пробежит x+0,1x километров (0,1x — это 10 от x).
Цикл с заданным числом повторений ( цикл -ДЛЯ, цикл с параметром). Логика работы этой конструкции описывается схемой, показанной на рисунке.
На алгоритмическом языке эта конструкция записывается так:
Обрати внимание!
В цикле-ДЛЯ всегда есть параметр цикла — величина целого типа, изменяющаяся в ходе выполнения цикла от своего начального значения i1 до конечного значения i2 с шагом R.
Выполняется цикл-ДЛЯ следующим образом:
- параметру цикла присваивается начальное значение;
- параметр цикла сравнивается с конечным значением; если параметр цикла не превышает конечное значение, то выполняется тело цикла, увеличивается значение параметра цикла на шаг и снова осуществляется проверка параметра цикла; если же параметр цикла превышает конечное значение, то выполнение цикла заканчивается.
Если величина шага в цикле с параметром равна единице, то шаг не указывают. Мы ограничимся рассмотрением именно таких циклов.
В отличие от двух предыдущих конструкций (цикл-ПОКА, цикл-ДО) цикл-ДЛЯ имеет строго фиксированное число повторений, что позволяет избежать зацикливания, т.е. ситуации, когда тело цикла выполняется бесконечно.
Пример 16.
Алгоритм переправы через реку воинского отряда из пяти человек. Солдаты могут воспользоваться помощью двух мальчиков — хозяев небольшой лодки, в которой может переправиться или один солдат, или два мальчика.
Пример 17. Для исполнителя Робот цикл с известным числом повторений реализуется с помощью следующей конструкции:
Так, если правее Робота не встретится препятствий, то, выполнив приведённый ниже алгоритм, он переместится на пять клеток вправо и закрасит эти клетки:
