Фибоначчиева система счисления
Фибоначчиева система счисления
Рассмотрим последовательность Фибоначчи: F1
= 1, F2
= 1, Fn
= Fn-1
+ Fn-2
при n > 2.
Любое натуральное число можно представить в виде суммы нескольких членов последовательности Фибоначчи. Такое представление будет неоднозначным, но если наложить дополнительное условие, что в представлении нет двух соседних членов последовательности Фибоначчи, то представление становится единственным.
Будем говорить, что A представимо в фибоначчиевой системе счисления в виде akak-1...a2
, где ai
равно 0 или 1, если A = akFk
+ ... + a2F2
и в записи akak-1...a2
нет двух единиц подряд.
Вот как записываются небольшие числа в фибоначчиевой системе счисления:
Дано число n. Найти его представление в фибоначчиевой системе счисления.
Входные данные
Одно целое число n (0 ≤ n ≤ 2 *109
).
Выходные данные
Вывести представление числа n в фибоначчиевой системе счисления без ведущих нулей.
1
1
12
10101