Как проверить является ли число палиндромом

Вперед, на поиски палиндромов

Не так давно на Хабре была статья про codebattle от hexlet.io. Ну и затянуло же нас с друзьями, это как наркотик! Вроде пытаешься на работу отвлечься, а руки прям сами тянутся зайти на сайт, и все мысли — об оптимизации решений.

И вот однажды попалась мне задачка, звучала она так: «The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». А если по-русски, то так: «десятичное число 585 в двоичном виде выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-ый подобный палиндром». Она совсем не сложная и решена была быстро.

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

Генерируем десятичные палиндромы

Для начала мне стало интересно, сколько же я смогу найти палиндромов на своей машинке. Хоть в чате и не советовали искать больше 22-х, я спокойно нашел 27 всего за 5 секунд, а вот следующий пришел только через 4 с лишним минуты. Дальше я уж ждать не стал — долго что-то. Чтобы начать оптимизацию, я решил поподробнее узнать палиндромы.

Сгенерировал себе несколько штук и начал рассматривать.

1. 1
2. 3
3. 5
4. 7
5. 9
6. 33
7. 99
8. 313
9. 585
10. 717
11. 7447
12. 9009
13. 15351
14. 32223
15. 39993
16. 53235
17. 53835
18. 73737
19. 585585
20. 1758571

По сути числовой палиндром — это некое число, которое взяли, отзеркалили и прикрепили в конец этого же числа. Т.е. взяли число 235, отзеркалили, получили 532 и соединили — получился прекрасный палиндром — 235532. И было принято решение: зачем перебирать все числа в поисках десятичного палиндрома, если можно их просто генерировать. Сказано — сделано!

Запустив, я увидел, что пропущены однознаковые палиндромы, и добавил простой цикл на первые девять чисел.

Запустив ещё раз, я увидел, что ошибка моя была гораздо сильнее. Я ведь совсем забыл про палиндромы с нечетным количеством знаков, таких как 313, 585 или 717! И вот тут мне пришлось крепко задуматься. Посмотрев на список полученных палиндромов, можно увидеть, что палиндромы с нечетным количеством знаков — это те же четные палиндромы, только с центровым знаком. Т.е. берем четный палиндром, вставляем в центр цифры 1-9 и вуаля — нечетные палиндромы готовы. Но! Если я буду вставлять их в этом цикле, я потеряю порядок чисел. Поэтому пришлось внести кардинальные изменения в код и отталкиваться от количества знаков.

Собственно, тут всё просто. Берем сначала одноразрядные числа 1-9. Создаем двухразрядные палиндромы. Следом трёхразрядные. Потом просто увеличиваем разряд и берем числа от 10-99. Получатся палиндромы 4-х и 5-тиразрядные. Ну и т.д.

Тестируем!

Для начала запустил посмотреть 28-ой палиндром. Оказалось что для улучшенной функции это абсолютно плёвая задача. 28-ой был получен за 0.15 секунды! А это значит, что скорость была увеличена больше чем в 1500 раз. Я был доволен. За 5 секунд я мог получить уже более 40-а палиндромов. 50-ый был получен за 2.5 минуты.

Обратив внимание на полученные палиндромы, я заметил, что все они нечетные. И ведь правда! Четные десятичные палиндромы в двоичном виде будут заканчиваться на 0, а так как они всегда начинаются с 1, то и палиндромом быть не могут. А это значит, что их даже проверять не нужно. А так как палиндромы мы генерируем, мы можем пропускать все числа с первой четной цифрой.

Простой continue по условию сразу отмёл. Нам даже не имеет смысла крутить на них цикл. Будем их пролистывать. Попробовав несколько вариантов:

Я остановился на последнем как на самом быстром и получил вот такой код.

Этим мы получили ускорение ещё примерно в два раза. 50-ый был получен за 88 секунд и, на мой взгляд, это был отличный результат!

Генерируем двоичные палиндромы

И вот я уже был готов остановиться и порадоваться, как мне пришла в голову мысль попробовать сформировать двоичные палиндромы. А что? Используемых цифр меньше, четных не сгенирируешь. Одни плюсы кругом!

Немного поразмыслив, я быстренько изменил код и получил:

После тестов я понял, что всё сделал правильно. 28-ой был получен за 0.05 секунды. 50-ый за 48 секунд. Когда брался за эту задачу, такого результата я совсем не ожидал.

Тут я уже решил, что хватит: я и так превзошел все свои ожидания. Хотя вру, конечно. Потом ещё пытался придумать как можно увеличить скорость ещё больше, но уже ничего в голову не пришло. Устал уже, да и ночь на дворе.

Проверка числа – является ли палиндромом

Эта программа меняет на обратное целое число (введенное пользователем) с помощью цикла while. Затем оператор if используется для проверки того, совпадает ли обратное число с исходным числом.

Эта программа на C++ принимает целое число от пользователя, и это целое число переворачивается.

Если обратное целое число равно целому числу, введенному пользователем, то это число является палиндромом, если не это число не является палиндромом.

