Алгоритмы. Простые исполнители - Обработка информации - ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ

Конспект

В данной главе мы собираемся обсудить принципы анализа и построения алгоритмов. Алгоритм — это последовательность команд, направленных на выполнение какого-либо действия. За время учебы в школе вы часто пользовались тем или другим алгоритмом. Обычно именно в форме алгоритма даются в математике правила, например, умножения или деления чисел. При обсуждении правил перевода чисел из одной системы счисления в другую мы тоже используем алгоритм.

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

Первое условие — наличие исполнителя, того, кто будет исполнять алгоритм. Им может быть робот, компьютер, человек, машина (например, стиральная или посудомойная).

Второе — система команд исполнителя (сокращенно — СКИ). Это набор тех команд/инструкций, которые исполнитель может выполнить. Крайне желательно, чтобы эти команды/инструкции были чётко определены и понятны для исполнителя. Особенно это важно, когда исполнитель — человек. Как правило, человек способен вольно трактовать данные ему команды/инструкции. Поэтому именно человек зачастую выполняет алгоритм с непредсказуемым результатом. В некоторых заданиях экзамена требуется именно исполнить предложенный алгоритм. Важно научиться выполнять алгоритм формально, не придумывая к нему при этом ничего лишнего.

Третье — должна быть известна среда исполнения, пространство, в котором работает/живёт/выполняет алгоритм исполнитель. Для робота, перемещающегося по клеткам лабиринта — это лабиринт. Для выдуманного исполнителя Кузнечика, прыгающего по числам на числовой прямой — это числовая прямая.

Четвёртое условие — система отказов. Это описание тех ситуаций, когда исполнитель не может выполнить указанную команду в том месте (в тот момент), в котором исполнитель сейчас находится. Например, если исполнитель должен уметь выполнять операцию деления, то отказ возникнет в тот момент, когда его попросят выполнить деление на ноль.

Рассмотрим несколько типичных учебных исполнителей.

1. У исполнителя Удвоитель две команды, которым присвоены номера:

1. Умножь на 2,

2. Прибавь 3.

Первая из них удваивает число на экране, вторая — увеличивает его на 3.

2. Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (а, b) (где а, b — целые числа), перемещающую Чертёжника из точки с координатами (х, у) в точку с координатами (х + а, у + b). Если числа а, b положительные, значение соответствующей координаты увеличивается; если отрицательные — уменьшается.

Например, Чертёжник находится в точке с координатами (9, 5). Команда Сместиться на (1, —2) переместит Чертёжника в точку (10, 3).

3. Исполнитель Робот живёт в прямоугольном лабиринте на клетчатой плоскости. Он умеет передвигаться, выполняя следующие команды:

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

При выполнении этих команд Робот перемещается на одну клетку соответственно:

вверх ↑, вниз ↓, влево ←, вправо →

Если Робот начнёт движение в сторону стены, то он разрушится и программа прервётся.

Четыре команды проверяют истинность условия отсутствия стены у той клетки, где находится РОБОТ:

сверху свободно снизу свободно слева свободно справа свободно

Определим у приведённых исполнителей, чем являются для них перечисленные выше условия.

Исполнитель	Системакомандисполнителя	Среда исполнения	Система отказов
Удвоитель	Умножь на 2 Прибавь 3	Шкала целых чисел. Текущее число отображается на экране. Можно сказать, числовая прямая	Отсутствует (нет каких-нибудь сведений или предположений, в каком случае Удвоителю может не удастся выполнить какую-либо из его команд)
Чертёжник	Сместиться на(а, b)	Бесконечное поле — координатная плоскость.	Отсутствует (нет сведений о том, что плоскость чем-то ограничена или что у Чертёжника что-то может сломаться)
Робот	вверх вниз влево вправо сверху свободно снизу свободно слева свободно справа свободно	Прямоугольный лабиринт на клетчатой плоскости	Движение в стену (если по границе клетки, в которой находится Робот, стоит стена и Робот получает команду движения в сторону этой стены, Робот разрушится)

Не всегда среда исполнения для исполнителя такая идеальная и бесконечная, как у Удвоителя или Чертёжника. Часто среда исполнения ограничена размерами или препятствиями и у исполнителя могут возникнуть разные ситуации, которые иногда даже не может предположить разработчик. В этом случае, как Вы, вероятно, понимаете, алгоритм приводит к непредсказуемому результату.

