Переворот строки и проверка палиндрома
💻 Информатика · 9 класс
Строки и их перебор
Строка — это последовательность символов, к каждому из которых можно обратиться по его номеру (позиции). Нумерация символов обычно начинается с единицы или с нуля в зависимости от языка программирования. Зная длину строки, можно перебирать её символы в цикле в любом направлении.
Палиндром — это слово или фраза, которые читаются одинаково слева направо и справа налево, например «казак» или «шалаш». Проверка палиндрома — классическая задача обработки строк.
Переворот строки
Чтобы развернуть строку, надо собрать новую строку, добавляя символы исходной в обратном порядке — от последнего к первому.
рез := ""
для i от длина(S) до 1 шаг -1:
рез := рез + S[i]
вывести резЗдесь мы идём с конца строки к началу и приписываем каждый символ к результату. После цикла переменная рез содержит перевёрнутую строку.
Проверка палиндрома
Самый понятный способ — сравнить исходную строку с её перевёрнутой копией. Если они совпали, строка является палиндромом. Более экономный способ — сравнивать символы попарно: первый с последним, второй с предпоследним и так далее.
| Позиции | Символы слова «довод» | Совпадение |
|---|---|---|
| 1 и 5 | д и д | да |
| 2 и 4 | о и о | да |
| 3 | в (середина) | не сравниваем |
Все пары совпали, поэтому слово «довод» — палиндром. Если бы хоть одна пара различалась, проверку можно было бы прекратить досрочно.
Почему достаточно половины
- Сравнение идёт от краёв к центру, поэтому хватает половины длины строки.
- Средний символ при нечётной длине не с чем сравнивать, и его пропускают.
- При первом же несовпадении ответ «не палиндром» уже известен.
Частая ошибка: при проверке фразы забывают убрать пробелы и привести буквы к одному регистру. «А роза упала на лапу Азора» — палиндром только после удаления пробелов и приведения к нижнему регистру.
Способ без новой строки
Перевернуть строку целиком не обязательно. Можно завести два указателя: один на первый символ, другой на последний. На каждом шаге сравнивают символы под указателями и сдвигают их навстречу друг другу — левый вправо, правый влево. Если все сравнения совпали до встречи указателей, строка является палиндромом.
Такой способ экономит память, потому что не создаёт копию строки, и работает быстрее: при первом же несовпадении проверку прекращают. Этот приём с двумя указателями встречается во многих задачах обработки строк и массивов.
Кратко о главном
- К символам строки обращаются по их номеру в цикле.
- Чтобы развернуть строку, символы добавляют в новую строку с конца к началу.
- Палиндром читается одинаково в обе стороны.
- Для проверки сравнивают пары символов от краёв к центру, достаточно половины длины.