Сколько существует восьмеричных пятизначных чисел, не содержащих в своей записи цифру 1, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?
Алгоритм решения задания 8. Часть 3
Пришло время рассмотреть третий тип задания 8 ЕГЭ по информатике. Ранее мы уже научились применять функцию product() для поиска номера подходящего слова в первом типе и количества комбинаций во втором типе этих заданий.
Третий тип похож на второй: мы также считаем последовательности, удовлетворяющие условиям. Главное отличие — фраза «все цифры различны». Поэтому вместо размещений с повторениями используем размещения без повторений.
Примеры этого типа решаются по одному шаблону. Перейдём к алгоритму.
Алгоритм решения
Алгоритм почти совпадает со вторым типом. Единственное принципиальное отличие: вместо product() используем permutations().
Во многих формулировках встречается условие, которое может показаться сложным: цифры одинаковой чётности не должны стоять рядом. Разберём его отдельно.
Начнём с типовой формулировки:
Числа восьмеричные, поэтому алфавит обычно состоит из цифр от 0 до 7. Числа пятизначные, значит укажем r=5. Кроме того, нужно проверить чередование чётных и нечётных цифр.
Переберём все соседние пары. Для каждой пары чётность цифр должна различаться: если первая цифра чётная, вторая должна быть нечётной, и наоборот.
В прошлой статье похожую проверку мы записывали через all(). Здесь для наглядности создадим отдельную функцию alternates_parity(), которая проверит чередование чётности.
Функция принимает один аргумент — проверяемую последовательность цифр в виде строки:
def alternates_parity(digits):В цикле переберём индексы всех цифр, кроме последней. Остановиться нужно на предпоследней позиции, потому что мы сравниваем digits[i] и digits[i + 1].
def alternates_parity(digits):
for i in range(len(digits) - 1):Определим чётность текущей цифры с индексом i:
def alternates_parity(digits):
for i in range(len(digits) - 1):
current_is_even = int(digits[i]) % 2 == 0Аналогично определим чётность следующей цифры:
def alternates_parity(digits):
for i in range(len(digits) - 1):
current_is_even = int(digits[i]) % 2 == 0
next_is_even = int(digits[i + 1]) % 2 == 0Если значения current_is_even и next_is_even равны, обе цифры имеют одинаковую чётность. Такая последовательность не подходит, поэтому функция сразу возвращает False:
def alternates_parity(digits):
for i in range(len(digits) - 1):
current_is_even = int(digits[i]) % 2 == 0
next_is_even = int(digits[i + 1]) % 2 == 0
if current_is_even == next_is_even:
return FalseЕсли цикл завершился, и одинаковая чётность ни разу не встретилась, цифры чередуются. После цикла возвращаем True:
def alternates_parity(digits):
for i in range(len(digits) - 1):
current_is_even = int(digits[i]) % 2 == 0
next_is_even = int(digits[i + 1]) % 2 == 0
if current_is_even == next_is_even:
return False
return TrueФункция для проверки чередования чётности готова. Используем её во всех примерах статьи.
Вернёмся к задаче. Из восьмеричного алфавита сразу исключим цифру 1, потому что она запрещена условием:
from itertools import permutations
# Сразу исключаем 1
alph = '0234567'Далее вставляем код нашей функции:
from itertools import permutations
# Сразу исключаем 1
alph = '0234567'
def alternates_parity(digits):
for i in range(len(digits) - 1):
current_is_even = int(digits[i]) % 2 == 0
next_is_even = int(digits[i + 1]) % 2 == 0
if current_is_even == next_is_even:
return False
return TrueДальше создаём счётчик, перебираем размещения из пяти различных цифр, исключаем ведущий ноль и проверяем чередование чётности. Каждый подходящий вариант увеличивает счётчик.
Вся наша программа в итоге выглядит так:
from itertools import permutations
# Сразу исключаем 1
alph = '0234567'
def alternates_parity(digits):
for i in range(len(digits) - 1):
current_is_even = int(digits[i]) % 2 == 0
next_is_even = int(digits[i + 1]) % 2 == 0
if current_is_even == next_is_even:
return False
return True
count = 0
for val in permutations(alph, r=5):
val = "".join(val)
if val[0] != '0' and alternates_parity(val):
count += 1
print(count)Программа выводит 180. Это ответ.
Пример 1
Перейдём к следующему заданию:
Сколько существует десятичных четырёхзначных чисел, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?
Здесь ещё проще. Алфавит состоит из десятичных цифр от 0 до 9, а числа четырёхзначные, поэтому укажем r=4.
Для проверки чередования чётности используем готовую функцию. Меняются только алфавит и значение r:
from itertools import permutations
alph = '0123456789'
def alternates_parity(digits):
for i in range(len(digits) - 1):
current_is_even = int(digits[i]) % 2 == 0
next_is_even = int(digits[i + 1]) % 2 == 0
if current_is_even == next_is_even:
return False
return True
count = 0
for val in permutations(alph, r=4):
val = "".join(val)
if val[0] != '0' and alternates_parity(val):
count += 1
print(count)Программа выводит 720. Это ответ.
Пример 2
Для закрепления рассмотрим ещё одно задание:
Сколько существует шестнадцатеричных трёхзначных чисел, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?
Тут мы впервые работаем с системой счисления выше 10 в задании 8. Здесь воспользуемся строками из модуля string.
Вспомним, как получить цифры шестнадцатеричной системы счисления:
from string import ascii_uppercase, digits
print(digits + ascii_uppercase[:6])
>>>0123456789ABCDEFС помощью этих строк сформируем алфавит:
from string import ascii_uppercase, digits
from itertools import permutations
alph = digits + ascii_uppercase[:6]Но функцию alternates_parity() нужно немного изменить. При преобразовании шестнадцатеричной цифры в число передадим функции int() основание системы счисления — 16.
Если попытаться преобразовать шестнадцатеричное число A1 без указания основания, Python выдаст ошибку:
hex_num = "A1"
print(int(hex_num))
>>>ValueError: invalid literal for int() with base 10Вторым аргументом int() укажем основание системы счисления:
hex_num = "A1"
print(int(hex_num, 16))
>>>161С учётом этого исправим функцию alternates_parity():
from string import ascii_uppercase, digits
from itertools import permutations
alph = digits + ascii_uppercase[:6]
def alternates_parity(value):
for i in range(len(value) - 1):
current_is_even = int(value[i], 16) % 2 == 0
next_is_even = int(value[i + 1], 16) % 2 == 0
if current_is_even == next_is_even:
return False
return TrueОстальная часть программы уже знакома. Полное решение выглядит так:
from string import ascii_uppercase, digits
from itertools import permutations
alph = digits + ascii_uppercase[:6]
def alternates_parity(value):
for i in range(len(value) - 1):
current_is_even = int(value[i], 16) % 2 == 0
next_is_even = int(value[i + 1], 16) % 2 == 0
if current_is_even == next_is_even:
return False
return True
count = 0
for val in permutations(alph, r=3):
val = "".join(val)
if val[0] != '0' and alternates_parity(val):
count += 1
print(count)Программа выводит 840. Это ответ.
Итоги
Мы разобрали три типа задания 8 и научились выбирать между product() и permutations(). В завершение запишем шаблон для третьего типа:
from itertools import permutations
alph = '*1'
count = 0
for val in permutations(alph, r=*2):
val = "".join(val)
if val[0] != '0' and *3:
count += 1
print(count)Здесь:
*1— алфавит из условия: для восьмеричной системы цифры от 0 до 7, для троичной — от 0 до 2 и так далее;*2— количество цифр в числе; значение подставляется без кавычек;*3— остальные условия. Для чисел не забудьте отдельно исключить ведущий ноль.
На этом мы закончили разбор алгоритмов решения задания 8 ЕГЭ по информатике. А попрактиковаться в решении заданий данного типа вы можете в нашем тренажёре.
