Количество монотонных чисел

Количество монотонных чисел


Представим, что увеличивающиеся числа — это числа, цифры которых, при прочтении слева на право, всегда не меньше предыдущих, например: 234559.

И наоборот, в понижающихся числах цифры слева на право не возрастают, например: 97732.

Вам не нужно быть новым Гауссом, чтобы понять, что все числа до ста относятся к одной из этих двух категорий.

Сейчас вам надо сделать функцию, которая подсчитывает количество таких чисел до 10 в н-ной степени (аргумент функции).

#include <string>
#include <cmath>
using namespace std; 
unsigned long long total_inc_dec(unsigned int n) {
  string curr_num; unsigned long long total = 0; int isInc;
  for (int i = 0; i < pow(10, n); i++) {
    curr_num = to_string(i);
    if (int(curr_num.length()) <= 2) {++total;}
    else {
      for (int it = 0; it < int(curr_num.length()); it++) {
        if (it==0) {
          if (curr_num[it] < curr_num[it+1]) {isInc = 1;}
          if (curr_num[it] == curr_num[it+1]) {isInc = 0;}
          if (curr_num[it] > curr_num[it+1]) {isInc = -1;}
        }
        else {
          if (curr_num[it] < curr_num[it+1]) {
              switch(isInc) {
                case 1:
                    if (it == int(curr_num.length()) - 2) {
                        ++total;
                    }
                    break;
                case 0: 
                    isInc = 1;
                    if (it == int(curr_num.length()) - 2) {
                        ++total;
                    }
                    break;
                case -1: 
                    it = int(curr_num.length());
                    break;
              }
          }
          if (curr_num[it] == curr_num[it+1]) {
              if (it == int(curr_num.length()) - 2) {
                ++total;
              }
          }
          if (curr_num[it] > curr_num[it+1]) {
            switch(isInc) {
                case -1:
                    if (it == int(curr_num.length()) - 2) {
                        ++total;
                    }
                    break;
                case 0: 
                    isInc = -1;
                    if (it == int(curr_num.length()) - 2) {
                        ++total;
                    }
                    break;
                case 1: 
                    it = int(curr_num.length());
                    break;
            }
          }
        }
      }
    }
  }
  return total;
}

Сегодня почти в первый раз услышал слово "оптимизировать". Вообще не знаю, как это сделать.



Текущее решение ...

... делает много лишней работы. Перебираются и проверяются все числа. Это не нужно. Например, если число имеет вид 132xxxxxxx, то его и всех его соседей можно пропустить. Они точно не пройдут проверку.

Короткая дорога ...

... подсказана Harry в комментарии к вопросу. Видите числовую последовательность? Отыщите её в энциклопедии OEIS: https://oeis.org/search?q=1+10+100+475+1675+4954+12952. Точного совпадения не будет, но будет ссылка на последовательность без единицы в начале: A364342. Читаем статью, убеждаемся что это наша последовательность, находим формулу, программируем, готово.

Если не повезло ...

... и последовательность не нашлась, придётся решать задачу головой. Будем считать отдельно возрастающие и отдельно убывающие числа.

Возрастающие числа

Нужен опыт чтобы догадаться до an,d - количество возрастающих чисел из ровно n цифр и первая цифра не меньше d. Факты:

  • an,9 = 1 – только одно возрастающее число из n цифр начинается с девятки;
  • a1,d = 10 - d – количество возрастающих чисел из одной цифры легко сосчитать;
  • an,d = an,d+1 + an-1,d – это важная формула. Если число начинается с цифры строго больше d, то такие числа "считает" первое слагаемое. Если число начинается с цифры равной d, то такие числа "считает" второе слагаемое. В этой формуле n > 1 и d < 9.

Нас интересуют все возрастающие числа из не более чем n цифр. Обозначим их через an. Обратите внимание на один индекс.

an = 1 + Σ1≤j≤n aj,1 – надо сложить возрастающие числа всех подходящих длин и добавить единицу для нуля.

Код прямо повторяет формулы:

unsigned long long a(unsigned n, unsigned d) {
    if (d == 9) {
        return 1;
    }
    if (n == 1) {
        return 10 - d;
    }
    return a(n, d + 1) + a(n - 1, d);
}

unsigned long long a(unsigned n) {
    unsigned long long s = 1;
    for (unsigned j = 1; j <= n; ++j) {
        s += a(j, 1);
    }
    return s;
}

