Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

У наведеному прикладі представлене десяткове число 37779. Максимально можливе десяткове число, що може бути описане типом word, дорівнює 65535, а мінімальне - 0.

Тип integer дає змогу використовувати як додатні, так і від'ємні числа (табл. 7).

Таблиця 7

Біти

У нашому прикладі дане число типу integer прочиталося б у десятковій системі числення як -27757.

Діапазон зміни значень типу integer можна визначити так. Для двійкового представления числа типу integer відведено 15 розрядів. Тобто максимальним числом, яке можна записати в ці розряди, е 111111111111111₂ - 32767₁₀. Отже, значения змінних типу integer можуть коливатися від -32768 до + 32767.

Чотирибайтові цілі числа, що в Pascal визначаються стан-дартним типом longint, виглядають на схемі аналогічно, але розташовуються в 32-х розрядах. Старший, 31-й, розряд відве-дено під знак числа, решту - під його двійкове представления. Максимальне двійкове число, яке складається з 31 одиниці, пе­реводиться в десяткову систему числення як 2147483647. За аналогією щодо міркувань у попередніх прикладах діапазон зміни значень даного типу є таким: -2147483648.. 2147483647.

На завершения розглянемо декілька цікавих ситуацій, що виникають при некоректному використанні типів та їх значень.

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

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

Нагадаємо ситуацію, яка може трапитися з цілою змінною, що описана типом byte: якщо до 5Ї максимально припустимого значения 255 додати ще 1. Результатом буде 0. Пояснити це можна так.

Переведемо вказані десяткові числа в двійкову систему чис­ления: 255₁₀ = 11111111₂; 256₁₀ = 100000000₂. Це означав, що найстарший біт двійкового зображення числа 256 не по-міщається в розрядну сітку змінної типу byte i його буде втра-чено. Залишиться 00000000, яке при переведенні до десяткової системи числення дасть значения 0.

Розглянемо випадок, коли маємо справу зі змінними типу integer. Втрата старших розрядів двійкового зображення числа призводить до зміни не тільки значения числа, a і його знака: якщо після втрати найстарших бітів, що не помістилися в роз­рядну сітку, значениям першого зліва біта буде 1, то значения числа буде зі знаком «-», якщо ж 0 - зі знаком «+».

Цей випадок можна спостерігати, коли обчислюємо значен­ия га! при великих п. Описуючи результат виконання даного об-числення як integer, ми можемо отримати правильне значения лише до л = 7 (л! = 5040), а типом longint до п = 12 (и! = = 479 001 600). При зростанні значень змінних, що виходять за вказані обмеження, значения результату буде незрозуміло мі-нятися: абсолютна величина його може зменшуватися, а знак ставати то «-», то «+». Наприклад, при описі var n: integer i значенні n = 8 результат n\ дорівнюватиме -25216 замість пра­вильно! відповіді 40320, а при описі var n: longint i значенні n = 13 результат n\ дорівнюватиме 1932053504 замість 6227020800.

Дійсні числа

Найчастіше для опису дійсних чисел використовуються такі типи: real (6 байт), single (4 байт), double (8 байт), extended (10 байт).

Як приклад розглянемо розташування в пам'яті значень змінних типу single. Нагадаємо, що дійсні числа в комп'ютері представляються в показниковій формі. Наприклад, число -1.0123 • 10~¹⁵ виглядатиме так (мал. 4):

55

-10123 Е-16

_{t t ft}

знак знак числа порядку

мавгиса порядок Мал. 4

Але із зазначеної на схемі інформації в пам'ять комп'ютера заноситься не все, а лише знак числа, мантиса числа (послі-довність ЇЇ цифр) та порядок. Причому все в двійковому представленні. Як бачимо, в пам'ять комп'ютера не заноситься знак порядку дійсного числа. Для уникнення проблеми запа-м'ятовування знака порядку до їх значень додаеться констант-не зміщення, яке робить їх завжди додатними. Ми не будемо детально розглядати щ" питания, оскільки вони є предметом іншого, більш глибокого вивчення. Схематично побітне пред­ставления короткого дійсного числа в пам'яті комп'ютера мож-на зобразити так (табл. 8):

Таблиця8 Біти

Текстова інформація Символи

