Задания к главе «Алгоритмика» (Ответы)




1. Продолжите фразы.

а) Исполнитель – это некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд.
б) Формальный исполнитель – исполнитель, который одну команду выполняет всегда одинаково.
в) Неформальный исполнитель – исполнитель, который одну команду может выполнить по-разному.
г) Управление – это процесс целенаправленного воздействия одних объектов на другие. Исполнители являются объектами управления.
д) Алгоритм – это предназначенное для конкретного исполнителя точное описание последовательности действий, направленных на решения поставленной задачи.

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

3. Исполнитель Кулинар предназначен для обжаривания лепёшек. Лепёшка считается готовой, если каждая её сторона жарилась 1 минуту.
Среда исполнителя – сковорода, на которой помещается две лепёшки.
Система команд исполнителя представлена в таблице:

Задания к главе «Алгоритмика» (Ответы)

Система отказов исполнителя следующая. Отказ «не понимаю» возникает тогда, когда исполнителю отдают команды «поместить 3», «перевернуть 3» и т.п.; этих команд нет в СКИ исполнителя Кулинар. Отказ «не могу» возникает при попытке поджарить одну сторону дважды. Для исполнителя Кулинар составьте алгоритм:

а) приготовления 4 лепёшек за 4 минуты:

Поместить 1, поместить 2, ждать, перевернуть 1, перевернуть 2, ждать, убрать 1, убрать 2.

б) приготовление 5 лепёшек за 5 минут:
Поместить 1, поместить 2, ждать, перевернуть 1, перевернуть 2, ждать, убрать 1, убрать 2.
Поместить 1, ждать, перевернуть 1, поместить 2, ждать, убрать 1, перевернуть 2, поместить 1, ждать, убрать 2, перевернуть 1, ждать, убрать 1.

4. Собрался Иван Царевич на бой со Змеем Горынычем, трёхглавым и трёххвостым.
«Вот тебе меч-кладенец, - говорит ему Баба Яга. – Одним ударом ты можешь срубить либо одну голову, либо две головы, либо один хвост, либо два хвоста. Запомни: срубишь голову – новая вырастет, срубишь хвост – два новых вырастут, срубишь два хвоста – голова вырастет, срубишь две головы – ничего не вырастет».
Какие удары и в какой последовательности должен наносить Иван Царевич, чтобы как можно быстрее срубить Змею все головы и все хвосты?
Решение задачи представьте в форме таблицы.

Задания к главе «Алгоритмика» (Ответы)


5. Внимательно прочитайте текст п. 3.1 «Алгоритм – модель деятельности исполнителя алгоритмов». Почему, по вашему мнению, его так назвали?
Задания к главе «Алгоритмика» (Ответы)


6. Охарактеризуйте исполнителя Чертёжник.
Исполнитель Чертёжник предназначен для построения рисунков на координатной плоскости.

7. Составьте для Чертёжника алгоритм рисования равнобедренного треугольника, если известны координаты концов отрезка, являющегося его высотой (4, 1) и (4, 6), а также координаты (2, 1) одной из вершин.
Задания к главе «Алгоритмика» (Ответы)


8. Составьте для Чертёжника алгоритм рисования прямоугольника со сторонами, параллельными осям координат, если известны координаты его двух вершин (2, 1) и (7, 5).
Задания к главе «Алгоритмика» (Ответы)


9. Составьте для Чертёжника алгоритм рисования ромба, центр которого находится в точке (5, 5), диагонали параллельны координатным осям, а их длины равны 8 и 4 единицам.
Задания к главе «Алгоритмика» (Ответы)


10. Составьте алгоритм управления Чертёжником, в результате выполнения которого на координатной плоскости будет нарисован квадрат, длина стороны которого равна 2 единицам.
Задания к главе «Алгоритмика» (Ответы)


11. Составьте алгоритм управления Чертёжником, в результате выполнения которого на координатной плоскости будет нарисован прямоугольник, длины сторон которого равны 3 и 4 единицам.

Задания к главе «Алгоритмика» (Ответы)


12. Составьте алгоритм управления Чертёжником, в результате выполнения которого на координатной плоскости будет нарисован произвольный параллелограмм.
Задания к главе «Алгоритмика» (Ответы)


13. Составьте алгоритмы рисования изображённых ниже фигур так, чтобы в процессе рисования перо не отрывалось от бумаги и ни одна линия не проводилась дважды.
Задания к главе «Алгоритмика» (Ответы)


14. Найдите в тексте п. 3.2 «Управление исполнителем Чертёжник» ответ на вопрос «Благодаря чему Чертёжник способен обучаться?»
Задания к главе «Алгоритмика» (Ответы)


15. Оформите в виде процедур алгоритмы рисования букв М, И, Р. Составьте алгоритмы рисования слов МИР, РИМ, МИМ.
Задания к главе «Алгоритмика» (Ответы)


16. Разработайте вспомогательный алгоритм для рисования домика. На его основе составьте основной алгоритм рисования улицы из пяти домиков.
Задания к главе «Алгоритмика» (Ответы)


17. Приведите пример жизненной ситуации, для описания которой уместно использовать цикл «повторить n раз».
Покраска кузова на заводе.
Уборка урожая на полях.
Скакать на скакалке.
Подтягивание на перекладине.

18. Составьте алгоритмы управления Чертёжником, после исполнения которых будут получены следующие рисунки.
Задания к главе «Алгоритмика» (Ответы)


19. Составьте алгоритмы управления Чертёжником, после исполнения которых будут получены следующие рисунки.
Задания к главе «Алгоритмика» (Ответы)

