ПАСКАЛЬ:ПОДАННЯ ЧИСЕЛ ТА ІНШИХ ЗНАЧЕНЬ

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<порядок><мантиса>.

Поле <знак> має довжину 1, а довжини двох інших позначимо d і r
відповідно. Зрозуміло, що 1+d+r=8N. Нехай s, e, m – значення цих полів
як беззнакових цілих. Вони подають:

s = 0 – знак ‘+’, s = 1 – знак ‘-‘;

e – його порядок t = e — (2d-1-1);

m – мантису (дробову частину) m1 = m? 2–r.

За значень e, відмінних від крайніх значень 0 та 2d-1, поля
<знак><порядок><мантиса> задають число, що є значенням виразу

(-1)s? (1+m1)? 2t (11.2)

Оскільки 1? 1+m1<2, то кажуть, що число подається в нормалiзованому виглядi. Показник t називається справжнім порядком числа, а e – "зсуненим" (він на 2d-1-1 більше від справжнього). Отже, значення e від 1 до 2d-2 задають справжні порядки t від 1-(2d-1-1)=2-2d-1 до 2d-2-(2d-1-1)=2d-1-1. Наприклад, нехай d=5, r=10, що задає двобайтове подання. Зсув порядку 25-1-1=24-1. Розглянемо зображення числа -12.375: -12.375 = (-1100.011)2 = (-1.100011)2? 23 , тобто t=3, m1=0.100011. Звідси s=1, e=3+(24-1)=18=(10010)2, m=1000110000, і число подається послідовністю бітів 1'10010'1000110000. Тут для наочності поля відокремлено апострофами. Послідовність бітів 0'00001'0000000000 подає мінімальне додатне число, зображуване за d=5, r=10: (1 + 0)? 21-24+1 = 2-14. Наступним числом, що подається як 0'00001'0000000001, буде (1+2-10) ? 21-24+1=2-14+2-24. Послідовність бітів 0'11110'11111111111 подає максимальне число (1+(210-1)? 2-10)? 225-2-24+1 = (2-2-10)? 215 =216 - 25 = 65504. Попереднє перед ним число має подання 0'11110'11111111110 і є (1+(210-2)? 2-10)? 225-2-24+1 = (2-2-9)? 215 =216 - 26 = 65472. Як бачимо, різниця між двома сусідніми числами міняється від 2-24 до 25=32. За e=0 незалежно від s і m подається число 0. За e=2d-1 подання числа використовуєтьсся спеціальним чином, про що ми говорити не будемо (докладніше про це див., наприклад, [Григ]). Зазначимо, що розташування й довжини полів у поданні дійсних чисел залежать від конкретного типу комп’ютера і можуть відрізнятися від указаних тут. Можливі й інші особливості. Задачі 8. Нехай a і b – імена змiнних бульового типу. Довести еквівалентнiсть виразів у наступних парах: а) a <= b та not a or b; б) a < true та not a. 9.* Указати внутрішнє подання символів, заданих виразами: а) chr(0), chr(48), chr(57), chr(13), chr(10), chr(65), chr(97); б) 20h, 30h, 1Ah, 1Bh, де суфікс "h" указує на шістнадцятковий запис. 10. Написати програму, яка для комп'ютера з невідомою системою подання чисел дозволяє визначити максимальне та мінімальне цілі типу integer. 11.* Указати двобайтовий додатковий код чисел -1, -8, -9, -32767, -32768. 12.* Нехай при додаваннi та відніманнi чисел типу integer перенос із старшого розряду стає змістом знакового розряду, а перенос із знакового розряду втрачається. Чому дорівнює значення виразу: а) maxint + 1; б) minint - 1, де maxint та minint позначають максимальне та мінімальне числа типу integer? 13.* Обчислити мінімальне та максимальне за модулем скінченні дійсні числа, що подаються в а) 4 байтах за d = 8, r = 23; б) 8 байтах за d = 11, r = 52; в) 10 байтах за d = 16, r = 63. 14. Нехай d і r з описання подання дійсних чисел невідомі. Написати програму а) обчислення d і r; б) друкування виразів, що задають мінімальне та максимальне додатні числа типу real; в) друкування виразу різниці між двома сусідніми зображуваними числами з відрізка [2i; 2i+1] за допустимих значень i. 3. Цілі та дійсні типи мови Турбо Паскаль Базовий тип цілих integer утворено цілими, які займають 2 байти в знаковому поданні. Тепер уже зрозуміло, чому їх діапазон від -32768 до 32767. Крім цього типу, в мові Турбо Паскаль є ще кілька типів для подання цілих. Укажемо їх імена, спосіб (знаковий/беззнаковий) та розміри подання в байтах, а також їх діапазони. Тип Byte – беззнакові в 1 байті, 0..255. Тип Shortint – знакові в 1 байті, -128..127. Тип Word – беззнакові в 2 байтах, 0..65535. Тип Longint – знакові в 4 байтах, -2147483648..2147483647. Для всіх цих типів означено всі операції, що й для типу Integer. Числа базового типу Real займають 6 байтів. 1 біт зайнятий знаком числа, 39 – дробовою частиною, 8 – порядком. Нескладно підрахувати, що діапазон додатних чисел – від 2-126? 2.9? 10-39 до (2-2-39)? 2127? 1038. Значення типу Single займають 4 байти (дробова частина – 23 біти, порядок – 8). Діапазон додатних значень – від 2-126 до (2-2-23)? 2127? 1038. Значення типу Double займають 8 байтів (дробова частина – 52 біти, порядок – 11). Відзначимо, що з урахуванням особливостей архітектури сучасних комп'ютерів краще користуватися цим типом, ніж типом real [Григ]. Діапазон додатних значень – від 2-1022? 10-315 до (2-2-52)? 21023? 10315. Значення типу Extended займають 10 байтів (дробова частина – 64 біти, порядок – 15). Діапазон додатних значень – від 2-16382? 10-4931 до ? 2? 216383? 104932. Відзначимо, що в процесорі комп'ютера числа обробляються саме в поданні типу Extended. При записі в регістри процесора числа з інших типів перетворюються в цей. Отже, цей тип має найбільший серед дійсних типів діапазон та найвищу точність подання дійсних чисел. Значення типу Comp (скорочене compound – складений) займають 8 байтів. Ці значення є дійсними поданнями цілих чисел від -263 до +263-1. До них застосовні операції дійсних, а не цілих типів. І останнє зауваження. Кількість байтів, які займаються значеннями будь-якого типу, можна дізнатися, викликавши функцію SIZEOF. Наприклад, із виклику sizeof(Longint) повертається 4, із виклику sizeof(Word) – 2. Задачі 15. У діалекті Турбо Паскаль на цілих типах визначена операція "додавання за модулем 2" із знаком xor. Вона виконується шляхом побітового додавання операндів за правилами 0? 0=1? 1=0, 1? 0=0? 1=1, тобто без переносу 1 у наступний розряд. Наприклад, у типі Byte 220 xor 127 =163 – це добре видно в байтовім поданні: ? 11011100 01111111 10100011 Довести її властивості: якщо a, b, c позначають довільні цілі операнди, то a xor a = 0, a xor 0 = a, a xor b = b xor a, (a xor b) xor c =a xor (b xor c), (a xor b) xor b = a.

Похожие записи