Информатика 9 класс. Урок 15.

Составление алгоритмов с ветвлениями

1. Составьте алгоритм для перехода дороги на светофоре.

Решение:

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

Таким образом, алгоритм имеет следующий вид:

1. Подойти к светофору.

2. Посмотреть на его свет.

3. Если горит зелёный, то перейти дорогу.

4. Если горит красный, то подождать, пока загорится зелёный, и уже тогда перейти дорогу.

Блок-схема данного алгоритма имеет вид:

Составление циклических алгоритмов

Рассмотрим пример на составление циклического алгоритма. Мы уже несколько раз обсуждали перевод чисел из десятичной системы в двоичную. Теперь пришло время чётко сформулировать этот алгоритм.

Напомним, что его принцип состоит в делении числа на 2 и записей остатков, получающихся при делении.

1. Составить алгоритм перевода чисел из десятичной системы в двоичную.

Решение:

То есть, алгоритм будет выглядеть так:

1. Если число равно 0 или 1, то это и будет его двоичное представление.

2. Если число больше 1, то мы делим его на 2.

3. Полученный остаток от деления записываем в последний разряд двоичного представления числа.

4. Если полученное частное равно 1, то его дописываем в первый разряд двоичного представления числа и прекращаем вычисления.

5. Если же полученное частное больше 1, то мы заменяем исходное число на него и возвращаемся в пункт 2).

Блок-схема этого алгоритма выглядит следующим образом:

Примечание: подумайте, можно ли как-то упростить приведенную блок-схему.

1. Как убить Кощея?

Наверное, все помнят из детства сказку, в которой рассказывается о местонахождении смерти Кощея Бессмертного: «Смерть моя – на конце иглы, которая в яйце, яйцо – в утке, утка – в зайце, заяц в сундуке сидит, сундук на крепкий замок закрыт и закопан под самым большим дубом на острове Буяне, посреди моря-океяна …»

Предположим, вместо Ивана-царевича бороться с Кощеем был брошен Иван-дурак. Давайте поможем Василисе Премудрой составить такой алгоритм, чтобы даже Иван-дурак смог убить Кощея.

1. Конечно же, сначала необходимо разыскать остров Буян (на такие вещи, будем считать, Иван-дурак способен).

2. Поскольку сундук закопан под самым большим дубом, то сначала необходимо найти самый большой дуб на острове.

3. Затем нужно выкопать сам сундук.

4. Прежде чем доставать зайца, необходимо сломать крепкий замок.

5. Теперь уже можно достать зайца.

6. Из зайца нужно достать утку.

7. Из утки достать яйцо.

8. Разбить яйцо и достать иголку.

9. Иголку поломать.

Его блок-схема выглядит так:

1. На распутье…

И снова обратимся к сказочным персонажам в поисках примеров различных алгоритмов. Когда речь идёт об алгоритмах с ветвлениями, то, конечно, нельзя не вспомнить о богатыре, стоящем на распутье возле камня.

На камне написано:

«Направо пойдёшь – коня потеряешь, себя спасёшь; налево пойдёшь – себя потеряешь, коня спасёшь; прямо пойдёшь – и себя и коня потеряешь».

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

1. Если мы пойдём направо, то потеряем коня. Если же мы не пойдём направо, то у нас остаётся два варианта (мы считаем, что назад возвращаться путник не будет): пойти прямо и налево.

2. В случае, если мы пойдём налево, то потеряем себя, а коня спасём.

3. Если же мы пойдём прямо, то потеряем и себя, и коня.

Блок-схема этого алгоритма выглядит так:

1. Репка

Русские народные сказки не оставили нас и без циклического алгоритма. И, как ни странно, спрятался он в одной из самых незамысловатых сказок – «Репке».

Вспомним сюжет сказки: дед тянет-потянет – вытянуть не может. Затем на помощь к деду по очереди подходят новые персонажи – и так до тех пор, пока не приходит мышка.

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

1. Изначально к Репке подошёл дед и попытался вытянуть.

2. Поскольку вытянуть Репку не получилось, то понадобилась помощь следующего персонажа.

3. И так происходит до тех пор, пока не появилась мышка (или, другими словами, до тех пор, пока Репку не вытащили).

Блок-схему нарисовать самостоятельно.