Назовём число красивым если любые две его соседние цифры образуют двузначное число, которое делится либо на 17, либо на 23. Для каждого натурального n (n больше или равно 2) найдите количество n-значных красивых чисел.

30 Янв 2020 в 19:49
146 +1
0
Ответы
1

Для решения этой задачи можно воспользоваться динамическим программированием. Пусть dp[i][j] - количество i-значных чисел, у которых последняя цифра равна j и они являются красивыми.

Используя это определение, мы можем создать следующие рекуррентные соотношения:

dp[i][j] = sum(dp[i-1][k]), где k является таким числом, что числа j10 + k или j10 + j образуют двузначное число, которое делится на 17 или 23.

Таким образом, мы можем выразить количество n-значных красивых чисел как сумму dp[n][j] для всех возможных j от 0 до 9.

Написанный алгоритм будет иметь асимптотическую сложность O(n*10^2).

Пример кода на Python:

n = 3 # задаем значение n
MOD = 10**9 + 7
dp = [[0] * 10 for _ in range(n+1)]
for j in range(1, 10):
if j*10 % 17 == 0 or j*10 % 23 == 0:
dp[2][j] = 1
for i in range(3, n+1):
for j in range(10):
for k in range(10):
if (j*10 + k) % 17 == 0 or (j*10 + k) % 23 == 0 or (j*10 + j) % 17 == 0 or (j*10 + j) % 23 == 0:
dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD
result = sum(dp[n]) % MOD
print(result)

Данный код вычислит количество n-значных красивых чисел для заданного значения n и выведет ответ.

18 Апр 2024 в 18:28
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир