Comment puis-je vérifier si un nombre est un palindrome?

Pour un nombre donné:

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

Si n == rev, puis num est un palindrome:

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

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

Fonctionne uniquement pour les entiers. Il n'est pas clair de l'énoncé du problème si des nombres à virgule flottante ou des zéros en tête doivent être pris en compte.

Au-dessus de la plupart des réponses ayant un problème trivial est que la variable int peut éventuellement déborder.

Se référer à http://leetcode.com/2012/01/palindrome-number.html

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

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

Poussez chaque chiffre individuel sur une pile, puis sautez-les. Si c'est le même avant et arrière, c'est un palindrome.

Je n'ai remarqué aucune réponse qui résolvait ce problème sans espace supplémentaire, c'est-à-dire que toutes les solutions que j'ai vues utilisaient une chaîne ou un autre entier pour inverser le nombre, ou d'autres structures de données.

Bien que des langages comme Java s'enroulent sur le débordement entier, ce comportement n'est pas défini dans des langages comme C. [ essayez d'Inverser 2147483647 (entier.MAX_VALUE) en Java ] La solution de contournement pourrait être d'utiliser un long ou quelque chose mais, stylistiquement, Je n'aime pas tout à fait ça approche.

Maintenant, le concept d'un nombre palindromique est que le nombre devrait se lire de la même manière en avant et en arrière. Grand. En utilisant ces informations, nous pouvons comparer le premier chiffre et le dernier chiffre. Astuce consiste, pour le premier chiffre, nous avons besoin de l'ordre du nombre. Dis, 12321. Diviser cela par 10000 nous obtiendrait le premier 1. La fuite 1 peut être récupérée en prenant le mod avec 10. Maintenant, pour réduire cela à 232. (12321 % 10000)/10 = (2321)/10 = 232. Et maintenant, le 10000 devrait être réduit d'un facteur 2. Donc, maintenant sur le code 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;
}

Édité selon la suggestion de Hardik pour couvrir les cas où il y a des zéros dans le nombre.

Sauf en faisant du nombre une chaîne, puis en inversant la chaîne.

Pourquoi rejeter cette solution? Il est facile à mettre en œuvre et lisible . Si on vous demandait sans ordinateur à portée de main si 2**10-23 est un palindrome décimal, vous le testeriez sûrement en l'écrivant en décimal.

En Python au moins, le slogan 'les opérations de chaîne sont plus lentes que l'arithmétique' est en fait faux. J'ai comparé l'algorithme arithmétique de Smink à l'inversion de chaîne simple int(str(i)[::-1]). Il n'y a aucune différence significative de vitesse-il est arrivé que l'inversion de chaîne soit légèrement plus rapide.

Dans les langages de bas niveau (C/C++), le slogan peut contenir, mais on risque des erreurs de débordement avec de grands nombres.

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)

Résultats en secondes (plus bas est meilleur):

Enfilées 1.50960231881
arithmétique 1.69729960569

En Python, il y a une manière rapide et itérative.

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

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

Cela empêche également les problèmes de mémoire avec la récursivité (comme l'erreur StackOverflow en Java)

J'ai répondu au problème D'Euler en utilisant une manière très brutale. Naturellement, il y avait un algorithme beaucoup plus intelligent à l'affichage quand je suis arrivé au nouveau fil de forum associé déverrouillé. A savoir, un membre qui est passé par la poignée Begoner avait une telle approche nouvelle, que j'ai décidé de réimplémenter ma solution en utilisant son algorithme. Sa version était en Python (en utilisant des boucles imbriquées) et je l'ai réimplémenté dans Clojure (en utilisant une seule boucle/récurrence).

Ici, pour votre amusement:

(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)))

Il y avait des Lisp répond aussi bien, mais ils étaient ungrokable pour moi.

Juste pour le plaisir, celui-ci fonctionne également.

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

Voici une version Scheme qui construit une fonction qui fonctionnera sur n'importe quelle base. Il a un contrôle de redondance: retourner false rapidement si le nombre est un multiple de la base (se termine par 0). Et il ne reconstruit pas tout le nombre inversé, seulement la moitié. C'est tout ce dont nous avons besoin.

(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)))))))

Le moyen le plus rapide que je connaisse:

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

Golang version:

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
}

Solution récursive dans ruby, sans convertir le nombre en chaîne

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

palindrome?(55655)

Sautez les premier et dernier chiffres et comparez-les jusqu'à épuisement. Il peut y avoir un chiffre à gauche, ou non, mais de toute façon, si tous les chiffres sautés correspondent, c'est un palindrome.

Voici une solution de plus en c++ en utilisant des modèles . Cette solution fonctionnera pour la comparaison de chaînes palindrome insensible à la casse .

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

