Wie überprüfe ich, ob eine Zahl ein Palindrom ist?

Wie überprüfe ich, ob eine Zahl ein Palindrom ist?

Jede Sprache. Beliebiger Algorithmus. (außer dem Algorithmus, die Zahl zu einer Zeichenfolge zu machen und dann die Zeichenfolge umzukehren).

Dies ist eines der Probleme von Project Euler . Als ich es in Haskell gelöst habe, habe ich genau das getan, was Sie vorgeschlagen haben, die Zahl in einen String umzuwandeln. Es ist dann trivial zu überprüfen, ob die Saite ein Pallindrom ist. Wenn es gut genug funktioniert, warum sollte man es dann komplexer machen? Ein Pallindrom zu sein ist eher eine lexikalische als eine mathematische Eigenschaft.

Für eine bestimmte Anzahl:

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

Wenn n == revdann numein Palindrom ist:

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

Funktioniert nur für Ganzzahlen. Aus der Problemstellung geht nicht hervor, ob Gleitkommazahlen oder führende Nullen berücksichtigt werden müssen.

Über den meisten Antworten mit einem trivialen Problem steht, dass die Variable int möglicherweise überläuft.

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

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

Schieben Sie jede einzelne Ziffer auf einen Stapel und entfernen Sie sie. Wenn es vorwärts und rückwärts gleich ist, ist es ein Palindrom.

Ich habe keine Antworten bemerkt, die dieses Problem ohne zusätzlichen Speicherplatz gelöst haben, dh alle Lösungen, die ich gesehen habe, haben entweder eine Zeichenfolge oder eine andere Ganzzahl verwendet, um die Zahl umzukehren, oder einige andere Datenstrukturen.

Obwohl Sprachen wie Java auf Integer - Überlauf umwickeln, ist dieses Verhalten in Sprachen wie C (undefined Versuchen Umkehren 2147483647 (Integer.MAX_VALUE) in Java )
könnte Abhilfe sein , eine lange oder etwas zu verwenden , aber stilistisch, weiß ich nicht ganz wie dieser Ansatz.

Das Konzept einer palindromischen Zahl ist nun, dass die Zahl vorwärts und rückwärts gleich lauten sollte. Toll. Mit diesen Informationen können wir die erste und die letzte Ziffer vergleichen. Trick ist, für die erste Ziffer brauchen wir die Reihenfolge der Nummer. Sagen wir, 12321. Wenn wir dies durch 10000 teilen, erhalten wir die führende 1. Die nachfolgende 1 kann abgerufen werden, indem der Mod mit 10 genommen wird. Nun, um dies auf 232 zu reduzieren (12321 % 10000)/10 = (2321)/10 = 232. Und jetzt müsste der 10000 um den Faktor 2 reduziert werden. Nun zum Java-Code ...

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

Bearbeitet gemäß Hardiks Vorschlag, um die Fälle abzudecken, in denen die Zahl Nullen enthält.

In Python gibt es einen schnellen, iterativen Weg.

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

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

Dies verhindert auch Speicherprobleme bei der Rekursion (wie StackOverflow-Fehler in Java)

Der schnellste Weg, den ich kenne:

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

Nur zum Spaß funktioniert dieser auch.

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;

außer die Zahl zu einer Zeichenfolge zu machen und dann die Zeichenfolge umzukehren.

Warum diese Lösung ablehnen? Es ist einfach zu implementieren und lesbar . Wenn Sie ohne Computer gefragt würden, ob 2**10-23es sich um ein Dezimalpalindrom handelt, würden Sie es sicherlich testen, indem Sie es in Dezimalzahl schreiben.

Zumindest in Python ist der Slogan "String-Operationen sind langsamer als Arithmetik" tatsächlich falsch. Ich habe den arithmetischen Algorithmus von Smink mit der einfachen Umkehrung von Strings verglichen int(str(i)[::-1]). Es gab keinen signifikanten Geschwindigkeitsunterschied - es kam vor, dass die Saitenumkehr geringfügig schneller war.

In kompilierten Sprachen (C / C ++) mag der Slogan gelten, aber man riskiert Überlauffehler mit großen Zahlen.

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)

Ergebnisse in Sekunden (niedriger ist besser):

aufgereihte 1.50960231881 Arithmetik 1.69729960569

Ich beantwortete das Euler-Problem mit einer sehr brutalen Art und Weise. Natürlich gab es einen viel intelligenteren Algorithmus, als ich zu dem neuen freigeschalteten zugehörigen Forenthread kam. Ein Mitglied, das sich an Begoner orientierte, hatte einen so neuartigen Ansatz, dass ich mich entschied, meine Lösung mithilfe seines Algorithmus neu zu implementieren. Seine Version war in Python (mit verschachtelten Schleifen) und ich habe sie in Clojure (mit einer einzelnen Schleife / Wiederholung) neu implementiert.

Hier zu Ihrer Unterhaltung:

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

Es gab auch Common Lisp-Antworten, aber sie waren für mich nicht zu widerlegen.

Hier ist eine Schema-Version, die eine Funktion erstellt, die für jede Basis funktioniert. Es gibt eine Redundanzprüfung: Geben Sie schnell false zurück, wenn die Zahl ein Vielfaches der Basis ist (endet mit 0).
Und es wird nicht die gesamte umgekehrte Zahl neu erstellt, sondern nur die Hälfte.
Das ist alles was wir brauchen.

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

Rekursive Lösung in Ruby, ohne die Zahl in einen String umzuwandeln.

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

palindrome?(55655)

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
}

Entfernen Sie die erste und die letzte Ziffer und vergleichen Sie sie, bis Sie keine mehr haben. Es kann eine Ziffer übrig sein oder nicht, aber so oder so, wenn alle abgesprungenen Ziffern übereinstimmen, ist es ein Palindrom.

Hier ist eine weitere Lösung in C ++ unter Verwendung von Vorlagen. Diese Lösung funktioniert für den Vergleich von Palindrom-Strings ohne Berücksichtigung der Groß- und Kleinschreibung.

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

Eine Methode mit einem etwas besseren konstanten Faktor als die @ sminks-Methode:

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

Hier ist eine # Version:

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

Eine Zahl ist palindromisch, wenn ihre Zeichenfolgendarstellung palindromisch ist:

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

Die angegebene Nummer zu überprüfen ist Palindrome oder nicht (Java Code)

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

Viele der hier veröffentlichten Lösungen kehren die Ganzzahl um und speichern sie in einer Variablen, die zusätzlichen Speicherplatz verwendet. O(n)Hier ist jedoch eine Lösung mit O(1)Speicherplatz.

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

Ich benutze diese Python-Lösung immer wegen ihrer Kompaktheit.

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

Versuche dies:

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

Hier ist eine Lösung, die Listen als Stapel in Python verwendet:

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

Beim Poppen des Stapels wird nur die am weitesten rechts stehende Seite der Zahl zum Vergleich berücksichtigt, und es wird nicht schnell fehlgeschlagen, die Überprüfungen zu reduzieren

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

Rekursiver Weg, nicht sehr effizient, bieten nur eine Option

(Python-Code)

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)