Перегляд вихідного коду сторінки Позиційна система числення

{{Системи числення}}
'''Позиційна система числення''' (або '''Позиційна нотація''') — [[система числення]], в якій значення кожного [[Число|числового]] [[Символ|знака]] ([[цифри]]) в запису числа залежить від його позиції ([[Розряд числа|розряду]]). Таким чином, позиція цифри має вагу у числі. Здебільшого вага кожної позиції кратна деякому [[Натуральні числа|натуральному числу]] <math>b</math>, <math>b>1</math>, яке називається ''основою'' системи числення.

Винахід позиційної системи числення, заснованої на помісному значенні цифр, приписують [[шумер]]ам і [[вавилон]]цям. Її було розвинуто [[Індія|індусами]] і вона отримала неоціненні наслідки для історії людської [[Цивілізація|цивилізації]].

До числа таких систем належить сучасна [[Десяткова система числення]] (з основою <math>b = 10</math>), виникнення якої пов'язують із лічбою на пальцях. У [[Середньовіччя|середньовічній]] [[Європа|Європі]] вона з'явилася через [[Італія|італійських]] купців, які у свою чергу запозичили її у [[Мусульмани|мусульман]].

== Класифікація позиційних систем числення ==
З метою ефективного використання систем числення в теорії і на практиці важливо їх класифікувати. У першу чергу розглянемо системи числення, які генерують числа однакової довжини.

Системи числення з рівною довжиною чисел належать до класу ''рівномірних'' кодів. Однакову довжину числа мають лише тоді, коли підмножини, які отримують в системах числення на кожному кроці розбиття вихідної множини, містять однакове число елементів.

Такі системи числення назвемо ''однорідними''. Їх також ще називають ''природними'', або ''степеневими''. Як уже зазначалось, характерною ознакою таких систем є однаковість їх чисел за довжиною. Крім цього, другою не менш важливою особливістю цих систем є те, що вага розрядів в них змінюється згідно зі степеневим законом. До цих систем числення належать [[Двійкова система числення|двійкова]], [[Десяткова система числення|десяткова]], п'ятерична і безліч подібних інших. За їх основи беруть числа 2, 10, 5 і&nbsp;т.&nbsp;д.

Розроблення більш складних, ніж однорідні, позиційних систем числення почалося в основному в другій половині 20-го століття після того, як з'явилася цифрова обчислювальна техніка. Такі системи назвемо ''неоднорідними''. Вони використовувались здебільшого при побудові спеціалізованих обчислювачів, систем зв'язку та керування, кодуючих та декодуючих пристроїв з метою підвищення їх ефективності.

Найпростішими неоднорідними системами числення є системи, в яких кількість елементів в усіх підмножинах, отриманих на попередньому кроці розбиття, буде однаковою. При цьому встановлюється функціональний зв'язок між номером кроку розбиття й числом підмножин у розбитті на цьому кроці.

Ваги цифр, які належать до одного розряду числа, у цьому випадку ''рівні'' між собою, однак вони на відміну від однорідних систем числення ''змінюються'' від розряду до розряду не за степеневим законом, як це відбувається для однорідних систем числення, а за більш складним. Числа для неоднорідних систем числення з такими обмеженнями мають, як і для однорідних, рівну довжину. Прикладом таких систем числення є факторіальні, а в більш загальному випадку системи зі змішаною основою, чи поліадичні.
На рис. 1.1 у вигляді блок-схеми наведена класифікація позиційних систем числення.
[[Файл:Класифікація_позиційних_систем_числення.png|стандартно|центр|700пкс|]]
<p align="center" >рис. 1.1 </p>


Таким чином, позиційні системи числення розподіляються на два великих класи&nbsp;— '''''однорідні''''' (з рівною довжиною чисел і основою в вигляді натурального числа) і '''''неоднорідні''''' (з рівною та нерівною довжиною чисел і більш складною основою, ніж натуральні числа). Однорідні системи числення відповідно до числа, яке взяте за їх основу, у свою чергу, поділяються на двійкові, трійкові, десяткові й т.д. Неоднорідні поділяються на системи зі ''змішаною'' основою, або поліадичні, і ''структурні''&nbsp;— з числовою або функціональною основою. Останні, у свою чергу, поділяться на ''комбінаторні'' і ''табличні''.

Всі позиційні системи числення без винятку можуть бути подані у вигляді дерев розбиття, вершини яких відображають кількість елементів у підмножинах, що розбиваються, а гілки&nbsp;— номери, що кодують підмножини, які виникають після розбиття. При цьому послідовності цих номерів утворюють числа позиційних систем числення. Номери в даному випадку є цифрами чисел.

