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

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

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

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

2348310 = 2 · 10 4 + 3 · 10 3 + 4 · 10 2 + 8 · 10 1 + 3 · 10 0 .

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

10001102 = 1 · 2 6 + 0 · 2 5 + 0 · 2 4 + 0 · 2 3 + 1 · 2 2 + 1 · 2 1 + 0 · 2 0 ;

7А0С16 = 7 · 16 3 + 10 · 16 2 + 0 · 16 1 + 12 · 16 0 .

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

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

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

Виналь = 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 и так далее. Следовательно, если запись числа в факториальной системе имеет вид dn dn–1…d2d1, то этому числу соответствует десятичное значение, равное

= d1 · 1! + d2 · 2! + d3 · 3! + … + dn · n!,

— где dk — цифра числа (0 dk 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! = 243220f (буква f в виде индекса говорит о записи числа в факториальной системе).

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

Фибоначчи, fk <0, 1>, причем в записи числа две единицы не должны стоять рядом 1 . Последнее замечание крайне важно: при несоблюдении этого условия запись числа будет неоднозначной. Например, число 510 может быть записано как 110Fib (5 = 1 · 3 + 1 · 2 + 0 · 1) и 1000Fib (5 = 1 · 5 + 0 · 3 + 0 · 2 + 0 · 1), но правильным считается второе число, где в записи нет двух подряд идущих единиц. В этом случае каждое натуральное число в фибоначчиевой системе счисления записывается единственным образом. Например, 200810 = 1597 + 377 + 34 = F16 + F13 + F8 = 1001000010000000Fib.

Читайте также:  Видеорегистратор с хорошей камерой

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Непозиционная система счисления — система, в которой, значение символа не зависит от его положения в числе. Непозиционные системы счисления возникли раньше позиционных систем. Они использовались в древности римлянами, египтянами, славянами и другими народами. Примером непозиционной системы счисления, дошедшей до наших дней, служит римская система счисления.

Цифры в римской системе обозначаются различными знаками: 1—I; 3—III; 5—V; 10—X; 50—L; 100—C; 500—D; 1000—M. Для записи промежуточных значений существует правило: каждый меньший знак, поставленный справа от большего, прибавляется к его значению, а слева — вычитается из него. Так, IV обозначает 4, VI—6, LX— 60, XC—90 и т.д. Основной недостаток непозиционных систем — большое число различных знаков и сложность выполнения арифметических операций.

Позиционные системы счисления

В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у мусульман.

Под позиционной системой счисления обычно понимается -ричная система счисления, которая определяется целым числом , называемым основанием системы счисления. Целое число без знака в -ричной системе счисления представляется в виде конечной линейной комбинации степеней числа :

, где — это целые числа, называемые цифрами, удовлетворяющие неравенству .

Каждая степень в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя (номером разряда). Обычно, в ненулевых числах , левые нули опускаются.

Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число записывают в виде последовательности его -ричных цифр, перечисляемых по убыванию старшинства разрядов слева направо:

Например, число сто три представляется в десятичной системе счисления в виде:

Читайте также:  Режим вечеринка honor что это

Значения первых 16 целых чисел в различных СС

Наиболее употребляемыми в настоящее время позиционными системами являются:

1 — единичная (счёт на пальцах, зарубки, узелки «на память» и др.);

2 — двоичная (в дискретной математике, информатике, программировании);

В двоичной системе счисления для записи чисел используется две цифры 0 и 1. Основание системы q=2 записывается как 102=[1*2 1 +0*2 0 ]10 В данной СС любое число может быть представлено последовательностью двоичных цифр. Эта запись соответствует сумме степеней цифры 2, взятых с указанными в ней коэффициентами

X=am*2m+am-1*2m-1+…+a1*21+a0*20+… . Например, двоичное число (10101101)2=1*27+0*26+1*25+0*24+1*23+1*22+0*21+1*20=17310

Правила двоичной арифметики:

1+1=10 (происходит перенос единицы в старший разряд);

10-1=1 (происходит заем единицы в старшем разряде);

10 — десятичная (используется повсеместно);

12 — двенадцатеричная (счёт дюжинами);

16 — шестнадцатеричная (используется в программировании, информатике);

60 — шестидесятеричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты).

В позиционных системах чем больше основание системы, тем меньшее количество разрядов (то есть записываемых цифр) требуется при записи числа.

Правила перевода из одной позиционной системы счисления в другую

Перевод целых чисел

