Борисенко О.А. Дискретна математика
Подождите немного. Документ загружается.
Дискретна математика
2. Переведення чисел у систему числення з кратною основою
Цей метод ефективний, якщо основи систем числення, які
підлягають перетворенню, кратні між собою. Наприклад, якщо
необхідно перевести десяткове число в п'ятеричну систему числення
чи навпаки. У цьому випадку основа 10 десяткової системи числення
націло ділиться на основу 5 п'ятеричної системи числення.
Наприклад, число 17 з десяткової системи числення у
п'ятеричну можна перевести таким чином:
17
(!0)
=1-10' +7-10° =2-5' +1-5
і
+ 2-5° =3-5' +2-5° = 32
(5)
.
3. Переведення чисел шляхом підбору степенів
Суть цього методу полягає в тому, що число, яке переводять,
подається як сума добутків різних степенів нової основи на можливі
цифри числа, яке отримують. Вони обираються таким чином, щоб ця
сума була якомога ближчою до числа, що переводиться, але не
більшою за нього. При цьому степені нового числа можна обрати з
відповідної таблиці. Коли сума добутків дорівнюватиме вихідному
числу, то новий запис числа буде отриманий.
Наприклад, необхідно перевести десяткове число 123^ у
двійкове. Найбільшим степенем числа 2, який не більший ніж число
123, буде число 2
б
= 64 < 123, оскільки степінь 2
7
= 128 > 123.
Наступним степенем у сумі з попереднім, який не більший ніж число
123, буде 2
5
= 32 (32 + 64 = 98 < 123), потім степінь 2
4
= 16 (16 + 32 +
+ 64= 112 < 123) і 2
3
=8 (8 + 16+ 32 + 64 =120 < 123). Степінь 2
2
=4
необхідно проминути, тому що 4 + 8 + 16 + 32 + 64 = 124 > 123. Проте,
залишається степінь 2
і
= 2, оскільки 2 + 8 + 16 + 32 + 64 = 122 <123.
У кінці додамо 2° =
1
і отримаємо, що
1
+ 2 + 8 +16 + 32 + 64 = 123.
Отже, двійковим числом, яке дорівнює кількісному еквіваленту
числа
123(,
, буде число
1111011
{2)
=1-2
6
+ 1-2
5
+1-2
4
+ 1-2
3
+0-2
2
+
1-2
1
+ 1-2°=123
(ш)
.
Аналогічно можна виконати переведення десяткового числа в
шістнадцятеричну систему числення, наприклад, число 377^ :
213
Борисенко О.А.
377
(10)
=1-16
2
+7-16
1
+9-16° = 256 + 112 + 9 = 179
(|6)
.
Відмінність переведення в шістнадцятеричну систему числення
від переведення у двійкову, розглянутого вище, полягає в тому, що
при переведенні у двійкову систему числення в процесі отримання
суми степенів числа 2 їх множення відбувалося на 1 чи 0 (у випадку
множення на 0 степінь виключався із суми степенів нового числа). У
даному ж випадку кожний новий степінь числа 16 треба послідовно
множити на числа 0, 1, ..., 15 до того моменту, поки серед
отримуваних добутків не виявиться той найбільший, за якого сума
здобутих раніше добутків з даним ще не перевищує початкового
числа, що переводять.
4. Переведення чисел з основою, одна з яких с степенем іншої
У випадку, переведення чисел Із системи числення з основою д,
що є степенем основи р системи числення, в яку відбувається
переведення, тобто д-р"', кожна цифра числа, що переводять, може
бути подана т цифрами в системі числення з основою р, і в
результаті буде отримане необхідне число.
Приклад 1. Дано восьмеричне число 12156^ з д =
8.
Потрібно
перевести його у двійкову систему числення, тобто з р = 2.
Розв'язання. Очевидно, що 8 = 2
3
.
Тому 12156
(8)
=010001101110ф.
У разі зворотного переведення із системи числення з основою
р у систему числення з основою д, р< д, цифри числа, яке
переводять, починаючи з молодших розрядів, об'єднують за т
розрядами й далі записують з допомогою однієї цифри в д-ричній
системі числення.
Приклад 2. Дано двійкове число 111001111111^. Потрібно
перетворити його в шістнадцятеричне.
Розв'язання. Якщо виходити зі співвідношення 2
4
=16,
отримаємо:
1110 0111 1111,,. =Е7Р„
Л
.
214
Дискретна математика
5. Переведення чисел у систему числення
на базі проміжного перетворення цифр
Основою даного методу переведення є числова функція для
позиційних чисел. Відповідно до цієї функції кожна цифра
початкового числа й основа д переводиться в систему числення з
основою р, а потім виконуються всі арифметичні операції, які
передбачені цією функцією.
Приклад 3. Перевести десяткове число 121^ з основою
<7
= 10
у двійкове
з
р = 2.
Розв'язання.
1. Переведемо всі цифри числа й основу <7 = 10 у двійкову
систему числення
1
(ш>
=0001
(2)
, 2
(1о)
=0010
(2)
, Ю
<10>
=1010
{2>
.
2. Обчислимо
(1010)
2
=1010x1010 = 1100100 и 2x10 = 0010x1010 = 10100.
3. Підставимо отримані значення в числову функцію для числа
121^ і отримаємо вираз :
121
(|0)
=М0
2
+ 2-10
1
+]-10° =0001x1100100 + 0010x1010 + 0001x0001 =
= 1100100 +10100 +
0001
= 1111001
(2)
.
Приклад 4. Перевести двійкове число 1001110^ у десяткове.
Розв'язання. Після запису числової функції числа, що
перетворюється у двійкову форму, і після того, як виконали в
десятковому вигляді всі зазначені в ній арифметичні операції,
отримаємо десяткове число, яке шукали:
1001110
{2)
=
1 •
2
6
+ 0
•
2
5
+ 0
•
2
4
+1
•
2
3
+
1 •
2
2
+1
•
2
і
+ 0
•
2° =
= 64 +
8
+ 4 +
2
= 78^.
215
Борисенко О.А.
6. Переведення чисел за допомогою використання
проміжної системи числення
Суть цієї дії полягає в тому, щоб з метою спрощення чи
прискорення переведення застосовувати проміжну систему числення.
Приклад 5. Перевести десяткове число 121
(
ю) у двійкову
систему числення з використанням як проміжної вісімкової системи
числення.
Розв'язання. Перетворимо з допомогою одного з відомих
методів десяткове число 121^ у вісімкову систему числення
121
{10)
=171
(8)-
Потім з вісімкової системи числення перейдемо до двійкової
171
(8>
=1111001
(2)
.
7. Переведення чисел у систему числення шляхом ділення на її основу
Алгоритм переведення чисел' із системи числення З ОСНОВОЮ (] у
систему числення з основою р є універсальним і найбільш широко
використовується на практиці.
Він містить такі кроки:
1. Розділити число, яке переводять, у системі числення з
основою
<7
на основу р за правилом системи числення з основою д.
2. Перевірити, чи не дорівнює частка нулю. Якщо не дорівнює,
то прийняти її за нове число й повернутися до пункту 1.
3. Якщо частка дорівнює нулю, то виписати всі отримані
залишки від ділення в порядку, зворотному їх отриманню.
4. Отриманий запис є записом числа в системі числення з
основою р.
Приклад 6. Перевести число 38^ у п'ятеричну систему
числення
Розв 'язання.
_38 [ 5
35
З
Відповідь. 38^ =123^.
216
Дискретна математика
Приклад 7. Перевести число 1у двійкову систему числення.
Розв'язання
|_2
10
2
Т[2_
0 0
Відповідь. 11
(10)
1011
<2 )•
Приклад 8. Перевести число 1101110^ у десяткову систему
числення шляхом ділення на основу 10.
Розв'язання. Попередньо переведемо число 10 у двійкову
систему числення 10^=1010^.
Потім, якщо використовувати алгоритм перетворення, треба
виконати згідно з ним ділення за правилами двійкової системи
числення:
1101110
1010
1010
1011 1010
0111
1010
0001
1010
0000 0001
0000
0000
1111 0001
1010
_1010
1010
0000
Залишки, які отримано у двійковій системі числення, виписують
послідовно один за одним у порядку, зворотному до порядку їх
отримання, і потім переводять у десяткові цифри:
0000
{2)
=0
(10>
, 0001
(2)
=1
(|0)
, 0001
и
=1,0000
{2)
=о
{10)
.
Послідовність цих цифр утворює десяткове число, яке шукали:
ОНО
(10)
=110Ш0
(2)
.
217
Борисенко О.А.
Приклад 9. Перевести вісімкове число 521/^ у десяткову
систему числення.
Розв'язання. Оскільки 10^ = 1, то, якщо виконувати ділення
десяткового числа 521 за правилами вісімкової системи числення,
отримаємо
521 12
50
_41
12
21
36 3
12
12
3
0
0
7
3
Відповідь. 521^=337^.
Приклад 10. Перевести шістнадцятеричне число 9ВЕ5^ у
десяткову систему числення й виконати перевірку розв'язка.
Розв'язання. Якщо врахувати, що в шістнадцятеричній системі
числення 1= А , то ділимо число 9ВЕ5^щ на А за правилами
шістнадцятсричної системи числення, користуючись при цьому
відповідними таблицями множення й віднімання.
9ВЕ5
А
96
Р96
4
А
А
5 А
_59
Ж.
27
4
_45 50
_4 Р
3
3 С 96
46
9
0
9
96
0
9
3
Відповідь. 9ВЕ5,,
Л
=
39909,
218
Дискретна математика
Перевірка
39909
16
32 _2494
79 \6_
64
89
150
80
144 94
69
80
64
14
5
16
155
16
144 9 16
11
0 0
9
Відповідь. 39909(
ІО>
= 9ЯЕ5
<16)
.
Необхідність введення додаткових символів у
шістнадцятеричній системі числення може спричинити при
переведенні деякі труднощі, оскільки необхідно весь час звертатись до
таблиць віднімання й множення в цій системі.
Ці труднощі можна зменшити, якщо замість символів А, В, С, О,
Е, Р у шістнадцятеричній системі числення скористатися десятковими
цифрами 10, 11, 12, 13, 14, 15 відповідно. При цьому треба
виокремити їх з обох боків у числах крапками. Тоді шістнадцятеричне
число 9ВЕ5^ =9.11.14.5^, а переведення його до десяткової
системи числення буде маги такий вигляд:
9.11.14.5 10
9.6 15.9.6 10
5.14
10
1.8.15
10
5.10
5.9
1.4 2.7
10
4.5 5.0
4.15
1.14 3
10
3.12
9.6
4.6 9
0
0
9
9£
0
9
3
Звертання до таблиць множення й віднімання в цьому випадку
можна уникнути, якщо виконувати безпосереднє переведення із
шістнадцятеричної системи числення у десяткову систему під час
кожної операції множення й віднімання, що може виявитись
простішою задачею, ніж пошуки відповідей у таблицях.
219
Борисенко О.А.
Наприклад, при знаходженні частки від ділення 9.11 на 10 слід
перевести 9.11 із шістнадцятеричної системи числення в десяткову
9-16' +11-16° =155
(І0)
.
Тоді ділення 155 на 10 дасть ціле значення 15, яке й ставимо як
першу цифру частки. Потім після множення 15 на 10 відбувається
переведення числа 1у шістнадцятеричну систему числення
(150^ = 9.6^), і тепер уже це число 9.6^ віднімається від того, що
ділили. Аналогічно можна отримати й цифри інших часток.
Приклад 11. Перевести шістнадцятеричне число 7Ву
десяткову систему числення.
Розв'язання. Подамо число 764^ у вигляді числа 7.11.4 і
розділимо його на А - 10:
_7.11.4
7.8
_3.4
3.2
2
Відповідь. 754,,^ =1972,
16
123 16
112
7
Перевірка.
_1972
16
_37
32 11
_52
48
4
7.11.4
{16)
= 7І?4
(]6>
.
220
Дискретна математика
РОЗДІЛ 3. НЕОДНОРОДНІ СИСТЕМИ ЧИСЛЕННЯ
Лекція 39
ФАКТОРІАЛЬНІ СИСТЕМИ ЧИСЛЕННЯ
1. Загальні положення
Факторіальні системи числення належать до систем зі змішаною
основою.
Зазвичай під факторіальною системою числення розуміють
вираз, який має вигляд:
Р
<ф>
= Х
п
-п\+ Х
п
^-(п-\)\+...
+
Х
г
І\+...
+
Х
г
\\+ Х
о
-0\,
де /=0,1,...,я; 0 <Х,<1.
Він має назву нумераційної, або числової, функції. Максимальне
число у факторіальній системі має вигляд:
Це випливає з нижченаведених перетворень числової функції,
коли X, =1. У цьому разі
Р
=
Р
ітх
=(п
+
1~\)-п)
+
((п-1)
+
1-\)-(п-\)\
+
...
...
+ (/ + 1-1)./! + ...+
(1
+
1-1)-1!
+ (0 +
1-1)-0!
=
= (и + 1)!~л! + и!-(л-1)! + ... + (/ + 1)!-/! +
...
+ 2!-1! +
1-1!
=
= (и + 1)!-1.
Мінімальне число 00...0...0 у факторіальній системі числення
Дійсно, якщо всі розряди X, = 0, то
Р = = 0-л!+0 (я-1)!+... + 0-/!+... + 0-1!+0-0! = 0.
Діапазон факторіальних чисел
221
Борисенко О.А.
При його знаходженні враховується, крім максимального числа,
ще й нуль.
2. Арифметичні операції
При виконанні арифметичних операцій додавання й віднімання
у факторіальній системі числення в нульовому розряді
використовують правила унітарної (одиничної) системи числення, у
першому - двійкової, у другому - трійкової й т.д. Операції множення
й ділення виконуються з допомогою операцій додавання й віднімання
за загальними правилами для однорідних систем числення.
Приклад 1. Виконати операції додавання й віднімання
факторіальних чисел А
<ф>
= 23110 і В
<ф>
=12200.
Розв'язання. Застосовуючи вираз для числової факторіальної
Функції, отримаємо максимальне число:
р
тп
=4
-
4!+3
-
3!+ 2
•
2!+1
•
1.4-0-0! = 119.
Додавання й віднімання чисел виконується таким чином:
23110 _ 23110
12200 12200
42010 10210
Перевірка.
23110
<#>
= 2-4!+3-3!+1-2!+1-1!+0-0! = 69
<10з>
;
12200^ =
1 •
4!+ 2• 3!+ 2
•
2!+ 0-1!+ 0•
0!
= 40
<10>
;
42010^ = 4
•
4!+ 2
•
3!+ 0
• 2 !+1 • 1!+
0
• 0!
= 69
<І0>
+ 40
<ІО>
= 109
<ІО>
;
10210^ =
1 •
4!+ 0• 3!+ 2• 2!+1
• 1!+
0•
0!
= 69
<І0>
-40
<10>
= 29
<ш>
.
3. Перетворення факторіальних чисел в однорідні числа
Перетворення факторіального числа в однорідне виконується
шляхом підстановки факторіального числа в числову (нумераційну)
функцію для факторіальних систем числення. При цьому виконуються
всі вказані в цій функції операції множення і додавання.
222