Информатика

Конспект

 

Составление линейных алгоритмов

 

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

Сегодня мы попрактикуемся в составлении алгоритмов. Это очень важные навыки. Мы уже неоднократно отмечали, что составить алгоритм, то есть объяснить другому, как выполнять те или иные задачи так, чтобы это было понятно каждому, - очень тяжело. Наша задача – научиться составлять алгоритмы для различных примеров, чтобы впоследствии, когда вы столкнётесь с необходимостью составлять алгоритмы для написания различных программ, это не составляло для вас особого труда.

 Начнём мы с самых простых алгоритмов – линейных. Их составление, обычно, не вызывает особого труда. Однако, навыки составления таких алгоритмов чрезвычайно важны.

Пример 1. Составить алгоритм запуска программы Paint в ОС Windows 7.

Решение:

Вспомним из курса информатики 5 класса порядок действий для запуска программы Paint.

1. Войти в меню «Пуск».
2. Войти в пункт «Все программы».
3. Войти в пункт «Стандартные».
4. Выбрать программу «Paint».

Данный алгоритм в виде блок-схемы имеет следующий вид:

 

Рис. 1. Блок-схема к примеру 1.

 

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

Рассмотрим пример на составление алгоритмов с ветвлениями.

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

Рис. 2. Светофор (Источник).

Решение:

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

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

1. Подойти к светофору.
2. Посмотреть на его свет.
3. Если горит зелёный, то перейти дорогу.
4. Если горит красный, то подождать, пока загорится зелёный, и уже тогда перейти дорогу.

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

Рис. 3. Блок-схема к примеру 2.

 

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

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

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

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

Решение:

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

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

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

Рис. 4. Блок-схема к примеру 3.

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

 

«Чтение» алгоритмов

Пример 4. По заданной блок-схеме выполнить действия алгоритма для числа 23.

Рис. 5. Блок-схема к примеру 4.

Решение:

1. a=23
2. 23+5=28
3. 28<35
4. 28+5=33
5. 33<35
6. 33+5=38
7. 38>35
8. 
9. 76 – двузначное число
10. 76-50=26.

Ответ: 26.

 

На этом уроке мы разобрали примеры составления алгоритмов, а также пример «чтения алгоритма» по готовой блок-схеме.

На следующем уроке мы обсудим игры и выигрышные стратегии.

 

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

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

Рис. 6. Кощей Бессмертный и Василиса Премудрая (Источник).

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

1. Конечно же, сначала необходимо разыскать остров Буян (на такие вещи, будем считать, Иван-дурак способен).
2. Поскольку сундук закопан под самым большим дубом, то сначала необходимо найти самый большой дуб на острове.
3. Затем нужно выкопать сам сундук.
4. Прежде чем доставать зайца, необходимо сломать крепкий замок.
5. Теперь уже можно достать зайца.
6. Из зайца нужно достать утку.
7. Из утки достать яйцо.
8. Разбить яйцо и достать иголку.
9. Иголку поломать.

Это тоже линейный алгоритм, хотя и более длинный, чем алгоритм запуска программы Paint.

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

Рис. 7. Блок-схема.

 

На распутье…

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

Рис. 8. Богатырь на распутье (Источник).

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

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

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

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

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

Рис. 9. Блок-схема.

 

Репка

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

Рис. 10. Репка.

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

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

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

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

Рис. 11. Блок-схема.

 

Список рекомендованной литературы

1. Босова Л.Л. Информатика и ИКТ: Учебник для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2012
2. Босова Л.Л. Информатика: Рабочая тетрадь для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2010.
3. Босова Л.Л., Босова А.Ю. Уроки информатики в 5-6 классах: Методическое пособие. – М.: БИНОМ. Лаборатория знаний, 2010.

 Рекомендованные ссылки на ресурсы интернет

1. Интернет портал «Сообщество взаимопомощи учителей» (Источник).
2. Интернет портал «Nsportal.ru» (Источник).
3. Интернет портал «Фестиваль педагогических идей» (Источник).

 Рекомендованное домашнее задание

1. §3.3, 3.4 (Босова Л.Л. Информатика и ИКТ: Учебник для 6 класса);
2. Постарайся самостоятельно составить линейный алгоритм из 5-6 фигур;
3. Составь блок-схему циклического алгоритма выполнения домашнего задания;