VPF::палиндромы - Форум программистов

Алкоголик

Дата 15.3.2009, 17:08 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 187
Регистрация: 26.1.2004

Репутация: нет
Всего: нет

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

Soah

Дата 15.3.2009, 17:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 512
Регистрация: 18.2.2009

Репутация: 5
Всего: 54

Цитата(Алкоголик @ 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 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

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;
}

вроде так...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »