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

Question

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

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

Answer 1

Для любого заданного номера:

n = num;
rev = 0;
while (num > 0)
{
    dig = num % 10;
    rev = rev * 10 + dig;
    num = num / 10;
}

Если n == rev, то num является палиндромом:

cout << "Number " << (n == rev ? "IS" : "IS NOT") << " a palindrome" << endl;

Answer 2

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

Answer 3

def ReverseNumber(n, partial=0):
    if n == 0:
        return partial
    return ReverseNumber(n // 10, partial * 10 + n % 10)

trial = 123454321
if ReverseNumber(trial) == trial:
    print("It's a Palindrome!")

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

Answer 4

Над большинством ответов, имеющих тривиальную проблему, может быть переполнение переменной int.

См. http://articles.leetcode.com/palindrome-number/

boolean isPalindrome(int x) {
    if (x < 0)
        return false;
    int div = 1;
    while (x / div >= 10) {
        div *= 10;
    }
    while (x != 0) {
        int l = x / div;
        int r = x % 10;
        if (l != r)
            return false;
        x = (x % div) / 10;
        div /= 100;
    }
    return true;
}

Answer 5

int is_palindrome(unsigned long orig)
{
    unsigned long reversed = 0, n = orig;

    while (n > 0)
    {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }

    return orig == reversed;
}

Answer 6

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

Answer 7

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

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

Теперь концепция палиндромного числа заключается в том, что число должно читаться одинаково вперед и назад. Отлично. Используя эту информацию, мы можем сравнить первую цифру и последнюю цифру. Хитрость в том, что для первой цифры нам нужен порядок числа. Скажем, 12321. Разделив это на 10000, мы получим лидирующие 1. Трейлинг 1 можно получить, взяв мод с 10. Теперь, чтобы уменьшить его до 232. (12321 % 10000)/10 = (2321)/10 = 232. И теперь 10000 нужно было бы сократить в 2 раза. Итак, теперь перейдем к коду Java ...

private static boolean isPalindrome(int n) {
    if (n < 0)
        return false;

    int div = 1;
    // find the divisor
    while (n / div >= 10)
        div *= 10;

    // any number less than 10 is a palindrome
    while (n != 0) {
        int leading = n / div;
        int trailing = n % 10;
        if (leading != trailing)
            return false;

        // % with div gets rid of leading digit
        // dividing result by 10 gets rid of trailing digit
        n = (n % div) / 10;

        // got rid of 2 numbers, update div accordingly
        div /= 100;
    }
    return true;
}

Отредактировано в соответствии с предложением Hardik , чтобы охватить случаи, когда в числе есть нули.

Answer 8

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

def reverse(n):
    newnum=0
    while n>0:
        newnum = newnum*10 + n % 10
        n//=10
    return newnum

def palindrome(n):
    return n == reverse(n)

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

Answer 9

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

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

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

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

def reverse(n):
    rev = 0
    while n > 0:
        rev = rev * 10 + n % 10
        n = n // 10
    return rev

upper = 10**6

def strung():
    for i in range(upper):
        int(str(i)[::-1])

def arithmetic():
    for i in range(upper):
        reverse(i)

import timeit
print "strung", timeit.timeit("strung()", setup="from __main__ import strung", number=1)
print "arithmetic", timeit.timeit("arithmetic()", setup="from __main__ import arithmetic", number=1)

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

нанизан 1.50960231881 арифметика 1.69729960569

Answer 10

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

a = num;
b = 0;
if (a % 10 == 0)
  return a == 0;
do {
  b = 10 * b + a % 10;
  if (a == b)
    return true;
  a = a / 10;
} while (a > b);
return a == b;