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

Question

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

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

Answer 1

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

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;
}

Answer 2

Вот версия Scheme, которая создает функцию, которая будет работать с любой базой. Он имеет проверку избыточности: быстро возвращает 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)))))))

Answer 3

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

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

(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, но они были для меня невыносимы.

Answer 4

Golang версия:

package main

import "fmt"

func main() {
    n := 123454321
    r := reverse(n)
    fmt.Println(r == n)
}

func reverse(n int) int {
    r := 0
    for {
        if n > 0 {
            r = r*10 + n%10
            n = n / 10
        } else {
            break
        }
    }
    return r
}

Answer 5

Рекурсивное решение в ruby, без преобразования числа в строку.

def palindrome?(x, a=x, b=0)
  return x==b if a<1
  palindrome?(x, a/10, b*10 + a%10)
end

palindrome?(55655)

Answer 6

Скопируйте первую и последнюю цифры и сравнивайте их, пока не закончится. Может быть оставленная цифра или нет, но в любом случае, если все совпавшие цифры совпадают, это палиндром.

Answer 7

Вот еще одно решение в c ++ с использованием шаблонов. Это решение будет работать для сравнения строк палиндрома без учета регистра.

template <typename bidirection_iter>
bool palindrome(bidirection_iter first, bidirection_iter last)
{
    while(first != last && first != --last)
    {
        if(::toupper(*first) != ::toupper(*last))
            return false;
        else
            first++;
    }
    return true;
}

Answer 8

def palindrome(n):
    d = []
    while (n > 0):
        d.append(n % 10)
        n //= 10
    for i in range(len(d)/2):
        if (d[i] != d[-(i+1)]):
            return "Fail."
    return "Pass."

Answer 9

Число является палиндромным, если его строковое представление является палиндромным:

def is_palindrome(s):
    return all(s[i] == s[-(i + 1)] for i in range(len(s)//2))

def number_palindrome(n):
    return is_palindrome(str(n))

Answer 10

Я всегда использую это решение Python из-за его компактности.

def isPalindrome(number):
    return int(str(number)[::-1])==number