Нетрадиционные системы счисления

Читателям газеты-вкладки “В мир информатики” конечно же известно, что существуют два вида систем счисления: позиционные и непозиционные. А знаете ли вы, что позиционные системы, в свою очередь, можно разделить на традиционные и нетрадиционные?

Напомним основные положения. В позиционной системе счисления количественный эквивалент цифры зависит от ее положения в записи числа. Для таких систем мы фиксируем некоторое основание — целое положительное число
р 2 и рассматриваем так называемый базис. Чтобы понять последнее понятие, давайте вспомним, что в привычной нам десятичной системе значение числа образуется следующим образом: значения его цифр умножаются на “веса” соответствующих разрядов и все полученные значения складываются. Например:

23483₁₀ = 2 · 10⁴ + 3 · 10³ + 4 · 10² + 8 · 10¹ + 3 · 10⁰.

Аналогично и для чисел, записанных в других системах счисления:

1000110₂ = 1 · 2⁶ + 0 · 2⁵ + 0 · 2⁴ + 0 · 2³ + 1 · 2² + 1 · 2¹ + 0 · 2⁰;

7А0С₁₆ = 7 · 16³ + 10 · 16² + 0 · 16¹ + 12 · 16⁰.

Последовательность чисел, каждое из которых задает “вес” соответствующих разрядов, и называют базисом системы счисления. Из приведенных примеров видно, что базисы десятичной, двоичной, шестнадцатеричной систем счисления образуют геометрическую прогрессию со знаменателем р, равным 10, 2 и 16 соответственно.

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

Если какое-то из перечисленных условий не соблюдается, то речь идет о нетрадиционной системе счисления. В статьях [2–3] рассказывалось, например, о троичной уравновешенной системе счисления с цифрами –1, 0 и 1 (присутствует отрицательное число). А можно ли в качестве базиса выбрать не геометрическую прогрессию, а некоторую последовательность натуральных чисел? Оказывается, да. Такая система, например, применялась для календаря и астрономических наблюдений индейцами племени майя. Они использовали 20-ричную систему счисления за некоторым исключением: р₀ = 1, р₁ = 20, р₂ = 18, р₃ = 20, р₄ = 20 и т.д. Это было сделано для облегчения расчетов календарного цикла. Например, число 100 в этой системе, равное 1 · 18 · 20 + 0 · 20 + 0 · 1 = 360, есть примерно число дней в нашем, “солнечном”, году. У индейцев 20 дней-кинов образовывали месяц (виналь, или уинал), 18 месяцев-уиналов образовывали год (тун) и так далее:

Кин = 1 день.

Виналь = 20 кин = 20 дней.

Тун = 18 виналь = 360 дней = около 1 года.

Катун = 20 тун = 7200 дней = около 20 лет.

Бактун = 20 катун = 144 000 дней = около 400 лет.

Пиктун = 20 бактун = 2 880 000 дней = около 8000 лет.

Калабтун = 20 пиктун = 57 600 000 дней = около 160 000 лет.

Кинчильтун = 20 калабтун = 1?152?000?000 дней =
= около 3 200 000 лет.

Алавтун = 20 кинчильтун = 23 040 000 000 дней =
= около 64 000 000 лет.

Также в качестве примера можно рассмотреть представление времени в виде количества суток, часов, минут и секунд. При этом величина “d дней h часов m минут s секунд” соответствует значению d · 24 · 60 · 60 + + h · 60 · 60 +
+ m · 60 + s секунд.

Рассмотрим еще две нетрадиционные системы счисления.

Первая называется факториальной. В этой системе счисления базис образует последовательность факториалов натуральных чисел: 1! = 1, 2! = 2,
3! = 6, … . Другой ее особенностью является то, что количество цифр, используемых в том или ином разряде (так называемая размерность алфавита), неодинаково — оно увеличивается с ростом номера разряда. В первом разряде могут быть только цифры 0 и 1, во втором — 0, 1 и 2, в k-м — 0, 1, 2, …, k и так далее. Следовательно, если запись числа в факториальной системе имеет вид d_n d_n–1…d₂d₁, то этому числу соответствует десятичное значение, равное

= d₁ · 1! + d₂ · 2! + d₃ · 3! + … + d_n · n!,

