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


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

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

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

Задачі

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, N1 друкується не більше, ніж R цифр дробової частини, де 0R80.

Уважати, що за P=36 числа від 10 до 35 позначено відповідно літерами від A до Z.

6. Означити таблиці додавання та множення однорозрядних Pкових чисел при P=2, 4, 8, 16. Написати програму друкування таких таблиць за P від 2 до 20.

7. Написати програму друкування таблиці символів, їх двійкових, шістнадцяткових та десяткових номерів.

2. Внутрішнє подання даних стандартних типів

2.1. Біт, байт та інші

У комп'ютері числа зберiгаються та обробляються в двiйковiй системі числення. Двійкова цифра 0 або 1 відображається станом елемента пам'яті, який вважається неподільним і називається Бiтом. Послідовність із 8 бітів називається Байтом. Байт своїми станами відображає 28=256 комбінацій із 0 та 1, а саме:

00000000

00000001

11111110

11111111

Множині цих комбінацій можна взаємно однозначно поставити у відповідність деякі множини значень: цілі числа від 128 до 127, або числа від 0 до 255, або пари 16кових цифр, або символи від chr0 до chr255 чи якісь інші множини з 256 елементів.

У двох сусідніх байтах подаються 28 28=65536 комбінацій із 0 та 1. Їм взаємно однозначно ставляться у відповідність цілі числа від 0 до 65535, або числа від 32768 до 32767 чи інші множини з 65536 елементів.

Аналогічно чотири сусідні байти відображають 284=4294967296 комбінацій із 0 та 1, яким зiставляються числа від 0 до 4294967295, або числа від 2147483648 до 2147483647 чи інші множини з 4294967296 елементів.

Два байти утворюють одиницю пам'яті, яка називається Словом. Іноді таке слово називається Напівсловом, а словом – послідовність із чотирьох байтів.

Послідовність із 1024 байтів утворює одиницю виміру розмірів пам'яті комп'ютера. Цю одиницю позначають Kбайт, проте це K – латинська літера, що читається кей і позначає не тисячу, а 1024.

Послідовність із 1K Kбайтів, тобто 1048576 байтів, називається Mбайтом. Ці дві одиниці у світі програмістів і користувачів часто не зовсім точно називають відповідно кілобайт і мегабайт, хоча це зовсім не тисяча і не мільйон байтів. До речі, 1Гбайт, хоча й читається гігабайт, позначає не мільярд, а 1073741824 байти.

2.2. Подання цілих чисел, символів та бульових значень

Бульовi значення False та True подаються, як правило, в одному байтi комбінаціями відповідно 00000000 та 00000001.

Символи від chr0 до chr255 зображаються в одному байтi комбінаціями з нулів та одиниць відповідно від 00000000 до 11111111. Наприклад, символ chr32, або ' ' пропуск, зображається як 00100000, символ chr48, або '0', – як 00110000 тощо.

Цілі числа подаються в комп'ютері, головним чином, у двох формах – Беззнаковій та Знаковій. Далі ми Будемо ототожнювати числа з їх поданням, усвідомлюючи, що з точки зору математики це не може бути правильним.

7 0

7 0

7 0

8N1

15 8

7 0

Беззнаковi Числа займають певну кількість N байтiв, яка задає дiапазон множину цих чисел від 0 до 28 N1. Найчастiше N=1, 2 або 4, і діапазони чисел – від 0 до відповідно 255, 65535 та 4294967295. Байти записуються від молодших до старших справа наліво та нумеруються від 0 до N1. Біти всередині байтiв так само записуються від молодших до старших справа наліво й нумеруються від 0 до 7 рис. 11.1. Усього в N байтах є 8 N бітів, які нумеруються справа наліво від 0 до 8 N1. Біти з номерами 8 N1, , 8 N8 утворюють старший байт він ліворуч, а з номерами 7, , 0 – молодший праворуч. Комбінація бітів X8 N1, , X0 зображає в двійковій системі число

X8 N1 28 N1+ X1 2+ X0.

Наприклад, комбінація 00 00 задає число 0, комбінація 00 01 – один, 00 10 – два, 11 11 – число 28 N1.

Таблиця 11.1

Число

Код

28 N1 1

01 11

28 N1 2

01 10

1

00 01

0

00 00

1

11 11

2

11 10

28 N1 + 1

10 01

28 N1

10 00

