Статья Автор: Деникина Н.В., Деникин А.В.

Числа в системе счисления

Ноль в начале не считается

Число и слово — почти одно и то же. Разряды вместо букв, цифры вместо алфавита.

Разница одна, и она стоит балла.

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

В системе с основанием p цифр ровно p: от 0 до p − 1. Первый разряд беднее остальных на одну цифру.

Перебираем и отбрасываем

product из модуля itertools выдаёт все записи заданной длины. Дальше остаётся отбросить лишние.
Перебирать числа будем программным путём и в виде строк. И тут еще одна ловушка: когда сравниваем текущий символ с цифрой, то цифру заключаем в кавычки, так как работаем со строками!

Первым делом — записи с нулём в начале. Одна строка if, и ловушки нет.

from itertools import product

count = 0
for w in product(sorted("01234567"), repeat=5):   # все записи длины 5 в 8-й системе
    word = "".join(w)                             # соединим цифры в одну строку
    if word[0] != "0":                            # ведущий ноль не считается, цифра в кавычках!
        count = count + 1

print(count)

Вывод программы:

Сколько мы отбросили

Всего записей длины 5 из восьми цифр было бы 8⁵ = 32768.

Программа насчитала 28672. Разница 4096 — это ровно те записи, что начинались с нуля.

Проверка формулой: первый разряд 7 вариантов, остальные по 8. 7 × 8⁴ = 28672. Сходится.

Пример 1. Все цифры различны и чётность чередуется

Сколько существует десятичных четырёхзначных чисел, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом? (Открытый вариант-2025)

Три условия сразу: четыре разряда, все цифры разные, соседи разной чётности.

Каждое проверяем отдельной строкой. set(word) убирает повторы — если длина не изменилась, значит все цифры различны.

from itertools import product

count = 0
for w in product(sorted("0123456789"), repeat=4):
    word = "".join(w)
    if word[0] == "0":
        continue
    if len(set(word)) != 4:                       # если все цифры различны
        continue
    
    # если все соседи разной четности, то считаем это число
    # word - строка, а проверка чётности возможна только у числа, 
    # поэтому int(word...)
    if all(int(word[i]) % 2 != int(word[i + 1]) % 2 for i in range(3)):
        count = count + 1

print(count)

Вывод программы:

Ответ и проверка

Проверим рассуждением. Чётность обязана строго чередоваться, значит есть два шаблона: чётная-нечётная-чётная-нечётная и наоборот.

В каждом шаблоне свои пять цифр на каждую позицию, но повторы запрещены — и первая цифра не ноль. Считая аккуратно, получаем те же 720.

Пример 2. Не более двух раз нечётные рядом

Сколько существует чисел, двенадцатеричная запись которых содержит 5 знаков и в которых не более двух раз нечётные цифры стоят рядом? (О. Лысенков)

Двенадцатеричная система: цифр двенадцать, от 0 до 11. Две последние обозначают буквами a и b.
Сформировать алфавит в программе можно вручую, в виде строки. Можно использовать модуль string для автоматического формирования строки (особенно если можность алфавита большая).

Модуль string содержит несколько констант, возьмем две - цифры (string.digits) и буквы (string.ascii_letters). Объединим все в одну строку и срезом возьмем первые 12 символов. Получим алфавит двенадцатеричной системы счисления.

import string

digits = (string.digits + string.ascii_letters)[:12]

«Не более двух раз рядом» — это про пары соседей. Считаем, сколько раз обе соседние цифры оказались нечётными, и требуем не больше двух.

from itertools import product
import string

digits = (string.digits + string.ascii_letters)[:12]   # алфавит 12СС

count = 0
for w in product(digits, repeat=5):
    word = "".join(w)
    if word[0] == "0":  # если начинается на ноль, то переходим к следующему числу
        continue
    pairs = []
    for i in range(4):
        if int(word[i], 16) % 2 == 1 and int(word[i], 16) % 2 == 1:
            pairs = pairs + 1
    if pairs <= 2:
        count = count + 1

print(count)

Результат работы программы

Что тут легко испортить

Первое: цифры a и b — тоже цифры. Поэтому чётность берём не от символа, а от его десятичного эквивалента int(word[i], 16). Можно проверять по индексу в строке:

digits.index(word[i]) % 2 == 1

Второе: считаем именно пары. В записи из пяти цифр таких пар четыре — с первой по четвёртую позицию.

Третье: три нечётные подряд дают две пары, а не одну. Цикл это учитывает сам, а руками легко просчитаться.

Задача 3. Два условия сразу

Сколько существует чисел, семеричная запись которых содержит 5 знаков и в которых не менее двух раз чётные цифры стоят рядом, при этом никакие три чётные цифры не стоят рядом? (О. Лысенков)

Здесь два ограничения тянут в разные стороны: пар должно быть много, но подряд идти нельзя.

Считаем оба признака и проверяем вместе.

from itertools import product

count = 0
for w in product(sorted("0123456"), repeat=5):
    word = "".join(w)
    if word[0] == "0":
        continue
    pairs = 0
    for i in range(4):
        if int(word[i]) % 2 == 0 and int(word[i + 1]) % 2 == 0:
            pairs = pairs + 1
    three = False
    for i in range(3):
        if int(word[i]) % 2 == 0 and int(word[i + 1]) % 2 == 0 and int(word[i + 2]) % 2 == 0:
            three = True
    if pairs >= 2 and three == False:
        count = count + 1

print(count)

Результат работы программы

Обрати внимание: ноль — чётная цифра. В семеричной системе чётных четыре — 0, 2, 4, 6, а нечётных три — 1, 3, 5.

И первый разряд снова особый: нулём он быть не может, поэтому чётных цифр там только три.

Ловушки

Забыли отбросить записи с нулём в начале. Ответ выйдет больше.
Посчитали цифры неверно: в системе с основанием p их ровно p, от 0 до p − 1.
Решили, что ноль нечётный. Ноль чётный.
Взяли чётность символа вместо чётности цифры — важно для систем больше десятичной.
Считали пары соседей с ошибкой: в записи из n цифр пар n − 1.

Проверь себя

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

Проверить ответ

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

Проверить ответ

Печать