Wikia

Математика

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

Обсуждение5
1426статей на этой вики

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

Позиционные системы счисления Править

228В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места, где он расположен. Такая система счисления основывается на том, что некоторое число n единиц (основание системы счисления) объединяется в одну единицу второго разряда, n единиц второго разряда объединяются в одну единицу третьего разряда и т. д. Основанием системы счисления может быть любое число, большее единицы.

Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации.
К числу таких систем относится современная десятичная система счисления (с основанием n = 10), возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших ее у мусульман. В вычислительной технике применялись и широко применяются системы счисления не только с основанием 2, 4, 8, 16, 32, 64, 256. Например, использовалась и троичная система счисления, цифры которой кодировались отсутствием электрического сигнала и положительным или отрицательным его уровнем. При записи больших чисел заслуживают внимания основания систем счисления 100, 1000, 10000, 1000000.

Определение Править

b-ричная система счисления определяется натуральным числом b > 1, называемым основанием системы счисления. x в b-ричной системе счисления его представляют в виде линейной комбинации степеней числа b:

x = \sum_{k=0}^n a_k b^k, где a_k — целые, 0 \leq a_k < b.

Примеры Править

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

 103 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0}.

Также распространены системы счисления с основаниями:

1511

Алгоритмы переводаПравить

http://valera.asf.ru/perl/cookbook/cont.php?id=19


ЗаписьПравить

Для записи чисел системы счисления с основанием до 36 включительно в качестве цифр используются арабские цифры (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) и затем буквы латинского алфавита (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z). При этом, a = 10, b = 11 и т. д., иногда x = 10.

При одновременной работе с несколькими системами счисления для их различения основание системы обычно указывается в виде нижнего индекса, который записывается в десятичной системе:

123_{10} — это число 123 в десятичной системе счисления;
1111011_2 — то же число, но в двоичной системе.

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

  • в ассемблере и записях общего рода, не привязанных к конкретному языку, буквой h (от hexadecimal) в конце числа (синтаксис Intel);
  • в Паскале знаком «$» в начале числа;
  • в C и многих других языках комбинацией 0x или 0X (от hexadecimal) в начале.

В некоторых диалектах языка Си по аналогии с «0x» используется префикс «0b» для обозначения двоичных чисел. (Обозначение «0b» не входит в стандарт ANSI C.)

СвойстваПравить

Позиционная система счисления обладает рядом важных свойств:

  1. Основание системы счисления в ней самой всегда записывается как 10; например, в двоичной системе счисления 10 означает число 2.
  2. Для записи числа x в b-ричной системе счисления требуется [log_b(x)] + 1 цифр, где [\cdot]целая часть числа.
  3. Сравнение чисел. Сравним числа 321 и 312. Для этого слева направо сравниваем цифры, стоящие на одних и тех же позициях: 3 = 3 — результат сравнения чисел не определён; 2 > 1 — первое число больше независимо от оставшихся цифр.
  4. Сложение чисел. Сложим 321 и 312. Для этого справа налево складываем отдельные цифры:
    1 + 2 = 3
    2 + 1 = 3
    3 + 3 = 6, итого 633.
    Таким же образом можно сложить числа произвольной длины.

Переход к другому основанию Править

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

Если число в b-ричной системе счисления равно

a_1\;a_2\;a_3 \ldots a_n,

то для перевода в десятичную систему вычисляем такую сумму:

\sum_{i=1}^n a_i\cdot b^{n-i}

или, в более наглядном виде:

a_1\cdot b^{n-1} + a_2 \cdot b^{n-2} + \ldots + a_{n-1} \cdot b^1 + a_n \cdot b^0,

либо, наконец, в виде схемы Горнера:

((\ldots(a_1 \cdot b + a_2) \cdot b + a_3) \ldots ) \cdot b + a_n.

Например:

1011002 =
= 1 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 0 · 1 =
= 1 · 32 + 0 · 16 + 1 · 8 + 1 · 4 + 0 · 2 + 0 · 1 =
= 32 + 8 + 4 + 0 = 4410

Пример на C для перевода 18 в 7-ричную систему выглядит так: (корректно работает до основания 10, дальше появятся «цифры» :;<=>?@012 и т.д.)

