Подсчет плавных чисел
Добавлено: 14 окт 2012, 21:26
Доброго времени суток, форумчане!) У меня следующая задача: "Назовем число плавным, если его две соседние цифры различаются не более, чем на 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);
}