Алгоритми арифметичних операцій над цілими невід’ємними числами у десятковій системі числення.

Ми розглянули означення арифметичних дій додавання, віднімання, множення та ділення, а також властивості цих дій. Розглянуті нами означення та властивості не залежать від способу зображення чисел. Разом з тим, виявляється, що техніка виконання арифметичних дій залежить від способу зображення чисел або, як кажуть, від системи числення чи нумерації чисел. У зв’язку зі сказаним постає питання: що ж таке система числення чи нумерація?

Позиційні та непозиційні системи числення, запис чисел у позиційних і непозиційних системах числення.

ПЛАН.

МОДУЛЬ ІУ. «СИСТЕМИ ЧИСЛЕННЯ. ПОДІЛЬНІСТЬ ЧИСЕЛ.».

Змістовний модуль 4.1. «Системи числення.».

1. Позиційні та непозиційні системи числення, запис чисел у позиційних і непозиційних системах числення.

2. Алгоритми арифметичних операцій над цілими невід’ємними числами у десятковій системі числення.

3. Запис чисел у позиційних системах числення, відмінних від десяткової. Арифметичні операції над числами у недесяткових позиційних системах числення. Перехід від запису чисел в одній позиційній системі числення до запису в іншій позиційній системі числення.

ЛІТЕРАТУРА:[1] – с. 141-155; [2] – с. 162-192; [3] – с. 271-289.

Означення: системою числення або нумерацією називається сукупність правил, знаків або слів, за допомогою яких можна зобразити письмово чи назвати усно будь-яке число.

Таким чином, система числення (у подальшому викладі для економії місця будемо використовувати скорочену абревіатуру СЧ) або нумерація – це спосіб запису і читання чисел. Саме тому розрізняють усну та письмову нумерації.

Означення: ціле невід’ємне число, зображене у певній системі числення називають системним або систематичним числом.

Досить цікавим є питання про те, коли з’явилися системи числення та якими вони бувають. З історії математики відомо, що СЧ з’явилися дуже давно, тоді, коли з’явилася писемність. Всі СЧ за своєю «граматичною» побудовою поділяються на дві великі групи: позиційні та непозиційні.

Непозиційні СЧ характеризуються тим, що кожен знак із множини знаків, що використовуються для позначення чисел у даній СЧ, завжди позначає одне й теж саме число незалежно від позиції (місця), яку він займає у запису числа. Так, наприклад, непозиційною системою числення є римська нумерація, в якій використовуються такі знаки або цифри для позначення чисел: І -1, У – 5, Х – 10, L – 50, C – 100, D – 500, M – 1000 тощо. У наш час непозиційні системи числення використовуються досить рідко. Слід також відзначити, що навіть римська система числення набула у процесі свого розвитку певних змін і стала адитивною. Це означає, що при записі чисел в цій СЧ використовуються певні правила, а саме: якщо менше число стоїть у запису перед більшим, то його слід віднімати від більшого, наприклад: ІХ – це 10-1=9; якщо менше число стоїть у запису після більшого, то його слід додавати до більшого, наприклад: ХІ це 10+1=11.

У позиційних системах числення кожна цифра в залежності від місця, яке вона займає у запису числа, позначає різне число. Так, наприклад, у числі 23242 маємо у записі три цифри 2, причому перша зліва позначає 2 десятки тисяч (20000), друга – 2 сотні одиниць (200), а третя – 2 одиниці. Найпоширенішою нині є десяткова позиційна система числення, яка, як вважають історики математики, виникла у ІІІ столітті в Індії. Цифра 0 (нуль), на думку дослідників історії математики, вперше зустрічається у УІІІ столітті. Араби запозичили цю систему числення і привезли її у ІХ столітті в Європу, де вона почала поширюватися під назвою арабської та стала загальновживаною у ХУ столітті. Скільки ж ще існувало позиційних систем числення, відмінних від десяткової? Є факти, що дають підстави твердити: позиційних систем числення було чимало. Так, і досі, у повсякденному житті ми зустрічаємося із залишками таких позиційних систем числення як шестидесятіркова (1 год. = 60 хв, 1 хв = 60 с, 1 копа снопів дорівнює 60 снопам тощо), дванадцятіркова (1 дюжина дорівнює 12) тощо.

Що ж спільного у записі чисел у позиційних системах числення? – для запису чисел використовується скінченна кількість знаків-цифр, причому залежно від системи числення кількість цифр є різною. Так, у десятковій позиційній системі числення для запису будь-якого числа використовується всього десять знаків-цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. для називання всіх чисел використовується також скінченна кількість слів. Так, для називання чисел, що вивчаються у початкових класах, використовуються слова: нуль, один, два, три, чотири, п’ять, шість, сім, вісім, дев’ять, десять, сорок, сто, тисяча, мільйон, мільярд, тобто шістнадцять нових слів, а решта утворюється із названих, наприклад: два-на-дцять, дев’яно-сто, одна тисяча п’ятсот шістдесят вісім тощо.

