БУМАЖНЫй НОМЕР 

 

Жизнь среди ветвей и рекурсий

01.10.2001
Евгений Скляревский

 

Несчастный мистер Бэггинс был не большой мастак лазать по деревьям, но делать нечего - его посадили на нижние ветки исполинского дуба, росшего на обочине, и хочешь не хочешь, а пришлось карабкаться вверх. Бильбо продирался сквозь густые сучья, ветки хлопали его по лицу, кололи глаза.
Дж. Р. Р. Толкиен. «Хоббит, или Туда и обратно»

Если ученые продолжают настаивать на нашем происхождении от мартышек, то имеет право на озвучивание и такой тезис: «Наблюдение веток на деревьях во время лазания по ним и размышление об их количестве, толщине, направленности и фрактальном рисунке дало толчок развитию разума». Продолжим этот процесс - понаблюдаем за несколькими близкими ветками.

Ветка первая. Великий Леонардо и волны на бирже

Представьте: ствол дерева пускает новую ветвь, на следующий год он «отдыхает» и только через год пускает еще одну. Так же ведет себя и каждая ветвь. Поэтому сначала имеется только главный ствол, на следующий год - две ветви, еще год спустя - три, потом 5, 8, 13. Полученная последовательность чисел, известная как ряд Фибоначчи, занимает важное место в математике, так как проявляется в самых неожиданных ее приложениях. Строгое определение этого ряда звучит так: каждое число ряда, начиная со второго, равно сумме двух предыдущих.

Леонардо Фибоначчи из Пизы первым познакомил европейцев с арабскими цифрами и десятичной системой, о которых он узнал, учась в Алжире. До него европейцы использовали неуклюжую и громоздкую римскую систему, тормозящую развитие математики. Подробнее о Фибоначчи и приложениях его работ читайте на www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibBio.html. Заслуги Леонардо Фибоначчи высоко оценены итальянцами: ему поставили памятник недалеко от знаменитой падающей башни. Но самым главным памятником средневековому математику служит названная его именем числовая последовательность. В последнее время числа Фибоначчи известны не только любителям математики, но и бизнесменам, экономистам и биржевым игрокам. Замечено, что волны Эллиота, описывающие колебания котировок ценных бумаг, являются огибающими маленьких волн, те, в свою очередь, еще более мелких, а количество мелких колебаний в периоде более крупного соответствует ряду Фибоначчи. Если вы разберетесь с числами Фибоначчи и волнами Эллиота, то можете разбогатеть, играя на бирже ценных бумаг. Заинтересовавшимся рекомендуем сайт компании Elliott Wave International. (Если у вас плохо с английским, зайдите на user.cityline.ru/~esfinkro, там есть доступно изложенная статья о волнах Эллиота.)

По иронии судьбы Леонардо Фибоначчи, внесший существенный вклад в развитие математики, в наши дни известен потому, что его именем названа последовательность, возникающая в совершенно тривиальной задаче. Вот эта задача в том виде, в каком ее сформулировал сам Фибоначчи.

«Пара кроликов через месяц производит на свет другую пару, а потомство они дают со второго месяца после рождения. Итак, через месяц будет две пары, через два месяца - три пары, а через четыре месяца - пять, так как к паре, рожденной первой парой, добавятся первые дети от второй пары…». Продолжая процесс (конечно, лучше карандашом на бумаге), мы и получим количество пар кроликов по месяцам: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… - эти числа и представляют собой ряд, названный по имени автора задачи.

Числа Фибоначчи привлекли математиков своей особенностью возникать в самых неожиданных местах. Замечено, например, что отношения чисел Фибоначчи, взятых через одно, соответствуют углу между соседними листьями на стебле растений, точнее, они говорят, какую долю оборота составляет этот угол: 1/2 - для вяза и липы, 1/3 - для бука, 2/5 - для дуба и яблони, 3/8 - для тополя и розы, 5/13 - для ивы и миндаля и т. д. Эти же числа вы найдете при подсчете семян в спиралях подсолнуха, в количестве лучей, отражающихся от двух зеркал, в количестве вариантов маршрутов переползания пчелы от одной соты к другой, во многих математических играх и фокусах.