== Визначення ==
У позиційній системі числення з основою ''b'' число подають у вигляді [[Векторний простір|лінійної комбінації]] [[Степінь|степенів]] числа ''b'':
: <math>x = \sum_{k=0}^n a_k b^k</math>, де <math>a_k</math> і <math>k</math> — цілі, <math>0 \leq |a_k| < |b|</math>

Основа позиційної системи числення не обов'язково повинна бути натуральним числом, узгоджену систему числення можна створити на основі відємного [[Цілі числа|цілого числа]], або із [[ірраціональні числа|ірраціональною базою]] (наприклад на основі [[золотий переріз|золотого перерізу]]).

=== Симетричні позиційні системи числення ===
Такі системи числення відрізняються тим, що використовують цифри не із множини натуральних чисел <math>(0, \ldots, b-1)</math>, а із множини цілих чисел <math>(-\frac{b-1}{2}, -\frac{b-3}{2}, \ldots, \frac{b-1}{2})</math>. Щоб цифри були цілими, потрібно, щоб ''b'' було непарним. У симетричних системах числення не вимагається додаткових позначень для знака числа. Крім цього, обчислення у симетричних системах зручні тим, що немає особливих правил [[округлення]], яке зводиться до простого відкидання зайвих розрядів, що різко зменшує систематичні помилки обчислень.

