Системы счисления в изложении для младших школьников. Материал для учителя

Позиционные системы счисления

В позиционной системе счисления число записывают в виде цепочки специальных символов:

a_na_n–1 ... a₂a₁                                                                (1)

Символы a_i называют цифрами. Они обозначают порядковые счетные количества, начиная с нуля и до значения на единицу меньшего числа q, называемого основанием системы счисления. То есть, если q — основание, то значения цифр лежат в интервале [0, q–1] (включая границы).

Положение цифры в записи числа (1) называют ее позицией, или разрядом.

Замечание 1. На этих страницах предпочтение отдается термину “позиция”. Во-первых, слово “позиция” хорошо согласуется с понятием “позиционная система счисления”, во-вторых, термин “позиционный вес” или “вес позиции” звучит лучше, понятнее и проще, чем “разрядный вес” или “вес разряда”. Однако учитель может и должен время от времени напоминать ученикам, что “позиция” и “разряд” — эквивалентные термины.

Замечание 2. Определение позиционной системы счисления, данное в текстах для ученика, не совсем точное. Одной только зависимости вклада цифры от позиции недостаточно. Например, в римской системе счисления вклад цифры также зависит от позиции (числа IV и VI — разные), но эта система не является позиционной. Точным определением можно считать всю совокупность правил построения числа, приведенную в данном контексте для учителя (то есть, наряду с фактом позиционной зависимости в определение входят: конечность множества цифр и правило нахождения числа по его записи).

Позиции нумеруются справа налево. Цифру, расположенную в первой позиции, называют младшей цифрой числа, в последней — старшей.

С каждой позицией связано число, которое мы будем называть ее весом (весом позиции).

Веса позиций определяются по следующему рекурсивному правилу:

1. Вес младшей позиции равен 1.

2. Вес каждой следующей позиции получается из веса предыдущей умножением на основание системы.

Пусть q — основание системы счисления. Тогда правило для вычисления позиционных весов w_i можно записать более кратко в виде рекуррентной формулы:

1. w₁ = 1.

2. w_i = w_i–1·q (для всех i > 1).

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

a_na_n–1 ... a₂a₁                                                                (1)

означает число N, равное сумме произведений цифр на их позиционные веса:

N = a_n·w_n + a_n–1·w_n–1 + ... + a₂·w₂ + a₁·w₁.                                        (2)

Произведение цифры на ее позиционный вес (то есть a_i·w_i) будем называть позиционным вкладом цифры.

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

В десятичной системе счисления числа записываются при помощи десяти арабских знаков: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Позиционные веса этой системы: ..., 1000, 100, 10, 1.

Запись 4627, например, “расшифровывается” так:

4627₁₀ = 4·1000 + 6·100 + 2·10 + 7·1.

В двоичной системе счисления числа записываются при помощи двух арабских знаков: 0 и 1. Позиционные веса этой системы: ..., 256, 128, 64, 32, 16, 8, 4, 2, 1.

Например, запись 10101 “расшифровывается” так:

10101₂ = 1·16 + 0·8 + 1·4 + 0·2 + 1·1.

Заметим, что из рекурсивного правила вычисления весов вытекает, что w_i = qⁱ–1 и, следовательно, запись (2) эквивалентна традиционной записи в виде степенного многочлена:

N = a_n·qⁿ–1 + a_n–1·qⁿ–2 + ... + a₂·q + a₁.                                     (3)

Докажем это по индукции. База индукции при i = 1 проверяется непосредственно: w₁ = q⁰ = 1.

Индукционное предположение: пусть утверждение справедливо при некотором n:

w_n = qⁿ–1.

Докажем, что оно будет справедливо и при n + 1.
То есть докажем справедливость равенства:

w_n+1 = qⁿ.

В самом деле, w_n+1 = w_n·q (по рекурсивному определению веса позиции), а w_n = qⁿ–1 по индукционному предположению. Получается:

w_n+1 = w_n·q = qⁿ–1·q = qⁿ.

Докажем, что любое число представимо в форме (1) (теорема 1) единственным образом (теорема 2).

Теорема 1 (существование). Любое число m можно представить в форме (1) при любом q > 1.

Доказательство. Докажем по индукции. Для m = 0
и m = 1 легко построить нужное представление — это соответственно 0 и 1 (при любом q > 1). Допустим, нам удалось представить число m в форме (1). Найдем тогда представление для m + 1. Для этого достаточно преобразовать сумму

a_n·qⁿ–1 + a_n–1·qⁿ–2 + ... + a₂·q + a₁ + 1 к форме (1).

Если a₁ < (q–1), то нужное представление получается заменой цифры a₁ на a^'₁ = a₁ + 1.

Если a₁ = (q–1), получаем перенос единицы в следующую позицию:

a_n·qⁿ F–1 + a_n–1·qⁿ–2 + ... + (a₂ + 1)·q + 0.

Далее рассуждаем аналогично. Если a₂ < (q–1), то нужное представление получается заменой цифры a₂ на a^'₂ = a₂ + 1. Если a₂ = (q–1), то a₂ заменяем нулем и переносим единицу в следующую позицию.

Либо на каком-то i < n мы закончим построение, либо получим запись 1000...0 — единицу и n нулей справа. Доказательство завершено.

Перед теоремой 2 докажем лемму.

Лемма. Вклад каждой ненулевой цифры в записи (1) превышает сумму вкладов цифр, расположенных правее нее.

a_na_n–1 ... a₂a₁.                                                          (1)

Доказательство. Докажем, что при любом n > 1:

a_n·qⁿ–1 > a_n–1·qⁿ–2 + ... + a₂·q + a₁.

Цифры a_i лежат в интервале [0, q–1], значит, достаточно доказать неравенство при наименьшей ненулевой цифре в левой части и максимальных цифрах в правой:

qⁿ–1 > (q–1)·qⁿ–2 + ... + (q–1)·q + (q–1).

В правой части выносим множитель (q–1) за скобку:

(q–1)·qⁿ–2 + ... + (q–1)·q + (q–1) = (q–1)·(qⁿ–2 + ... + q + 1).

Сумму геометрической прогрессии в последней скобке вычислим по известной формуле:

(q–1)·(qⁿ–2 + ... + q + 1) = (q–1)·(qⁿ–1–1)/(q–1) = qⁿ–1 – 1.

Получаем очевидное неравенство, которое доказывает лемму:

qⁿ–1 > qⁿ–1 – 1.

Теорема 2 (единственность). Число в форме (1) представляется единственным способом.

Доказательство. Из леммы следует, что числа, имеющие в своей записи разное количество цифр (незначащие нули слева не учитываются), не могут быть равными: число с большим количеством цифр всегда больше. Значит, нужно только доказать, что если a_i не равно b_i для всех i от 1 до n, то записи

a_na_n–1 ... a₂a₁                                                                (4)

b_nb_n–1 ... b₂b₁                                                               (5)

не могут обозначать одно и то же число.

Просмотрим записи (4) и (5) слева направо в поисках несовпадающих цифр. Пусть это будут a_k и b_k и пусть a_k – b_k = d.

На k-м месте в записи обнаружилась разница в d·q^k–1. Эта разница должна компенсироваться вкладами позиций, расположенных правее. Но это невозможно, так как по лемме сумма вкладов позиций, расположенных правее, всегда меньше вклада текущей позиции. Теорема доказана.

Для перевода чисел из системы с основанием q в десятичную систему можно воспользоваться формулой (2), выполнив в ней умножения и сложения.

N = a_n·w_n + a_n–1·w_n–1 + ... + a₂·w₂ + a₁·w₁                             (2)

При переводе из двоичной системы задействовано только сложение (ибо на 1 можно не умножать). Таким образом, получаем правило перевода, сформулированное в Читальном зале:

Для перевода из двоичной системы в десятичную нужно над каждой двоичной цифрой записать вес ее позиции и сложить числа, записанные над единицами.

Так, например, для числа 10111 получаем:

10111₂ = 16 + 4 + 2 + 1 = 23₁₀

Общее правило перевода из q-ичной системы в десятичную звучит так:

Для перевода из q-ичной системы в десятичную нужно над каждой цифрой записать вес ее позиции и найти сумму произведений цифр на их позиционные веса (то есть найти сумму позиционных вкладов).

Так, например, для числа 10212₃ получаем:

Складываем цифры, умноженные на их позиционные веса (позиции с нулевыми цифрами, понятно, можно опустить):

10212₃ = 1·81 + 2·9 + 1·3 + 2·1 = 104₁₀.

Для перевода чисел из десятичной системы в систему с основанием q будем по-прежнему опираться на формулу (2):

N = a_n·w_n + a_n–1·w_n–1 + ... + a₂·w₂ + a₁·w₁.                            (2)

Алгоритм перевода.

I. Повторять, пока число не обратится в ноль:

II. В позиции, не занятые построенными цифрами, записать нули.

В каждой позиции берется максимально возможная цифра, так как по лемме вклад этой цифры нельзя компенсировать цифрами, расположенными правее. Алгоритм будет работать в силу доказанного существования (теорема 1) и единственности (теорема 2) представления числа в форме (1).

Для двоичной системы получаем вариант алгоритма, приведенный в материале для ученика.

Для перевода в двоичную нужно построить шаблон с весами двоичных цифр:

Перевод числа выполняется по следующему алгоритму:

I. Повторять, пока число не обратится в ноль:

1. Записать 1 в первую слева позицию, вес которой не больше текущего числа.

2. Уменьшить текущее число на вес построенной единицы.

II. В позиции, не занятые единицами, записать нули.

Такой способ перевода на практике оказывается гораздо проще и быстрее традиционного алгоритма с нахождением остатков.

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

Скажем, вклад цифры 2 в позиции 243 — число 486, а в позиции 9 — число 18.

Для перевода в троичную систему нужно просмат­ривать таблицу по строкам в поисках наибольшего числа, не превосходящего текущее значение.

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

Значит, троичное число начинается цифрой 2:

183₁₀ = 2????₃

Далее работаем с числом 183–162 = 21:

183₁₀ = 202??₃

Для числа 21–18 = 3 в таблице есть точное значение, перевод закончен:

183₁₀ = 20210₃.

Для систем с большим основанием соответствующие таблицы будут, конечно, объемнее. Построим в качестве последнего примера таблицу для перевода в шестнадцатеричную систему счисления:

Пусть нужно перевести в шестнадцатеричную систему число 4255. Ищем в таблице (слева направо по строкам, начиная сверху) первое число, которое окажется не больше исходного числа 4255:

Получаем первую цифру 1 в позиции 4096:

Осталось закодировать 4255 – 4096 = 159.

Строку 256 пропускаем (соответствующая цифра будет 0), а в строке 16 находим подходящее значение 144:

Получаем цифры в позициях 256 и 16:

Осталось закодировать 159 – 144 = 15. Понятно, что это значение младшей цифры:

Получается: 4255₁₀ = 109F₁₆.

Этот раздел представлен в материале для ученика схематично, в ознакомительном порядке.

Теме можно посвятить отдельный, большой и достаточно интересный урок, но материала и так получилось много — трудно объять необъятное!

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

Раздел поддержан домашними заданиями варианта 3. Эти упражнения можно рекомендовать любознательным школьникам в качестве индивидуальных заданий.