Значениями змінних типу char є довільні символи (літери, цифри, знаки операцій, коми, дужки тощо), які використо-вуються в даній мові програмування. Значения цього типу вважаються впорядкованими. Спосіб упорядкування залежить від машинної реалізації мови, однак завжди вважається, що цифри упорядковані за зростанням, а літери - за абеткою. Ко-дування упорядкованих символів починається від 0 до 255. Це пояснюється тим, що значения зміиних цього типу займають у пам'яті комп'ютера 1 байт (11111111₂ = 255₁₀). Таким сим­волом може бути будь-який символ із таблиці ASCU-кодів.

Наприклад, символ 'А' латинської абетки у таблиці ASCII-кодів позначений кодом 65 (65_J0 = 1000001₂). Тому при введенні цього символу в пам'ять комп'ютера запипіеться така послі-довність двійкових цифр (табл. 9):

56

Таблиця9

Байт

Рядки

Рядкова інформація або текстові дані представляються у вигляді послідовності двійково-кодованих символів і можуть займати декілька байтів, тобто стільки байтів, скільки сим-волів входить до цього рядка. У Pascal на довжину рядкових ве­личин накладаеться обмеження у 255 символів.

Наприклад, символи абревіатури 'ПК' будуть кодуватися так: 'П' - 143₁₀ = 10001111₂; 'К' - 138₁₀ = 10001010₂. У пам'яті комп'ютера вони розташуються так, як показано в таблиці 10.

Таблиця 10

Байт h + 1

Байт fe

К

п

3 таблиці 10 можна зробити висновок, одо оскільки байти нумеруються справа наліво, то таким же чином розташовують-ся і коди відповідних символів.

/ Запитання для самоконтролю

1. Як порозрядно в пам'яті комп'ютера представляються значения цілих чисел: однобайтові, двобайтові, чотирибайтові?

2. Як визначається діапазон зміни значены цілих чисел?

3. Як порозрядно в пам'яті комп'ютера представляються значения дійсних чисел?

4. Як визначається діапазон зміни значень дійсних чисел?

5. Як представляється в пам'яті комп'ютера символьна інфор-мація?

6. Як представляється в пам'яті комп'ютера рядкова інформація?

57

Розділ III

СТРУКТУРИ ДАНИХ

Основним завданням будь-якого алгоритму є обробка інфор-мації. Яким чином представити інформацію? Адже від зручно-го способу її представления залежить і зручність обробки.

Наприклад, структура телефонного довідника або шкільно-го журналу нам знайома і уявити її іншою складно. Зрозуміло, що, переписавши телефонний довідник у вигляді звичайного тексту, ми унеможливимо пошук у ньому інформації.

Записуючи перелік деяких завдань, ми, не замислюючись, використовуємо таку структуру, як список, нумеруючи його пункти або позначаючи їх якимись символами. А от листа ми пишемо у вигляді звичайного тексту. Але і тут виділяємо ок-ремі смислові абзаци для зручності його читання.

Отже, перш ніж починати обмірковувати питания опрацювання інформації, треба визначитися, як ЇЇ представити. Найчастіше на практиці обидва ці продеси взаємопов'язані. Тобто інколи під час роботи з інформацією нам доводиться змі-нювати, вдосконалювати те представления, що було обране спочатку.

Структура даних - це спосіб представления інформації.

В алгоритмізації знання різноманітних структур даних, ефективне їх використання мають неабияке значения. Правильне, коректне визначення структур даних, що використовуються в алгоритмі, - це значна частина успіху.

Деякі структури даних визначаються безпосередньо в мовах програмування, які ми використовуємо для реалізації алгорит-мів. Наприклад, ви вже знайомі з простими змінними, масивами. А деякі організовуються самими розробниками алгорит-мів. Саме з ними ми маемо ознайомитися в цьому розділі.

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

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

• відображення структури даних на пам'ять комп'ютера;

• обробка інформації в даній структурі.

58

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

Також не менш важливою є інформація про доступ до еле-ментів кожної структури: прямий чи послідовний.

Якщо до будь-якого елемента заданої структури можна ді-статися, не переглядаючи всі, то такий доступ називають прямим. У протилежному випадку — послідовним.

ПРОСТА ЗМІННА

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

Отже, тепер протягом виконання програми з ім'ям описаної змінної пов'язана конкретна адреса в пам'яті комп'ютера та відповідна до її типу кількість байтів, що починаються з цієї адреси.

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