Задача к ЕГЭ по информатике на тему «количество информации и комбинаторика» №6

Просмотров 6 Комментарии 0

Сколько существует шестизначных чисел, в двоичной записи которых нет двух стоящих рядом одинаковых цифр?

Решение 1: ручками

Все шестизначные числа это числа от 100000 до 999999 включительно. Стоит узнать, чему равны и сколько цифр в двоичной записи 100000 и 999999:

$10000010 = 110000110101000002$ , кол-во цифр 17,

$99999910 = 111101000010001111112$ , кол-во цифр 20.

Поскольку по усл. в двоичной записи не может быть двух стоящих рядом одинаковых цифр, то значит мы ищем числа, где цифры чередуются, т.е с 1 на 0. И при этом, количество цифр не меньше 17 и не больше 20. Подходящие нам варианты: $101010101010101010$ , $1010101010101010101$ , $10101010101010101010$ .

Решение 2: программой

k = 0
for x in range(100000, 1000000):
    s = bin(x)[2:]
    if all(s[y] != s[y+1] for y in range(len(s) - 1)):
        k += 1
print(k)

Ответ: 3