В учебных задачах система команд исполнителя обычно проста и непредвиденных ситуаций не возникает. Выполнение ряда заданий при этом даже не требует особенных навыков, а выполняется в пределах здравого смысла и понимания основного принципа формального алгоритма. Ваша задача не придумывать, как мог бы выполниться алгоритм, потому что вам так хочется, а выполнять ровно то, что написано.

Разбор типовых задач

Задача 1. Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она чётна, то в начало цепочки символов добавляется символ Г, а если нечётна, то дублируется средний символ цепочки.

В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А — на Б, Б — на В и т. д., а Я — на А).

Получившаяся таким образом цепочка является результатом работы алгоритма.

Например, если исходной была цепочка УРА, то результатом работы алгоритма будет цепочка ФССБ, а если исходной была цепочка ПУСК, то результатом работы алгоритма будет цепочка ДРФТЛ.

Дана цепочка символов РЕКА. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т.е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)?

Русский алфавит:

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

Решение

Выполним формально, по действиям, предложенный алгоритм. Посчитаем в исходной цепочке символов РЕКА количество символов. Получаем 4. Это чётное число. Согласно алгоритму, нужно добавить в начало цепочки символ Г. Получаем цепочку символов ГРЕКА. Заменяем в цепочке каждый символ на следующий по алфавиту:

Г → Д

Р → С

Е → Ё

К → Л

А → Б

Получаем цепочку символов ДСЁЛБ.

Для полученной цепочки ДСЁЛБ ещё раз применим алгоритм.

Посчитаем количество символов в цепочке. Получаем 5. Это нечётное число.

Согласно алгоритму, дублируем средний символ цепочки. Это символ Ё. Получаем цепочку ДСЁЁЛБ. Заменяем в цепочке каждый символ на следующий по алфавиту:

Д → Е

С → Т

Ё → Ж

Ё → Ж

Л → М

Б → В

Получаем цепочку символов ЕТЖЖМВ.

Ответ: ЕТЖЖМВ.

Задача 2. Автомат получает на вход трёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа — сумма старшего и среднего разрядов, а также сумма среднего и младшего разрядов заданного числа.

2. Полученные два числа записываются друг за другом в порядке невозрастания (без разделителей).

Пример. Исходное число: 277.

Поразрядные суммы: 9, 14.

Результат: 149.

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

1616 169 163 1916 1619 316 916 116

В ответе запишите только количество чисел.

Решение

Постараемся понять, что является средой исполнения для данного автомата. По условию автомат получает трёхзначное десятичное число и обрабатывает его цифры-разряды. Из математики известно, что трёхзначное десятичное число — это целое число от 100 до 999. Цифры-разряды этого числа принимают значения от 0 до 9 (за исключением первой цифры, которая не равно нулю, потому что иначе число не будет трёхзначным). Эти цифры в парах складываются. Сумма двух цифр может быть от 0 до 18. Ноль получается при сложении двух нулей, 18 — при сложении двух девяток. Больше 18 сумма получиться не может. То есть, полученные суммы — одно- или двухзначные числа.

Результирующее число алгоритма получается записыванием полученных сумм друг за другом. Из-за этого действия теряется информация о том, что является первой суммой, а что — второй, и где граница между ними.

Хорошо бы ещё чётко понимать, что означает приведённый здесь термин “невозрастающая последовательность”, а именно, что второе число не возрастает над первым, т. е. первое число больше или равно второму.

Кроме приведённых условий следует не забыть проверить ещё одно. По условию при получении двух сумм цифр-разрядов в обоих суммах используется одна и та же — средняя — цифра. Это значит, что нужно не забыть проанализировать полученные два числа-суммы на то, могут ли они быть получены по приведённому алгоритму, т.е. совпадет ли у них одна из цифр-слагаемых. Так, например, число 152 разбивается на части: 15 и 2. Каждое из этих чисел лежит в диапазоне 0..18 и первое больше или равно второму. Однако, оно не будет получено нашим автоматом, потому что наименьшая цифра, которая может участвовать как одно из двух слагаемых для получения числа 15, — это 6 (15 = 6 + 9). А наибольшая цифра, которая может участвовать как одно из двух слагаемых для получения числа 2 — это 2 (2 = 2 + 0). Поэтому приведённое число 152 не является результатом работы автомата.

Теперь анализируем данные по условию числа. Пытаемся разбить их на возможные пары сумм.

1616. Может быть разбито на два числа как 1 616, либо 16 16, либо 161 6. Первый и третий варианты не подходят, так как трёхзначной суммы получиться не должно. Вариант 16 16 не противоречит условию — число 16 лежит в нужном диапазоне (от 0 до 18) и последовательность 16,16 является невозрастающей (16 ≥ 16).

Попробуем получить пример трёхзначного исходного числа: 888. Обе суммы равны 16. Подходит.

169. Может быть разбито на два числа как 1 69, либо 16 9. Первый вариант не подходит, потому что 69 выходит за допустимый диапазон (от 0 до 18). Второй вариант подходит под диапазон и подходит под неубывание (16 ≥ 9). Пример исходного числа: 790 (суммы 7 + 9 = 16 и 9 + 0 = 9). Подходит.

Для удобства составим таблицу анализа оставшихся чисел.

Число	Варианты разбиения на два числа	Попадают ли оба числа в диапазон 0..18	Выполняется ли условие неубывания	Подобрать пример исходного числа	Подходит ли хотя бы один вариант разбиения
163	1 63	0≤1≤18-Да, 0≤63≤18-Нет	16≥3-Да	Невозможно	Нет
	16 3	0≤16≤18-Да, 0≤3≤18-Да
1916	1 916	0≤916≤18-Нет			Нет
	19 16	0≤19≤18-Нет
	191 6	0≤191≤18-Нет
1619	1 619	0≤619≤18-Нет			Нет
	16 19	0≤16≤18-Да, 0≤19≤18-Нет
	161 9	0≤161≤18-Нет
316	3 16	0≤3≤18-Да, 0≤16≤18-Да	3≥16-Нет		Нет
	31 6	0≤31≤18-Нет
916	9 16	0≤9≤18-Да, 0≤16≤18-Да	9≥16-Нет		Нет
	91 6	0≤91≤18-Нет
116	1 16 11 6	(0≤1≤18-Да, 0≤16≤18-Да 0≤11≤18-Да, 0≤6≤18-Да	1≥16-Нет 11≥6-Да	560 (5 + 6 = 11, 6 + 0 = 6)	Да

Среди всех предложенных чисел подошли только первые два (1616 и 169) и последнее (116), всего 3.

Ответ: 3.

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

Задача 3. У исполнителя Делитель две команды, которым присвоены номера:

1. раздели на 2

2. вычти 1

Первая из них уменьшает число на экране в 2 раза, вторая уменьшает его на 1.

Исполнитель работает только с натуральными числами.

Составьте алгоритм получения из числа 65 числа 4, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 12112 — это алгоритм:

раздели на 2

вычти 1

раздели на 2

раздели на 2

вычти 1,

который преобразует число 42 в число 4).

Если таких алгоритмов более одного, то запишите любой из них.

Решение

Будем исходить из того, что в условии нас просят найти самый быстрый алгоритм. Хотя это и не указано в условии явно, фраза “алгоритм, ..., содержащий не более 5 команд” наводит именно на такие размышления. Из этих соображений анализируем возможные команды Делителя и понимаем, что команда номер 1 (раздели на 2) гораздо быстрее уменьшает текущее число, чем вторая команда (вычти 1). Поэтому будем пытаться использовать команду “раздели на 2” в каждом возможном случае. Нетрудно понять, что это произойдёт только в том случае, если текущее число — чётное. При делении нечётного числа на 2 получится нецелое число, а по условию Делитель работает только с натуральными числами. Попытаемся получить требуемое число 4 из числа 65 по принципу: при любой возможности, делить текущее число на 2 (т. е. если текущее число — чётное). Если это невозможно — вычитать 1.

Попробуем обработать по этому принципу исходное число 65.

№ шага алгоритма	Текущее число	Делится ли оно на 2 (чётное ли)?	Выполнение действия	№ команды Делителя
1	65	Нет	65 вычесть 1 = 64	2
2	64	Да	64 разделить на 2 = 32	1
3	32	Да	32 разделить на 2 = 16	1
4	16	Да	16 разделить на 2 = 8	1
5	8	Да	8 разделить на 2 = 4	1

Составляем друг за другом последовательность номеров команд. Ответ: 21111.

Задача 4. У исполнителя Удвоитель две команды, которым присвоены номера:

1. умножь на 2

2. прибавь 1

Первая из них увеличивает число на экране в 2 раза, вторая увеличивает его на 1.

Исполнитель работает только с натуральными числами.

Составьте алгоритм получения из числа 4 числа 42, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 12112 — это алгоритм:

умножь на 2

прибавь 1

умножь на 2

умножь на 2

прибавь 1,

который преобразует число 2 в число 21).

Если таких алгоритмов более одного, то запишите любой из них.

Решение

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

Однако, в данном случае задача обратная — следует выбирать между операцией умножения и операцией сложения. Обе эти операции могут быть произведены над любым натуральным числом. Поэтому нам не удастся, решая задачу подобным же способом, принимать решение о том, какую из команд применять — умножение на 2 или прибавление 1 на основании какого-то свойства числа (чётности?).

Поэтому будем решать задачу в обратную сторону — искать, как можно получить из числа 42 число 4, выполняя обратные команды. Ведь, если число нечётное, то оно не может быть получено командой умножения на 2, следовательно, оно было получено другой командой (прибавь 1).

№ шага алгоритма	Текущее число	Могло ли оно быть получено умножением на 2 (чётное ли оно)?	Выполнение действия	№ команды Делителя
5	42	Да	42 / 2 = 21	1 (21 ∙ 2 = 42)
4	21	Нет	21 - 1 = 20	2 (20 + 1 = 21)
3	20	Да	20 / 2 = 10	1 (10 ∙ 2 = 20)
2	10	Да	10 / 2 = 5	1 (5 = 2 = 10)
1	5	Нет	5 - 1 = 4	2 (4 + 1 = 5)

В последнем столбце таблицы получили обратную последовательность необходимых действий.

Записав номера команд в порядке снизу вверх, получим ответ: 21121.

Задача 5. У исполнителя Удвоитель две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 2

Первая из них увеличивает число на экране на 1, вторая увеличивает его в 2 раза.

Исполнитель работает только с натуральными числами.

Составьте алгоритм получения из числа 5 числа 52, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 21221 — это алгоритм:

умножь на 2

прибавь 1

умножь на 2

умножь на 2

прибавь 1,

который преобразует число 2 в число 21).

Если таких алгоритмов более одного, то запишите любой из них.

Решение

Решим задачу тем же способом, что и в предыдущем примере.

№ шага алгоритма	Текущее число	Могло ли оно быть получено умножением на 2 (чётное ли оно)?	Выполнение действия	№ команды Делителя
5	52	Да	52 / 2 = 26	2 (26 ∙ 2 = 52)
4	26	Да	26 / 2 = 13	2 (13 ∙ 2 = 26)
3	13	Нет	13 - 1 = 12	1 (12 + 1 = 13)
2	12	Да	12 / 2 = 6	2 (6 ∙ 2 = 12)
1	6	Да	6 / 2 = 3	?

Заметим, что предлагаемый алгоритм решения задачи на данном примере даёт сбой на последнем шаге. Если “бездумно” выполнить действие деления для текущего числа 6, то результатом будет число 3, которое никак не может получиться в требуемом алгоритме получения из числа 5 числа 52. Значит, на последнем шаге следует обратить внимание, что от нужного числа 5 нас отделяет только одно действие “вычесть 1” и вместо деления на 2 (обратного команде “2. умножь на 2”) выполнить вычитание единицы (обратного команде “прибавь 1”).

Записываем получившиеся номера команд снизу вверх, поставив самой нижней командой 1: 12122.

Предлагаемый метод решения задачи, когда мы однозначно, за исключением последнего шага, принимаем решение, что при чётном числе было выполнено чётное действие (в информатике такой алгоритм называется жадным алгоритмом), не всегда возможно применять. Но попробовать решить задачу мы вам рекомендуем именно начиная с него. Если ответ не получается, попытайтесь “свернуть в другую сторону” — для чётного текущего числа вместо действия “умножь/подели на 2” выполните другое действие. Возможно, это даст нужный результат.

Задача 6. У исполнителя Удвоитель две команды, которым присвоены номера:

1. прибавь 3

2. умножь на 2

Первая из них увеличивает число на экране на 3, вторая увеличивает его в 2 раза.

Исполнитель работает только с натуральными числами.

Составьте алгоритм получения из числа 14 числа 52, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 21221 — это алгоритм:

