«Лучшее — враг хорошего». — Вольтер
палиндром-охотник
Лучший способ узнать что-то новое — спорный вопрос, но никто не может искренне не согласиться с тем, что выполнение и повторение — два наиболее эффективных способа достижения такой цели!
Знакомство с информацией через чтение — это хорошо, но этого недостаточно для извлечения информации из долговременной памяти.
Тем не менее, сборка охотника за палиндромами была моим способом лучше понять 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. — Бьярн Страуструп.
Исходный код: Палиндром-охотник.