Archives‎ > ‎

Задание 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 про двоичную систе-
му счисления.
Comments