Комбинаторные алгоритмы для программистов



             

Целые - часть 2


Следовательно, число

 N - d_k r^k = (d_{k - 1} d_{k - 2},\ldots,d_0 = (e_{k - 1} e_{k - 2} \ldots e_0 )_r

имеет два различных представления, что противоречит предположению, что

N
- наименьшее из таких чисел.

Для доказательства того, что каждое положительное целое имеет представление по основанию

r
, достаточно задать алгоритм, конструирующий (с необходимостью единственное) представление данного числа
N
.

Алгоритм 1. Преобразование числа

N
в его представление
(d_k d_{k {-1} \ldots d_1 d_0 )_r
в системе счисления с основанием
r
.

Он строит последовательность

d_0,d_1,d_2,\ldots d_k
путем повторения деления на
r
и записи остатков. Пусть на первом шаге при делении
N
на
r
остаток будет
d_0
. Частное, полученное в результате первого шага, делим на
r
, вновь полученное частное делим на
r
и так далее. Полученная в результате такого процесса последовательность остатков и будет требуемым представлением
N
по основанию
r
.

Важным обобщением систем счисления с основанием

r
являются смешанные системы счисления, в которых задается не единственное основание
r
, а последовательность оснований
r_0,r_1,r_2,\ldots,
и последовательность (2.2) соответствует целому

N = d_0 + d_1 r_0 + d_2 r_0 r_1 + d_3 r_0 r_1 r_2 + \ldots + d_k \prod\limits_{i = 0}^{k - 1} {r_i },

где теперь каждое

d_i
удовлетворяет неравенству
0 \leqslant d_i < r_i
и
d_k \ne 0
, если
N \ne 0
- тот факт, что каждая такая последовательность соответствует единственному числу и каждое положительное целое число имеет единственное представление, следует из простого обобщения результатов для обычных систем счисления, которые являются частным случаем смешанных систем при
r_i = r,i \geqslant 0
.

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

Пример. Рассмотрим нашу систему измерения времени: секунды, минуты, часы, дни недели и годы. Это - в точности смешанная система с

r_0 = 60,r_1 = 60,r_2 = 24,r_3 = 7,r_4 = 52
.

Представление целого

N
в смешанной системе счисления
(r_0,r_1,\ldots )
осуществляется с помощью алгоритма 2, который является простым обобщением алгоритма 1. Вместо того, чтобы для получения
d_k
в качестве делителя всегда использовалась
r
, в алгоритме 2 используется
r_k
.

Алгоритм 2. Преобразование числа

N
в его представление
(d_0,d_1,\ldots,d_k )
в смешанной системе счисления
(r_0,r_1,r_2,\ldots ).




Содержание  Назад  Вперед