Системы счисления. Задача 1-16

Укажите через запятую в порядке возрастания все числа, не превосходящие 30, запись которых в двоичной системе счисления оканчивается на 101. Числа указывайте в десятичной системе счисления.

Ответ
5,13,21,29
Решение

Способ 1

Если число в двоичной системе счисления оканчивается на 1, то искомое число в десятичной системе счисления при делении на 2  должно давать остаток 1, то есть x = 2  y + 1, где x - искомое число, а y - любое целое положительное число.

В свою очередь число y должно делиться на 2 без остатка, так как следующий разряд в двоичной записи числа 0, y = 2 ∗ z , где z любое положительное целое число.

Наконец, для третьего разряда (следующего деления): z = 2 ∗ k  + 1, где k - любое целое положительное число.

Подставляя это выражение в предыдущее получим: y = 2 ∗ (2 ∗ k + 1)  = 4 ∗ k  + 2

Полученное выражение подставим в первое: x = 2 ∗ (4 ∗ k + 2) + 1 =  8 ∗ k + 5 .

При k = 0, получаем x = 5,
при  k = 1, получаем x = 13,
при  k = 2, получаем x = 21,
при  k = 3, получаем x = 29,
при  k = 4, получаем x = 37, но оно уже больше 30.

Способ 2

Искомые числа в двоичной системе счисления занимают 5 разрядов, так как 25 = 32, что больше 30. Запишем все пяти-разрядные двоичные числа, которые оканчиваются на 101:

0 0 1 0 1
0 1 1 0 1
1 0 1 0 1
1 1 1 0 1

Обратите внимание - старшие два разряда последовательно меняются.

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

001012 = 22 + 20 = 5
011012 = 23 + 22 + 20 = 13
101012 = 24 + 22 + 20 = 21
111012 = 24 + 23 + 22 + 20 = 29