«Лучшее — враг хорошего». — Вольтер

палиндром-охотник

Лучший способ узнать что-то новое — спорный вопрос, но никто не может искренне не согласиться с тем, что выполнение и повторение — два наиболее эффективных способа достижения такой цели!

Знакомство с информацией через чтение — это хорошо, но этого недостаточно для извлечения информации из долговременной памяти.

Тем не менее, сборка охотника за палиндромами была моим способом лучше понять c++ и основные концепции программирования.

Что такое палиндром?

Палиндром – это слово, число, фраза или другая последовательность символов, которая читается так же, как в прямом, так и в обратном порядке.
Википедия

Но что такое атомный палиндром?

Вот практический пример:

Atomic palindrome example: “civic”

!Atomic palindrome example: “A nut for a jar of tuna”

Эй, переставил что?

Перестановка – это перестановка символов, которая позволяет "aab"превратиться в палиндром: "aba".
Каждый палиндром также является переставленным палиндромом, но наоборот. неправда.

Беги

В основной функции укажите имя файла txt, правильно размещенное в папке artifacts
при создании экземпляра объекта палиндром следующим образом:

«Беги, лес, беги!»
Форрест Гамп (1994)

g++ src/palindrome.cpp main.cpp -o <output file name>

Публичный интерфейс:

Помимо основной функции void Palindrome::readWordsFromFile() объект Palindrome предоставляет средства, реализованные для обеспечения его функциональности. Они есть:

Алгоритмы

Я расскажу о самой сложной функции.

Вероятно, самый известный способ найти перестановку палиндрома — это грубая сила. Он состоит из генерации всех возможных перестановок и проверки, является ли это палиндромом или нет. Но это не самое эффективное решение. Обычно этот алгоритм требует рекурсии, и вы должны знать, насколько это дорого. Используйте его только тогда, когда вам нужно.

Я решил решить эту проблему следующим образом:
определить свойства палиндрома:

if данное слово состоит из нечетного числа символов, каждое из которых встречается minus 1 должно встречаться четное количество раз;
например: madam -> [m,m] + [a,a] minus [d]

else if данное слово состоит из четного числа символов, каждое из которых должно встречаться четное число раз;
например: noon -> [n.n] + [o,o]

Помните: "Каждый переставленный палиндром является палиндромом".

Поместите это в код!

Для этого я полагаюсь на набор контейнеров С++. К счастью, этот тип контейнера позволяет использовать только уникальные элементы. Что ж, остальная часть работы была простой.
Имея строку str, я проверяю количество символов, которые она содержит. Если это нечетное число, мы знаем, что *" четное количество повторяющихся символов минус 1;"*.

Мы можем использовать флаговую переменную charRemaining, чтобы помочь нам сохранить эту информацию:

Итерация str:

Для каждого символа в str я вызываю insert и с помощью second проверяю, существует ли уже элемент.
Простая логика:

if элемент еще не существует, вставьте его.
else if он уже существует, удалите его вхождение с помощью erase.

Тип возвращаемого значения — логическое выражение с простым сравнением:

Вот и все, надеюсь, вам понравилось. Будьте осторожны.

Использованная литература:

Принципы и практика программирования с использованием C++ 2 ed. — Бьярн Страуструп.

Исходный код: Палиндром-охотник.