Решение без строк
Тем, кто справился с первой частью, предлагают задачу со звёздочкой — сделать то же самое, но не используя строки, а работая только с числами. Попробуем и мы.
Сделаем в JavaScript функцию, которая будет возвращать true, если в переменной лежит палиндром, и false — если нет. Всё остальное будем писать внутри этой функции:
Теперь обработаем три стандартные ситуации:
- Если в переменной лежит ноль, то это палиндром.
- Если переменная меньше ноля, то это не палиндром.
- Если переменная делится на 10 без остатка — это тоже не палиндром.
Запишем это на JavaScript:
Чтобы проверить, является ли число палиндромом или нет, можно сделать так: отрезаем от числа цифры справа по одной, добавляем их в начало нового числа и постоянно сравниваем новое и старое значение. Если они станут равны — перед нами палиндром. Читайте комментарии, чтобы вникнуть в то, что происходит в коде:
Для запуска кода просто вызываем функцию и передаём её нашу переменную:
Чтобы попрактиковаться, попробуйте сделать такое же, но на Python и не подглядывая в наш код.
Текст:
Михаил Полянин
Редактор:
Максим Ильяхов
Художник:
Алексей Сухов
Корректор:
Ирина Михеева
Вёрстка:
Кирилл Климентьев
Соцсети:
Виталий Вебер
РЕШЕНИЕ
динамическое
программирование
Анализ алгоритма
Пусть dp[i][j]
хранит количество палиндромов, которое можно получить из подстроки si…sj удалением букв. Тогда dp[i][i] = 1, так как слово
из одного символа является палиндромом.
Пусть si = sj = X, подстрока si…sj имеет вид XPX. Здесь через P обозначена подстрока
si+1…sj-1. Разобьем палиндромы строки XPX на непересекающиеся
группы:
·включающие левый символ X и не включающие правый
символ X. Их число равно количеству палиндромов в строке XP минус количество
палиндромов в P, то есть dp[i][j
– 1] – dp[i + 1][j – 1];
·включающие правый символ X и не включающие левый
символ X. Их число равно количеству палиндромов в строке PX минус количество
палиндромов в P, то есть dp[i + 1][j] – dp[i + 1][j – 1];
·палиндромы строки P. Их количество равно dp[i
+ 1][j – 1]. Однако с каждым
палиндромом Q строки P мы можем
построить и палиндром XQX.То
есть палиндромов типа XQX также будет dp[i + 1][j – 1].
·палиндром XX (одинпалиндром).
Общее количество палиндромов для случая si = sj равно
(dp[i][j – 1] – dp[i + 1][j – 1]) +
(dp[i
+ 1][j] – dp[i + 1][j – 1]) +
2 * dp[i
+ 1][j – 1] +
1
= dp[i][j – 1] + dp[i + 1][j] + 1.
Пусть si ≠ sj, подстрока si…sj имеет вид XPY (si = X, sj = Y). Разобьем палиндромы строки XPY на непересекающиеся группы:
·включающие символ X и не включающие символ Y. Их
число равно количеству палиндромов в строке XP минус количество палиндромов в
P, то есть dp[i][j
– 1] – dp[i + 1][j – 1];
·включающие символ Y и не включающие символ X. Их
число равно количеству палиндромов в строке PY минус количество палиндромов в
P, то есть dp[i + 1][j] – dp[i + 1][j – 1];
·палиндромы строки P. Их количество равно dp[i
+ 1][j – 1].
Общее количество палиндромов для случая si ≠ sj равно
(dp[i][j – 1] – dp[i + 1][j – 1]) +
(dp[i
+ 1][j] – dp[i + 1][j – 1]) +
dp[i
+ 1][j – 1]
= dp[i][j
– 1] + dp[i + 1][j] – dp[i + 1][j – 1].
Пример
Из строки aba удалением
букв можно получить 5 палиндромов.
Рассмотрим строку abab = ss1s2s3. Поскольку s ≠ s3, то подстрока s…s3 имеет вид XPY. Отсюда dp
=
(dp[] – dp) +
(dp –
dp) +
dp[2=
= dp[] + dp – dp[2 = 5 + 5 – 2 = 8.
Рассмотрим строку abcba = ss1s2s3s4. Поскольку s= s4, то подстрока s…s4 имеет вид XPX. Отсюда dp
=
(dp[] – dp) +
(dp –
dp) +
2 * dp[3 +
1=
= dp[] + dp[4+ 1 = 6 + 6 + 1 = 13.
Реализация алгоритма
В массиве s храним входную строку. Объявим массив dp.
#define MAX 65
char
s;
long long dp;
Читаем входную строку. Заполняем dp[i][i] = 1.
gets(s);
n = strlen(s);
memset(dp,0,sizeof(dp));
for(i
= 0; i < n; i++) dp = 1;
Перебираем длины подстрок len и позиции их начала i.
for(len
= 1; len < n; len++)
for(i
= 0; i + len < n; i++)
{
j = i + len;
Для каждой такой подстроки si…sj
вычисляем значение dp[i][j] – количество палиндромов, которое
можно получить из нее удалением символов. Поскольку подстроки si…sj перебираются в порядке возрастания их длин, то
значения dp на всех подотрезках меньшей длины уже вычислены.
if (s == s)
dp = dp + dp + 1;
else
dp = dp + dp —
dp;
}
Выводим ответ.
printf(«%lld\n»,dp);
Реализация алгоритма – рекурсия
#include<stdio.h>
#include<string.h>
#defineMAX 61
В массиве s храним входную строку. Объявим массив
dp.
char s;
longlong dp;
int i, j,
len, n;
longlong f(inti, intj)
{
Если i > j, то палиндромов не существует.
if (i > j) return 0;
Слово из
одного символа является палиндромом, установим dp[i][i] = 1.
if (i == j) return dp = 1;
Если значение dp[i][j] уже вычислено, то
возвращаем его.
if (dp != -1) return dp;
Вычисляем значение dp[i][j] в зависимости от того, одинаковы или не одинаковы
символы si и sj.
if (s == s)
dp = f(i + 1, j) + f(i, j — 1) + 1;
else
dp = f(i + 1, j) + f(i, j — 1) — f(i + 1, j — 1);
return dp;
}
int main(void)
{
Основная часть программы. Читаем входную строку s. Инициализируем массив dp.
gets(s); n =
strlen(s);
memset(dp, -1, sizeof(dp));
Выводим ответ.
printf(«%lld\n», f(0, n — 1));
return 0;
}
Java реализация
import java.util.*;
publicclass Main
{
static String s;
staticlongdp[][];
staticlong f(inti, intj)
{
if (i > j) return 0;
if (i == j) returndpi] = 1;
if (dpi] != -1) returndpi];
if (s.charAt(i) == s.charAt(j))
dpi] = f(i + 1,j) + f(i,j — 1) + 1;
else
dpi] = f(i + 1,j) + f(i,j — 1) — f(i + 1,j — 1);
returndpi];
}
publicstaticvoid
main(String[] args)
{
Scanner con = new Scanner(System.in);
s = con.nextLine();
intn = s.length();
dp = newlongn];
for(inti = 0; i < n; i++)
for(intj = 0; j < n; j++)
dpi] = -1;
System.out.println(f(0,n-1));
con.close();
}
}
Решение, где используем строки
Самый простой способ проверить, число в переменной палиндром или нет, — преобразовать его в строку, выставить знаки задом наперёд и сравнить с оригиналом. Этим мы сразу решаем проблему отрицательных чисел, когда «−121»превращается в «121−» и сразу становится ясно, что это не палиндром.
Сначала решим это на Python. Тут вообще суть в одной строке:
Здесь мы использовали трюк с переворачиванием строки без её изменения — применили конструкцию . Работает это так:
- Первым параметром указывают начало, откуда начинать обработку строки. Раз ничего не указано, то начинаем с первого символа.
- Второй параметр — на каком по счёту символе надо остановиться. Здесь тоже ничего нет, поэтому алгоритм пройдёт до конца строки.
- Последний параметр — шаг и направление обработки. У нас указана минус единица, значит, алгоритм обработает строку справа налево, на каждом шаге считывая по символу.
- В итоге этот код вернёт нам строку, собранную в обратном порядке, при этом с оригинальной строкой ничего не случится — она останется неизменной.
Мы уже делали похожие штуки, когда писали свой генератор новых слов, но там было одно двоеточие, а здесь два.
Теперь решим это же, но на JavaScript:
Здесь мы использовали другой метод пересборки:
- X.toString() — переводит число в строку.
- split(«») — разбивает строку на массив из символов. В кавычках принцип разделения — если бы там была точка, то разделили бы на местах точек. А так как там пустота, то делится вообще по каждому из символов.
- reverse() — меняет элементы в массиве в обратном порядке.
- join(«») — добавляет результат к пустой строке, чтобы на выходе получить строку в обратном порядке.
