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

Краткое содержание

Этот урок изучает позиционную запись, в которой значение каждой цифры зависит от занимаемого ею места. В нём доказывается, что всякое натуральное число записывается единственным образом по любому основанию $b \geq 2$ с помощью процедуры, состоящей в повторном делении на основание, и показывается, как переводить числа между основанием $10$ и основаниями $2$ , $8$ и $16$ , а между тремя последними с помощью группировки двоичных цифр. Урок показывает, что сложение и умножение выполняются по любому основанию по тем же правилам, что и по основанию $10$ , объясняет, почему работают признаки делимости, и распространяет их на другие основания, а завершается заметкой об истории систем счисления и об использовании основания $2$ в компьютерах.

Цели обучения

Понимать позиционную запись и вычислять значение числа, записанного по любому основанию.
Доказывать существование и единственность записи по основанию $b$ и находить её последовательными делениями.
Переводить числа между основаниями $2$ , $8$ , $10$ и $16$ , а также складывать и умножать по основанию $2$ .
Обосновывать признаки делимости на $b - 1$ и на $b + 1$ по основанию $b$ и применять их по основанию $10$ и по другим основаниям.

Позиционная запись

Записывая $2025$ , мы не складываем четыре цифры: каждая из них умножается на степень $10$ , зависящую от её положения. Первая $2$ означает две тысячи; вторая, два десятка. Цифра $0$ показывает, что сотен нет, и, занимая своё место, удерживает остальные цифры в положенных им разрядах.

2025 = 2 \cdot 10^3 + 0 \cdot 10^2 + 2 \cdot 10 + 5

Этот принцип, называемый позиционной записью, не зависит от числа $10$ . Если $b \geq 2$ есть натуральное число, называемое основанием, то цифрами по основанию $b$ называются числа $0, 1, \ldots, b - 1$ , и последовательность цифр $a_k, a_{k-1}, \ldots, a_1, a_0$ , где $a_k \neq 0$ , представляет число

n = a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0

Цифры пишутся одна за другой слева направо, а основание указывается нижним индексом: например, $3412_5$ есть число, которое по основанию $5$ записывается цифрами $3$ , $4$ , $1$ и $2$ , и читается « $3412$ по основанию $5$ ». Говорят, что $a_i$ стоит в разряде $i$ , причём разряды считаются справа, начиная с $0$ . Число без индекса записано по основанию $10$ . По основанию $2$ есть всего две цифры, $0$ и $1$ , которые называются битами; по основанию $16$ нужно шестнадцать цифр, и к десяти обычным цифрам добавляются буквы A, B, C, D, E и F, равные $10$ , $11$ , $12$ , $13$ , $14$ и $15$ .

Значение числа, записанного по основанию $b$ , можно вычислить, раз за разом вынося $b$ за скобки, что избавляет от вычисления степеней: это правило Горнера.

ЛеммаПравило Горнера

Для всякого $k$ и любых чисел $a_0, a_1, \ldots, a_k$ сумма произведений $a_i b^i$ получается, если начать с $a_k$ и $k$ раз повторить действие: умножить на $b$ и прибавить следующий коэффициент.

a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0 = (\cdots((a_k b + a_{k-1}) b + a_{k-2}) \cdots) b + a_0

Доказательство проводится индукцией по $k$ и использует только дистрибутивность. Это выражение есть значение при $x = b$ многочлена $a_k x^k + \cdots + a_1 x + a_0$ , и урок об алгебре многочленов вернётся к нему.

Доказательство

$a_0 = a_0$
База индукции: при $k = 0$ обе части сводятся к $a_0$ , поскольку правило не выполняет ни одного действия.
$\dato{h}{c_k b^k + \cdots + c_1 b + c_0 = (\cdots(c_k b + c_{k-1}) \cdots) b + c_0}$
Предположение индукции: правило верно для всякой суммы из $k + 1$ слагаемых с любыми коэффициентами, доходящей до степени $b^k$ .
$a_{k+1} b^{k+1} + \cdots + a_1 b + a_0 = \resaltar{(a_{k+1} b^k + \cdots + a_2 b + a_1)} \, b + a_0$
Рассмотрим сумму, доходящую до $b^{k+1}$ . По дистрибутивности выносим $b$ за скобки из всех слагаемых, кроме последнего.
$a_{k+1} b^{k+1} + \cdots + a_1 b + a_0 = \resaltar{((\cdots(a_{k+1} b + a_k) \cdots) b + a_1)} \, b + a_0$
Скобка имеет вид, указанный в предположении индукции, с коэффициентами $c_i = a_{i+1}$ ; записываем её по правилу, а умножив её на $b$ и прибавив $a_0$ , получаем правило для $k + 1$ . По принципу индукции правило верно для всякого $k$ .

ПримерЗначение числа, записанного по основанию 5

Вычислить число, которое по основанию $5$ записывается как $3412_5$ , двумя способами: складывая значения разрядов и по правилу Горнера.

Доказательство

$3412_5 = \resaltar{3} \cdot 5^3 + \resaltar{4} \cdot 5^2 + \resaltar{1} \cdot 5 + \resaltar{2}$
Каждая цифра умножается на степень $5$ , соответствующую её разряду: $5^3$ , $5^2$ , $5$ и $1$ .
$3 \cdot \resaltar{125} + 4 \cdot \resaltar{25} + 1 \cdot 5 + 2 = \resaltar{375} + \resaltar{100} + 5 + 2 = \dato{v}{482}$
Вычисляем степени и произведения и складываем.
$3412_5 = \resaltar{((3 \cdot 5 + 4) \cdot 5 + 1)} \cdot 5 + 2$
По правилу Горнера выносим $5$ за скобки из трёх первых слагаемых, а затем из двух первых слагаемых в скобке.
$\resaltar{3 \cdot 5 + 4} = 19, \quad \resaltar{19 \cdot 5 + 1} = 96, \quad \resaltar{96 \cdot 5 + 2} = \resaltar{482}$
Вычисляем изнутри наружу: каждый результат умножается на основание, и к нему прибавляется следующая цифра. Получается то же значение без единой степени.

Далее в этом уроке

Существование и единственность записи
Основания 2, 8 и 16
Действия по основанию 2
Признаки делимости
Делители основания
Делимость на $b - 1$ и на $b + 1$
Историческая и прикладная заметка
Решённые задачи
Число, вдвое большее числа, записанного в обратном порядке
Переставленные цифры
Числа-палиндромы с чётным количеством цифр
Умножение удвоением
Гири Баше
Задачи для самостоятельного решения
Цифры степени без её вычисления
Интернет-адрес
От основания 3 к основанию 9
Делимость на 7, на 11 и на 13
Удвоение в двух системах