void perevod( unsigned int num, unsigned int base )
{
  #define LENGTH ( 8 * sizeof( unsigned int ) ) /* размер с запасом */

  char str[ LENGTH + 1]; /* +1 для символа [[EOS]] */
  char *pstr = str + LENGTH - 1; /* начинаем заполнять цифрами с конца */

  str[ LENGTH ] = '\0'; /* добавляем EOS */

  if( num == 0 ) *pstr = '0'; /* если цикл не будет крутиться */
  else
    do
    {
      *pstr-- = '0' + num % base; /* заполняем цифрами, сдвигаясь влево */
      num /= base;
    }
    while( num > 0 );

  printf( "%s\n", pstr + 1 ); /* печатаем, начиная с 1го ненулевого символа */

  #undef LENGTH /* уже не нужно */
}

void main()
{
  perevod( 18, 7 );
}

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

Для перевода необходимо делить число с остатком на основание счисления до тех пор, пока частное больше основания счисления.

Пример:ыв

Невозможно разобрать выражение (лексическая ошибка): 44_{10}</mуцath> переведём в двоичную систему 44 делим на 2. частное 22, остаток 0 *22 делим на 2. частнцукыаое 11, остаток 0 11 делим на 2. частное 5, остаток 1 5 делим нывафываа 2. частное 2, остаток 1 2 делим на 2. частное 1, остаток 0 1 делим на 2. частное 0, остаток 1 Частное равно нулю, деление закончено. Тыаыфаеперь записав все остатки справа налево получим число<math>101100_2


Перевод из двоичной в восьмеричную и шестнадцатеричную системы Править

Для этого типа операций существует упрощенный алгоритм.

Для восьмеричной — разбиваем число на триплеты, преобразуем триплеты по таблице

000 0 100 4
001 1 101 5
010 2 110 6
011 3 111 7

Для шестнадцатеричной — разбиваем на квартеты, преобразуем по таблице

0000 0 0100 4 1000 8 1100 C 
0001 1 0101 5 1001 9 1101 D
0010 2 0110 6 1010 A 1110 E
0011 3 0111 7 1011 B 1111 F

Пример:

преобразуем 1011002
восьмеричная — 101 100 → 548
шестнадцатеричная — 0010 1100 → 2C16

Перевод из восьмеричной и шестнадцатеричной систем в двоичную Править

Для этого типа операций существует упрощенный алгоритм-перевёртыш.

Для восьмеричной — преобразуем по таблице в триплеты

0 000 4 100
1 001 5 101
2 010 6 110
3 011 7 111

Для шестнадцатеричной — преобразуем по таблице в квартеты

0 0000 4 0100 8 1000 C 1100 
1 0001 5 0101 9 1001 D 1101
2 0010 6 0110 A 1010 E 1110
3 0011 7 0111 B 1011 F 1111

Пример:

преобразуем 
548 → 101 100
2C16 → 0010 1100

См. Таблица порядков двоичных, шестнадцатеричных и десятичных чисел

Дробное счисление в других системах счисления Править

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

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

Рассмотрим пример: число 103,625 можно представить как

 103,625 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0} + 6 \cdot 10^{-1} + 2 \cdot 10^{-2} + 5 \cdot 10^{-3}.

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

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

Рассмотрим пример перевода двоичного числа 1100,0112 в десятичное. Целая часть этого числа равна 12 (см. выше), а вот перевод дробной части рассмотрим подробнее:

 0,011 = 0 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} = 0 + 0,25 + 0,125 = 0,375.

Итак, число 1100,0112 = 12,37510.

Точно также осуществляется перевод из любой системы счисления, только вместо «2» ставится основание системы.

Для удобства перевода, целую и дробную части числа почти всегда переводят по-отдельности, а результат потом суммируют.

Перевод из двоичной системы в 8- и 16-ричную Править

Перевод дробной части из двоичной системы счисления в системы счисления с основаниями 8 и 16 осуществляется точно также, как и для целых частей числа, за тем лишь исключением, что разбивка на октавы и тетрады идёт вправо от десятичной запятой, недостающие разряды дополняются нулями справа. Например, рассмотренное выше число 1100,0112 будет выглядеть как 12,38 или C,616.

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

Для перевода дробной части числа в другие системы счисления нужно обратить целую часть в нуль и начать умножение получившегося числа на основание той системы, в которую нужно перевести. Если в результате умножения будут снова появляться целые части, их нужно повторно обращать в нуль, предварительно запомнив (записав) значение получившейся целой части. Операция заканчивается, когда дробная часть полностью обратится в нуль. Ниже приводится пример перевода числа 103,62510 в двоичную систему счисления.

Переводим целую часть по правилам, описанным выше, получаем 10310 = 11001112.
0,625 умножаем на 2. Дробная часть 0,250. Целая часть 1.
0,250 умножаем на 2. Дробная часть 0,500. Целая часть 0.
0,500 умножаем на 2. Дробная часть 0,000. Целая часть 1.
Итак, сверху вниз получаем число 1012
103,62510 = 1100111,1012

