Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > палиндромы

Автор: Алкоголик 15.3.2009, 17:08

Здраствуйте.
Интересует такой алгоритм.
Дан интервал например от 1 до 10000000 нужно найти в нем количество палиндромов(чисел которые читаются справа на лево, так же как и ислева на право). Простой перебор это не интерестно и не оптимально. Что посоветуете?

Автор: Soah 15.3.2009, 17:51

Цитата(Алкоголик @ 15.3.2009, 17:08

)

Что посоветуете?

придумать формулу

а принимает значения [1,9] -> 9 значений
b,c, d, e,... принимают значения [0,9] -> 10 значений

aa -> 9 палиндромов
aba -> 9*10 = 90 палиндромов
abba -> 9*10 = 90 палиндромов
abcba - > 9*10*10 = 900 палиндромов
abccba - > 9*10*10 = 900 палиндромов
...

Автор: Silent 18.3.2009, 13:29

N - количество цифр в числе, F(x) - количество палиндромов от от 10^(x-1)..10^х
тогда F(x+1)=10*F(x), х%2!=0 (поскольку abba -> abZba, Z=(0..9))
а для x%2==0 формула проста: F(x)=10^(x/2)-1
остается пройтись и сложить циклом:

Код


int F(int x)
{
  if (x%2==0) return 10^(x/2)-1;
  else return 10*F(x-1);
}
int Count(int K)  //до какого разряда считаем - если 1..10000000 - то K=7
{
  int res = 0;
  for (int i=1;i<=K;i++) res += F(i);
  return res;
}

вроде так...