Сторінка
1
1. Позиційні системи числення 1.1. Запис натуральних чисел Система числення – це система запису, або позначення, чисел. Найдосконалішими системами числення виявилися позиційні. У цих системах число, позначене цифрою, залежить від її місця (позиції) в записі числа. Наприклад, звичні нам записи 13 і 31 у десятковій системі складаються з однакових цифр (значків "1" і "3"), але позначають різні числа 1× 10+3 і 3× 10+1. Позиційна система числення з основою P (P-кова) має P цифр C0, C1, … , CP-1, що звичайно позначають натуральні числа від 0 до P-1. Ці записи та позначені ними числа – значення цих записів – називаються однорозрядними P-ковими. Цифри десяткової системи 0, 1, 2, … , 9 називаються арабськими, хоча й були запозичені арабами в індусів. У програмуванні широко застосовується шістнадцяткова система, в якій перші 10 цифр арабські, а наступні шість – A, B, C, D, E, F. Вони позначають числа, десятковий запис яких 10, 11, 12, 13, 14, 15 відповідно. Число P у P-ковій системі позначається дворозрядним записом C1C0, число P+1 – записом C1C1 тощо до P× P-1. Наприклад, 10, 11, . , 99 у десятковій системі, 10, 11 у двійковій, 10, 11, … , 1F, 20, … , FF у 16-ковій. Число P× P позначається вже трьома цифрами C1C0C0, далі йде C1C0C1 тощо. Наприклад, 100, 101, … , 999 у десятковій системі, 100, 101, 110, 111 у двійковій, 100, 101, … , FFF у 16-ковій. І взагалі, запис вигляду
(akak-1¼ a1a0)P позначає в P-ковій системі число, що є значенням полінома ak× Pk+ak-1× Pk-1+¼ +a1× P+a0. Наприклад, двійковий запис (10011)2 позначає число, яке в десятковому записі має вигляд 1× 24+0× 23+0× 22+1× 21+1× 20=19. 16-ковий запис (1BC)16 позначає десяткове 1× 162+11× 16+12=444. Найправіша цифра в запису числа позначає кількість одиниць і називається молодшою, найлівіша – кількість чисел Pk і називається старшою. Ми звикли до десяткового подання чисел, і саме воно, головним чином, використовується в Паскаль-программах, але в комп'ютері числа, як правило, подаються в двійковій системі. Таким чином, виникає необхідність створювати двійкове подання числа за його десятковим записом і навпаки. Зауважимо до речі, що такі перетворення записів чисел з однієї системи в іншу здійснюються при виконанні процедур читання і запису readln і writeln. За P-ковим записом (akak-1 ¼ a1a0)P натурального числа N можна побудувати десяткове подання, обчисливши значення полінома за допомогою операцій множення та додавання в десятковій системі. Саме цим ми займалися двома абзацами вище. Розглянемо, як одержати за натуральним числом N цифри його P-кового подання. Нехай N=(akak-1 ¼ a1a0)P, і кількість цифр k+1 невідомі. Запишемо подання в такому вигляді: N = ak× Pk+ak-1× Pk-1+¼ +a1× P+a0 = (…(ak× P+ak-1)× P+¼ +a1)× P+a0. Звідси очевидно, що значенням a0 є N mod P, a1 – (N div P) mod P тощо. Таким чином, якщо поділити N на P у стовпчик, то остача від ділення буде значенням молодшої цифри. Потім можна так само поділити на P частку від першого ділення – остача буде виражати кількість "P-кових десятків" тощо поки остання частка не виявиться менше P. Вона й буде значенням старшої цифри. При P>10 ще треба перетворити числа більше 9 у цифри. Наприклад, одержимо цифри 16-кового подання десяткового числа 1022: _1022 | 16 _63 | 16 96 63 48 3 _62 15 48 14 Виділені 14, 15 і 3 – це кількості 16-кових "одиниць", "десятків" і "сотень" відповідно. Позначимо їх 16-ковими цифрами E, F і 3 відповідно та одержимо запис 3FE. Якщо натуральне N подано в базовому типі цілих, то одержати його P-кові цифри можна за наступним алгоритмом (остання цифра утворюється як остача від ділення на P частки, меншої від P): while N > 0 do begin d:= N mod P ; за значенням d побудувати P-кову цифру; N := N div P end Якщо позначити цифрами A, B, … , Z числа від 10 до 35, то з використанням відповіді до задачі 10.5 за цим алгоритмом можна утворити подання чисел аж до 36-кової системи. Для використання ще більших основ систем числення треба додатково розширити алфавіт цифр. 1.2. Дробові числа P-кове подання чисел, менших 1, має вигляд 0.a-1 a-2 ¼ , де a-i – P-кові цифри. Цей запис позначає дійсне число – значення виразу
a-1× P-1+a-2× P-2+ ¼ Наприклад, (0.1101)2 позначає десяткове 1× 2-1+1× 2-2+0× 2-3+1× 2-4=0.5+0.25+0.0625=0.8125; (0.21)3 – 2× 3-1+1× 3-2=0.777…=0.(7); (0.BC)16 – 11× 16-1+12× 16-2=0.734375. За P-ковим поданням, у якому задано r старших цифр, десятковий запис числа утворюється обчисленням значення многочлена
a-1× P-1+a-2× P-2+ … +a-r× P-r. Нагадаємо, що якщо основа P має прості дільники, відмінні від 2 і 5, то число зі скінченним P-ковим записом зображується нескінченним, але періодичним десятковим дробом. Якщо ж простими дільниками P є тільки 2 і 5, то й десятковий дріб скінченний. Розглянемо, як за дійсним значенням V одержати цифри його P-кового подання. Нехай V=(0.a-1a-2…)P. Запишемо подання в такому вигляді: V=P-1× (a-1+P-1× (a-2+¼ )). Тоді V× P=a-1+P-1× (a-2+¼ ), звідки очевидно, що a-1=ë V× Pû , і P-1× (a-2+¼ ) = {V× P}, де ë V× Pû та {V× P} позначають цілу та дробову частини V× P. Помноживши {V× P} на P і узявши цілу частину, одержимо a-2 тощо. Наприклад, при V=0.75, P=3 одержимо
a-1=ë 0.75× 3û =2, {0.75× 3}=0.25, a-2=ë 0.25× 3û =0, {0.25× 3}=0.75 тощо. Таким чином, трійковим поданням 0.75 буде нескінченний періодичний дріб (0.(20))3. Маючи дійсне значення V, V<1, можна одержати r перших цифр його P-кового подання, виконавши алгоритм for i := 1 to r do begin V := V*P; d:= trunc ( V ) ; за значенням d побудувати P-кову цифру; V := V - trunc ( V ) end. 1.3. "1+1=10, 5´ 8=28" Якщо додати 1 і 1, то одержимо 2. Але в двійковій системі це 10, тобто в двійковій системі 1+1=10. При додаванні в стовпчик це означає суму 0 і перенос 1 у наступний розряд. Наприклад, додамо в стовпчик 3 і 6 у двійковій системі: + 11 110 1001 У десятковій системі 10+13=23. Те ж саме в шістнадцятковій виглядає як A+D=17. Взагалі, додаючи дві або більше P-кові цифри, у результаті одержуємо (їх сума) mod P із переносом (їх сума) div P. Наприклад, у шістнадцятковій системі + 9D FAE 104B (неважко перевірити, що при додаванні в стовпчик D+E=1B, 1+9+A=14, 1+F=10). Усі вчаться в школі не тільки додавати, але й множити. Коли ми множимо число в десятковій системі у стовпчик на число, записане одною цифрою X, то обчислюємо добуток чергової цифри числа та X. Остачу від ділення цього добутку на 10 додаємо до переносу від попереднього розряду й одержуємо суму S. Молодшу цифру S, тобто остачу від ділення на 10, записуємо в результат, а старшу, тобто S div 10, запам'ятовуємо як перенос. І так рухаємося від молодшої цифри співмножника до старшої. Знайомо, чи не так? У P-ковій системі відбувається те ж саме, тільки остачі беруться від ділення не на 10, а на P. Наприклад, у шістнадцятковій системі 5´ 8 при діленні на 16 дає остачу 8 і частку 2, тобто 5´ 8=28. У вісімковій системі ´ 1234 7 11102 (4´ 7 при діленні на 8 дає 2 в остачі й 3 у переносі, 3´ 7+3 дає 0 і 3 тощо). Множення на число, у якого більше однієї цифри, зводиться до множень на окремі цифри, запису результатів із зсувом та додавання у стовпчик. Наприклад, у вісімковій системі ´ 77 123 275 176 77 . 12155 Аналогічно в шістнадцятковій системі ´ FE 20A 9EC 1FC . 205EC Задачі 1. За заданими P та P-ковими записами чисел N указати їх десяткове подання: а) P = 16, N = F1, FF, FFFE; б) P = 8, N = 377, 1200; в) P = 2, N = 1000, 1111, 11111111, 100000000. г) P=36, N=ZY, 100 (36-кові цифри A, B, ¼ , Y, Z позначають десятковi числа 10, 11, ¼ , 34, 35 відповідно). 2. За десятковим записом чисел 32, 48, 100, 255, 640, 1024, 32767 указати їх 2-, 8-, 16-кові подання. 3. * Записати P-кове подання десяткових дробів d, де а) d = 0.5, P = 2, 3, 5, 8, 16, 20; б) d = 0.1, P = 2, 3, 5, 8, 16, 20. 4. * За основами P та P-ковими записами дробів указати їх десяткове подання: а) P = 2; 0. 0001; 0. 1111; 0. 11111111; б) P = 3; 0. 001; 0.22; 0.11; в) P = 16; 0.1; 0. FF; 0.8; 0. (7). 5. Написати процедуру друкування цифр P-кового запису числа N, де 1 < P < 37, а) N типу integer (цифри друкуються у зворотному порядку); б) N типу integer (цифри друкуються у прямому порядку); в) N має тип real, N<1 (друкується не більше, ніж R цифр дробової частини, де 0<R<80). Уважати, що за P=36 числа від 10 до 35 позначено відповідно літерами від A до Z. 6. Означити таблиці додавання та множення однорозрядних P-кових чисел при P=2, 4, 8, 16. Написати програму друкування таких таблиць за P від 2 до 20. 7. Написати програму друкування таблиці символів, їх двійкових, шістнадцяткових та десяткових номерів.
Завантажити реферат