Знаковi Числа займають ті самі N, тобто 1, 2 або 4 байти. Найстарший біт зображає знак числа: 0 – знак '+', 1 – знак ''. Додатні числа Подаються так само, як i беззнакові, лише за рахунок знакового біта дiапазон їх менший – від 0 до 28 N11. За N=1, 2 або 4 це відповідно 127, 32767 та 2147483647. Таке подання називається Прямим кодом. Наприклад, прямим кодом максимального цілого є 011 1.

Від'ємні числа Подаються в коді, названому Додатковим. Для від'ємного числа A він позначається D A й утворюється так:

1 за прямим кодом числа |A| заміною всіх 0 на 1 та всіх 1 на 0 будується Обернений код RA;

2 за RA як беззнаковим цілим числом обчислюється DA=RA+1.

Очевидно, що D A= R|A|1. Наприклад, побудуємо двобайтовий додатковий код числа –144. Прямим двобайтовим кодом числа 144 буде

0000'0000'1001'0000

апострофи записано для наочності, оберненим –

1111'1111'0110'1111.

До нього додається 1:

1111'1111'0110'1111

1

1111'1111'0111'0000,

І ми одержуємо додатковий код числа 144. Він є також оберненим кодом числа 143.

За додатковим кодом від'ємне число відновлюється у зворотному порядку:

1 DA вважається беззнаковим цілим; обчислюється RA=DA1;

2 код, обернений до RA, є прямим кодом числа | A |.

Той самий результат можна дістати, якщо

1 побудувати код RDA, обернений до DA;

2 до RDA як до беззнакового додати 1.

Відповідність знакових цілих чисел та їх кодів наведено в табл. 11.1. Як бачимо, від'ємних чисел на одне більше, ніж додатних.

Елемент X Довільного типупереліку подається як беззнакове цiле число ord X.

2.3. Принципи подання дійсних чисел

Дiйснi числа в більшості комп'ютерів подаються в N=4, 6, 8 або 10 байтах, поділених на Поля послідовності бітів:

знакпорядокмантиса.

Поле знак має довжину 1, а довжини двох інших позначимо D І R відповідно. Зрозуміло, що 1+ D+ R=8 N. Нехай S, E, M – значення цих полів як беззнакових цілих. Вони подають:

S = 0 – знак '+', S = 1 – знак '';

E – його Порядок T = E 2 D11;

M Мантису дробову частину M1 = M 2– R.

За значень E, відмінних від крайніх значень 0 та 2 D1, поля знакпорядокмантиса задають число, що є значенням виразу

1 S 1+ M1 2 T 11.2

Оскільки 1 1+ M12, то кажуть, що число подається в Нормалiзованому виглядi. Показник T називається Справжнім порядком Числа, а E Зсуненим він на 2 D11 більше від справжнього. Отже, значення E від 1 до 2 D2 задають справжні порядки T Від 12 D11=22 D1 до 2 D22 D11=2 D11.

Наприклад, нехай D=5, R=10, що задає двобайтове подання. Зсув порядку 2511=241. Розглянемо зображення числа 12.375:

12.375 = 1100.0112 = 1.1000112 23,

Тобто T=3, M1=0.100011. Звідси S=1, E=3+241=18=100102, M=1000110000, і число подається послідовністю бітів 1'10010'1000110000. Тут для наочності поля відокремлено апострофами.

Послідовність бітів 0'00001'0000000000 подає мінімальне додатне число, зображуване за D=5, R=10:

1 + 0 2124+1 = 214.

Наступним числом, що подається як 0'00001'0000000001, буде

1+210 2124+1=214+224.

Послідовність бітів 0'11110'11111111111 подає максимальне число

1+2101 210 225224+1 = 2210 215 =216 25 = 65504.

Попереднє перед ним число має подання 0'11110'11111111110 і є

1+2102 210 225224+1 = 229 215 =216 26 = 65472.

Як бачимо, різниця між двома сусідніми числами міняється від 224 до 25=32.

За E=0 незалежно від S і M подається число 0. За E=2 D1 подання числа використовуєтьсся спеціальним чином, про що ми говорити не будемо докладніше про це див., наприклад, [Григ].

Зазначимо, що розташування й довжини полів у поданні дійсних чисел залежать від конкретного типу комп’ютера і можуть відрізнятися від указаних тут. Можливі й інші особливості.