Паскаль. Прикладне програмне забезпечення


Позиційні системи числення

1.1. Запис натуральних чисел

Система Числення – це система запису, або позначення, чисел. Найдосконалішими системами числення виявилися Позиційні. У цих системах число, позначене цифрою, залежить від її місця позиції в записі числа. Наприклад, звичні нам записи 13 і 31 у десятковій системі складаються з однакових цифр значків 1 і 3, але позначають різні числа 1 10+3 і 3 10+1.

Позиційна Система Числення З Основою P Pкова має P цифр C0, C1, , CP1, що звичайно позначають натуральні числа від 0 до P1. Ці записи та позначені ними числа – Значення Цих записів – називаються Однорозрядними Pковими.

Цифри десяткової системи 0, 1, 2, , 9 називаються арабськими, хоча й були запозичені арабами в індусів.

У програмуванні широко застосовується шістнадцяткова система, в якій перші 10 цифр арабські, а наступні шість – A, B, C, D, E, F. Вони позначають числа, десятковий запис яких 10, 11, 12, 13, 14, 15 відповідно.

Число P у PКовій системі позначається дворозрядним записом C1 C0, число P+1 – записом C1 C1 тощо до P P1. Наприклад, 10, 11,..., 99 у десятковій системі, 10, 11 у двійковій, 10, 11, , 1F, 20, , FF у 16ковій. Число P P позначається вже трьома цифрами C1 C0 C0, далі йде C1 C0 C1 тощо. Наприклад, 100, 101, , 999 у десятковій системі, 100, 101, 110, 111 у двійковій, 100, 101, , FFF у 16ковій. І взагалі, запис вигляду

Akak1 A1 A0 P

Позначає в Pковій системі число, що є значенням полінома

Ak Pk+ Ak1 Pk1+ + A1 P+ A0.

Наприклад, двійковий запис 100112 позначає число, яке в десятковому записі має вигляд 1 24+0 23+0 22+1 21+1 20=19. 16ковий запис 1BC16 позначає десяткове 1 162+11 16+12=444.

Найправіша цифра в запису числа позначає кількість одиниць і називається Молодшою, найлівіша – кількість чисел Pk І називається Старшою.

Ми звикли до десяткового подання чисел, і саме воно, головним чином, використовується в Паскальпрограммах, але в комп'ютері числа, як правило, подаються в двійковій системі. Таким чином, виникає необхідність створювати двійкове подання числа за його десятковим записом і навпаки. Зауважимо до речі, що такі перетворення записів чисел з однієї системи в іншу здійснюються при виконанні процедур читання і запису readln і writeln.

За Pковим записом Akak1 A1 A0 P натурального числа N можна побудувати десяткове подання, обчисливши значення полінома за допомогою операцій множення та додавання в десятковій системі. Саме цим ми займалися двома абзацами вище.

Розглянемо, Як одержати за натуральним числом N цифри його Pкового подання. Нехай N= Akak1 A1 A0 P, і кількість цифр K+1 невідомі. Запишемо подання в такому вигляді:

N = ak Pk+ Ak1 Pk1+ + A1 P+ A0 = Ak P+ Ak1 P+ + A1 P+ A0.

Звідси очевидно, що значенням A0 є N Mod P, A1 – N Div P Mod P Тощо. Таким чином, якщо поділити N на P у стовпчик, то остача від ділення буде значенням молодшої цифри. Потім можна так само поділити на P частку від першого ділення – остача буде виражати кількість Pкових десятків тощо поки остання частка не виявиться менше P. Вона й буде значенням старшої цифри. При P10 ще треба перетворити числа більше 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. A1 A2 , де Ai Pкові цифри. Цей запис позначає дійсне число – значення виразу

A1 P1+ A2 P2+

Наприклад, 0.11012 позначає десяткове

1 21+1 22+0 23+1 24=0.5+0.25+0.0625=0.8125;

0.213 – 2 31+1 32=0.777=0.7; 0.BC16 – 11 161+12 162=0.734375.

За Pковим поданням, у якому задано R старших цифр, Десятковий запис числа утворюється обчисленням значення многочлена

A1 P1+ A2 P2+ + Ar Pr.

Нагадаємо, що якщо основа P має прості дільники, відмінні від 2 і 5, то число зі скінченним Pковим записом зображується нескінченним, але періодичним десятковим дробом. Якщо ж простими дільниками P є тільки 2 і 5, то й десятковий дріб скінченний.

Розглянемо, Як за дійсним значенням V одержати цифри його Pкового подання. Нехай V=0. A1 A2 P. Запишемо подання в такому вигляді:

V= P1 A1+ P1 A2+.

Тоді V P= A1+ P1 A2+, звідки очевидно, що A1= V P , і P1 A2+ = { V P}, де V P та { V P} позначають цілу та дробову частини V P. Помноживши { V P} на P і узявши цілу частину, одержимо A2 тощо. Наприклад, при V=0.75, P=3 одержимо

A1= 0.75 3 =2, {0.75 3}=0.25, A2= 0.25 3 =0, {0.25 3}=0.75 тощо.

Таким чином, трійковим поданням 0.75 буде нескінченний періодичний дріб 0.203.

Маючи дійсне значення V, V1, можна одержати R перших цифр його Pкового подання, виконавши алгоритм

For i:= 1 To r Do

Begin

V:= VP;

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