Паскаль подання чисел та інших значень

ПАСКАЛЬ:ПОДАННЯ ЧИСЕЛ ТА ІНШИХ ЗНАЧЕНЬ
1. Позиційні системи числення
1.1. Запис натуральних чисел
Системачислення– це система запису, або позначення, чисел. Найдосконалішими системами числення виявилися позиційні. У цих системах число, позначене цифрою, залежить від її місця (позиції) в записі числа. Наприклад, звичні нам записи 13 і 31 у десятковій системі складаються з однакових цифр (значків «1» і «3»), але позначають різні числа 110+3 і 310+1.
ПозиційнасистемачисленнязосновоюP(P-кова) має Pцифр C, 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-ковій системі позначається дворозрядним записом C1C, число P+1 – записом C1C1тощо до PP-1. Наприклад, 10, 11,…, 99 у десятковій системі, 10, 11 у двійковій, 10, 11, …, 1F, 20, …, FF у 16-ковій. Число PPпозначається вже трьома цифрами C1CC, далі йде C1CC1 тощо. Наприклад, 100, 101, …, 999 у десятковій системі, 100, 101, 110, 111 у двійковій, 100, 101, …, FFF у 16-ковій. І взагалі, запис вигляду
(akak-1a1a)P
позначає в P-ковійсистемі число, що є значенням полінома
akPk+ak-1Pk-1++a1P+a.
Наприклад, двійковий запис (10011)2позначає число, яке в десятковому записі має вигляд 124+023+022+121+12=19. 16-ковий запис (1BC)16позначає десяткове 1162+1116+12=444.
Найправіша цифра в запису числа позначає кількість одиниць і називається молодшою, найлівіша – кількість чисел Pkі називається старшою.
Ми звикли до десяткового подання чисел, і саме воно, головним чином, використовується в Паскаль-программах, але в комп'ютері числа, як правило, подаються в двійковій системі. Таким чином, виникає необхідність створювати двійкове подання числа за його десятковим записом і навпаки. Зауважимо до речі, що такі перетворення записів чисел з однієї системи в іншу здійснюються при виконанні процедур читання і запису readln і writeln.
За P-ковимзаписом (akak-1 a1a)Pнатурального числа Nможна побудувати десяткове подання, обчисливши значення полінома за допомогою операцій множення та додавання в десятковій системі. Саме цим ми займалися двома абзацами вище.
Розглянемо, як одержати за натуральним числом N цифри його P-кового подання. Нехай N=(akak-1 a1a)P, і кількість цифр k+1 невідомі. Запишемо подання в такому вигляді:
N =akPk+ak-1Pk-1++a1P+a0 = (…(akP+ak-1)P++a1)P+a.--PAGE_BREAK--
Звідси очевидно, що значенням aє NmodP, a1– (NdivP) modP тощо. Таким чином, якщо поділити Nна Pу стовпчик, то остача від ділення буде значенням молодшої цифри. Потім можна так само поділити на Pчастку від першого ділення – остача буде виражати кількість "P-ковихдесятків" тощо поки остання частка не виявиться менше P. Вона й буде значенням старшої цифри. При P>10 ще треба перетворити числа більше 9 у цифри. Наприклад, одержимо цифри 16-кового подання десяткового числа 1022:
_1022 |16_63 |16
9663 483
_62 15
48
14
Виділені 14, 15 і 3 – це кількості 16-кових «одиниць», «десятків» і «сотень» відповідно. Позначимо їх 16-ковими цифрами E, F і 3 відповідно та одержимо запис 3FE.
Якщо натуральне Nподано в базовому типі цілих, то одержати його P-кові цифриможна за наступним алгоритмом (остання цифра утворюється як остача від ділення на Pчастки, меншої від P):
whileN > 0 do
begin
d:= N modP ;
за значенням d побудувати P-кову цифру;
N := N divP
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 одержимо    продолжение
--PAGE_BREAK--
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, Vrперших цифр його P-ковогоподання, виконавши алгоритм
fori := 1 tor 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-ковіцифри, у результаті одержуємо
(їхсума) modP
із переносом (їхсума) divP. Наприклад, у шістнадцятковій системі
+ 9D
FAE
104B
(неважко перевірити, що при додаванні в стовпчик D+E=1B, 1+9+A=14, 1+F=10).
Усі вчаться в школі не тільки додавати, але й множити. Коли ми множимо число в десятковій системі у стовпчик на число, записане одною цифрою X, то обчислюємо добуток чергової цифри числа та X. Остачу від ділення цього добутку на 10 додаємо до переносу від попереднього розряду й одержуємо суму S. Молодшу цифру S, тобто остачу від ділення на 10, записуємо в результат, а старшу, тобто Sdiv10, запам'ятовуємо як перенос. І так рухаємося від молодшої цифри співмножника до старшої. Знайомо, чи не так?
У 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
а) N типу integer (цифри друкуються у зворотному порядку);
б) N типу integer (цифри друкуються у прямому порядку);
в) N має тип real, N
Уважати, що за 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-кових цифр, або символи від chr(0) до chr(255) чи якісь інші множини з 256 елементів.
У двох сусідніх байтах подаються 2828=65536 комбінацій із 0 та 1. Їм взаємно однозначно ставляться у відповідність цілі числа від 0 до 65535, або числа від -32768 до 32767 чи інші множини з 65536 елементів.    продолжение
--PAGE_BREAK--
Аналогічно чотири сусідні байти відображають (28)4=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.
Символивід chr(0) до chr(255) зображаються в одному байтi комбінаціями з нулів та одиниць відповідно від 00000000 до 11111111. Наприклад, символ chr(32), або ' ' (пропуск), зображається як 00100000, символ chr(48), або '0', – як 00110000 тощо.
Цілі числа подаються в комп'ютері, головним чином, у двох формах – беззнаковійта знаковій. Далі ми будемо ототожнювати числа з їх поданням, усвідомлюючи, що з точки зору математики це не може бути правильним.
 
 
 
 
7 … 0
…
7 … 0
7 … 0
8N-1 …
 
15 … 8
7 … 0 Беззнаковiчислазаймають певну кількість Nбайтiв, яка задає дiапазон (множину) цих чисел від 0 до 28N-1. Найчастiше N=1, 2 або 4, і діапазони чисел – від 0 до відповідно 255, 65535 та 4294967295. Байти записуються від молодших до старших справа наліво та нумеруються від 0 до N-1. Біти всередині байтiв так само записуються від молодших до старших справа наліво й нумеруються від 0 до 7 (рис. 11.1). Усього в Nбайтах є 8Nбітів, які нумеруються справа наліво від 0 до 8N-1. Біти з номерами 8N-1, , 8N-8 утворюють старший байт (він ліворуч), а з номерами 7, , 0 – молодший (праворуч). Комбінація бітів x8N-1, , xзображає в двійковій системі число
x8N-128N-1+x12+x.
Наприклад, комбінація 0000 задає число 0, комбінація 0001 – «один», 0010 – «два», 1111 – число 28N-1.
Таблиця 11.1
число
код
28N-1— 1
0111
28N-1— 2
0110


1
0001
0000
-1
1111
-2
1110


-28N-1+ 1
1001
-28N-1
1000 Знаковiчислазаймають ті самі N, тобто 1, 2 або 4 байти. Найстарший біт зображає знак числа: 0 – знак '+', 1 – знак '-'. Додатні числа подаються так само, як i беззнакові, лише за рахунок знакового біта дiапазон їх менший – від 0 до 28N-1-1. За N=1, 2 або 4 це відповідно 127, 32767 та 2147483647. Таке подання називається прямим кодом. Наприклад, прямим кодом максимального цілого є 0111.
Від'ємні числа подаються в коді, названому додатковим. Для від'ємного числа Aвін позначається D (A) й утворюється так:
1)за прямим кодом числа |A| заміною всіх 0 на 1 та всіх 1 на 0 будується обернений кодR(A);
2)за R(A) як беззнаковим цілим числом обчислюється D(A)=R(A)+1.
Очевидно, що D(A)=R(|A|-1). Наприклад, побудуємо двобайтовий додатковий код числа –144. Прямим двобайтовим кодом числа 144 буде
0000'0000'1001'0000
(апострофи записано для наочності), оберненим –
1111'1111'0110'1111.    продолжение
--PAGE_BREAK--
До нього додається 1:
1111'1111'0110'1111
1
1111'1111'0111'0000,
і ми одержуємо додатковий код числа -144. Він є також оберненим кодом числа -143.
За додатковим кодом від'ємне число «відновлюється» у зворотному порядку:
1)D(A) вважається беззнаковим цілим; обчислюється R(A)=D(A)-1;
2)код, обернений до R(A), є прямим кодом числа | A |.
Той самий результат можна дістати, якщо
1)побудувати код R(D(A)), обернений до D(A);
2)до R(D(A)) як до беззнакового додати 1.
Відповідність знакових цілих чисел та їх кодів наведено в табл. 11.1. Як бачимо, від'ємних чисел на одне більше, ніж додатних.
Елемент Xдовільного типу-перелікуподається як беззнакове цiле число ord(X).
2.3. Принципи подання дійсних чисел
Дiйснi числав більшості комп'ютерів подаються в N=4, 6, 8 або 10 байтах, поділених на поля(послідовності бітів):
.
Поле має довжину 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нормал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.    продолжение
--PAGE_BREAK--
Як бачимо, різниця між двома сусідніми числами міняється від 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.