8.02 Подсчет количества слов/чисел

Решение руками

В 5-й системе счисления всего 5 цифр: 4, 3, 2, 1 и 0. По условию в числе не должно присутствовать цифры 3, поэтому алфавит сокращаетcя до 4, 2, 1, 0. Всего получилось три чётных цифры и одна нечётная.

Так как недопустимо ставить рядом две цифры одинаковой чётности, чётные и нечётные цифры должны чередоваться, таких вариантов всего два: Ч Н Ч Н Ч и Н Ч Н Ч Н.

Запишем эти же варианты, но с количеством цифр из алфавита, не забывая, что на первом месте в числе не может стоять ноль. Получим:

Решение через циклы:

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

Сначала создаём строку a = ’0124’ — это набор доступных цифр (исключаем 3, как указано в условии). Создаём пустое множество count = set() для хранения уникальных чисел, удовлетворяющих условиям.

Используем 5 вложенных циклов for, по одному на каждую позицию числа:

1. for x1 in ’124’ — первая цифра числа, не может быть 0.

2. for x2 in a, for x3 in a, for x4 in a, for x5 in a — перебираем все остальные цифры числа, включая 0.

Внутри циклов формируем строку s = x1+x2+x3+x4+x5, представляющую текущее число.

Затем проверяем условие, что никакие две чётные или две нечётные цифры не стоят рядом. Для этого используем all(int(s[i]) \% 2 != int(s[i+1]) \% 2 for i in range(len(s)-1)) — это проверяет для всех соседних пар цифр, что остатки от деления на 2 различны. Если условие выполняется, добавляем число в множество count.

После завершения перебора всех комбинаций выводим len(count) — количество допустимых чисел.

# Создаём строку с возможными цифрами (исключая 3)
a = "0124"

# Создаём множество для хранения уникальных допустимых чисел
count = set()

# Перебираем первую цифру числа (не может быть 0)
for x1 in "124":
    # Перебираем вторую цифру числа
    for x2 in a:
        # Перебираем третью цифру числа
        for x3 in a:
            # Перебираем четвёртую цифру числа
            for x4 in a:
                # Перебираем пятую цифру числа
                for x5 in a:
                    # Формируем строку числа из выбранных цифр
                    s = x1+x2+x3+x4+x5
                    # Проверяем условие: нет двух чётных или двух нечётных цифр подряд
                    if all(int(s[i]) % 2 != int(s[i+1]) % 2 for i in range(len(s)-1)):
                        # Добавляем число в множество
                        count.add(s)
# Выводим количество допустимых чисел
print(len(count))

Решение через itertools:

Для упрощения перебора всех комбинаций используем модуль itertools и функцию product для генерации всех пятеричных пятизначных комбинаций цифр ’0’-’4’.

1. Преобразуем кортеж i в строку s с помощью ’’.join(i).

2. Проверяем, что в числе нет цифры 3 и первая цифра не равна 0: if not (’3’ in s) and s[0] != ’0’.

3. Для упрощения проверки чередования чётных и нечётных цифр заменяем все чётные цифры на ’2’: s = s.replace(’0’,’2’).replace(’4’,’2’).

4. Проверяем, что одинаковые цифры не стоят подряд: if not(’22’ in s) and not(’11’ in s). Если условие выполнено, увеличиваем счётчик cnt.

В конце выводим cnt — количество допустимых чисел.

from itertools import product

# Счётчик допустимых чисел
cnt = 0

# Перебор всех 5-значных комбинаций цифр "0"-"4"
for i in product("01234", repeat=5):
    # Преобразуем кортеж в строку числа
    s = "".join(i)
    # Проверяем отсутствие цифры 3 и что число не начинается с 0
    if not ("3" in s) and s[0] != "0":
        # Заменяем все чётные цифры на "2"
        s = s.replace("0", "2").replace("4", "2")
        # Проверяем, что одинаковые цифры не стоят подряд
        if not ("22" in s) and not ("11" in s):
            # Если условие выполнено, увеличиваем счётчик
            cnt += 1

# Выводим cnt — количество допустимых чисел
print(cnt)