Непозиционные и смешанные системы счислений

                                 Непозиционные и смешанные системы счисления.

Система счисления — символический метод записи , представление чисел с помощью письменных знаков. Системы счисления подразделяются на позиционные и непозиционные.

В непозиционных системах счисления величина, которую обозначает цифра, не зависит от положения в  числе. При этом система может  накладывать ограничения на положение  цифр, например, чтобы они были расположены  в порядке убывания.

Унарная система  счисления

Уна́рная (единичная, разная) система счисления — положительная суммарная целочисленная система счисления с основанием, равным 1. В качестве единственной «цифры» используется «1»Запись числа здесь выглядит следующим образом: ||||||||| – это 9. Унарную систему принято считать позиционной, хотя на самом деле она таковой не является.

Фибоначчиевая система счисления

числа Фибона́ччи — элементы числовой последовательности, где каждое следующее число образуется суммой двух перед ним стоящих чисел (кроме первых двух)

 

x=∑k=0nfkFk, где Fk — числа Фибоначчи, fk∈{0,1}, при этом в записи fnfn−1…f0 не встречается две единицы подряд. Вот эти числа: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …

Эта смешанная система  счисления для целых чисел  основывается на числах Фибоначчи:

• F₂= 0+1 = 1,
• F₃= 1+1 = 2,
• F₄= 1+2 = 3,
• F₅= 2+3 = 5,
• F₆= 3+5 = 8 и т.д.

 

 

Нега-позиционная система счисления.

Не́га-позицио́нная система счисления — это позиционная система счисления с отрицательным основанием.

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

• 174_-10 = 1*(-10)² + 7*(-10)¹ + 4*(-10)⁰ = 1*100 + 7*(-10) + 4 = 100 – 70 + 4 = 34₁₀  (здесь в числе 174 всего 3 знака, поэтому заранее можно было сказать, что число положительное!) 
• 46_-10 = 4*(-10)¹ + 6*(-10)⁰ = 4*(-10) + 6 = -40 + 6 = -34₁₀  (здесь в числе 46 всего 2 знака, поэтому заранее можно было сказать, что число отрицательное!) 
• 11001_-2 = 1*(-2)⁴ + 1*(-2)³ + 1*(-2)⁰ = 16 – 8 +1 = 9₁₀ (здесь в числе 11001 всего 5 знаков, поэтому заранее можно было сказать, что число положительное!)

 

 

 

Уравновешенная  система счисления

Уравновешенные системы счисления бывают только с нечетным основанием: 3, 5, 7 и т.д.

 

Например:

• троичная уравновешенная система состоит из чисел 0, 1 и -1 (всего ТРИ знака)
• десятичная уравновешенная система состоит из чисел 0, 1, 2, 3, 4, 5, -1, -2, -3, -4, -5 (всего ДЕСЯТЬ знаков)

Запись в этой системе  счисления выглядит так:

перевод здесь осуществляется следующим образом:

 

 Факториальная система  счисления

 

Факториа́л числа n (обозначается n!, произносится эн факториа́л) — произведение всех натуральных чисел до nвключительно.

То есть n! = 1*2*3*…*n

Примеры:

• 2! = 1*2 = 2
• 5! = 1*2*3*4*5 = 120
• 8! = 1*2*3*4*5*6*7*8 = 40320
• 10! = 1*2*3*4*5*6*7*8*9*10 = 3628800
• d! = 1*2*3*4*…*d

Факториа́л нуля равен единице

x=∑k=1ndkk!, где 0⩾dk⩾k. 

• 1345_ф = 1*4! + 3*3! + 4*2! + 5*1! = 1*(1*2*3*4) + 3*(1*2*3) + 4*(1*2) + 5*1 =  1*20 + 3*6 + 4*2 + 5*1 = 20 + 18 + 8 + 5 = 51₁₀ (т.е. берем первый знак – 1, с ним вместе осталось 4 знака, поэтому умножаем 1 на 4!; далее идет 3, с ней вместе осталось 3 знака, поэтому 3*3!; далее 4, с ней вместе 2 знака, потому 4*2!; и в итоге 5, за ним знаков нет, это одна цифра, поэтому 5*1!)
• 607_ф = 6*3! + 7*1! = 6*(1*2*3) + 7* (1) = 6*6 +7*1 = 36 + 7 = 43₁₀

 

 

Смешанная система счисления

В смешанной системе счисления  может использоваться любая из ранее  нами рассмотренных систем счисления:

= 2*5⁴ -1*3³ + 1*2² +5*2! +F₃ = 2*625 – 1*27 + 1*4 + 5*(1*2) + (1+1) = 1250 – 27 + 4 + 10 + 2 = 1239₁₀

 

Биномиальная система  счисления. Представление, использующее биномиальные коэффициенты

x=∑k=1n(ckk), где 0⩾c1<c2<⋯<cn.

Система счисления майя

Майя использовали 20-ричную систему счисления за одним исключением: во втором разряде было не 20, а 18 ступеней, то есть за числом (17)(19) сразу следовало число (1)(0)(0). Это было сделано для облегчения расчетов календарного цикла, поскольку (1)(0)(0) = 360 примерно равно числу дней в солнечном году.

Римская система счисления

Каноническим примером фактически непозиционной системы счисления  является римская, в которой в качестве цифр используются латинские буквы: 
I обозначает 1, 
V — 5, 
X — 10, 
L — 50, 
C — 100, 
D — 500, 
M — 1000

Например, II = 1 + 1 = 2 
здесь символ I обозначает 1 независимо от места в числе.

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

IV = 4, в то время как: 
VI = 6

Система остаточных классов (СОК)

Представление числа в системе  остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно-простых модулей (m1,m2,…,mn) с произведением M=m1⋅m2⋅⋯⋅mn так, что каждому целому числу x из отрезка [0,M−1] ставится в соответствие набор вычетов (x1,x2,…,xn), где

x≡x1(modm1);

x≡x2(modm2);

…

x≡xn(modmn).

При этом китайская теорема  об остатках гарантирует однозначность  представления для чисел из отрезка [0,M−1].

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются  покомпонентно, если про результат известно, что он является целочисленным и также лежит в [0,M−1].

Недостатками СОК является возможность  представления только ограниченного  количества чисел, а также отсутствие эффективных алгоритмов для сравнения  чисел представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям (m1,m1⋅m2,…,m1⋅m2⋅⋯⋅mn−1).

Перевод чисел из СОК в десятичную систему счисления==== Формула перевода имеет вид:

A = a₁*B₁+a₂*B₂+…+a_n*B_n-r*P, где a₁, …, a_n - представление числа А в СОК с основаниями p₁, p₂, …, p_n;

P = p₁, p₂, …, p_n;

r = 0,1,2,… (целые числа), причем r выбирают так, чтобы разность  между левой и правой частью  выражения была меньше P;

B_i = (P/p_i)*k_i, где k_i = 1, 2, …, p_i, причем k_i выбирается таким, чтобы остаток от деления B_i/p_i был равен 1.

Пример.

А = (2,4,6) в системе с  основаниями: p₁ = 3, p₂ = 5, p₃ = 7.

p₂*p₃ = 3*5*7 = 105.

B₁ = 105/3*k₁ = 35*2 =70;

B₂ = 105/5*k₁ = 21*1 =21;

B₃ = 105/7*k₁ = 15*1 =15;

A = 2*70+4*21+6*15 - r*105;

A = 314 - r*105 = 104, где r=2.