Що ж таке число у позиційній системі числення? – це всяка скінченна послідовність цифр, причому кожна цифра в цьому записі означає відповідну кількість одиниць того чи іншого розряду. Розряди називають перший, другий, третій тощо. Для зручності розряди об’єднують по три, називаючи їх класами. Так, перший клас, що об’єднує перші три розряди, називають класом одиниць, другий клас – класом тисяч, третій - класом мільйонів, четвертий – класом мільярдів тощо. Наприклад, число 2345=2000+300+40+5=2·1000+3·100+4·10+5=2·10³+3·10²+4·10¹+5·10º. У цьому записі особливу роль відіграє число 10, яке називають основою десяткової позиційної системи числення. Існують СЧ з іншими основами, наприклад: СЧ, основою якої є число 2, називають двійковою. Для запису чисел у цій системі числення використовують всього дві цифри 0 і 1; у трійковій системі числення використовується три цифри: 0,1,2; у дванадцятірковій системі числення основою є число 12, а тому для запису чисел використовується дванадцять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, (10), (11), причому дві останні цифри взято в дужки, щоб відрізняти їх від запису двоцифрових чисел 10 і 11. Таким чином, щоб визначити, скільки цифр використовується для запису чисел у тій чи іншій позиційній системі числення потрібно визначити її основу. Так, у шестидесятірковій системі числення використовується для запису чисел шістдесят цифр: 0, 1, 2, … (58), (59). У загальному випадку у системі числення з основою q використовується q-1 цифра, якщо не рахувати цифру 0.

Як же відрізнити запис числа в одній позиційній системі числення від запису в іншій? – для цього справа знизу пишуть індексом основу системи числення (за винятком десяткової!), наприклад: 1012₃, 1(11)123(10)5₁₂, 123456 тощо. Відповідь на запитання «а чи всяке натуральне число можна записати у вказаній позиційній системі числення?» дає наступна теорема.

Теорема: будь-яке натуральне число можна зобразити у довільній позиційній системі числення і до того ж єдиним чином.

Доведення: оскільки у формулюванні теореми говориться про існування та єдиність зображення, то її доведення складатиметься з двох частин. У першій частині доведемо існування такого зображення, а у другій – його єдиність. Для доведення існування зображення використаємо теорему про існування частки та остачі. Розглянемо деяке натуральне число а в позиційній системі числення з основою q. Між числами а і q можливе одно із трьох співвідношень: 1) а<q; 2) а=q; 3) а>q. Розглянемо поступово всі три випадки. Якщо а<q, то тоді в системі числення з основою q ми маємо одноцифрове число а. Отже, зображення числа а існує. Якщо а=q, то ми маємо найменше двоцифрове число цієї системи числення, яке зображатиметься так: а=10_q. Отже, і в цьому випадку зображення існує.

Нехай а>q. Тоді згідно з теоремою про існування частки і остачі існує два числа g₀ і r₀ такі, що а=q•g₀+r₀, де 0≤r₀<q. Якщо g₀<q, то ми будемо мати двозначне число а=q•g₀+r₀=g₀r₀. Якщо ж g₀>q, то поділивши g₀ на q, одержимо рівність g₀=q•g₁+r₁, а тоді а=q•(q•g₁+r₁)₀+r₀=q²•g₁+r₁q+r₀=g₁r₁r₀. Якщо g₁>q, то поділивши g₁ на q, одержимо g₁=q•g₂+r₂, а тоді а=q²•(q•g₂+r₂)+r₁q+r₀=q³•g₂+q²r₂+r₁q+r₀. Якщо g₂<q, то число а=g₂r₂r₁r₀. Цей процес буде продовжуватися доти, доки не отримаємо g_n<q. Таким чином, отримаємо запис: а=g_n•qⁿ+r_n-1•q^n-1+r_n-2•q^n-2+…+r₂•q²+r₁•q¹+r₀=r_ng_n-1r_n-2…r₂r₁r₀, де r_n, r_n-1, r_n-2,…,r₂, r₁, r₀ – цифри числа а. Отже, зображення числа а у системі числення з основою q існує. Першу частину теореми доведено.

