Кодирование чисел. Системы счисления

Что нужно знать:
принципы кодирования чисел в позиционных системах счисления
чтобы перевести число, скажем, 12345N, из системы счисления с основанием в десятичную систему, нужно умножить значение каждой цифры на в степени, равной ее разряду:
последняя цифра записи числа в системе счисления с основанием – это остаток от деления этого числа на N
две последние цифры – это остаток от деления на N2 , и т.д.
число 10N записывается как единица и N нулей:

число 10N-1 записывается как N девяток:
число 10N-10M = 10M · (10N-M – 1) записывается как N-M девяток, за которыми стоят M нулей:
число 2N в двоичной системе записывается как единица и N нулей:
число 2N-1 в двоичной системе записывается как N единиц:
число 2N–2K при K < N в двоичной системе записывается как N–K единиц и K нулей:
Что нужно знать:

поскольку , получаем , откуда следует, что
число 3N записывается в троичной системе как единица и N нулей:
число 3N-1 записывается в троичной системе как N двоек:
число 3N – 3M = 3M · (3N-M – 1) записывается в троичной системе как N-M двоек, за которыми стоят M нулей:
Что нужно знать:

можно сделать аналогичные выводы для любой системы счисления с основанием a:
число aN в системе счисления с основанием a записывается как единица и N нулей:
число aN-1 в системе счисления с основанием a записывается как N старших цифр этой системы счисления, то есть, цифр (a-1):
число aN – aM = aM · (aN-M – 1) записывается в системе счисления с основанием a как N-M старших цифр этой системы счисления, за которыми стоят M нулей:
Что нужно знать:

Пример 1
Значение арифметического выражения: 99 – 39 + 919 – 19 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?
Решение:
Приведём все числа к степеням тройки, учитывая, что 19=27-8=33-(2∙31+2∙30):
99 – 39 + 919 – 19= (32)9 – 39 + (32)19 – (33 – (2∙31 + 2∙30)) = 318 – 39 + 338 – 33 + 2∙31 + 2∙30
Перепишем выражение, располагая степени тройки в порядке убывания: 318 – 39 + 338 – 33 + 2∙31 + 2∙30 = 338 + 318 – 39 – 33 + 2∙31 + 2∙30

Пример 1
Сначала рассмотрим часть выражения, в которой имеется два расположенных подряд «минуса»: 318 - 39 ‑ 33:
найдём разность двух крайних чисел: 318 – 33, в её троичной записи 18 – 3=15 «двоек» и 3 «нуля»;
вычтем из этого числа значение 39: одна из «двоек» (на 10-й справа позиции) уменьшится на 1, остальные цифры не изменятся;
итак, троичная запись разности 318 – 39 – 33 содержит 15 – 1=14 «двоек», одну «единицу» и 3 «нуля»
Прибавим к полученному значению сумму: 2∙31 + 2∙30 = 223. В троичной записи результата два крайних справа нуля заменяются на «двойки», остаётся один ноль. Общее количество «двоек»: 14+2=16.

Пример 1
Прибавление значения 338 не изменит количества «двоек» в троичном числе: слева от имеющихся цифр появятся ещё 38 – 18=20 «нулей» и одна «единица» – на 39-й справа позиции.
Итак, результат, записанный в троичной системе, содержит 39 цифр. Его состав: 16 «двоек», 2 «единицы» (их позиции: 39-я и 10-я справа) и 21 «нуль» (39-16-2=21).
Ответ: 16.

Пример 2
Значение арифметического выражения: 98 + 35 – 9
записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Пример 2
Решение:
приведём все слагаемые к виду 3N и расставим в порядке убывания степеней:
98 + 35 – 9 = 316 + 35 – 32
первое слагаемое, 316, даёт в троичной записи одну единицу – она нас не интересует
пара 35 – 32 даёт 5 – 2 = 3 двойки
Ответ: 3.

Пример 3
Сколько значащих нулей в двоичной записи числа
4512 + 8512 – 2128 – 250
Решение:
Общая идея: количество значащих нулей равно количеству всех знаков в двоичной записи числа (его длине!) минус количество единиц
приведём все числа к степеням двойки, учитывая, что 250 = 256 – 4 – 2 = 28 – 22 – 21:
4512 + 8512 – 2128 – 250 = (22)512 + (23)512 – 2128 – 28 + 22 + 21 = 21536 + 21024 – 2128 – 28 + 22 + 21

Пример 3
старшая степень двойки – 21536, двоичная запись этого числа представляет собой единицу и 1536 нулей, то есть, состоит из 1537 знаков; таким образом, остаётся найти количество единиц
вспомним, число 2N–2K при K < N записывается как N–K единиц и K нулей:
для того чтобы использовать это свойство, нам нужно представить заданное выражение в виде пар вида 2N–2K, причём в этой цепочке степени двойки нужно выстроить по убыванию
в нашем случае вы выражении
21536 + 21024 – 2128 – 28 + 22 + 21
стоит два знака «минус» подряд, это не позволяет сразу использовать формулу

