Алгоритм перевода целых чисел из десятичной системы счисления в ФСС

1. Найдем максимальное число F из базиса фибоначчиевой системы, которое не превосходит число А, и зафиксируем его номер k (F = F_k). Искомая запись числа А в фибоначчиевой системе будет содержать k цифр. Сформируем “заготовку” искомого фибоначчиева числа в виде 10...0. (нулей - k -1 штук).

2. Вычислим разность А = А - F,.

3. Если полученное значение А равно 0, переход на п. 7.

4. Найдем максимальное число F из базиса фибоначчиевой системы, которое не превосходит число А, и зафиксируем его номер p (F = Fp).

5. В сформированную заготовку на р -е место поставим 1.

6. Положим k = p. Переход на п. 2.

7. Сформированная “заготовка” является искомым числом в ФСС. Конец алгоритма.

4.2. Избыточность ФСС. Операции свертки и развертки в ФСС

Фибоначчиева система счисления обладает удивительным свойством — свойством избыточности, оказывается, что многие числа в ФСС могут выглядеть по-разному. Например, десятичное число 40 можно записать в ФСС четырьмя разными способами

40₁₀ = 10001001 _fib = 10000111 _fib = 1101001 _fib = 110011 _fib

Различные фибоначчиевы представления одного и того же числа могут быть получены друг из друга с помощью специальных фибоначчиевых операций свертки (011 => 100) и развертки (100 => 011). Эти операции выполняются над фибоначчиевой записью числа и не меняют значения числа.

(По определению, очередное число базиса равно сумме двух предыдущих.)

Замечание 1. Операция свертки уменьшает количество единиц в фибоначчиевой записи числа, но может увеличить на единицу количество цифр в записи, если исходная запись начиналась с двух единиц. Например, 11 0101 = 100 0101.

Замечание 2. Операция развертки увеличивает количество единиц в фибоначчиевой записи числа, но может уменьшить на единицу количество цифр в записи, если исходная запись начиналась с комбинации “100”. Например, 100 0101 = 11 0101.

Если над записью числа в ФСС выполнить все возможные свертки, то мы придем к специальному фибоначчиевому представлению числа, называемому минимальной формой, в которой нет двух рядом стоящих единиц. Если же в фибоначчиевой записи выполнить все возможные операции развертки, то придем к специальному фибоначчиевому изображению, называемому максимальной, или развернутой, формой, в которой рядом не встречается двух нулей. Любое число А представляется в минимальной или максимальной форме единственным способом.