Точно также осуществляется перевод в системы счисления с любым основанием.

Сразу нужно отметить, что этот пример специально подобран, в общем случае очень редко удаётся завершить перевод дробной части числа из десятичной системы в другие системы счисления, а потому, в подавляющем большинстве случаев, перевод можно осуществить с какой либо долей погрешности. Чем больше знаков после запятой — тем точнее приближение результата перевода к истине. В этих словах легко убедиться, если попытаться, например, перевести в двоичный код число 0,626.

Симметричные позиционные системы счисления Править

Такие системы счисления отличаются от обычных тем, что используют цифры не из множества (0, \ldots, b-1), а из множества (-\frac{b-1}{2}, -\frac{b-3}{2}, \ldots, \frac{b-1}{2}). Чтобы цифры были целыми, нужно, чтобы b было нечётным. В симметричных системах счисления не требуется дополнительных обозначений для знака числа. Кроме того, вычисления в симметричных системах удобны тем, что не требуется особых правил округления — оно сводится к простому отбрасыванию лишних разрядов, что резко уменьшает систематические ошибки вычислений.

Чаще всего используется симметричная троичная система счисления с цифрами (-1,0,1). Она применяется в троичной логике и была технически реализована в вычислительной машине «Сетунь».

Смешанные системы счисленияПравить

Смешанная система счисления является обобщением b-ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел \{b_k\}_{k=0}^{\infty} и каждое число x представляется как линейная комбинация:

x = \sum_{k=0}^n a_{k}b_k, где на коэффициенты a_{k} (называемые как и прежде цифрами) накладываются некоторые ограничения.

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

Если b_k=b^k для некоторого b, то смешанная система счисления совпадает с b-ричной системой счисления.

Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина d дней h часов m минут s секунд соответствует значению d\cdot 24\cdot 60\cdot 60 + h\cdot 60\cdot 60 + m\cdot 60 + s секунд.

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

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

x = \sum_{k=0}^n f_k F_k, где F_k — числа Фибоначчи, f_k\in\{0,1\}, при этом в записи f_nf_{n-1}\dots f_0 не встречается две единицы подряд.

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

Представление

x = \sum_{k=1}^n d_k k!, где 0\leq d_k \leq k.

Биномиальная система счисленияПравить

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

x = \sum_{k=1}^n {c_k\choose k}, где 0\leq c_1 < c_2 < \dots < c_n.

Система счисления майяПравить

Майя использовали 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

См. римские цифры.

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

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно-простых модулей (m_1, m_2, \dots, m_n) с произведением M=m_1\cdot m_2\cdot \dots\cdot m_n так, что каждому целому числу x из отрезка [0,M-1] ставится в соответствие набор вычетов (x_1, x_2, \dots, x_n), где

x \equiv x_1 \pmod{m_1};
x \equiv x_2 \pmod{m_2};
x \equiv x_n \pmod{m_n}.

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

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

Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям (m_1, m_1\cdot m_2, \dots, m_1\cdot m_2\cdot\dots\cdot m_{n-1}).

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

Формула перевода имеет вид:

A = a1*B1+a2*B2+…+an*Bn-r*P, где a1, …, an - представление числа А в СОК с основаниями p1, p2, …, pn;

P = p1, p2, …, pn;

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

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

Пример.

А = (2,4,6) в системе с основаниями: p1 = 3, p2 = 5, p3 = 7.

P = p1*p2*p3 = 3*5*7 = 105.

B1 = 105/3*k1 = 35*2 =70;

B2 = 105/5*k1 = 21*1 =21;

B3 = 105/7*k1 = 15*1 =15;

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

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

Ссылки Править

Шаблон:Викиучебник


ar:أنظمة عد be-x-old:Сыстэма зьлічэньня bg:Бройна система bs:Brojevni sistem ca:Sistema de numeració cs:Číselná soustava da:Talsystemeo:Cifereca sistemoeu:Zenbaki-sistemagl:Sistema de numeración he:שיטות ספירה hr:Brojevni sustav hu:Számrendszerek id:Sistem bilangannl:Talstelsel no:Tallsystem pl:System liczbowysh:Brojevni sistem sl:Številski sistem sv:Talsystem ta:எண்ணுருuk:Система числення yi:נומערן סיסטעםzh-min-nan:Sò͘-jī

Викия-сеть

Случайная вики