Une méthode avec un facteur constant un peu meilleur que la méthode @sminks:

num=n
lastDigit=0;
rev=0;
while (num>rev) {
    lastDigit=num%10;
    rev=rev*10+lastDigit;
    num /=2;
}
if (num==rev) print PALINDROME; exit(0);
num=num*10+lastDigit; // This line is required as a number with odd number of bits will necessary end up being smaller even if it is a palindrome
if (num==rev) print PALINDROME

Voici une version f#:

let reverseNumber n =
    let rec loop acc = function
    |0 -> acc
    |x -> loop (acc * 10 + x % 10) (x/10)    
    loop 0 n

let isPalindrome = function
    | x  when x = reverseNumber x -> true
    | _ -> false

Un nombre est palindromique si sa représentation de chaîne est palindromique:

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

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."

Pour vérifier le nombre donné est Palindrome ou non (code Java)

class CheckPalindrome{
public static void main(String str[]){
        int a=242, n=a, b=a, rev=0;
        while(n>0){
                    a=n%10;  n=n/10;rev=rev*10+a;
                    System.out.println(a+"  "+n+"  "+rev);  // to see the logic
               }
        if(rev==b)  System.out.println("Palindrome");
        else        System.out.println("Not Palindrome");
    }
}

Beaucoup de solutions affichées ici inversent l'entier et le stockent dans une variable qui utilise un espace supplémentaire qui est O(n), Mais voici une solution avec O(1) Espace.

def isPalindrome(num):
    if num < 0:
        return False
    if num == 0:
        return True
    from math import log10
    length = int(log10(num))
    while length > 0:
        right = num % 10
        left = num / 10**length
        if right != left:
            return False
        num %= 10**length
        num /= 10
        length -= 2
    return True

J'utilise toujours Cette solution python en raison de sa compacité.

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

Essayez ceci:

reverse = 0;
    remainder = 0;
    count = 0;
    while (number > reverse)
    {
        remainder = number % 10;
        reverse = reverse * 10 + remainder;
        number = number / 10;
        count++;
    }
    Console.WriteLine(count);
    if (reverse == number)
    {
        Console.WriteLine("Your number is a palindrome");
    }
    else
    {
        number = number * 10 + remainder;
        if (reverse == number)
            Console.WriteLine("your number is a palindrome");
        else
            Console.WriteLine("your number is not a palindrome");
    }
    Console.ReadLine();
}
}

Voici une solution utilisant des listes comme piles en python:

def isPalindromicNum(n):
    """
        is 'n' a palindromic number?
    """
    ns = list(str(n))
    for n in ns:
        if n != ns.pop():
            return False
    return True

Popping la pile ne considère que le côté le plus à droite du nombre pour la comparaison et il échoue rapidement pour réduire les contrôles

 public class Numbers
 {
   public static void main(int givenNum)
   { 
       int n= givenNum
       int rev=0;

       while(n>0)
       {
          //To extract the last digit
          int digit=n%10;

          //To store it in reverse
          rev=(rev*10)+digit;

          //To throw the last digit
          n=n/10;
      }

      //To check if a number is palindrome or not
      if(rev==givenNum)
      { 
         System.out.println(givenNum+"is a palindrome ");
      }
      else
      {
         System.out.pritnln(givenNum+"is not a palindrome");
      }
  }
}

let isPalindrome (n:int) =
   let l1 = n.ToString() |> List.ofSeq |> List.rev
   let rec isPalindromeInt l1 l2 =
       match (l1,l2) with
       | (h1::rest1,h2::rest2) -> if (h1 = h2) then isPalindromeInt rest1 rest2 else false
       | _ -> true
   isPalindromeInt l1 (n.ToString() |> List.ofSeq)

checkPalindrome(int number)
{
    int lsd, msd,len;
    len = log10(number);
    while(number)
    {
        msd = (number/pow(10,len)); // "most significant digit"
        lsd = number%10; // "least significant digit"
        if(lsd==msd)
        {
            number/=10; // change of LSD
            number-=msd*pow(10,--len); // change of MSD, due to change of MSD
            len-=1; // due to change in LSD
            } else {return 1;}
    }
    return 0;
}

Manière récursive, pas très efficace, il suffit de fournir une option

(code Python)

def isPalindrome(num):
    size = len(str(num))
    demoninator = 10**(size-1)
    return isPalindromeHelper(num, size, demoninator)

def isPalindromeHelper(num, size, demoninator):
    """wrapper function, used in recursive"""
    if size <=1:
        return True
    else:       
        if num/demoninator != num%10:
            return False
        # shrink the size, num and denominator
        num %= demoninator
        num /= 10
        size -= 2
        demoninator /=100
        return isPalindromeHelper(num, size, demoninator)