Операция выполнена!
Закрыть
info@vsetut.pro
Стать автором
Вернуться

Фибоначь врагов

31.08.2026 20:37:02 | Хабр
Хабы: Разработка игр, Игры и игровые консоли, Программирование

Структуру, о которой ниже пойдёт речь, знали в древней Индии за тысячу лет до самого Фибоначчи и переоткрыли в 1988 году двое математиков, при этом весь граф целиком строится из строк, состоящих только из цифр 1 и 2, или если мы вычтем единицу, то получим 0/1 и бинарный вид.

Берём любую конечную строку из цифр 1 и 2, например такую "11212" и складываем цифры 1 + 1 + 2 + 1 + 2 = 7 и получаем ранг этой строки. Теперь простой вопрос: сколько существует строк заданного ранга? Строку такого же ранга можно получить двумя способами, либо дописав цифру 2 к строке ранга r-2, либо дописав цифру 1 к строке ранга r-1, и других вариантов нет, потому что других цифр в нашем алфавите из единиц и двоек нет.

ранг 0: “” → 1
ранг 1: 1 → 1
ранг 2: 11, 2 → 2
ранг 3: 111, 12, 21 → 3
ранг 4: 1111, 112, 121, 211, 22 → 5
ранг 5: … → 8

Заметили справа подозрительное 1, 1, 2, 3, 5, 8? Да... это последовательность Фибоначчи f® = f(r-1) + f(r-2), с небольшим условием, что f(0) = 1 (пустая строка) и f(1) = 1 (единственная строка “1”), из-за этого вся последовательность сдвинута на одну позицию относительно канонических чисел Фибоначчи, и f® = F(r+1).

То же самое делали индийские стиховеды, с своих стихах - короткий слог занимает одну единицу длительности, длинный две, что позволяло красиво бить ритм и получать благозвучные конструкции в тексте, так что числа Фибоначчи в этом контексте старше самого Фибоначчи. Интересно что связывает стихи, Фибоначчи и дерево технологий в играх? Го под кат...

Читать далее
Подробнее
Читайте также
НОВОСТИ

ВСЕ НОВОСТИ
ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro

Copyright © 2026 - vsetut.pro