Убывающие числа

Схема та же: bn,d - количество убывающих цепочек цифр (не чисел - здесь это важно) из ровно n цифр и первая цифра не больше d.

  • bn,0 = 1 – только одна убывающая цепочка из n цифр начинается с нуля;
  • b1,d = d + 1 – количество убывающих цепочек из одной цифры легко сосчитать;
  • bn,d = bn,d-1 + bn-1,d – если число начинается с цифры строго меньше d, то такие числа "считает" первое слагаемое. Если число начинается с цифры равной d, то такие числа "считает" второе слагаемое. В этой формуле n > 1 и d > 0.

Нас интересуют все убывающие числа (на этот раз не цепочки, числа) из не более чем n цифр. Обозначим их через bn. Снова обратите внимание на один индекс.

bn = (Σ1≤j≤n bj,9) - (n - 1) – надо сложить возрастающие цепочки всех подходящих длин и вычесть цепочки, которые не являются числами. Таких цепочек n - 1: 00, 000, 0000, ...

unsigned long long b(unsigned n, unsigned d) {
    if (d == 0) {
        return 1;
    }
    if (n == 1) {
        return d + 1;
    }
    return b(n, d - 1) + b(n - 1, d);
}

unsigned long long b(unsigned n) {
    unsigned long long s = 0;
    for (unsigned j = 1; j <= n; ++j) {
        s += b(j, 9);
    }
    return s - (n - 1);
}

"Монотонные" числа

Количество "монотонных" чисел cn:

  • c0 = 1 – последовательности a и b не определены для n = 0, требуется отдельное определение;
  • сn = an + bn - 9·n - 1 – число "монотонных" чисел это число возрастающих чисел плюс число убывающих чисел минус те числа, которые мы сосчитали два раза. Два раза сосчитан ноль и числа в которых все цифры одинаковы: 333, 9999. Таких чисел 9·n.
unsigned long long c(unsigned n) {
    if (n == 0) {
        return 1;
    }
    return a(n) + b(n) - 9 * n - 1;
}

Динамическое программирование

Это решение на моём железе считает c25 = 236030401 за одну секунду. Это лучше чем было, но можно ещё лучше. Функции a(n, d) и b(n, d) многократно вызываются для одних и тех же аргументов. Заменим их на таблицы:

unsigned long long a(unsigned n) {
    std::vector<std::array<unsigned long long, 10>> a(n + 1);
    for (unsigned i = 1; i < 10; ++i) {
        a[1][i] = 10 - i;
    }
    for (unsigned j = 2; j <= n; ++j) {
        a[j][9] = 1;
        for (unsigned i = 8; i > 0; --i) {
            a[j][i] = a[j][i + 1] + a[j - 1][i];
        }
    }

    unsigned long long s = 1;
    for (unsigned j = 1; j <= n; ++j) {
        s += a[j][1];
    }
    return s;
}

unsigned long long b(unsigned n) {
    std::vector<std::array<unsigned long long, 10>> b(n + 1);
    for (unsigned i = 1; i < 10; ++i) {
        b[1][i] = i + 1;
    }
    for (unsigned j = 2; j <= n; ++j) {
        b[j][0] = 1;
        for (unsigned i = 1; i < 10; ++i) {
            b[j][i] = b[j][i - 1] + b[j - 1][i];
        }
    }

    unsigned long long s = 0;
    for (unsigned j = 1; j <= n; ++j) {
        s += b[j][9];
    }
    return s - (n - 1);
}

Этот код считает быстро и правильно для n ≤ 375. c375 = 17980269677772943001. Дальше переполняется unsigned long long. Расчёт занимает микросекунды, можно было бы успокоится. Но есть способ быстрее и с меньшим количеством кода.

Метод шаров и перегородок

TODO: продолжить

Так выглядит оптимизированный вариант:

#include <iostream>

unsigned long long cnk(unsigned long long n, unsigned long long k) {
    unsigned long long p = 1;
    for (unsigned long long i = 1; i <= k; ++i) {
        p = p * (n - k + i) / i;
    }
    return p;
}

unsigned long long mono(unsigned n) {
    return cnk(n + 9, 9) + cnk(n + 10, 10) - 10 * n - 1;
}

int main() {
    unsigned n;
    if (std::cin >> n) {
        std::cout << mono(n) << '\n';
    }
}





Report content on this page

Report Page

Please submit your DMCA takedown request to dmca@telegram.org