Допустим, число Х из системы счисления с основанием q требуется перевести в систему счисления с основанием р. Перевод осуществляется по следующему правилу. Целую часть числа делим на новое основание р. Полученный от деления первый остаток является младшей цифрой целой части числа с основанием р. Целую часть полученного числа снова делим на основание р. В результате определим второй остаток, равный следующей после младшей цифре числа с основанием р’, деление будем производить до тех пор, пока не получим частное меньше делителя. Последнее частное дает старшую цифру числа с основанием р.

Число 137,458 перевести в двоичную систему счисления. Перевод осуществляется заменой каждой восьмеричной цифры трехзначным двоичным числом (триадой):

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

Число 5F,9416 перевести в двоичную систему счисления. Перевод осуществляется заменой каждой шестнадцатеричной цифры четырехзначным двоичным числом (тетрадой):

т.e. 5F,9416=01011111,100101002.Исходя из Число 5F,9416 в восьмеричной системе счисления имеет вид 137,458.

В десятичной двоично-кодированной системе счисления, часто называемой двоично-десятичной системой, используются десятичные числа. В ней каждую цифру деся-тичного числа (от 0 до 9) заменяют тетрадой.

Число 273,5910 перевести в двоично-десятичную систему счисления. Перевод осуществим следующим образом:

т.е. 273,5910 = 001001110011,010110012-10

Двоично-десятичную запись числа используют непосредственно или как промежу-точную форму записи между обычной десятичной его записью и машинной двоичной. Вычислительная машина сама по специальной программе переводит двоично-десятичные числа в двоичные и обратно.

Число 2610 перевести в двоичную систему счисления. Перевод осуществим методом последовательного деления десятичного числа 26 на основание новой системы счисления — 2. Остатки от деления образуют искомое число в двоичной СС. Таким образом:

В результате получаем 2610 = 110102

Число 19110 перевести в восьмеричную систему счисления. Перевод осуществим методом последовательного деления десятичного числа 191 на основание новой системы счисления — 8. Остатки от деления образуют искомое число в восьмеричной СС.Остатки отделения образуют восьмеричное число

В результате получаем 19110 = 2772

Перевод из позиционной СС в десятичную:

Перевод из любой позиционной системы счисления в десятичную осуществляется следующим методом:

1) над каждым разрядом числа расставляют его номер по порядку справа налево, начиная с нуля; 2) цифры числа являются коэффициентами при основании системы счисления в степенях соответствующих номеру разряда; 3) суммируют полученные произведения оснований системы счисления в степенях равных соответствующему номеру разрядов на цифры числа.

Рассмотрим данный алгоритм на примере перевода 11010012 в десятичную СС: 11010012 = [1*2 6 +1*2 5 +0*2 4 +1*2 3 +0*2 2 +0*2 1 +1*2 0 ]10 = 10510

Перевод дробных чисел

Предположим, что правильную дробь X, представленную в системе счисления с основанием q, требуется перевести в систему счисления с основанием р. Перевод осуществляем по следующему правилу. Исходное число умножаем на новое основание р. Получающаяся при этом целая часть произведения является первой искомой цифрой. Дробную часть произведения снова умножаем на основание р, целая часть нового произведения будет второй искомой цифрой. Дробную часть снова умножаем на основание р и т. д.

в результате 0,3110 = 0,01001112

Из этого примера следует, что перевод дробей может представлять собой бесконечный процесс, а результат перевода — приближенный.

Число цифр в числе, представленном в системе счисления с основанием р, определяется из условия, что точность числа в этой системе должна соответствовать точности числа в системе счисления с основанием q.

Читайте также:  Как очистить кэш ватсап на айфоне

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

0,11101112 = [1*2 -1 +1*2 -2 +1*2 -3 +1*2 -5 +1*2 -6 +1*2 -7 ]10 = 0,9296875

Перевод произвольных чисел.

Числа, имеющие целую и дробную часть, переводятся в два этапа: вначале целая часть числа, а затем дробная.

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

Смешанная система счисления является обобщением -ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел , и каждое число в ней представляется как линейная комбинация:

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

Записью числа в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса , начиная с первого ненулевого.

В зависимости от вида как функции от смешанные системы счисления могут быть степенными, показательными и т. п. Когда для некоторого , смешанная система счисления совпадает с показательной -ричной системой счисления.

Наиболее известным примером смешанной системы счисления является представление времени в виде количества суток, часов, минут и секунд. При этом величина « дней, часов, минут, секунд» соответствует значению секунд.

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

