Информатика. 10 класс (Повышенный уровень)

Правила выполнения арифметических действий (сложения, вычитания, умножения и деления) в десятичной системе счисления хорошо известны. Эти же правила применимы к выполнению арифметических действий и в других позиционных системах счисления.

В примере 25.5 рассмотрены правила выполнения поразрядных арифметических действий в двоичной системе счисления.

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

Сложение

Чтобы в системе счисления с основанием  получить сумму S двух чисел A и B, нужно просуммировать образующие их цифры по разрядам  от младшего разряда к старшему по следующим правилам:

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, переносим в первый разряд.
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), нужно вычислять разности образующих их цифр по разрядам i от младшего к старшему по следующему правилу:

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. В отличие от других арифметических действий деление выполняется начиная со старшего разряда делимого.

Пример 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. Найти частное чисел 13351₈ и 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.