WikiSort.ru - Не сортированное

В математике негафибоначчиева система счисления — универсальный код, который кодирует ненулевые целые числа в двоичные кодовые слова. Обобщает фибоначчиеву систему счисления на все ненулевые целые числа (а не только натуральные). Все коды заканчиваются "11" и не имеют "11" в середине или начале слова. Коды для целых чисел от -11 до 11 приведены ниже.

xx  негафибоначчиево представление негафибоначчиев код
-11 101000                         0001011
-10 101001                         1001011
-9  100010                         0100011
-8  100000                         0000011
-7  100001                         1000011
-6  100100                         0010011
-5  100101                         1010011
-4  1010                           01011
-3  1000                           00011
-2  1001                           10011
-1  10                             011
 0  0                              (не кодируется)
 1  1                              11
 2  100                            0011
 3  101                            1011
 4  10010                          010011
 5  10000                          000011
 6  10001                          100011
 7  10100                          001011
 8  10101                          101011
 9  1001010                        01010011
 10 1001000                        00010011
 11 1001001                        10010011

Код Фибоначчи тесно связан с негафибоначчиевым представлением, иногда используемой математиками позиционной системой счисления. Код негафибоначчи для каждого ненулевого целого числа — это в точности его негафибоначчиево представление (представление через числа Фибоначчи с отрицательными номерами) с обратным порядком цифр и дополнительной единицей в конце. Все отрицательные числа имеют нечетное количество разрядов, все положительные — четное.

Для кодирования ненулевого целого числа X следует:

1. Рассчитать количество необходимых разрядов N путём суммирования нечетных (или четных) чисел негафибоначчи с номерами от 1 до N.
2. После нахождения N — количества битов для кодирования X — вычесть N-е число негафибоначчи из X, запомнить получившуюся разность и поставить единицу на место N-го разряда искомого кодового слова.
3. Спускаясь от N-го бита до первого, сравнивать каждое соответствующее число негафибоначчи с получившейся разностью. Вычитать его из разности, если модуль новой разности будет меньше, и, кроме того, предыдущий старший разряд не единица. Рассматривать новую разность и т.д. В соответствующий разряд ставится единица, если вычитание осуществлялось, и ноль в противном случае.
4. На N+1-е место помещается единица, чтобы закончить кодирование и показать, что бит, чтобы закончить.

Для декодирования следует удалить последнюю единицу, остальным битам присвоить значения 1, -1, 2, -3, 5, -8, 13... (числа негафибоначчи), и сложить значения в ненулевых разрядах.

См. также

• Фибоначчиева система счисления
• Теорема Цекендорфа
  

Ссылки

• Knuth, Donald (2008), Negafibonacci Numbers and the Hyperbolic Plane, Paper presented at the annual meeting of the Mathematical Association of America, San Jose, California .
• Knuth, Donald (2009), The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams, ISBN 0-321-58050-8 . In the pre-publication draft of section 7.1.3 see in particular pp. 36–39.
• Margenstern, Maurice (2008), Cellular Automata in Hyperbolic Spaces, vol. 2, Advances in unconventional computing and cellular automata, Archives contemporaines, с. 79, ISBN 9782914610834, <https://books.google.com/books?id=eEgvfic3A4kC&pg=PA79> .