В факториальной системе счисления основаниями являются последовательность факториалов , и каждое натуральное число представляется в виде:

, где .

Факториальная система счисления используется при декодировании перестановок списками инверсий: имея номер перестановки, можно воспроизвести её саму следующим образом: число, на единицу меньшее номера (нумерация начинается с нуля) записывается в факториальной системе счисления, при этом коэффициент при числе i! будет обозначать число инверсий для элемента i+1 в том множестве, в котором производятся перестановки (число элементов меньших i+1, но стоящих правее его в искомой перестановке)

Пример: рассмотрим множество перестановок из 5 элементов, всего их 5! = 120 (от перестановки с номером 0 — (1,2,3,4,5) до перестановки с номером 119 — (5,4,3,2,1)), найдём 101-ую перестановку: 100 = 4!*4 + 3!*0 + 2!*2 + 1!*0 = 96 + 4; положим ti — коэффициент при числе i!, тогда t4 = 4, t3 = 0, t2 = 2, t1 = 0 , тогда: число элементов меньших 5, но стоящих правее равно 4; число элементов меньших 4, но стоящих правее равно 0; число элементов меньших 3, но стоящих правее равно 2; число элементов меньших 2, но стоящих правее равно 0 (последний элемент в перестановке «ставится» на единственное оставшееся место) — таким образом, 101-я перестановка будет иметь вид: (5,3,1,2,4) Проверка данного метода может быть осуществлена путём непосредственного подсчёта инверсий для каждого элемента перестановки.

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

Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число в ней представляется в виде:

, где — числа Фибоначчи, , при этом в коэффициентах есть конечное количество единиц и не встречаются две единицы подряд.

Важным обобщением позиционных систем с постоянным основанием являются смешанные системы, где основания меняются от разряда к разряду. Обозначим основания разрядов с номерами 0, 1, . k через р, р1, . рk. Тогда запись вида Аp=ak. a2a1aозначает представление в смешанной системе счисления величины ak×р(k-1)× . ×p1р+ . +a2p1р+a1р + a. Каждый коэффициент ai удовлетворяет неравенcтву: 0£ ai n :

а) количество вершин в сфере радиусом 1 равно n, а количество вершин в шаре радиусом 1 равно n +1;

б) количество вершин в сфере радиусом 2 равно n (n – 1)/2,
а количество вершин в шаре радиусом 2 равно n(n+1)/2+1.

4. Доказать (например, с использованием метода математической индукции), что общее количество вершин в бинарном дереве Т n равно 2 n+ 1 –1.

5. Доказать методом математической индукции, что в n-мерном кубе В n число ребер равно n∙2 n– 1 .

6. Доказать, что на множестве всех n-мерных булевых векторов расстояние Хэмминга удовлетворяет неравенству треугольника:

7. Пусть В n — множество всех n – мерных двоичных векторов
b n , которые появляются случайно c одинаковой вероятностью. Доказать, что средневероятный вес wсв(b n ) булевых векторов`b n равен n/2.

8. Перевести в двоичную систему и систему с основанием 4 числа B23DA16, АD7С16.

9. Перевести в десятичную систему числа F9B8316, CАF516.

10.Перевести в шестнадцатеричную систему числа 1101102 , 11011012 , 10110110101012 .

11.Перевести, используя сокращенные правила перевода, из восьмеричной системы в двоичную числа 57168, 1738 , 2658 .

12. Перевести следующие дроби в десятичную систему:

13. Выполнить следующие арифметические действия:

14. Перевести в факториальную систему числа:

15. Перевести в десятичную систему из факториальной числа:
а) 423010, б) 231200, в) 142110, г) 502110.

Дата добавления: 2015-10-05 ; просмотров: 3359 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Ссылка на основную публикацию
Установить gvlk ключ что это
В связи с недавним выходом окончательной RTM версии пакета Microsoft Office 2016, корпоративные заказчики уже могут начинать переход на новую...
Топ вай фай адаптеров для пк
На заре развития интернета люди пользовались только проводным трафиком. После этого в «моду» начали входить модемы, которые подключались к беспроводному...
Топ дешевых наушников с хорошим звуком
Проводные наушники должны умереть! Так решил мобильный рынок и производители смартфонов, стремительно избавляющиеся от устаревшего 3,5 мм джека. Стоит ли...
Установить openal32 dll для windows 7
Данная библиотека задействуется во многих процессах во время работы компьютера. Например, она используется в играх, мультимедиа и различных программах. Иногда...
Adblock detector