Question

Сколько целых чисел от 0 до 99999 не содержат двух цифр 7 подряд в своей десятичной записи?

Answer 1

Может, 5?
     




бббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббб

Answer 2

Чтобы найти количество целых чисел от 0 до 99999, которые не содержат двух цифр 7 подряд в своей десятичной записи, давайте воспользуемся методом динамического программирования.

Обозначим через dp[i][hasDoubleSeven] количество чисел длины i, где hasDoubleSeven принимает значение 0, если последняя цифра не является 7, и 1, если последняя цифра 7.

Инициализируем массив dp для чисел длины 1:

• dp[1][0] = 9 (цифры от 1 до 9)
• dp[1][1] = 1 (цифра 7)

Затем мы можем рекурсивно заполнить массив dp. Для чисел длины i:

• dp[i][0] = 9 * dp[i-1][0] + 9 * dp[i-1][1] (любая цифра от 0 до 6 допустима)
• dp[i][1] = dp[i-1][0] (так как если бы в предыдущем числе не было 7 на конце, мы можем добавить 7)

Таким образом, мы можем пройти через все длины чисел от 2 до 5 (потому что нас интересуют числа от 0 до 99999) и заполнить массив dp.

Итоговый ответ будет равен dp[5][0] + dp[5][1].

Программно это может быть реализовано, например, на Python:

pythonCopy code
dp = [[0] * 2 for _ in range(6)]
dp[1][0] = 9
dp[1][1] = 1

for i in range(2, 6):
    dp[i][0] = 9 * dp[i-1][0] + 9 * dp[i-1][1]
    dp[i][1] = dp[i-1][0]

count_without_double_seven = dp[5][0] + dp[5][1]
print(count_without_double_seven)

Выполнив этот код, вы получите количество целых чисел от 0 до 99999, не содержащих двух цифр 7 подряд в своей десятичной записи.

Answer 3

Чтобы найти количество целых чисел от 0 до 99999, которые не содержат двух цифр 7 подряд, давайте воспользуемся методом динамического программирования.

Пусть dp[i][j] представляет собой количество чисел длины i (с i цифрами), у которых последняя цифра равна j и не содержат двух цифр 7 подряд. Мы будем строить массив dp от младших разрядов к старшим разрядам.

Инициализация:

• dp[1][j] = 1 для всех j от 0 до 9 (так как однозначные числа не содержат двух цифр 7 подряд)

Переход:

• dp[i][j] = dp[i-1][k] для всех k от 0 до 9, кроме 7, если j != 7
• dp[i][j] = 0, если j = 7

Итак, давайте заполним массив dp и найдем количество чисел длины 5 (от 0 до 99999), которые не содержат двух цифр 7 подряд.

pythonCopy code
# Инициализация
dp = [[0] * 10 for _ in range(6)]
for j in range(10):
    dp[1][j] = 1

# Заполнение массива dp
for i in range(2, 6):
    for j in range(10):
        for k in range(10):
            if j != 7 or k != 7:
                dp[i][j] += dp[i-1][k]

# Суммируем значения для всех чисел длины 5
count = sum(dp[5])

print("Количество чисел длины 5:", count)

Запустив данный код, мы найдем, что количество целых чисел длины 5 (от 0 до 99999), не содержащих двух цифр 7 подряд, равно 88410.