8381. Количество чисел

 

На факультативе по математике Орхану встретилась следующая задача: найти количество натуральных чисел от 1 до 10n, все цифры в которых различны.

Поскольку Орхан также ходит на занятия по информатике в физ-мат лицей, он без труда написал программу, вычисляющую ответ. А вы сможете?

 

Вход. Одно целое число n (1 ≤ n ≤ 18).

 

Выход. Выведите количество искомых натуральных чисел.

 

Пример входа 1

Пример выхода 1

1

9

 

 

Пример входа 2

Пример выхода 2

2

90

 

 

РЕШЕНИЕ

рекурсия

 

Анализ алгоритма

Если число состоит как минимум из 11 цифр (и более), то оно обязательно содержит хотя бы две одинаковые цифры. Поэтому для n > 10 ответ будет таким же как и для n = 10.

Отметим, что нас интересуют не n-значные числа, а числа на промежутке от 1 до 10n, которые состоят из однозначных, двузначных, трехзначных, …, n-значных чисел. Рассмотрим, какое количество k-значных чисел (1 ≤ k ≤ n) входит в искомое множество:

·        k = 1: однозначных чисел всего 9 (от 1 до 9);

·        k = 2: двузначных чисел всего 9 * 9 = 81 (цифру десятков можно выбрать 9 способами – от 1 до 9, цифру единиц – тоже 9 способами, так как из цифр от 0 до 9 уже одна использована в десятках);

·        k = 3: трехзначных чисел всего 9 * 9 * 8 = 648 (цифру сотен можно выбрать 9 способами, цифру десятков 9 способами, цифру единиц 8 способами так как из цифр от 0 до 9 две уже использованы);

 

Действуя подобным образом, можно утверждать, что k-значных чисел (при 1 < k ≤ 10) будет в точности 9 * 9 * 8 * 7 * … * (11 – k).

 

Реализация алгоритма

Читаем входное значение n.

 

scanf("%d",&n);

 

Для n > 10 ответ будет таким же как и для n = 10.

 

if (n > 10) n = 10;

 

В переменной res находим количество натуральных чисел от 1 до 10n, все цифры в которых различны.

 

res = 0;

if (n >= 1) res += 9;

if (n >= 2) res += 9*9;

if (n >= 3) res += 9*9*8;

if (n >= 4) res += 9*9*8*7;

if (n >= 5) res += 9*9*8*7*6;

if (n >= 6) res += 9*9*8*7*6*5;

if (n >= 7) res += 9*9*8*7*6*5*4;

if (n >= 8) res += 9*9*8*7*6*5*4*3;

if (n >= 9) res += 9*9*8*7*6*5*4*3*2;

if (n >= 10) res += 9*9*8*7*6*5*4*3*2*1;

 

Выводим ответ.

 

printf("%d\n",res);

 

Реализация алгоритма – при помощи циклов

 

#include <stdio.h>

 

int i, j, n, res, s;

 

int main(void)

{

  scanf("%d",&n);

  if (n > 10) n = 10;

 

  res = 0;

  for(i = 1; i <= n; i++)

  {

    s = 9;

    for(j = 9; j > 10 - i; j--)

      s = s * j;

    res = res + s;

  }

 

  printf("%d\n",res);

  return 0;

}