§ 25. Кадзіраванне лікавых даных

Разгледзім перавод правільнага дзесятковага дробу ў любую іншую пазіцыйную сістэму лічэння.

Для пераводу дзесятковага дробу F у сістэму лічэння з асновай q ( F₁₀ → F_q) неабходна F памножыць на q, затым дробавую частку здабытку зноў памножыць на q і г. д., да таго часу, пакуль дробавая частка здабытку не стане роўнай нулю або пакуль не будзе дасягнута патрэбная дакладнасць уяўлення F у сістэме лічэння q (вызначана колькасць лічбаў у запісе выніку).

Схема пераводу дзесятковага дробу ў двайковую сістэму лічэння выглядае наступным чынам:

Пры паўторы значэнняў дробавай часткі (правы слупок табліцы) паўтаральную групу лічбаў у запісе цэлых частак (левы слупок табліцы) трэба запісаць як перыяд дробу.

У прыкладзе 25.1 Ювыкананы пераводы  (F₁₀ → F_q) дзесятковых дробаў у пазіцыйную сістэму лічэння з асновай q ( F₁₀ → F_q).  

Для змешаных лікаў перавод  (F1₀ → F_q) выконваецца асобна для цэлай і дробавай часткі (прыклад 25.2).

У сітуацыі пераводу дробаў  Zp → Zq, калі асновы сістэм лічэння (p і  q) з’яўляюцца ступенямі двойкі, двайковую сістэму лічэння зручна выкарыстоўваць для пераводу як прамежкавую па схеме Zp → Z₂ → Zq. У гэтым выпадку падзел лічбаў у запісе ліку на групы пачынаецца з нулявога разраду і выконваецца гэтак жа, як і пры пераводзе цэлых лікаў (прыклад 25.3). Пры гэтым разрады ў запісе лікаў нумаруюцца з 0, і лічба ў нулявым разрадзе адпавядае адзінкам. Нумарацыя разрадаў узрастае ўлева ад нулявога разраду і спадае ўправа, г. зн. у дробавай частцы ліку нумарацыя разрадаў адмоўная.

Алгарытм пераводу дробавых і змешаных лікаў з сістэмы лічэння з асновай p у сістэму лічэння з асновай 10 (Zp → Z₁₀ ), гэтак жа як для цэлых лікаў, выцякае са спосабу ўяўлення ліку ў сістэме лічэння з асновай p (прыклад 25.4).

Правілы выканання арыфметычных дзеянняў (складання, аднімання, множання і дзялення) у дзесятковай сістэме лічэння добра вядомыя. Гэтыя ж правілы выкарыстоўваюцца ў дачыненні да выканання арыфметычных дзеянняў і ў іншых пазіцыйных сістэмах лічэння.

У прыкладзе 25.5 разгледжаны правілы выканання паразрадных арыфметычных дзеянняў у двайковай сістэме лічэння.

Разгледзім алгарытмы выканання кожнага з арыфметычных дзеянняў у пазіцыйных сістэмах лічэння з адвольнай асновай р.

Складанне

Каб у сістэме лічэння з асновай p атрымаць суму S двух лікаў A і B, трэба падсумаваць лічбы, якія іх утвараюць, па разрадах i ад малодшага разраду да старэйшага па наступных правілах:

1. Каліa_i + b_i < p, то , s_i = a_i + b_i значэнне (i + 1)-га разраду не змяняецца.
2. Каліa_i + b_i ≥ p, то, s_i = a_i + b_i – p, значэнне (i + 1)-га рразраду павялічваецца на 1. Гэта звязана з тым, што  адзінак i-га разраду адпавядае адной адзінцы ( i + 1)-га разраду, а ў кожным разрадзе не можа знаходзіцца больш за (p – 1) адзінак.

Прыклад 25.6. Скласці лікі 1111₂ і 101₂.

1. Складваем значэнні ў нулявых разрадах складаемых: 1 + 1 = 10₂. Запісваем 0, а 1 пераносім у першы разрад: 1 + 1 = 10₂. 
2. У першых разрадах складваем:
   1 + 0 = 1  і дабаўляем 1 з нулявога разраду. Атрымліваем 1 + 0 + 1 = 10₂. Запісваем 0, а 1 пераносім у другі разрад.
3. Складваем значэнні ў другіх разрадах: 1 + 1 + 1 = 3(11₂), 3 ≥ 2, значыць, запісваем 1, а 1 пераносім у трэці разрад.
4. Вылічваем у трэцім разрадзе: 1 + 1 = 2. Паколькі 2 ≥ 2, то запісваем 0, а 1 пераносім у чацвёрты разрад.

Упрыкладзе 25.7 выканана складанне двайковных змешаных лікаў.

Прыклад 25.8. Скласці лікі 6354₈ і 743₈.

1. Вылічваем: 4 + 3 = 7.
2. Складваем: 5 + 4 = 9. 9 ≥ 8, значыць, запісваем 1 (паколькі 9 – 8 = 1), а 1 пераносім у другі разрад.
3. Вылічваем: 3 + 7 = 10. Дабаўляем 1 з першага разраду 10 + 1 = 11.  11 ≥ 8, значыць, запісваем  3 (11 – 8 = 3 ), а 1 пераносім у трэці разрад.
4. У трэцім разрадзе: 6 + 1 = 7.

Прыклад 25.9. Скласці лікі 5B4₁₆ і C52₁₆.

1. У нулявым разрадзе: 4 + 2 = 6.
2. Вылічваем: B(11) + 5 = 16. 16 ≥ 16, значыць, запісваем  0 (16 – 16 = 0), а 1 пераносім у другі разрад.
3. Складваем: 5 + C(12) = 17. Дабаўляем 1 з другога разраду: 17 + 1 = 18. 18 ≥ 16, значыць, запісваем 2 (18 – 16 = 2), а 1 пераносім у трэці разрад.

Адніманне

Каб у сістэме лічэння з асновай  атрымаць рознасць R двух лікаў A і B  ( A > B), трэба вылічваць рознасці лічбаў, якія іх утвараюць, па разрадах ад малодшага да старэйшага па наступным правіле:

1.  Каліa_i  ≥  b_i, то r_i = a_i – b_i, значэнне ў (i + 1 )-м разрадзе не змяняецца.
2. Калі a_i  <  bi, то r_i = p + a_i – b_i, то значэнне ў (i + 1 )-разрадзе памяншаецца на 1. Пры гэтым, калі a_i = 0, то займаем адну разрадную адзінку (роўную аснове сістэмы лічэння p) у (i + 1)-м разрадзе і працягваем займаць да бліжэйшага да i-га старшага разраду (уключна), дзе a_i ≠ 0.

Прыклад 25.10. Знайсці рознасць лікаў 1000₂ и 11₂.

1. У нулявым разрадзе: 0 < 1. Займаем у першым разрадзе. Паколькі ў двух наступных разрадах запісаны 0, то працягваем займаць да трэцяга разраду, дзе запісана 1. Атрымліваем  2 – 1 = 1 (10₂ – 1₂ = 1₂). У вынік запісваем 1.
2. У першым разрадзе пасля таго, як занялі, засталося 1 (2(10₂) – 1). Аднімаем: 1 – 1 = 0. У вынік запісваем 0.
3. У другім разрадзе засталося 1. Аднімаем: 1 – 0 = 1. У вынік запісваем  1.
4. У трэцім разрадзе застаецца 0.

Прыклад 25.11. Знайсці рознасць лікаў 7450₈ і 736₈.

1. У нулявым разрадзе:  0 < 6. . Займаем у першым разрадзе 8(10₈). Аднімаем: 8 – 6 = 2. У вынік запісваем  2.
2. У першым разрадзе засталося 4. Аднімаем: 4 – 3 = 1. У вынік запісваем  1.
3. У другім разрадзе: 4 < 7. Займаем у трэцім разрадзе 8. Вылічваем: 8 + 4 – 7 = 5. У вынік запісваем 5.
4. У трэцім разрадзе застаецца 6, што і запісваем у вынік.

У прыкладзе 25.12 разгледжана адніманне лікаў у шаснаццацярычнай сістэме лічэння, якое выконваецца па аналагічным алгарытме.

Множанне

Каб у сістэме лічэння з асновай p атрымаць здабытак М ліку A і ліку  B < p, трэба вылічыць здабытак лічбаў ліку А па разрадах ад малодшага да старшага і ліку В у адпаведнасці з правіламі:

1. Каліa_i · b < p, то  m_i = a_i · b і значэнне ў (i + 1)-м разрадзе не змяняецца.
2. Каліa_i · b < p, то  m_i = ai · b modp, а значэнне ў ( i + 1 )-м разрадзе павялічваецца на  a_i · b divp.

Прыклад 25.13. Знайсці здабытак лікаў 1212₃ і 2₃.

1. Вылічваем: 2 · 2 = 4. Паколькі 4 ≥ 3, у вынік запісваем  4 mod 3 = 1. Значэнне ў першым разрадзе павялічваем на   4 div 3 = 1.
2. Вылічваем: 1 · 2 + 1 = 3, 3 ≥ 3, значыць, у вынік запісваем 3 mod 3 = 0, а другі разрад павялічваем на 3 div 3 = 1.
3. Вылічваем: 2 ^.  2 + 1 = 5. У вынік запісваем 5 mod 3 = 2. Трэці разрад павялічваем на 5 div 3 = 1.
4. Паўтараем п. 2. У трэцім разрадзе выніку запісваем 0, а ў чацвёртым  — 1.

У прыкладах 25.14 і 25.15 па аналагічным алгарытме выканана множанне мнагазначнага ліку на адназначны лік у іншых сістэмах лічэння.

Множанне мнагазначнага ліку на мнагазначны лік выконваецца слупком. Пры гэтым два множнікі размяшчаюцца адзін пад адным так, каб разрады лікаў супадалі (знаходзіліся ў адным слупку).

У прыкладах 25.16 і 25.17 выканана множанне мнагазначнага ліку на мнагазначны лік.

*Дзяленне

Аперацыю дзялення нельга звесці да паразрадных аперацый над лічбамі, якія складаюць лік. Дзяленне лікаў у сістэме лічэння з адвольнай асновай p выконваецца гэтак жа, як і ў дзесятковай сістэме лічэння. А гэта значыць, што пры выкананні дзялення ўжываюцца правілы множання і аднімання лікаў у сістэме лічэння з асновай p. У адрозненне ад іншых арыфметычных дзеянняў дзяленне выконваецца, пачынаючы са старшага разраду дзялімага.

Прыклад 25.18. Знайсці дзель лікаў 101010₂ і 111₂.

1. Параўноўваем значэнне ў самым старшым разрадзе і дзельнік. Калі дзельнік большы за значэнне ў дадзеным разрадзе, то разглядаем гэта значэнне і значэнне ў наступным разрадзе як лік. Паўтараем аперацыю да моманту, калі атрыманы лік зраўняецца або перавысіць значэнне дзельніка ( 1 <  111, 10 < 111, 101 < 111, 1010 > 111).
2. Падбіраем такі лік (1), пры якім здабытак дзельніка і гэтага ліку (111) будзе максімальна блізкім па значэнні (але не большым) да ліку, атрыманага ў п. 1. Запісваем гэты лік у дзель першым.
3. Аднімаем здабытак (п. 2) ад ліку, утворанага значэннямі выбраных разрадаў  (1010 – 111).
4. Астачу пішам пасля рысы  (11).
5. Зносім значэнне наступнага разраду да астачы (1) і правяраем, атрыманы лік (111) большы за дзельнік ці роўны яму. Калі не, то зносім значэнне яшчэ аднаго разраду да таго часу, пакуль не ўтворыцца лік, большы за дзельнік ці роўны яму, пры гэтым не забываем запісваць нулі ў дзель.
6. Прарабляем усё вышэйпералічанае да таго часу, пакуль лічбы ў дзеліве не скончацца ці ў астачы не атрымаецца лік, меншы за дзельнік.

Прыклад 25.19. Знайсці дзель лікаў 3351₈ і 163₈.

1. Параўноўваем:1 <  163, 13 < 163, 133 < 163. 1335 > 163.
2. Падбіраем: 6 · 163 = 1262 < 1335.
3. Аднімаем: 1335 – 1262 = 53.
4. Зносім 1 і атрымліваем  531 > 163.
5. Падбіраем: 3 ^.  163 = 531.
6. Аднімаем: 531 – 531 = 0.

Прыклад 25.20. Найти частное чисел 8D2F6C₁₆ и DF₁₆.

1. Параўноўваем: 8 < DF, 8D < DF, 8D2 > DF.
2. Падбіраем: А ^. DF = 8B6 < 8D2.
3. Аднімаем: 8D2 – 8B6 = 1C.
4. Зносім F і атрымліваем 1CF > DF.
5. Падбіраем: 2 ^. DF = 1BE < 1CF.
6. Аднімаем: 1CF – 1BE = 11.
7. Зносім 6 і атрымліваем  116 > DF.
8. Подбираем: 1 ^. DF = DF.
9. Аднімаем: 116 – DF = 37.
10. Зносім C і атрымліваем  37C > DF.
11. Падбіраем: 4 ^. DF = 37C.
12. Аднімаем: 37C – 37C = 0.

1. Як перавесці правільны дзесятковы дроб у іншую сістэму лічэння?

2. Як перавесці змешаны лік з дзестковай сістэмы лічэння ў любую іншую сістэму лічэння?

3. Які алгарытм выкарыстоўваецца пры пераводзе змешанага ліку з сістэмы лічэння з любой асновай у дзесятковую сістэму лічэння?

4. Якія правілы двайковай арыфметыкі?

5. Як выконваецца аперацыя складання лікаў у любой пазіцыйнай сістэме лічэння?

6. Як выконваецца аперацыя аднімання лікаў у любой пазіцыйнай сістэме лічэння?

7. Як выконваецца аперацыя множання лікаў у любой пазіцыйнай сістэме лічэння?

8. Правілы выканання якіх арыфметычных дзеянняў выкарыстоўваюцца пры выкананні дзялення ў любой пазіцыйнай сістэме лічэння

Сістэма лічэння

Колькасць лічбаў пасля коскі.

2^-7

8^-4

16^-3