Найти количество чисел заданного порядка, модуль разницы соседних цифр которых не больше 1

Question

[mixator]

Нужно найти количество чисел заданного порядка, модуль разницы соседних цифр которых не больше 1

То есть:
Для чисел порядка 1(все однозначные числа) = 9 (нет соседних цифр)
Для чисел порядка 2(двухзначные) = 26(10, 11, 20, 21, 22, 23... )

Реализация простого перебора не интересует.
Интересует есть ли формула по которой можно найти это количество.

Ответ:
goo.gl/nC0XIY

a(n) = Sum_{r=0..9} u(n,r) where u(n,r) = 0 if r<0 or r>9, u(1,0) = 0, u(1,r) = 1 for 1<=r<=9, and otherwise u(n,r) = u(n-1,r-1) + u(n-1,r) + u(n-1,r+1).

G.f.: -x*(3*x^4-18*x^3-9*x^2+28*x-9)/(x^5-6*x^4-x^3+10*x^2-6*x+1).

Спасибо

Answer 1

[Mrrl]

Формула, несомненно, существует. Правда, в ней будут присутствовать корни многочлена (z^5-6*z^4+10*z^3-z^2-6*z+1)*(z^5-4*z^4+2*z^3+5*z^2-2*z-1) (неразрешимого в радикалах), и выписать её совсем не просто. Но, при большой необходимости, возможно.
Впрочем, если в формуле может присутствовать матрица, то ответ такой:

(1 1 1 1 1 1 1 1 1 1)*(M^(n-1))*transpose(0 1 1 1 1 1 1 1 1 1),

где M - матрица 10х10, в которой в клетках (m,n), для которых abs(m-n)<2, стоят единицы, а в остальных клетках - нули.

Comments

[mixator]

не совсем понял идею с матрицей, можете разжевать?

[Mrrl]

Пусть мы уже посчитали числа длины N-1. На 0 кончается a0 чисел, на 1 - a1,... на 9 - a9 чисел. Тогда среди чисел длины N на 0 будет заканчиваться a0+a1, на 1 - a0+a1+a2,..., на 9 - a8+a9 чисел. Обозначим вектор-столбец (a0,a1,...,a9) как v{N-1}, а (a0+a1, a0+a1+a2,..., a8+a9) как vN. Нетрудно увидеть, что vN=M*v{N-1}, где M - матрица, описанная выше. Если v1=(0,1,1,...,1) - вектор, содержащий количество чисел длины 1 (все цифры кроме нуля), то получим, что vN=M^(N-1)*v1. Осталось найти сумму его координат - для этого умножим вектор слева на строку (1,1,1...,1). И получим формулу с матрицей.
Чтобы получить формулу без матрицы, надо перейти в её жорданов базис - найти собственные значения и собственные векторы. Собственные значения будут корнями характеристического многочлена (z^5-6*z^4+10*z^3-z^2-6*z+1)*(z^5-4*z^4+2*z^3+5*z^2-2*z-1). В конечном итоге, формула будет выглядеть как S(N)=sum(ci*zi^N), где zi - корни многочлена, а ci - какие-то коэффициенты. Чтобы их найти, придётся немного посчитать, но при наличии хорошей системы компьютерной алгебры это можно сделать за несколько часов (или даже быстрее - если система хорошо знакома).

[mixator]

Понял. Спасибо

Answer 2

[Rsa97]

У вас уже неправильно, для двузначных будет (10, 11, 12, 21, 22, 23, 32, 33, 34...).
Модуль разницы:

Верхнюю оценку получить легко, 10*3^(n-1), а вот точное число посчитать по формуле скорее всего не получится, 0 и 9 портят всю картину.

Comments

[mixator]

Модуль разницы не: abs(a-b) < 2 ?
Код, который считает прямым перебором: https://ideone.com/BeF3IN

[Rsa97]

У Вас указано 20 в качестве решения и не указано 12. Может просто опечатка

[mixator]

Опечатка, прошу прощения.

[Rsa97]

Можно делать рекурсивный перебор:

int num(int len, int prefix) {
    if (len == 0)
        return 1;
    return (prefix > 0 ? num(len-1, prefix-1) : 0)+
               num(len-1, prefix)+
               (prefix < 9 ? num(len-1, prefix+1) : 0);
}

void main(void) {
  int N = 10;
  int len = 0;
    for (int i = 1; i <= 9; i++)
        len += num(N-1, i);
}

[mixator]

К сожалению, не вижу преимущества перед прямым перебором

[Rsa97]

Да, подумав понял, что рекурсия здесь тоже не оптимальна - большинство веток рассчитываются по три раза. Быстрее будет такая реализация (по смыслу очень близко к приведённой матричной формуле):

void main() {
  unsigned long long digits[2][12] = { 
    { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0},
    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} };
  int row = 0;
  int N = 20;
  unsigned long long res;
    res = 0;
    for (int j = 1; j < 10; j++)
        res += digits[row][j+1];
    cout << "1 => " << res << endl; 
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < 10; j++)
            digits[1-row][j+1] = digits[row][j]+digits[row][j+1]+digits[row][j+2];
        row = 1-row;
        res = 0;
        for (int j = 1; j < 10; j++)
            res += digits[row][j+1];
        cout << (i+1) << " => " << res << endl; 
    }
}

[Mrrl]

Да, если не пытаться выписать формулу, а программировать алгоритм (при небольших N), то, конечно, надо делать так. Хотя ряды можно и не перещёлкивать:

int A[12]={0,0,1,1,1,1,1,1,1,1,1,0},B[12];
int res=9;
printf("1 => 9\n");
for(int K=2;K<=N;K==){
for(int a=1;a<=10;a++) res+=B[a]=A[a-1]+A[a+1];
for(int a=1;a<=10;a++) A[a]+=B[a];
printf("%d => %d\n",K,res);
}

Будет ли это быстрее, не знаю. Но квадратных скобок точно меньше :)

[Mrrl]

(там не K== а K++)

[Rsa97]

И в pritnf не res, а res-A[1]. Число с 0 начинаться не может.
А вообще, результат имеет порядок 3^N+1, поэтому для N > 40 придётся уже писать свою длинную арифметику.

[Mrrl]

Числа, начинающиеся с нуля, были отсеяны в инициализации массива A. A[1] - это количество чисел, оканчивающихся на нуль.
А свою длинную арифметику писать незачем, достаточно использовать double.