— где d_k — цифра числа (0 d_k k). Десятичному же числу 2008 соответствует 2 · 720 + 4 · 120 + 3 · 24 + 2 · 6 + 2 · 2 + 0 · 1 = 2 · 6! + 4 · 5! + 3 · 4! + 2 · 3! +
+ 2 · 2! + 0 · 1! = 243220_f (буква f в виде индекса говорит о записи числа в факториальной системе).

Фибоначчиева система счисления известна еще более узкому кругу специалистов. Из названия нетрудно догадаться, что она основывается на числах Фибоначчи. В этой системе счисления вес k-го разряда равен k-му числу Фибоначчи: 1, 2, 3, 5, 8, 13, 21, 34, 55, … (каждый член, начиная с третьего, равен сумме двух предыдущих). Используемые цифры (алфавит) — только 0 и 1. Следовательно, если запись числа в фибоначчиевой системе имеет вид f_n f_n–1…f₂f₁, то этому числу соответствует десятичное значение, равное , где F_k — числа

Фибоначчи, f_k {0, 1}, причем в записи числа две единицы не должны стоять рядом¹. Последнее замечание крайне важно: при несоблюдении этого условия запись числа будет неоднозначной. Например, число 5₁₀ может быть записано как 110_Fib (5 = 1 · 3 + 1 · 2 + 0 · 1) и 1000_Fib (5 = 1 · 5 + 0 · 3 + 0 · 2 + 0 · 1), но правильным считается второе число, где в записи нет двух подряд идущих единиц. В этом случае каждое натуральное число в фибоначчиевой системе счисления записывается единственным образом. Например, 2008₁₀ = 1597 + 377 + 34 = F₁₆ + F₁₃ + F₈ = 1001000010000000_Fib.

Необходимо отметить, что, хотя для записи числа в этой системе счисления используются только цифры 0 и 1, эту запись нельзя считать двоичным представлением числа.

Задания для самостоятельной работы²

1. Какие из чисел записаны не по правилам факториальной системы счисления: 42220, 44000, 86633300, 8663320?

2. Определите десятичный эквивалент чисел, записанных

а) в факториальной системе: 502101, 4422310;

б) в фибоначчиевой системе: 10010101, 101010101.

3. Запишите десятичные числа 34502 и 45087012 в факториальной системе счисления.

4. Перечислите первые 14 натуральных чисел в фибоначчиевой системе счисления. Проанализируйте полученные числа и сформулируйте правила перечисления натуральных чисел (правила получения очередного числа) в этой системе.

5. Запишите десятичные числа 30, 125 и 1949 в фибоначчиевой системе счисления.

6. Объясните, какое отношение имеют необычные счеты, показанные на рисунке, к данной статье? Какое десятичное число отложено на правых счетах?

7. На известном вам языке программирования напишите программы перевода десятичного натурального числа N (N 2³¹ – 1) в факториальную и фибоначчиеву системы счисления и обратно.

В заключение ответим на вопрос, который скорее всего возник у читателей: а зачем нужны такие системы счисления? Факториальная система счисления используется, например, специалистами в теории чисел для нумерации перестановок. Системы, аналогичные фибоначчиевой, применяются при кодировании информации. В свое время была даже сделана попытка создания компьютера, основанного на фибоначчиевой системе счисления [1]. Это теоретически и практически интересные системы записи чисел. Изучение особенностей таких систем продолжается и в настоящее время, и у наших читателей есть возможность заняться серьезным исследованием данного вопроса.

Литература

1. Андреева Е.В., Босова Л.Л., Фалина И.Н. Математические основы информатики. Элективный курс: Учебное пособие. М.: БИНОМ. Лаборатория знаний, 2005.

2. О троичной системе счисления. / Информатика, № 4/2006.

3. Гашков С.Б. Системы счисления и их применения. / Информатика, № 4/2006.

4. Кузьмищев В.А. Тайна жрецов майя. М.: Молодая гвардия, 1975.

5. Касаткин В.Н. Новое о системах счисления. Киев: Выща школа, 1982.

6. Стахов А.П. Музей гармонии и Золотого Сечения. http://goldenmuseum.com/index_rus.html.

---

1 Имеется также вариант фибоначчиевой системы счисления, в которой в записи чисел не допускаются два рядом стоящих нуля. — Прим. ред.

2 Ответы и/или программы (можно не все) присылайте в редакцию. Фамилии всех приславших будут опубликованы, а лучшие ответы мы поощрим. — Ред.