Задание 5 "Черепахи"
Черепахи в этой задаче двигаются по прямой или по плоскости.
Начальное положение - точка O, начальное направление тоже зада-
но, для измерения расстояния есть единица длины. При таких до-
говоренностях прямая становится числовой прямой, а на плоскости
оказывается введена полярная система координат и имеется соот-
ветствующая ей декартова. Для знатоков заметим, что плоскость -
это комплексная прямая (размерность над полем комплексных чисел
равна 1).
Черепаха управляется с помощью программы. Кроме программы
должны быть даны начальный шаг черепахи и правило изменения ша-
га. Нас будет интересовать вопрос, в какую точку придет черепа-
ха.
Программа представляет собой слово, конечное или, может
быть, бесконечное вправо, в котором на каком-то месте стоит
точка, а остальные буквы берутся из некоторого алфавита. Если
слово конечное и кончается точкой, то точку можно не писать.
Слово мы будем давать в этом тексте в угловых скобках. Алфавит,
если в задаче не оговорено иное, состоит из двух цифр 0 и 1.
Бортовой компьютер черепахи находит в программе точку и де-
лит программу на две части, первая часть до точки, а вторая -
начиная с точки, и сначала для определенности выполняет первую
часть, а потом - вторую.
При выполнении первой части, если она есть, компьютер считы-
вает данные о начальном шаге и передает их черепахе. После это-
го он смотрит на первый знак справа.
Далее повторяется следующее.
Если рассматриваемый знак 0, то компьютер дает черепахе ко-
манду "ничего не делать", а если 1, то дает команду "сделать
шаг". После этого компьютер меняет черепахе шаг согласно прави-
лу изменения шага и переходит к следующему знаку налево, если
он есть.
При выполнении второй части, если она есть, компьютер считы-
вает данные о начальном шаге и передает их черепахе. После это-
го он смотрит на первый знак после точки.
Далее повторяется следующее. Компьютер меняет черепахе шаг
согласно правилу изменения шага. Если рассматриваемый знак 0,
то компьютер дает черепахе команду "ничего не делать", а если
1, то дает команду "сделать шаг". После этого компьютер перехо-
дит к следующему знаку направо, если он есть.
Правило изменения шага условимся давать для случая перехода
к знаку направо, в случае перехода к знаку налево действуют об-
ратные указания.
====================== Черепаха на прямой =====================
начальный шаг 1, правило изменения шага - умножить на 1/2
===============================================================
Пример: программа < 10110111 >
Согласно договоренностям, эта программа записывается с точкой
так: < 10110111. >, правило изменения шага при переходе к знаку
налево - умножить шаг на 2. Черепаха придет в точку
1+1*2^1+1*2^2+0*2^3+1*2^4+1*2^5+0*2^6+1*2^7 = 183
Пример: программа < 101.01 >
Черепаха придет в точку
(1+0*2^1+1*2^2) + (0*1/2+1*1/2^2) = 5+1/4 = 5.25
Пример: программа < .11111... >
Здесь 1 после точки периодически повторяется. Условимся период
показывать в круглых скобках. Тогда нашу программу можно запи-
сать так: < .(1) >. Черепаха после выполнения команды, которую
дал компьютер, прочитав n-ый знак, нажодится в точке
1/2+1/2^2+...+1/2^n = 1-1/2^n
Эта точка стремится к точке 1 при n, стремящемся к бесконечнос-
ти. Если черепаха двигается со скоростью 1 м/сек, то в точке 1
она окажется через 1 сек после начала движения.
Покажем, как можно найти точку, в которую придет черепаха, дру-
гим способом.
Если после выполнения программы < .(1) > черепаха оказывается в
точке x (сделав шаги длиной 1/2, 1/2^2, 1/2^3, ...), то после
выполнения программы < .0(1) > она оказывается в точке x/2, так
как сделает шаги в 2 раза меньшей длины. С другой стороны,
путь, проходимый по программе < .(1) >, равен сумме пути, про-
ходимого по программе < .1 >, и пути, проходимого по программе
< .0(1) >:
.1
.01111...
---------
.11111...
Отсюда мы получаем уравнение
x = 1/2 + x/2
из которого находим x=1.
Пример: программа < .(10) >
Коротко: так как
< .(10) > = < .10 > + < .00(10) >,
то черепаха, двигаясь по этой программе, придет в точку x, яв-
ляющуюся решением уравнения
x = 1/2 + x/4,
откуда x=2/3.
Пример: программа < .1(10) >
Коротко:
пусть черепаха по этой программе придет в точку x=< .1(10) >,
тогда двигаясь по программе < 1.(10) > (точку в записи слова
передвинули вправо на 1 -- на чем это сказалось?) она придет в
точку
2x = < 1.(10) > = < 1. > + < .(10) > = 1 + 2/3 = 5/3,
откуда x=5/6.
5.1. Найдите слово-программу, переводящую черепаху в точку 100.
5.2. Найдите программу, переводящую черепаху в точку 25/8.
5.3. Найдите программу, переводящую черепаху в точку 1/3.
5.4. Найдите программу, переводящую черепаху в точку 1/6.
5.5. Напишите программу на знакомом Вам языке программирования,
которая по целому положительному x дает слово-программу для че-
репахи, по которой она попадает в точку x.
5.6. Напишите программу на знакомом Вам языке программирования,
которая по x из интервала от 0 до 1 (рациональному или вещес-
твенному) дает слово-программу для черепахи, по которой она по-
падает в точку x.
==================== Черепаха на плоскости ====================
начальный шаг 1
правило изменения шага: умножить на r
и сделать поворот налево на alpha
программа < 1.(1) >
След черепахи при движении по такой программе
и с таким правилом изменения шага
называется логарифмической спиралью
===============================================================
Пример: r=1/sqrt{2}, alpha=45 градусов.
Рассмотрим квадрат с вершинами (0,0), (2,0), (2,2), (0,2). В
него "вписан" квадрат с вершинами (1,0), (2,1), (1,2), (0,1), в
него вписан следующий квадрат и так далее.
Черепаха из точки O(0,0) доходит до середины стороны первого
квадрата, потом двигается до середины стороны вписанного в него
второго квадрата и так далее. В итоге она приходит в точку
(1,1) -- центр первого квадрата.
Следующая задача относится к рассматриваемому примеру, но ее
стоит делать не обращаясь к рисунку с квадратом, о котором сей-
час было рассказано.
5.7. Докажите, что если черепаха находится в точке (x,y), то
после следующего шага она будет в точке с координатами
x' = 1 + (x-y)/2,
y' = (x+y)/2.
5.8. Попробуйте найти объяснение тому, что черепаха движется в
точку, координаты которой являются решениями системы
1+(x-y)/2 = x,
(x+y)/2 = y.
5.9. Пусть r=1/2, alpha=60 градусов. В какую точку придет чере-
паха?
Указание. Вместо квадрата нужно рассмотреть правильный тре-
угольник.
5.10. "Золотое сечение". Пусть alpha=90 градусов, след черепахи
-- ломаная OABC..., точки O и C - противоположные вершины квад-
рата. Найдите r.
5.11. Докажите (задача 5.10), что точка, в которую приходит че-
репаха, - это точка пересечения отрезков OB и AC.
5.12. Опишите движение черепахи в случае r=1 и alpha=45 граду-
сов.
5.13. Опишите движение черепахи в случае r=1 и alpha=360/5=72
градуса.
Движение в этом случае будет периодическим с периодом 5. Поэто-
му сумма x-координат пяти последовательных шагов черепахи будет
равна 0.
5.14. Получите исходя из этого равенство
cos (72 градусов) - cos (36 градусов) = -1/2,
а из него - квадратное уравнение для cos(36 градусов), решив
которое найдите выражение cos(36 градусов) через радикалы
(квадратные корни).
========================= 360 черепах =========================
с номерами n = 0, 1, 2, ..., 359 градусов
начальный шаг 1
правило изменения шага для n-ой черепахи:
умножить на r=1/2 и сделать поворот налево на n градусов
===============================================================
5.15. 360 черепах двигаются в соответствии с описанным выше
правилом по программе < .(1) >. Докажите, что точки T_n (n = 0,
1, 2, ..., 359), в которые эти черепахи придут, расположены на
окружности, опирающейся на отрезок с концами T_0 и T_{180} как
на диаметр.
5.16. Что изменится, если программа будет такой: < 1.(1) > ?
5.17. Нарисуйте на одном чертеже кривые, на которых расположат-
ся черепахи после выполнения программ движения < .1 >, < .01 >,
< .11 >, < .001 >, < .011 >, < .101 >, < .111 >, < .0001 >,
< .0011 >, ....
5.18. Назовем точку P плоскости достижимой, если можно указать
угол alpha (не обязательно выражающийся целым числом градусов)
и программу движения черепахи, начинающуюся с точки, при движе-
нии по которой черепаха попадает в точку P. Здесь у нас r=1/2.
Какие точки достижимые и какие заведомо недостижимые?
========================= 360 черепах =========================
с номерами n = 0, 1, 2, ..., 359 градусов
начальный шаг 1
правило изменения шага для n-ой черепахи:
(умножить на r=1 и) сделать поворот налево на n градусов
===============================================================
5.19. Нарисуйте кривые, на которых расположатся черепахи после
выполнения программ движения
а) < 1.1 >; б) < 1.11 >; в) < 1.111 >; г) < 1.1111 >.
Что общего у них?
5.20. Назовем точку P плоскости достижимой, если можно указать
угол alpha (не обязательно выражающийся целым числом градусов)
и программу движения черепахи, начинающуюся с 1 и потом точки,
при движении по которой черепаха попадает в точку P. Здесь у
нас r=1. Какие точки достижимые и какие заведомо недостижимые?
О задачах
Задачи про черепаху - это задачи на двоичную систему счисле-
ния, суммирование геометрических прогрессий и комплексные чис-
ла. Система счисления и соответственно правило изменения шага
могут быть взяты другие. Рядом находится изучение фракталов.
Полезное чтение:
1. Алгоритмика. 5-7 классы: Учебник и задачник для общеобразо-
ват. учеб. заведений / А.К.Звонкин, А.Г.Кулаков, С.К.Ландо,
А.Л.Семенов, А.Х.Шень. - М.: Дрофа, 1998 (и др. издания).
В частности, стоит обратить внимание на исполнители Удво-
итель и Раздвоитель и посмотреть все, что покажется близким.
2. Кушниренко А.Г. и др. Основы информатики и вычислительной
техники. - М.: Просвещение, 1991 (и др. издания).
По этой книге стоит учить программирование, при этом исполь-
зуя среду КуМир < http://www.infomir.ru > с ее многочисленным
набором исполнителей, среди которых имеются дающие богатые воз-
можности для математических экспериментов исполнители "Чертеж-
ник" и "Комплексные числа". В этом учебнике стоит разобрать
все, что относится к математике и программированию для матема-
тики. В частности (это не первое по важности), можно увидеть,
что написано про кодирование алгоритмов управления исполнителя-
ми.
Центральные задачи 5.15 и 5.16 происходят из лекций Э.Э.Шно-
ля "О решении уравнений", опубликованных в VIII выпуске сборни-
ка "Математическая школа" (изд-во МГУ, 1966). Процитирую:
"Из некоторой точки A_0 на плоскости отложен отрезок длины 1
вдоль оси OX, затем из его конца A_1 - отрезок A_1A_2 длины 1/2
под углом alpha к первому, затем A_2A_3 длины 1/4 под углом
alpha ко второму и т.д. Доказать, а) что последовательность то-
чек A_0, A_1, ... стремится к некоторой точке C_{alpha}, *б)
что при изменении угла alpha от 0 до 360 градусов точка
C_{alpha} описывает окружность. Указание. Использовать комплек-
сные числа."
В этом цикле задачи для 6-7 классов тоже можно найти, это
задачи 5.12 и 5.13, где нужно просто найти правильные слова для
описания движения, а также задачи 5.1 и 5.2 про двоичную систе-
му счисления.
(С) С.И.Соболев, 1999-2002