Найчастіше використовується симетрична [[трійкова система числення]] із цифрами <math>\{-1, 0, 1\}</math> або <math>\{\bar{1},0,1\}</math>. Вона застосовується у [[Трійкова логіка|трійковій логіці]] і була технічно реалізована в обчислювальній машині [[Сетунь (комп'ютер)|«Сетунь»]].

==== Приклади ====
Наприклад, число «тисяча п'ятсот вісімдесят сім» представляється у десятковій системі числення у вигляді:
: <math> 1587 = 1 \cdot 10^{3} + 5 \cdot 10^{2} + 8 \cdot 10^{1} + 7</math>.
А число «одна друга»:
: <math> 0{,}5 = 0 \cdot 10^{0} + 5 \cdot 10^{-1}</math>.
Використовуючи позиційний принцип, ми можемо зобразити будь-яке [[Дійсні числа|дійсне число]] за допомогою усього лиш десяти цифр у їх різних комбінаціях.

У системі із основою <math>(-10)</math> число «одинадцять» буде виглядати так:
: <math> 11 = 1 \cdot (-10)^{2} + 9 \cdot (-10)^{1} + 1 \cdot (-10)^{0} = 100 - 90 + 1</math>.
Числа «один» і «два» у симетричній системі <math>\{\bar{1},0,1\}</math> з базою <math> \phi=(1+\sqrt{5})/2</math> виглядають так:
: <math> 10{,}\bar{1} = 1 \cdot \phi^{1} + \bar{1} \cdot \phi^{-1} \approx 1{,}618 - 0{,}618</math>.
: <math> 100{,}\bar{1} = 1 \cdot \phi^{2} + \bar{1} \cdot \phi^{-1} \approx 2{,}618 - 0{,}618</math>.


Також поширені системи числення з основами:
* 2 — [[Двійкова система числення|двійкова]] (у [[Дискретна математика|дискретній математиці]], [[Інформатика|інформатиці]], [[Програмування|програмуванні]])
* 8 — [[Вісімкова система числення|вісімкова]] (у [[Програмування|програмуванні]])
* 12 — [[дванадцяткова система числення|дванадцяткова]] (мала широке застосування у давнину, подекуди використовується і нині)
* 16 — [[шістнадцяткова система числення|шістнадцяткова]] (поширена у [[Програмування|програмуванні]], а також для кодування [[шрифт]]ів)
* 60 — [[шістдесяткова система числення|шістдесяткова]] (для [[Градус, мінута, секунда|виміру кутів]] і, зокрема, [[Довгота|довготи]] і [[Широта|широти]])

== Запис ==
Для запису чисел системи числення з основою до 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&nbsp;=&nbsp;10, b&nbsp;=&nbsp;11 і&nbsp;т.д.

За одночасної роботи із кількома системами числення для їх розрізнення основи систем зазвичай вказують нижнім індексом, який записується у десятковій системі:
:<math>453_{10}</math> — це число 453 у десятковій системі числення;
:<math>111000101_2</math> — те ж число, але у двійковій системі;
:<math>705_8</math> — те ж число, але у вісімковій системі.

У деяких спеціальних галузях застосовуються особливі правила вказування основи. Наприклад, у програмуванні шістнадцяткова сиситема позначається:
* у [[Асемблер|мові асемблера]] і записах загального роду, не прив'язаних до конкретної мови, буквою h (від '''h'''exadecimal) у кінці числа (синтаксис Intel) — 75h (<math>453_{10}</math>);
* у [[Pascal (мова програмування)|Паскалі]] знаком «$» на початку числа;
* у [[C (мова програмування)|Ci]] і багатьох інших мовах комбінацією 0x або 0X (від he'''x'''adecimal) на початку.

== Властивості ==
Позиційна система числення має такі властивості:
# Основа системи числення у ній самій завжди записується як 10. Наприклад, у двійковій системі <math>10_2</math> означає число <math>2_{10}</math>.
# Для запису числа ''x'' у системі числення з основою ''b'' потрібно <math>[\log_b(x)] + 1</math> цифр, де <math>[\cdot]</math> — [[ціла частина]] числа.
# Порівняння чисел. Порівняємо два числа 516 і 561. Для цього зліва направо порівнюємо цифри, які стоять на однакових позиціях: 5&nbsp;=&nbsp;5 — результат порівняння не визначений; 1&nbsp;<&nbsp;6 — перше число менше незалежно від цифр, що залишились.
# Додавання чисел. Додамо 516 і 221. Для цього справа наліво додаємо цифри, що стоять на однакових позиціях:
#* 6&nbsp;+&nbsp;1&nbsp;=&nbsp;7
#* 1&nbsp;+&nbsp;2&nbsp;=&nbsp;3
#* 5&nbsp;+&nbsp;2&nbsp;=&nbsp;7
#* загалом — 737.

Таким самим чином можна додавати числа довільної довжини.

== Перехід до іншої основи ==
=== Переведення довільної позиційної системи числення до десяткової ===
Якщо число у системі числення з основою ''b'' дорівнює
: <math>a_1\;a_2\;a_3 \ldots a_n,</math>
то для переведення його до десяткової системи обчислюють наступну суму:
: <math>\sum_{i=1}^n a_i\cdot b^{n-i}</math>
або, більш наглядно:
: <math>a_1\cdot b^{n-1} + a_2 \cdot b^{n-2} + \ldots + a_{n-1} \cdot b^1 + a_n \cdot b^0,</math>
або, нарешті, у вигляді [[Схема Горнера|схеми Горнера]]:
: <math>((\ldots(a_1 \cdot b + a_2) \cdot b + a_3) \ldots ) \cdot b + a_n.</math>

==== Приклад ====
:<math>101100_2=</math>
::= 1 · 2<sup>5</sup> + 0 · 2<sup>4</sup> + 1 · 2<sup>3</sup> + 1 · 2<sup>2</sup> + 0 · 2<sup>1</sup> + 0 · 1 =
::= 1 · 32 + 0 · 16 + 1 · 8 + 1 · 4 + 0 · 2 + 0 · 1 =
::= 32 + 8 + 4 + 0 = 44<sub>10</sub>

=== Переведення із десяткової до довільної позиційної системи числення ===
Для переведення потрібно ділити число із залишком на основу системи числення допоки частка не стане меншою за основу.

==== Приклад ====
:<math>44_{10}</math> переведемо до двійкової системи
 44 ділимо на 2; частка 22, залишок 0
 22 ділимо на 2; частка 11, залишок 0
 11 ділимо на 2; частка  5, залишок 1
  5 ділимо на 2; частка  2, залишок 1
  2 ділимо на 2; частка  1, залишок 0
Частка менша двох, ділення закінчено. Тепер записуємо останню частку від ділення і усі залишки, починаючи з останнього, зліва направо, отримаємо число <math>101100_2</math>.

=== Переведення із двійкової у вісімкову і шістнадцяткову системи і навпаки ===
Для цього типу операцій існує спрощений алгоритм.

Для вісімкової — розбиваємо числа на триплети, перетворюючи триплети згідно з таблицею
 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

==== Приклад 1 ====
Перетворимо 101100<sub>2</sub>
: у вісімкову — 101 100 → 54<sub>8</sub>
: у шістнадцяткову — 0010 1100 → 2C<sub>16</sub>

==== Приклад 2 ====
Перетворимо до двійкової системи
: 76<sub>8</sub> → 111 110
: 3E<sub>16</sub> → 0011 1110

== Див. також ==
* [[Система числення]]
* [[Непозиційні системи числення]]
* [[Від'ємна основа|Нега-позиційна система числення]]
* [[Таблиця множення]]
== Посилання ==
* {{УСЕ-4|[http://slovopedia.org.ua/29/53409/20582.html Система числення позиційна]}}
{{Без джерел|дата=травень 2016}}
{{ВП-портали|Математика|}}
[[Категорія:Системи числення]]
[[Категорія:Позиційні системи числення| ]]