Задания к главе «Алгоритмика» (Ответы)


20. Придумайте свои задачи для Чертёжника.
Задания к главе «Алгоритмика» (Ответы)


21. Охарактеризуйте исполнителя Робот.
Исполнитель Робот действует на прямоугольном клетчатом поле. Между некоторыми клетками поля могут быть расположены стены. Некоторые клетки могут быть закрашены. Робот занимает одну клетку поля.

22. Приведите все алгоритмы из трёх команд, которые переместят Робота из исходного положения в точку Б.
Задания к главе «Алгоритмика» (Ответы)


23. Маша придумала узор для Робота. Коля стёр ровно половину закрашенных клеток. Восстановите рисунок, зная, что он симметричен относительно вертикальной оси. Напишите программу для Робота.
Задания к главе «Алгоритмика» (Ответы)


24. Напишите программу, с помощью которой Робот сможет достичь клетки Б во всех трёх лабиринтах.
Задания к главе «Алгоритмика» (Ответы)

вправо
вниз
влево
вниз
вправо
вниз
вниз
влево



25. Напишите программу, с помощью которой Робот попадает в клетку Б.
Задания к главе «Алгоритмика» (Ответы)


26. Известны два вспомогательных алгоритма Робота:
Задания к главе «Алгоритмика» (Ответы)


27. Составьте алгоритмы, под управлением которых Робот закрасит указанные клетки.
Задания к главе «Алгоритмика» (Ответы)


28. Приведите пример жизненной ситуации, для описания которой уместно использовать цикл «пока».
Бить врага, пока не сдастся.
Красить забор, пока не закрасится.
Стрелять по мишени, пока не попадёшь.

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

Задания к главе «Алгоритмика» (Ответы)


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

Задания к главе «Алгоритмика» (Ответы)


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

Задания к главе «Алгоритмика» (Ответы)


32. Известно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закрашена.
Составьте блок-схему алгоритма, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.

Задания к главе «Алгоритмика» (Ответы)


33. В ряду из десяти клеток правее Робота некоторые клетки закрашены:
Задания к главе «Алгоритмика» (Ответы)

б) Составьте алгоритм (напишите программу), под управлением которого Робот закрасит клетки на одну выше и на одну ниже каждой закрашенной клетки.

ПОВТОРИТЬ 10 РАЗ
вправо
ЕСЛИ закрашено ТО
вниз
закрасить
вверх
вверх
закрасить
вниз
КОНЕЦ
КОНЕЦ

34. Напишите программу, с помощью которой Робот может попасть в клетку D во всех трёх лабиринтах.
Задания к главе «Алгоритмика» (Ответы)

ЕСЛИ слева свободно ТО
влево
вниз
вправо
вниз
вправо
ИНАЧЕ; ЕСЛИ снизу свободно ТО
вниз
вправо
вверх
вправо
вниз
вправо
вверх
ИНАЧЕ; ЕСЛИ справа свободно ТО
вправо
вправо
вправо
вверх
вверх
вверх
влево
вниз
вниз
влево
влево
вверх
вверх
вправо
КОНЕЦ

35. Напишите программу, следуя которой, Робот сможет пройти по коридору от левого нижнего угла поля к правому верхнему. Коридор имеет ширину в одну клетку и тянется в направлении слева-снизу вправо-вверх. Пример возможного коридора изображён на рисунке.
Задания к главе «Алгоритмика» (Ответы)

ПОКА сверху свободно ИЛИ справа свободно
ДЕЛАТЬ
ЕСЛИ сверху свободно ТО
вверх
ИНАЧЕ
вправо
КОНЕЦ
КОНЕЦ

36. Внимательно прочитайте текст п. 3.3 «Управление исполнителем Робот». Ответьте на следующие вопросы:
1) Что общего у циклов «повторить n раз» и «пока»?
2) Какие между ними различия?
3) Нужны ли две конструкции для описания повторяющихся действий?

Задания к главе «Алгоритмика» (Ответы)


37. Сравните возможности исполнителей Чертёжника и Робота.
Робот более обширная программа, т.к. Чертёжник может только чертить. Робот может использовать цикл «пока», а Чертёжник – «повторить n раз».

38. Выпишите основные понятия главы 3 «Алгоритмика» и дайте их определения.

Исполнитель - человек, группа людей, животное или техническое устройство, способные выполнять заданные команды. Различают неформальных и формальных исполнителей.
Неформальный исполнитель – одну и ту же команду может выполнять по-разному, формальный – всегда одинаково. Для каждого формального исполнителя можно указать круг решаемых задач, среду, систему команд, систему отказов и режимы работы.

Алгоритм – это предназначенное для конкретного исполнителя точное описание последовательности действий, направленных на решение поставленной задачи. Алгоритм – модель деятельности исполнителя алгоритмов.
Алгоритм вспомогательный – алгоритм, решающий некоторую подзадачу основной задачи.
Алгоритм линейный – алгоритм, в котором команды выполняются в порядке, в котором они записаны, т.е. последовательно друг за другом.
Система команд исполнителя (СКИ) – перечень всех команд, которые может выполнить конкретный исполнитель.

Цикл (повторение) – форма организации действий, при которой выполнение одной и той же последовательности команд (тела цикла) повторяется, пока выполняется некоторое заранее установленное условие. Если число повторений тела цикла известно заранее, то можно использовать цикл «повторить n раз». Если число повторений тела цикла заранее неизвестно, используют цикл «пока».
Ветвление – форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий.