Вычислительные алгоритмы позиционной системы

Использование позиционной системы связано с созданием на основе исходного множества сложной структуры множеств с различными элементами – единицами, десятками, сотнями и т. д. Работа с множествами, состоящими из разнородных элементов характерна и в случае целых и рациональных чисел. Но образцом является позиционная система счисления, где определены правила перевода элементов одного множества в элементы другого. Именно на возможности перевода десятков в единицы и обратно, сотен в десятки и обратно и т. д. основаны вычислительные алгоритмы позиционной системы – сложение, вычитание, умножение и деление.

При вычитании двух чисел, записанных в десятичной позиционной системе счисления, вычитание начинается с единиц. Если уменьшаемое содержит больше (или столько же) единиц, чем вычитаемое, то вычитание выполняется. В противном случае один десяток уменьшаемого распаковывается, и его единицы переносятся в разряд единиц. Может, однако, оказаться, что уменьшаемое не имеет ни одного десятка, тогда распаковывается сотня, тысяча, десяток тысяч и т. д. Десяток доходит до единиц, а в остальные разряды попадают девятки, поскольку 10 ⁿ – 1 = 99….9, где число девяток равно n.

Распаковка десятков тысяч

Распаковка

1

Распаковка десятков

Уменьшаемое

–

Вычитаемое

Разность

Вычитание единиц

3 – 5 вычитание невозможно, следует распаковать десятку. Уменьшаемое принимает вид 1 0 0 1 13.

Повторное вычитание единиц

13 – 5 = 8

Вместо двух десятков остался один

Вычитание десятков

1 – 7 вычитание невозможно, следует распаковать один из высших разрядов – десяток тысяч. Уменьшаемое принимает вид 0 9 9 11 13.

Повторное вычитание десятков

11 – 7 = 4

Вычитание сотен и тысяч

9 – 9 = 0

9 – 0 = 9

При перемножении двух чисел, записанных в десятичной позиционной системе счисления, используется следующие обстоятельства. Пусть перемножаются два записанных в позиционной системе счисления числа

а = а_n·10ⁿ + а_{n – 1}·10^{n – 1} + … + а₂·10² + а₁·10¹ + а₀·10⁰ и

b = b_m·10^m + b_{m – 1}·10^{m – 1} + … + b₂·10² + b₁·10¹ + b₀·10⁰.

Используя законы коммутативности и дистрибутивности получим

a·b = a·(b_m·10^m + b_{m – 1}·10^{m – 1} + … + b₂·10² + b₁·10¹ + b₀·10⁰) =

a·b_m·10^m +…+ a·b_k ·10^k + … + a·b₂·10² + a·b₁·10¹ + a·b₀·10⁰.

В итоге оказывается, что для получения результата нужно вычислить несколько произведений вида a·b_k ·10^k и сложить их. Поскольку операцией сложения мы уже владеем, достаточно разобраться в том, как вычисляются числа вида a·b_k ·10^k, где k = 0, 1, …, m, а число b_k записывается одной цифрой.

Используя запись числа а в десятичной позиционной системе счисления получим

a·b_k ·10^k = (а_n·10ⁿ + а_{n – 1}·10^{n – 1} + … + а₂·10² + а₁·10¹ + а₀·10⁰)· b_k ·10^k =

(а_n·10^{n+ k} +а_{n – 1}·10^{n+ k – 1} + …+ а₂·10 ^k+2 + а₁·10^k+1 + а₀·10 ^k+ 0·10 ^{k– 1}+…+ 0·10⁰. )·b_k.

Очевидно, что позиционная запись числа в скобках получается из записи числа а добавлением k нулей в младшие разряды.

Займёмся разбором вопроса об умножении произвольного натурального числа на число, которое записывается одной цифрой. Умножение начинается с младших разрядов. Для перемножения чисел-цифр (а_i и b_k) используется таблица умножения. Получаемые при этом старшие разряды добавляются к следующему произведению чисел-цифр (а_i+1 и b_k).

	Таблица умножения		Умножение на число-цифру                                     =                       Дополнительно получено   Умножение единиц 6 7 = 42 4 десятка   Десятки 7 7 + 4= 49 + 4= 53 5 сотен   Сотни 8 7 + 5= 56 + 5= 61 6 тысяч   Тысячи 9 7 + 6= 63 + 6= 69 6 дес.тысяч

Умножение чисел в десятичной позиционной системе счисления

Перемножаемые числа записываются одно под другим. Далее поочерёдно вычисляются произведения первого сомножителя на слагаемые второго, имеющие вид bk ·10k. Все произведения выписываются одно под другим и суммируются.

+

0

0

0

В записи умножения столбиком нули младших разрядов опускаются, но позиционные сдвиги соблюдаются.

1-е слагаемое

=

2-е слагаемое

=

3-е слагаемое

=

Деление двух чисел, записанных в десятичной позиционной системе счисления, основывается на следующих соображениях. Важнейшим обстоятельством является то, что при делении с остатком любого натурального числа на 10^k, где k+1 равно числу разрядов этого числа, частное равно старшей цифре этого числа: р_k·10^k + p_{k – 1}·10^{k – 1} + … + p₀·10⁰: 10^k = р_k·10^k + r, где r < 10^k.

Пусть заданы два числа, записанных в позиционной системе счисления числа а = а_n·10ⁿ + а_{n – 1}·10^{n – 1} + … + а₀·10⁰ и b = b_m·10^m + b_{m – 1}·10^m–1 + … + b₀·10⁰.

Считая, известным их частное a: b, а также число разрядов k+1 в его записи, мы можем найти цифру старшего разряда, разделив с остатком a: b на 10^k. Тот же самый результат будет получен, если разделить с остатком a на b∙10^k.

Пусть q = q_k·10^k + q_{k – 1}·10^k–1 + … + q₂·10² + q₁·10¹ + q₀·10⁰ – запись частного в позиционной системе счисления. Тогда верно выражение а = (b∙10^k)·q_k + r_k, (где r_k < b∙10^k). Его смысл как раз и состоит в том, что при делении с остатком числа а на число b∙10^k (при некотором, изначально неизвестном, значении k) может быть получена цифра старшего разряда частного a: b.

Остаток r_k равен а – (b∙10^k)·q_k = q_{k – 1}·10^{k – 1} + … + q₂·10² + q₁·10¹ + q₀·10⁰. Точно так же рассуждения, применённые к числу r_k, позволяют с помощью деления с остатком на b∙10^k–1 найти следующую цифру q_k–1 в записи частного. При этом будет получен остаток r_k–1 = q_k–2·10^k–2 + … + q₂·10² + q₁·10¹ + q₀·10⁰. С его помощью можно найти очередную цифру q_{k – 2}. Продолжая этот процесс, можно найти все цифры частного. Последний остаток определяется тем, что он меньше делителя b.

Итак, деление одного натурального числа на другое распадается на несколько однотипных шагов. Характер каждого шага таков: делимое нужно домножить на некоторую степень десяти, чтобы при делении делимого на полученное число частное было меньше 10. Умножение числа на степень десяти производится дописыванием нулей справа к десятичной записи числа. Нужно дописывать нули до тех пор, пока из делителя получается число меньшее, чем делимое. Затем подбирается частное, выражаемое одной цифрой, и вычисляется остаток.

Приведём пример выполнения данного шага. При делении 9876 на 19 дописыванием нулей получаем из делителя возрастающую последовательность чисел 190, 1900, 19000, … Из неё нужно выбрать самое большое число, не превосходящее делимого. Им является 1900. Умножим это число на числа, выражаемые цифрами: 1900·1 = 1900, 1900·2 = 3800, 1900·3 = 5700, 1900·4 = 7600, 1900·5 = 9500, 1900·6 = 11400. Последнее число больше делимого, поэтому частное равно 5. В итоге 9876 = 1900·5 + 376.