Подсчет плавных чисел

[arthur07]

Доброго времени суток, форумчане!) У меня следующая задача: "Назовем число плавным, если его две соседние цифры различаются не более, чем на 1. По данному натуральному n определите количество плавных натуральных чисел, имеющих длину n . Гарантируется, что ответ не превосходит 231-1." Саму задачу я решил частично, т.е. запрограммировал в лоб, следующим алгоритмом: прохожу циклом от первого числа до последнего с заданным количеством цифр, каждое число проверяю на то, соответствует ли оно принципу плавных чисел, если да, то +1. Алгоритм простой, но не эффективный. Если n=9, то ответа можно и не дождаться. Посоветуйте, пожалуйста, альтернативные алгоритмы или способы оптимизации кода для повышения производительности.

Код: Выделить всё

int kol = 0;
        int n = 8;
        for(int number = (int)Math.pow(10, (n - 1)); number < Math.pow(10, n); number++){
            boolean plavnoe = true;
            int number_now = number;
            while(((number_now / 10) != 0) && (plavnoe == true)){
                double ch_sleva = (number_now % 100) / 10;
                double ch_sprava = number_now % 10;
                double zn = ch_sleva - ch_sprava;
                if((1 < zn) || (zn < -1)){
                    plavnoe = false;
                }
                number_now = number_now / 10;
            }
            if(plavnoe ==  true){
                kol++;
                }
        }
        System.out.println(kol);
    }