<img src="https://habrastorage.org/getpro/habr/upload_files/2c8/2c0/4c9/2c82c04c94300716bfdd64042ee1b805.png" /><p>Структуру, о которой ниже пойдёт речь, знали в древней Индии за тысячу лет до самого Фибоначчи и переоткрыли в 1988 году двое математиков, при этом весь граф целиком строится из строк, состоящих только из цифр 1 и 2, или если мы вычтем единицу, то получим 0/1 и бинарный вид.</p><p>Берём любую конечную строку из цифр 1 и 2, например такую "11212" и складываем цифры 1 + 1 + 2 + 1 + 2 = 7 и получаем ранг этой строки. Теперь простой вопрос: сколько существует строк заданного ранга? Строку такого же ранга можно получить двумя способами, либо дописав цифру 2 к строке ранга r-2, либо дописав цифру 1 к строке ранга r-1, и других вариантов нет, потому что других цифр в нашем алфавите из единиц и двоек нет.</p><p>ранг 0: “” → 1 <br>ранг 1: 1 → 1 <br>ранг 2: 11, 2 → 2 <br>ранг 3: 111, 12, 21 → 3 <br>ранг 4: 1111, 112, 121, 211, 22 → 5 <br>ранг 5: … → 8</p><p>Заметили справа подозрительное 1, 1, 2, 3, 5, 8? Да... это последовательность Фибоначчи f® = f(r-1) + f(r-2), с небольшим условием, что f(0) = 1 (пустая строка) и f(1) = 1 (единственная строка “1”), из-за этого вся последовательность сдвинута на одну позицию относительно канонических чисел Фибоначчи, и f® = F(r+1).</p><p>То же самое делали индийские стиховеды, с своих стихах, где короткий слог занимает одну единицу длительности, длинный две, что позволяло красиво бить ритм и получать благозвучные конструкции в тексте, так что числа Фибоначчи в этом контексте старше самого Фибоначчи. Интересно что связывает стихи, Фибоначчи и дерево технологий в играх? Го под кат...</p> <a href="https://habr.com/ru/articles/1076886/?utm_source=habrahabr&utm_medium=rss&utm_campaign=1076886#habracut">Читать далее</a>