Question

Сколько существует чисел с суммой цифр 10, в записи которых нет ни одного нуля?

Answer 1

Ответ:

9 или 5

Пошаговое объяснение:

1+9

2+8

3+7

4+6

5+5

дальше те же числа но в другом порядке

6+4

7+3

8+2

9+1

Answer 2

Давайте разберемся с этой задачей.

Чтобы найти количество чисел с суммой цифр 10, в записи которых нет ни одного нуля, давайте рассмотрим все возможные комбинации цифр от 1 до 9, так как у нас нет нулей в числах. Мы ищем все способы представить число 10 в виде суммы таких цифр.

Давайте воспользуемся методом динамического программирования. Создадим массив dp, где dp[i] будет означать количество чисел с суммой цифр i, в которых нет ни одного нуля.

Изначально dp[0] = 1 (только один способ - это пустое число). Затем мы будем заполнять массив dp поочередно для всех сумм от 1 до 10.

plaintextCopy code
dp[0] = 1
dp[1] = 1
dp[2] = 1
...
dp[9] = 1

Когда мы доходим до dp[i], чтобы посчитать количество чисел с суммой цифр i, мы можем рассмотреть все возможные предыдущие суммы (от 1 до i-1) и добавить к ним цифру от 1 до 9. Но при этом нам нужно учесть, что числа не должны содержать нули.

Итак, для dp[i], мы делаем следующее:

plaintextCopy code
dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-9]

Теперь мы можем последовательно заполнить массив dp и найти dp[10], что будет искомым количеством чисел.

plaintextCopy code
dp[0] = 1
dp[1] = 1
dp[2] = 2
dp[3] = 4
dp[4] = 8
dp[5] = 16
dp[6] = 32
dp[7] = 64
dp[8] = 128
dp[9] = 256
dp[10] = dp[9] + dp[8] + ... + dp[1] = 256 + 128 + ... + 1 = 511

Итак, количество чисел с суммой цифр 10, в записи которых нет ни одного нуля, равно 511.