Самое замечательное свойство ряда Фибоначчи состоит в том, что отношение двух последовательных членов ряда попеременно то больше, то меньше отношения золотого сечения и с возрастанием номера члена ряда разность между его отношением к предыдущему члену и отношением золотого сечения стремится к нулю. (О золотом сечении мы как-нибудь поговорим подробно.)

Еще несколько интересных свойств чисел Фибоначчи.

  1. Квадрат любого числа Fn на единицу отличается от произведения Fn-1*Fn+1. Знак разности Fn2 - Fn-1 *Fn+1 при переходе от n к n+1 изменяется на противоположный.
  2. Для любых четырех последовательных членов ряда Фибоначчи A, B, C и D справедливо соотношение C2-B2=A*D.
  3. Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом 60. Если от каждого числа брать по две последние цифры, то они образуют последовательность с периодом, равным 300.
  4. Каждое третье число Фибоначчи делится на 2, каждое четвертое - на 3, каждое пятое - на 5, каждое шестое - на 8 и т. д., делители сами образуют ряд Фибоначчи.
  5. За исключением F4=3 всякое простое число Фибоначчи имеет простой номер (например, число F13=233 простое, и номер его - тоже простое число). К сожалению, обратное утверждение справедливо не всегда: простой номер отнюдь не означает, что соответствующее число Фибоначчи будет простым. Первым контрпримером служит F19=4181= =37Ч113.
  6. Единственными квадратами среди чисел Фибоначчи являются F1=F2=1 и F12=144.

Рассмотрим эти числа как идеальный полигон для знакомства с рекурсией.

Ветка вторая. Космическая частица и рекурсия

Сначала поясним, что такое рекурсия. Почти во всех языках программирования можно задать функцию (подпрограмму с параметром) и при необходимости вызывать ее. Если функция в процессе выполнения вызывает сама себя, то такой прием называется рекурсией.

Тут мы предлагаем читателям задуматься: что значит «функция вызывает сама себя»? Хорошей моделью, на наш взгляд, служит известный стишок «Дом, который построил Джек», а еще лучшей - пародия на него команды КВН Физтеха («КВН раскрывает секреты». - М.: Молодая гвардия, 1967).

Вот стенд, который построил студент,
А вот космическая частица,
Которая с бешеной скоростью мчится
В стенде, который построил студент.
А вот инженер молодой, бледнолицый,
Который клянет и судьбу и частицу,
Которая с бешеной скоростью мчится
В стенде, который построил студент.
А вот кандидат, горделивый не в меру,
Который блистательно сделал карьеру,
Совместно работая с тем инженером,
Который клянет и судьбу и частицу,
Которая с бешеной скоростью мчится
В стенде, который построил студент.
А вот начальник, на вид простоватый,
Который был шефом того кандидата,
Который блистательно сделал карьеру,
Совместно работая с тем инженером,
Который клянет и судьбу и частицу,
Которая с бешеной скоростью мчится
В стенде, который построил студент.
А вот консультант от академии,
С которым встречался время от времени
Тот самый начальник, на вид простоватый,
Который был шефом того кандидата,
Который блистательно сделал карьеру,
Совместно работая с тем инженером,
Который клянет и судьбу и частицу,
Которая с бешеной скоростью мчится
В стенде, который построил студент.
А вот отчетов горы бумажные,
В которых копалась комиссия важная,
Которая выдала крупную премию,
Тому консультанту из академии,
Начальнику дали за вид простоватый,
Кусок уделили тому кандидату,
Который блистательно сделал карьеру,
Остатки вручили тому инженеру,
Который уже не ругает частицу,
Которая с бешеной скоростью мчится
В стенде, который построил СТУДЕНТ.