умножь на 2

прибавь 3

умножь на 2

умножь на 2

прибавь 3,

который преобразует число 2 в число 31).

Если таких алгоритмов более одного, то запишите любой из них.

Решение

Будем решать эту задачу тем же способом, который предлагается в решении предыдущего примера.

№ шага алгоритма	Текущее число	Могло ли оно быть получено умножением на 2 (чётное ли оно)?	Выполнение действия	№ команды Делителя
5	52	Да	52 / 2 = 26	2 (26 ∙ 2 = 52)
4	26	Да	26 / 2 = 13	?
Мы получили число 13, которое меньше стартового числа 14, которое мы хотели бы получить. Очевидно, этим способом ничего не получится. Вернёмся на шаг назад и выберем для него другую команду
4	26	Да, но выбираем другое	26 - 3 = 23	1 (23 + 3 = 26)
3	23	Нет	23 - 3 = 20	1 (20 + 3 = 23)
2	20 ,	Да	20 / 2 = 10	?
Снова неудача. Снова “откатываемся назад” и выбираем другую команду.
2	20	Да, но выбираем другое	20 - 3 = 17	1 (17 + 3 = 20)
1	17	Нет	17 - 3= 14	1 (14 + 3 = 17)

Записываем номера команд снизу вверх: 11112.

Подобный способ решения задачи называется “перебор с возвратом”. Можно его рассматривать в виде дерева решения, которое строим, последовательно изменяя текущее число и при каждой развилке (чётном текущем числе) двигаясь всегда в одну сторону (выбирая умножение/деление). Если на каком-нибудь шаге оказывается, что мы пришли по этому дереву в тупик (получили невозможное число), откатываемся назад к точке последней развилки и двигаемся далее по ней. Если и она приводит в тупик, возвращаемся к предыдущей развилке. В данном случае дерево решения выглядит следующим образом:

Можно было бы применять такой же метод и напрямую, “в лоб”. То есть, не разворачивать задачу, рассматривая вместо сложения и умножения команды вычитания и деления, а сразу пытаться из исходного числа получить конечное. Такой способ решение будет сложнее и дольше, потому что в нём предположение о развилке придётся делать для каждого получаемого числа. Это серьезно увеличивает возможное дерево рассматриваемых решений.

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

Задача 7. Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (а, b) (где а, b — целые числа), перемещающую Чертёжника из точки с координатами (х, у) в точку с координатами (х + а, у + b). Если числа а, b положительные, значение соответствующей координаты увеличивается; если отрицательные — уменьшается.

Например, если Чертёжник находится в точке с координатами (9, 5), то команда Сместиться на(1, -2) переместит Чертёжника в точку (10, 3).

Запись

Повтори k раз

Команда1 Команда2 Команда3

конец

означает, что последовательность команд Команда1 Команда2 Команда3 повторится k раз.

Чертёжнику был дан для исполнения следующий алгоритм:

Повтори 3 раз

Сместиться на (—2, —3) Сместиться на (3, 2)

Сместиться на (—4, 0)

конец

На какую одну команду можно заменить этот алгоритм, чтобы Чертёжник оказался в той же точке, что и после выполнения алгоритма?

1. Сместиться на (-9,-3)

2. Сместиться на (-3,9)

3. Сместиться на (-3,-1)

4. Сместиться на (9,3)

Решение

Исследуем, на сколько сместится Чертёжник в результате выполнения приведённого алгоритма. Так как нас интересует только смещение Чертёжника относительно начальной позиции и не интересует, в каких именно координатах окажется Чертёжник, для простоты и удобства будем считать, что начальное положение Чертёжника — в точке (0, 0).

Первый метод решения. Простой, но долгий. Выполним друг за другом по порядку все команды алгоритма Чертёжника. В нём три команды повторяются 3 раза. Всего 9 команд. Не слишком долго.

Команда	Вычисление новых координат	Координаты Чертёжника после выполнения команды
Начальное положение	—	(0, 0)
Сместиться на (-2, -3)	0 – 2 = -2, 0 – 3 = -3	(-2, -3)
Сместиться на (3, 2)	-2 + 3 = 1, -3 + 2 = -1	(1,-1)
Сместиться на(-4, 0)	1 - 4 = -3, -1 + 0 = -1	(-3, -1)
Сместиться на (-2, -3)	-3 – 2 = -5, -1 – 3 = -4	(-5, -4)
Сместиться на (3, 2)	-5 + 3 = -2, -4 + 2 = -2	(-2, -2)
Сместиться на (-4, 0)	-2 - 4 = -6, -2 + 0 = -2	(-6, -2)
Сместиться на (-2, -3)	-6 - 2 = -8, -2 - 3 = -5	(-8, -5)
Сместиться на (3, 2)	-8 + 3 = -5, -5 + 2 = -3	(-5, -3)
Сместиться на(-4,0)	-5 - 4 = -9, -3 + 0 = -3	(-9, -3)

Чтобы Чертёжнику вернуться из точки (-9, -3) в исходную точку (0, 0), ему нужно выполнить команду: (0 - (-9), 0 - (-3)) = (9, 3). Ищем такой ответ в списке вариантов ответа.

Ответ: 4.

Второй метод решения

Понимаем, что перемещение Чертёжника по одной координате зависит только от соответствующего Смещения (а или b, в зависимости от координаты), и не зависит от значения другой координаты. Значит, можно рассматривать суммарное смещение Чертёжника в результате выполнения алгоритма по каждой координате отдельно.

Рассматриваем смещение по координате X:

3 раза сместиться на: -2, 3 и на -4. Т. е.:

3 ∙ (-2 + 3 - 4) = 3 ∙ (-3) = -9.

Рассматриваем смещение по координате Y:

3 раза сместиться на: -3, 2 и на 0. Т. е.:

3 ∙ (-3 + 2 + 0) = 3 ∙ (-1) = -3.

Получаем, что в результате алгоритма Чертёжник суммарно сместится на (-9, -3). Чтобы вернуться обратно в исходную точку, Чертёжник должен компенсировать смещение по каждой оси. Т. е. сместиться по каждой оси на противоположное значение.

Получаем, что требуемое смещение: (9, 3).

Ответ: 4.

Задача 8. Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:

Вперёд n (где n — целое число), вызывающая передвижение Черепашки на n шагов в направлении движения.

Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.

Запись

Повтори k раз

Команда1 Команда2 Команда3

конец

означает, что последовательность команд в скобках повторится kраз.

Черепашке был дан для исполнения следующий алгоритм:

Повтори 12 раз

Направо 45 Вперёд 20 Направо 45

конец

Какая фигура появится на экране?

1. Квадрат

2. Правильный двенадцатиугольник

3. Правильный восьмиугольник

4. Незамкнутая ломаная линия

Решение

Способ первый. Выполним по действиям все команды Черепашки. Три команды повторяются 12 раз. Всего 36 команд. Довольно-таки много. Выполним эти команды по очереди. Будем рисовать линию, которую рисует Черепашка и отмечать её текущее положение и направление при помощи жирной точки и выходящей из неё стрелки.

Команда	Положение Черепашки и след, который она за собой оставляет
Исходное положение
Направо 45
Вперёд 20
Направо 45
Направо 45
Вперёд 20
Направо 45
Направо 45
Вперёд 20
Направо 45
Направо 45
Вперёд 20
Направо 45
Направо 45
Вперёд 20

К этому моменту становится ясно, что Черепашка дальше будет продолжать перемещаться по тому же самому пути, который она уже нарисовала и что дальнейшие действия Черепашки ничего не изменят в картинке. Делаем вывод, что фигура, которая появится на экране в результате этого алгоритма — квадрат.

Ответ: 1.

Второй способ решения задачи хорош в том случае, если вы изучали ранее в школе Черепашку (например, Лого Черепашку) и хорошо понимаете “Правило 360 градусов”. То есть, чтобы Черепашка нарисовала правильный N-угольник со стороной Х_у Черепашка должна N раз повторить две команды: Вперёд Х, Направо 360/N. Анализируя алгоритм работы Черепашки в приведённой задаче, обнаруживаем, что Черепашка на каждом шаге делает одно движение Вперёд, и в начале и конце повторяющихся действий поворачивается на 45 градусов. То есть, в каждой точке поворота в сумме получается 45 + 45 градусов. Всего 90 градусов. Значит, Черепашка делает повторяющиеся действия практически эквивалентные командам “Вперёд X, Направо 90”.

Если такие действия сделать хотя бы 4 раза, получится правильный четырёхугольник (360/90 = 4), то есть, квадрат.

Ответ: 1.