Составление алгоритмов с ветвлениями
-
Составьте алгоритм для перехода дороги на светофоре.
Решение:
Возможны следующие ситуации: в тот момент, когда мы подошли к дороге горел красный или зелёный свет. Если горел зелёный свет, то можно переходить дорогу. Если же горел красный свет, то необходимо дождаться зелёного – и уже тогда переходить дорогу.
Таким образом, алгоритм имеет следующий вид:
-
Подойти к светофору.
-
Посмотреть на его свет.
-
Если горит зелёный, то перейти дорогу.
-
Если горит красный, то подождать, пока загорится зелёный, и уже тогда перейти дорогу.
Блок-схема данного алгоритма имеет вид:
Составление циклических алгоритмов
Рассмотрим пример на составление циклического алгоритма. Мы уже несколько раз обсуждали перевод чисел из десятичной системы в двоичную. Теперь пришло время чётко сформулировать этот алгоритм.
Напомним, что его принцип состоит в делении числа на 2 и записей остатков, получающихся при делении.
-
Составить алгоритм перевода чисел из десятичной системы в двоичную.
Решение:
То есть, алгоритм будет выглядеть так:
-
Если число равно 0 или 1, то это и будет его двоичное представление.
-
Если число больше 1, то мы делим его на 2.
-
Полученный остаток от деления записываем в последний разряд двоичного представления числа.
-
Если полученное частное равно 1, то его дописываем в первый разряд двоичного представления числа и прекращаем вычисления.
-
Если же полученное частное больше 1, то мы заменяем исходное число на него и возвращаемся в пункт 2).
Блок-схема этого алгоритма выглядит следующим образом:
Примечание: подумайте, можно ли как-то упростить приведенную блок-схему.
-
Как убить Кощея?
Наверное, все помнят из детства сказку, в которой рассказывается о местонахождении смерти Кощея Бессмертного: «Смерть моя – на конце иглы, которая в яйце, яйцо – в утке, утка – в зайце, заяц в сундуке сидит, сундук на крепкий замок закрыт и закопан под самым большим дубом на острове Буяне, посреди моря-океяна …»
Предположим, вместо Ивана-царевича бороться с Кощеем был брошен Иван-дурак. Давайте поможем Василисе Премудрой составить такой алгоритм, чтобы даже Иван-дурак смог убить Кощея.
-
Конечно же, сначала необходимо разыскать остров Буян (на такие вещи, будем считать, Иван-дурак способен).
-
Поскольку сундук закопан под самым большим дубом, то сначала необходимо найти самый большой дуб на острове.
-
Затем нужно выкопать сам сундук.
-
Прежде чем доставать зайца, необходимо сломать крепкий замок.
-
Теперь уже можно достать зайца.
-
Из зайца нужно достать утку.
-
Из утки достать яйцо.
-
Разбить яйцо и достать иголку.
-
Иголку поломать.
Его блок-схема выглядит так:
-
На распутье…
И снова обратимся к сказочным персонажам в поисках примеров различных алгоритмов. Когда речь идёт об алгоритмах с ветвлениями, то, конечно, нельзя не вспомнить о богатыре, стоящем на распутье возле камня.
На камне написано:
«Направо пойдёшь – коня потеряешь, себя спасёшь; налево пойдёшь – себя потеряешь, коня спасёшь; прямо пойдёшь – и себя и коня потеряешь».
Попробуем составить алгоритм действий, который составил автор надписи на камне для путников?
-
Если мы пойдём направо, то потеряем коня. Если же мы не пойдём направо, то у нас остаётся два варианта (мы считаем, что назад возвращаться путник не будет): пойти прямо и налево.
-
В случае, если мы пойдём налево, то потеряем себя, а коня спасём.
-
Если же мы пойдём прямо, то потеряем и себя, и коня.
Блок-схема этого алгоритма выглядит так:
-
Репка
Русские народные сказки не оставили нас и без циклического алгоритма. И, как ни странно, спрятался он в одной из самых незамысловатых сказок – «Репке».
Вспомним сюжет сказки: дед тянет-потянет – вытянуть не может. Затем на помощь к деду по очереди подходят новые персонажи – и так до тех пор, пока не приходит мышка.
Попытаемся составить алгоритм действий всех персонажей сказки для того, чтобы они всё-таки смогли вытянуть Репку.
-
Изначально к Репке подошёл дед и попытался вытянуть.
-
Поскольку вытянуть Репку не получилось, то понадобилась помощь следующего персонажа.
-
И так происходит до тех пор, пока не появилась мышка (или, другими словами, до тех пор, пока Репку не вытащили).
Блок-схему нарисовать самостоятельно.