Фибоначиева система счисления
Пример довольно экзотической системы счистления - система основанная на числах Фибоначи. (Кстати она не позиционная, а со смешанным основанием). (Пример смешанного основания: 7 дней 24 часа 60 минут 60 секунд).
Фибоначи
Числа Фибоначи определяются так: F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 (для n > 1) --------------------------------------------------------------- n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Fn 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 --------------------------------------------------------------- Собственно это и есть базис.
Правила для записи чисел: две единицы не могут стоять рядом в соседних разрядов (это правило для канонической формы) (запись начинаем Fn...F1) 0 000000 1 000001 2 000010 3 000100 4 000101 5 001000 6 001001 7 001010 8 010000 9 010001 10 010010 11 010100 12 010101 13 100000 14 100001 15 100010 16 100100 17 100101 18 101000 19 101001 20 101010 Числа Фибоначи можно обобщить и в отрицательную сторону: --------------------------------------------------------------- n 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 Fn 0 1 -1 2 -3 5 -8 13 -21 34 -55 --------------------------------------------------------------- не буду приводить систему счистления для отрицательных чисел Фибоначи Примеры: 37[10] = 34 + 3 = 10000000[Ф] + 100[Ф] = 10000100[Ф] 25[10] = 21 + 3 + 1 = 1000000 [Ф] + 100[Ф] + 1[Ф] = 1000101[Ф] Система имеет избыточность. т.е. одно и то же число можно представить различными способами: 19 = 13 + 5 + 1 19 = 13 + 3 + 2 + 1 Операции для переведения чисел в разные варианты: Свертка 011 -> 100 Развертка 100 -> 011 Минимальная форма числа: Если мы выполним все возможные свертки то получим минимальную форму Максимальная форма числа: Если мы выполним все возможные развертки то получим максимальную форму Пример: 19 = 101001 13 + 5 + 1 *** 100111 13 + 3 + 2 + 1 *** 011111 8 + 5 + 3 + 2 + 1 Прибавление единицы (счетчики): сводится к свертке ------------------------------------------------------------- 0 0000000 1 0000000 + 1 = 0000001 = 0000010 ## 2 0000010 + 1 = 0000011 = 0000100 *** 3 0000100 + 1 = 0000101 = 0000110 = 0001000 ## *** 4 0001000 + 1 = 0001001 = 0001010 ## 5 0001010 + 1 = 0001011 = 0001100 = 0010000 *** *** 6 0010000 + 1 = 0010001 = 0010010 ## 7 0010010 + 1 = 0010011 = 0010100 *** 8 0010100 + 1 = 0010101 = 0010110 = 0011000 = 0100000 ## *** *** ------------------------------------------------------------- Соответсвенно вычитание 1 сводится к развертке Для сравнения двух чисел в фибоначиевой системе надо их сначала привести к минимальной форме. Таблица сложения: F[k] + F[k] = F[k] + F[k-1] + F[k-2] F[k] + F[k] = F[k+1] + F[k+2] 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1.11 Появляются варианты 1 + 1 = 10.01 Для операций сложения числа надо приводить к минимальной форме Таблица вычитания: F[n+k] - F[n] = F[n+k-2] + F[n+k-3] + ... + F[n-1] 0 - 0 = 0 1 - 1 = 0 1 - 0 = 0.11 10 - 1 = 0.1 100 - 1 = 1.1 1000 - 1 = 11.1
Факториальная система счисления
n! = 1 * 2 * ... * (n-1) * n 0! = 1! = 1 n! (n-1)! ... 3! 2! 1! A = An*n! + An-1*(n-1)! + .... + A2*2! + A1* 1! + ... A-1/2! + A-2/3! + ... 0 <= Ai+1 <= i, i=1,2,... A0 не используется
Базис: --------------------- P P! --------------------- 10 3628800 9 362880 8 40320 7 5040 6 720 5 120 4 24 3 6 2 2 1 1 ---------------------
Примеры 3221[ф!] = 3*4! + 2*3! + 2*2! + 1*1! = 89[10] 40301[ф!] = 4*5! + 3*3! + 1*1! = 499[10]