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

Ответ 2 · рейтинг 270 · Jorge Ferreira

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

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;

Ответ 3 · рейтинг 24 · Mark Ransom

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!")

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

Ответ 4 · рейтинг 22 · Jiaji Li

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

См. https://web.archive.org/web/20180222083908/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;
}

Ответ 5 · рейтинг 9 · Grant Limberg

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

Ответ 6 · рейтинг 8 · Debosmit Ray

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

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

Теперь концепция палиндромного числа заключается в том, что число должно читаться одинаково вперед и назад. Здорово. Используя эту информацию, мы можем сравнить первую цифру и последнюю цифру. Хитрость в том, что для первой цифры нам нужен порядок числа. Скажем, 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;
}

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

Ответ 7 · рейтинг 8 · Flowers

Самый быстрый способ, который я знаю:

bool is_pal(int n) {
    if (n % 10 == 0) return 0;
    int r = 0;
    while (r < n) {
        r = 10 * r + n % 10;
        n /= 10;
    }
    return n == r || n == r / 10;
}

Ответ 8 · рейтинг 6 · ytpillai

В 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).

Ответ 9 · рейтинг 5 · Toon Krijthe

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

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;

Ответ 10 · рейтинг 5 · Colonel Panic

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

Зачем отказываться от этого решения? Это просто реализовать и легко читать. Если бы вас спросили, не имея под рукой компьютера, является ли 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

Ответ 11 · рейтинг 4 · Chris Vest

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

Вот для вашего развлечения:

(defn palindrome? [n]
  (let [len (count n)]
    (and
      (= (first n) (last n))
      (or (>= 1 (count n))
        (palindrome? (. n (substring 1 (dec len))))))))

(defn begoners-palindrome []
  (loop [mx 0
         mxI 0
         mxJ 0
         i 999
         j 990]
    (if (> i 100)
      (let [product (* i j)]
        (if (and (> product mx) (palindrome? (str product)))
          (recur product i j
            (if (> j 100) i (dec i))
            (if (> j 100) (- j 11) 990))
          (recur mx mxI mxJ
            (if (> j 100) i (dec i))
            (if (> j 100) (- j 11) 990))))
      mx)))

(time (prn (begoners-palindrome)))

Были и ответы на Common Lisp, но мне они были непонятны.

Ответ 12 · рейтинг 4 · z5h

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

(define make-palindrome-tester
   (lambda (base)
     (lambda (n)
       (cond
         ((= 0 (modulo n base)) #f)
         (else
          (letrec
              ((Q (lambda (h t)
                    (cond
                      ((< h t) #f)
                      ((= h t) #t)
                      (else
                       (let*
                           ((h2 (quotient h base))
                            (m  (- h (* h2 base))))
                         (cond
                           ((= h2 t) #t)
                           (else
                            (Q h2 (+ (* base t) m))))))))))
            (Q n 0)))))))