В приведенной выше программе пользователю предлагается ввести положительное число, которое хранится в переменной num .

Затем число сохраняется в другой переменной n, чтобы проверить его, когда исходное число было перевернуто.

Внутри цикла do … while последняя цифра числа отделяется с помощью кода digit = num% 10 ;. Затем эта цифра добавляется к переменной rev .

Перед добавлением цифры к rev нам сначала нужно умножить текущие данные в переменной rev на 10, чтобы добавить цифру к n- му месту в числе.

Например: в количестве 123, 3 находится в нуль – е место, 2 в одном месте и е 1 в сто – е место.

Таким образом, чтобы добавить еще один номер 4 после того, как 123, нам нужно перенести текущие номера влево, так что теперь 1 в тысяче – е место, 2 в одном – е место, 3 находится в одном – е место и 4 в ноль -е место.

Это легко сделать, умножив 123 на 10, что даст 1230, и сложив число 4, что даст 1234. То же самое сделано в приведенном выше коде.

Когда цикл do while, наконец, заканчивается, мы получаем обратное число в rev . Затем это число сравнивается с исходным числом n .

Как проверить, является ли число палиндромом?

любой язык. Любой алгоритм. (за исключением алгоритма превращения числа в строку, а затем реверсирования строки).

30 ответов:

Это одна из проблем проекта Эйлера. Когда я решил в Haskell я сделал именно то, что вы предлагаете, преобразовать число в строку. Тогда тривиально проверить, что строка является паллиндромом. Если он работает достаточно хорошо, то зачем беспокоиться о том, чтобы сделать его более сложным? Быть паллиндромом-это скорее лексическое свойство, чем математическое.

для любого заданного числа:

если n == rev затем num — палиндром:

работает только для целых чисел. Из постановки задачи неясно, нужно ли учитывать числа с плавающей запятой или ведущие нули.

выше большинства ответов, имеющих тривиальную проблему, заключается в том, что переменная int, возможно, может переполниться.

см.http://leetcode.com/2012/01/palindrome-number.html

нажмите каждую отдельную цифру в стек, а затем вытащите их. Если это то же самое вперед и назад, это палиндром.

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

хотя языки, такие как Java, обертываются при переполнении целых чисел, это поведение не определено в таких языках, как C. [попробуйте повернуть вспять 2147483647 (целое число.MAX_VALUE) в Java] Обходной путь может быть использовать длинный или что-то еще, но стилистически мне это не совсем нравится подход.

(12321 % 10000)/10 = (2321)/10 = 232. И теперь, 10000 должны быть уменьшены в несколько раз 2. Итак, теперь перейдем к Java-коду.

отредактировано согласно Хардик’s, чтобы покрыть случаи, когда есть нули в количестве.

за исключением того, чтобы сделать число строкой,а затем перевернуть строку.

зачем отвергать это решение? это легко реализовать и читабельный. Если вас спросили без компьютера под рукой ли 2**10-23 — это десятичный палиндром, вы наверняка проверите его, записав его в десятичном формате.

по крайней мере, в Python лозунг «строковые операции медленнее, чем арифметика» на самом деле ложен. Я сравнил арифметический алгоритм Сминка с простым разворот строки int(str(i)[::-1]) . Существенной разницы в скорости не было-случалось, что разворот струны был незначительно быстрее.

в языках низкого уровня (C/C++) лозунг может иметь место, но один риск переполнения ошибок с большими числами.

результаты в секундах (чем ниже, тем лучше):

зашнурованный 1.50960231881
арифметика 1.69729960569

в Python, есть быстрый, итерационный способ.

Это также предотвращает проблемы с памятью с рекурсией (например, ошибка StackOverflow в Java)

Я ответил на проблему Эйлера, используя очень грубый способ. Естественно, был гораздо более умный алгоритм на дисплее, когда я добрался до Нового разблокированного связанного потока форума. А именно, у члена, который пошел по ручке Begoner, был такой новый подход, что я решил переопределить свое решение, используя его алгоритм. Его версия была в Python (с использованием вложенных циклов), и я переопределил ее в Clojure (используя один цикл/повторение).

здесь для вашего развлечение:

были также общие ответы на шепелявость, но они были для меня недоступны.

просто для удовольствия, это тоже работает.

вот вариант схемы, которая создает функцию, которая будет работать против любой базы. Он имеет проверку избыточности: быстро возвращает false, если число кратно базе (заканчивается на 0). И он не перестраивает все обратное число, только половину. Это все, что нам нужно.

Дано натуральное n. Определить, является ли это число палиндромом

Вот мой код, но я не знаю, что делать дальше. Как мне дописать этот код, не используя массивы, указатели, строки и тому подобное. Эта задача должна решаться как-то с помощью цикла.

Желательно использовать рекурсивную функцию. Для упрощения решения проблемы можно использовать строковое представление данных. Предлагаю вариант использования нерекурсивной функции, данную вещь можно просто в main использовать.

не забудь прописать setlocate и так далее.

Совет

не используй go to — усложняет восприятие кода и качество кода, посторайся обходится без него