Теперь, надеемся, всем ясно, что такое рекурсия, позволяющая писать компактные программы. (Представьте, как сократится стишок, если вместо повторов вызывать предыдущие строки с последующим углублением.) Приведем текст программы, выводящей на экран номер и значение числа Фибоначчи, вычисляемого функцией Fib. Причем сама функция Fib, кроме заданных первого и второго чисел, обращается сама к себе, чтобы сложить два предыдущих значения ряда.

program m; {Числа Фибоначчи}
VAR I : INTEGER ;
FUNCTION FIB (T:INTEGER): INTEGER ;
begin
IF (T=1) OR (T=2) THEN Fib:=1
ELSE Fib:=FIB(T-1)+FIB(T-2)
end;
BEGIN
FOR I:=1 TO 10 DO
WRITELN(I,’ ‘,FIB(I));
END.

Проследим, например, как вычисляется пятый член ряда Фибоначчи. Для него значение функции должно равняться сумме четвертого и третьего членов. При вычислении четвертого члена функция обратиться к третьему и второму, при вычислении третьего - ко второму и первому, которые равны единице. Подобное «погружение» произойдет и при вычислении третьего члена как слагаемого четвертого. То есть мы видим, что такое применение рекурсии на редкость неэффективно: мы заставляем программу совершать множество «движений», количество которых лавинообразно растет с ростом номера числа в ряду. Вся красота и изящность компактного написания программы свелась на нет, поскольку пошла во вред производительности. А как же надо было составить программу, чтобы работа была эффективной? Задать массив и заполнять его такой же функцией, но без рекурсии, обращаясь к уже посчитанным членам ряда, помещенным в массив. Программа будет работать «мгновенно», но окажется не такой красивой. Как говорит Жванецкий, процесс важнее результата…

Ветка третья. L-системы L-деревьев

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

Это так называемые L-системы. В основе их построения лежат два принципа. Первый - так называемая «черепашья графика» (оператор draw(x,y), когда движение рисуется пошагово в приращениях относительно текущей точки. В «солидных» языках этого оператора нет, но его легко смоделировать, задавая движение в приращениях координат). Второй принцип - изюминка метода: каждое единичное движение заменяется на весь рисунок. Например, нарисуем вилку-рогатульку. На следующем шаге работы программы каждая из трех палочек вилки заменяется такой же вилкой, превращая первую вилку в ветку с сучками, на следующем шаге получим лохматый куст, потом пушистое дерево, красивое, фрактальное. На рисунках ниже вы видите деревья, полученные после двух, и трех шагов.

 

1

2

 

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

3

Лучшей отправной точкой для путешествия в мир L-систем является страничка Fantastic Fractals. На ней можно найти алгоритмы построения деревьев разных видов с иллюстрациями.

Конечно, прорисовывать каждый шаг заменой текста программы довольно утомительно, поэтому снова вспоминаем о рекурсии. Любое дерево рисуется по заданной формуле одной маленькой процедуркой, которая сама себя и вызывает (авторы написали программу на Visual Basic’e и готовы выслать ее всем желающим. Эта программа рисует ветку, клонимую ветром. Меняя переменную глубину рекурсии можно уменьшать или увеличивать «пушистость» ветки).

А меняя закон движения можно получать самые удивительные и фантастические изображения.

 

4

5

6

 

Ветка четвертая. Речка

Желающих получить больше информации об этих удивительных деревьях приглашаем посетить «Речку», текущую по самым «живописным местам» занимательного программирования - фракталам, паутине и, конечно, L-деревьям. Там вы найдете алгоритм построения объемного дерева с возможностью просмотра его стереоизображения и рассуждения о толщине веток. Со ссылкой на самого Леонардо да Винчи «Речка» предполагает, что суммарная площадь сечения всех веток и ствола на любой высоте постоянна, поэтому видимая ширина ствола и веток уменьшается пропорционально квадратному корню из числа веток. Не правда ли, красивая идея? Можно воплотить ее при рисовании L-деревьев, как это сделали авторы «Речки». А можно попытаться раскрасить деревья, сделав, например, красный цвет зависящим от счетчика цикла i(k), и получить куст, у которого все левые сучки красного цвета. Включите фантазию - и дерзайте!

7