Алгоритм перевода целых чисел из фибоначчиевой системы счисления в десятичную

1. Напишем над каждой цифрой в фибоначчиевой записи числа, начиная с младшей цифры, вес соответствующего разряда.

2. Сложим все числа, стоящие над единицами. Полученное число будет десятичным эквивалентом фибоначчиева числа.

 

Пример 2.Решим обратную задачу. Запишем в фибоначчиевой системе счисления десятичные числа 10₁₀, 25₁₀ и 100₁₀.

Для решения нашей задачи достаточно подобрать такие числа Фибоначчи, сумма которых равна исходному десятичному числу. Например, число 10 можно представить суммой следующих чисел Фибоначчи: 10₁₀ = 5 + 3 + 2. Это позволяет записать нам 10₁₀ в виде 1110 (выполнили разложение по базису).

Однако это же число 10₁₀ можно записать в фибоначчиевой системе счисления и по-другому:

10₁₀ = 10010_fib = 1*8 + 0*5 + 0*3 + 1*2 + 0*1.

Аналогично, число 25₁₀ можно также записать несколькими способами:

25₁₀ = 1000101_fib = 110101_fib.

Число 100₁₀ можно записать как минимум шестью способами:

100₁₀ = 1000010011_fib = 1000010100_fib = 110010011_fib = 110010100_fib = 101110011_fib = 101110100_fib.