Пример 3
используем теперь равенство , так что – 2128 = – 2129 + 2128; получаем
21536 + 21024 – 2129 + 2128 – 28 + 22 + 21
здесь две пары 2N–2K , а остальные слагаемые дают по одной единице
общее число единиц равно 1 + (1024 – 129) + (128 – 8) + 1 + 1 = 1018
таким образом, количество значащих нулей равно 1537 – 1018 = 519
ответ: 519.

Пример 4
Сколько единиц в двоичной записи числа
42015 + 8405 – 2150 – 122
приведём все числа к степеням двойки, учитывая, что 122 = 128 – 4 – 2 = 27 – 22 – 21:
42015 + 8405 – 2150 – 122 = (22)2015 + (23)405 – 2150 – 27 + 22 + 21 =24030 + 21215 – 2150 – 27 + 22 + 21
вспомним, число 2N–2K при K < N записывается как N–K единиц и K нулей:
для того чтобы использовать это свойство, нам нужно представить заданное выражение в виде пар вида 2N–2K, причём в этой цепочке степени двойки нужно выстроить по убыванию

Пример 4
в нашем случае вы выражении
24030 + 21215 – 2150 – 27 + 22 + 21
стоит два знака «минус» подряд, это не позволяет сразу использовать формулу
используем теперь равенство , так что – 2150 = – 2151 + 2150; получаем 24030 + 21215 – 2151 + 2150 – 27 + 22 + 21
здесь две пары 2N–2K , а остальные слагаемые дают по одной единице
общее число единиц равно 1 + (1215 – 151) + (150 – 7) + 1 + 1 = 1210
ответ: 1210.

Пример 5
Решите уравнение
Ответ запишите в троичной системе счисления. Основание системы счисления указывать не нужно.
Решение:
переведём все числа в десятичную систему счисления:
собирая всё в одно уравнение получаем
это уравнение имеет два решения, 6 и -8; основание системы счисления – натуральное число, поэтому ответ – 6
переводим ответ в троичную систему: 6 = 2∙31 = 203.
ответ: 20.

Пример 6
Сколько единиц в двоичной записи числа
42014 + 22015 – 8
Решение:
приведём все числа к степеням двойки:
42014 + 22015 – 8 = (22)2014 + 22015 – 23 = 24028 + 22015 – 23
вспомним, что число 2N-1 в двоичной системе записывается как N единиц: ,
а число 2N–2K при K < N записывается как N–K единиц и K нулей:
согласно п. 2, число 22015 – 23 запишется как 2012 единиц и 3 нуля
прибавление 24028 даст ещё одну единицу, всего получается 2012 + 1 = 2013 единиц
ответ: 2013.

Пример 7
Решите уравнение .
Ответ запишите в шестеричной системе счисления. Основание системы счисления указывать не нужно.
удобнее всего перевести все числа в десятичную систему, решить уравнение и результат перевести в шестеричную систему
получаем
уравнение приобретает вид , откуда получаем
переводим 15 в шестеричную систему счисления:
ответ: 23.

Пример 8
Запись десятичного числа в системах счисления с основаниями 3 и 5 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?
Решение
если запись числа в системе счисления с основанием N заканчивается на 0, то это число делится на N нацело
поэтому в данной задаче требуется найти наименьшее натуральное число, которое делится одновременно на 3 и на 5, то есть, делится на 15
очевидно, что это число 15.

Пример 9
Запись числа 6710 в системе счисления с основанием N оканчивается на 1 и содержит 4 цифры. Укажите основание этой системы счисления N.
Решение:
поскольку запись в системе счисления с основанием N заканчивается на 1, то остаток от деления числа 67 на N равен 1, то есть при некотором целом имеем
следовательно, основание N – это делитель числа 66
с другой стороны, запись числа содержит 4 цифры, то есть

Пример 9
выпишем кубы и четвертые степени первых натуральных чисел, которые являются делителями числа 66:
видим, что из этого списка только для числа N = 3 выполняется условие
таким образом, верный ответ – 3.
можно сделать проверку, переведя число 67 в троичную систему 6710 = 21113

Пример 10
Запись числа 38110 в системе счисления с основанием N оканчивается на 3 и содержит 3 цифры. Укажите наибольшее возможное основание этой системы счисления N.
Решение:
поскольку запись в системе счисления с основанием N заканчивается на 3, то остаток от деления числа 381 на N равен 3, то есть при некотором целом имеем
следовательно, основание N – это делитель числа

Пример 10
с другой стороны, запись числа содержит 3 цифры, то есть
неравенство дает (так как )
неравенство дает (так как )
таким образом, ; в этом диапазоне делителями числа 378 являются числа
9, при получаем запись числа
14, при получаем запись числа
18, при получаем запись числа
наибольшим из приведенных чисел – это 18 (можно было сразу искать подбором наибольший делитель числа 378, начиная с 19 «вниз», на уменьшение)
таким образом, верный ответ – 18.

Пример 11
Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием четыре оканчивается на 11?
Общий подход:
вспомним алгоритм перевода числа из десятичной системы в систему с основанием N , из него следует, что младшая цифра результата – это остаток от деления исходного числа на N , а две младших цифры – это остаток от деления на N2 и т.д.
в данном случае N=4 , остаток от деления числа на N2=16 должен быть равен 114 = 5
потому задача сводится к тому, чтобы определить все числа, которые меньше или равны 25 и дают остаток 5 при делении на 16