Другу частину теореми про єдиність такого зображення доведемо методом від супротивного. Припустимо, що існує два різних способи зображення числа а у системі числення з основою q, а саме: а=а_n•qⁿ+а_n-1•q^n-1+а_n-2•q^n-2+…+а₂•q²+а₁•q¹+а₀ і а=в_k•q^k+в_k-1•q^k-1+в_k-2•q^k-2+…+в₂•q²+в₁•q¹+в₀, де а_n, а_n-1, а_n-2, …, а₂, а₁, а₀, в_k, в_k-1, в_k-2, …, в₂, в₁, в₀ - цифри числа а у першому та другому зображеннях. Припустимо для визначеності, що n>k. Тоді а=а_n•qⁿ+а_n-1•q^n-1+а_n-2•q^n-2+…+а₂•q²+а₁•q¹+а₀=в_k•q^k+в_k-1•q^k-1+в_k-2•q^k-2+…+в₂•q²+в₁•q¹+в₀. Нехай у цих записах різні цифри одиниць, тобто а₀≠в₀. Для визначеності виберемо, що а₀>в₀. Тоді знайдемо різницю а₀-в₀=(в_k•q^k+в_k-1•q^k-1+в_k-2•q^k-2+…+в₂•q²+в₁•q¹)-(а_n•qⁿ+а_n-1•q^n-1+а_n-2•q^n-…+а₂•q²+а₁•q¹)=q((в_k•q^k-1

+в_k-1•q^k-2+в_k-2•q^k-3+…+в₂•q¹+в₁)-(а_n•q^n-1+а_n-1•q^n-2+а_n-2•q^n-3+…+а₂•q¹+а₁)). За умовою а₀<q і в₀<q, а тоді а₀-в₀<q. Отже, а₀-в₀ не ділиться націло на q, у той час як права частина рівності q((в_k•q^k-1+в_k-1•q^k-2+в_k-2•q^k-3+…+в₂•q¹+в₁)-(а_n•q^n-1+а_n-1•q^n-2+а_n-2•q^n-3+…+а₂•q¹+а₁)) ділиться націло на q. Таким чином, якщо менше за q число (а₀-в₀):q, то це можливо за умови а₀-в₀=0, тобто а₀=в₀. А це суперечить вибору а₀ і в₀. Аналогічно можна довести, що і при а₁≠в₁, а₂≠в₂, …, а_k≠в_k ми прийдемо до суперечності з вибором цих чисел, тобто одержимо, що а₁=в₁, а₂=в₂, …, а_k=в_k. Це означає, що а_k+1=а_k+2=а_k+3=…=a_n=0. Отже, якщо зображення існує, то воно єдине. Теорему доведено повністю.

Вправа: запишіть число 34210321₅ у вигляді суми розрядних доданків у п’ятірковій системі числення.

Розв’язання: у цьому числі є вісім розрядів, а тому найвищий степінь основи системи числення 5 буде сім. Отже, маємо: 34210321₅=3•5⁷+4•5⁶+2•5⁵+1•5⁴+0•5³+3•5²+2•5¹+1•5⁰.

2. Ми вже зазначали, що означення арифметичних операцій та їх властивості не залежать від системи числення, а от техніка виконання операцій змінюється. Саме тому розглянемо сутність техніки виконання операцій над цілими невід’ємними числами в позиційній системі числення. Для успішного виконання арифметичних операцій додавання, віднімання, множення та ділення в усіх позиційних системах числення використовують таблиці додавання, віднімання, множення та ділення. Для прикладу наведемо таблиці додавання одноцифрових чисел у двійковій та дев’ятірковій системах числення (див. таблицю № 4.1.).

Таблиця № 4.1. Таблиці додавання у двійковій та дев’ятірковій системах числення.

Правила додавання багатоцифрових чисел у будь-якій системі числення ґрунтуються на правилі додавання суми до суми. Ці правила дають змогу додавати «в стовпчик», записуючи доданки один під другим та починаючи додавання з нижчих розрядів. Якщо сума одиниць одного розряду перевищує основу системи числення, то на місці цього розряду записують остачу від ділення суми на основу системи числення, а частку додають до наступного розряду. Приклади додавання чисел у п’ятірковій та десятковій системі числення представлені у таблиці № 4.2.

Таблиця № 4.2. Приклади додавання у п’ятірковій та дев’ятірковій системах числення.

Віднімання чисел в системах числення, відмінних від десяткової, також виконується на основі таблиць віднімання, одну із яких представлено у наступній таблиці № 4.3. для системи числення з основою 4. Правило віднімання багатоцифрових чисел базується на таблицях віднімання та на алгоритмі віднімання, який представлено у таблиці № 4.4 для десяткової та шестіркової систем числення.

Таблиця № 4.3. Таблиця віднімання для системи числення з основою 4.

Таблиця № 4.4. Віднімання для систем числення з основами 9 і 6.

Множення у будь-якій позиційній системі числення розпочинається із складання таблиць множення. Так, у шестірковій системі числення таблиця множення матиме вигляд, представлений у таблиці № 4.5. Множення розглядається як додавання однакових доданків. Алгоритм множення в усіх позиційних системах числення однаковий за формою (див. таблицю № 4.6.).

Таблиця № 4.5. Таблиця множення у системі числення з основою 6.

Виконання дій ділення у системах числення, відмінних від десяткової, потребує дуже доброго знання відповідних таблиць множення цієї системи числення, а тому ми обмежимося лише розглядом конкретних прикладів, представлених у таблиці № 4.7. Принагідно зазначимо, що порядок виконання арифметичних операцій у будь-якій позиційній системі числення зберігається.

Таблиця № 4.6. Множення у системах числення з основами 6 і 9.

Таблиця № 4.7. Приклади ділення у дев’ятірковій системі числення.

4224829 249 -24 16529 -156 -132 -48

4824829 2419 -482 20029 -482