Системы счисления Автор: Цветкова Мария Олеговна 1 курс ис

Скачать 106.67 Kb.

Название	Системы счисления Автор: Цветкова Мария Олеговна 1 курс ис
Дата публикации	17.03.2013
Размер	106.67 Kb.
Тип	Документы

odtdocs.ru > Математика > Документы

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

Автор: Цветкова Мария Олеговна

1 курс ИС

Содержание:

Позиционные системы счисления
Смешанные системы счисления
Непозиционные системы счисления
Системы счисления разных народов

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

^ Иллюстрация 1: Позиционные системы счисления И-Цзин

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

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

$x = \sum_{k=0}^{n-1} a_k b^k$ , где a_k — это целые числа, называемые цифрами , удовлетворяющие неравенству $0 \leq a_k \leq (b-1)$ .

Каждая степень b^k в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя k (номером разряда). Обычно для ненулевого числа x требуют, чтобы старшая цифра a_n_{− 1} в b-ричном представлении x была также ненулевой.

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

$x = a_{n-1} a_{n-2}\dots a_0.$

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

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

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

1 — единичная (как позиционная может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.);
2 — двоичная (в дискретной математике, информатике, программировании);
3 — троичная;
4 — четверичная;
Иллюстрация 2: Различные системы счисления
5 — пятеричная;
8 — восьмеричная;
10 — десятичная (используется повсеместно);
12 — двенадцатеричная (счёт дюжинами);
16 — шестнадцатеричная (используется в программировании, информатике, а также в шрифтах
60 — шестидесятеричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты).

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

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

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

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

В зависимости от вида b_k как функции от 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$ секунд.
^

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

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

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

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

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

$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 {c_k\choose k}$ , где $0\leq c_1 < c_2 < \dots < c_n$ .

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

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках.⁴ СОК определяется набором взаимно простых модулей $(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 = 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₁*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.
^

Система счисления Штерна-Броко

Система счисления Штерна-Броко — способ записи положительных рациональных чисел, основанный на дереве Штерна-Броко.⁵
^

Системы счисления разных народов

Древнеегипетская система счисления

Древнеегипетская десятичная непозиционная система счисления возникла во второй половине третьего тысячелетия до н.э. Для обозначения чисел 0, 1, 10, 10², 10³, 10⁴, 10⁵, 10⁶, 10⁷ использовались специальные цифры. Числа в египетской системе счисления записывались как комбинации этих цифр, в которых каждая из цифр повторялась не более девяти раз. Значение числа равно простой сумме значений цифр, участвующих в его записи.

Иллюстрация 3: Древнеегипетская система счисления

Алфавитные системы счисления

Иллюстрация 4: Древнерусская алфавитная система счисления
Алфавитными системами счисления пользовались древние армяне, грузины, греки (ионическая система счисления), арабы, евреи и другие народы Ближнего Востока. В славянских богослужебных книгах греческая алфавитная система была переведена на буквы кириллицы.
^

Еврейская система счисления

Еврейская система счисления в качестве цифр используются 22 буквы еврейского алфавита. Каждая буква имеет своё числовое значение от 1 до 400. «Ноль» отсутствует. Наиболее часто можно встретить цифры, записанные таким образом в нумерации лет по иудейскому календарю.
^

Греческая система счисления

Греческая система счисления, также известная как ионийская или новогреческая — непозиционная система счисления, в которой, в качестве символов для счёта, употребляют греческие буквы, а также дополнительные символы, такие как ς (стигма), Ϙ (копа) и Ϡ (сампи).

Эта система пришла на смену аттической, или старогреческой, системе, которая господствовала в Греции в III веке до н.э..

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

1 α	10 ι	100 ρ
2 β	20 κ	200 σ
3 γ	30 λ	300 τ
4 δ	40 μ	400 υ
5 ε	50 ν	500 φ
6 ς	60 ξ	600 χ
7 ζ	70 ο	700 ψ
8 η	80 π	800 ω
9 θ	90 Ϙ	900 Ϡ

Пример

Данные символы позволяют записать числа лишь от 1 до 999, например:

45 — με
632 — χλβ
970 — Ϡο

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

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

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

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

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

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

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

Для записи основными знаками были точки (единицы) и отрезки (пятёрки).
^

Кипу инков

Прообразом баз данных, широко использовавшихся в Центральных Андах (Перу, Боливия) в государственных и общественных целях в I—II тысячелетии н. э., была узелковая письменность Инков — кипу, состоявшая как из числовых записей десятичной системы, так и не числовых записей в двоичной системе кодирования. В кипу применялись первичные и дополнительные ключи, позиционные числа, кодирование цветом и образование серий повторяющихся данных. Кипу впервые в истории человечества использовалось для применения такого способа ведения бухгалтерского учёта как двойная запись.

Иллюстрация 5: Кипу инков

Список иллюстраций :

Позиционные системы счисления И-Цзин
Различные системы счисления
Древнеегипетская система счисления
Древнерусская алфавитная система счисления
Кипу инков

1Разряд — это структурный элемент числа в позиционных системах счисления.

2Линейная комбинация - это математическое выражение, построенное из математических объектов (переменных, матриц, функций и т.п.), соединенных знаками суммы (+) или разности (-).

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

4Если натуральные числа

попарно взаимно просты, то для любых целых

таких, что

при всех

, найдётся число N, которое при делении на a_i даёт остаток r_i при всех

5Дерево Штерна — Броко — способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева.

Добавить документ в свой блог или на сайт

	Урок усвоения новых знаний. Тема: «История чисел и системы счисления» Цель: познакомить учащихся с историей возникновения и развития систем счисления; указать на основные недостатки и преимущества непозиционных...		История развития систем счисления Системы счисления различаются выбором узловых чисел и способами образования алгоритмических, а с появлением письменных обозначений...
	Представление числовой информации с помощью систем счисления. Перевод... ...		Основания системы счисления Непозиционная система счисления – система, в которой символы, обозначающие то или иное количество, не меняют своего значения в зависимости...
	Утверждаю Ректор университета Целью лабораторной работы является: ознакомление с базовыми арифметическими командами процессора на примере решения задачи смены...		Цифры и системы счисления автор: Энциклопедия кругосвет «первый», равно как «два» и «второй», во многих языках не имеют между собой ничего общего, в то время как лежащие за пределами первобытного...
	Урок по теме «Представление числовой информации с помощью систем счисления» Формулировка Проблемы использование технологии «Корзина идей», понятие систем счисления		Г. Нижневартовск 20 11 год Мария Монтессори «изучать человеческое тело», поступила на медицинский факультет Римского университета и в 1895 г стала первой женщиной-врачом. Вскоре...
	Нижние Ачалуки" Малгобекского района ри султыговой Т. Г. Тема урока: " Цели: повторить основные понятия, определения в различных системах счисления; указать и повторить наиболее сложные алгоритмы вычислительных...		Нетрадиционный курс 5 класс. Автор-составитель: учитель экологии... Экологическое воспитание учащихся сегодня является одной из важнейших задач общества, а значит, и образования

Системы счисления Автор: Цветкова Мария Олеговна 1 курс ис

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

Содержание:

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

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

Системы счисления разных народов

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

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

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

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

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

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

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

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

Система счисления Штерна-Броко

Системы счисления разных народов

Древнеегипетская система счисления

Алфавитные системы счисления

Еврейская система счисления

Греческая система счисления

Пример

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

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

Кипу инков

Похожие: