.

Позиційні системи числення (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 2816
Скачать документ

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

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$&(,’”aeoe* X – \ %$%,'V'’'°'?'?'?'A'A'Ae'I'?'O'U'ae'Z(\(`(b(d(f(j(uoueuouououououououauau auauUuUaUuououououeueueuoueueueouoOoOEOuoAuouoOEOo» 6$6oioicioicioicioiciciaciciciacOcOcOcOciacOcOcOcOcacicicicic?c?c?cic?c? Ae?c3/4ci Hбайтом. Ці дві одиниці у світі програмістів і користувачів часто не зовсім точно називають відповідно "кілобайт" і "мегабайт", хоча це зовсім не тисяча і не мільйон байтів. До речі, 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, ? , x0 зображає в двійковій системі число x8N-1? 28N-1+? x1? 2+x0. Наприклад, комбінація 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 0 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. До нього додається 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

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Ответить

Курсовые, Дипломы, Рефераты на заказ в кратчайшие сроки
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020