Jak sprawdzić, czy liczba jest palindromem?

Jak sprawdzić, czy liczba jest palindromem?

Dowolny język. Dowolny algorytm. (z wyjątkiem algorytmu przekształcania liczby w łańcuch, a następnie odwracania ciągu).

To jeden z problemów Projektu Euler . Kiedy rozwiązałem to w Haskell, zrobiłem dokładnie to, co sugerujesz, przekonwertuj liczbę na String. Sprawdzenie, czy łańcuch jest pallindromem, jest wtedy trywialne. Jeśli działa wystarczająco dobrze, to po co komplikować go? Bycie pallindromem jest raczej właściwością leksykalną niż matematyczną.

Dla dowolnej liczby:

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

Jeśli n == revwięc numjest palindromem:

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

Działa tylko dla liczb całkowitych. Ze stwierdzenia problemu nie jest jasne, czy należy brać pod uwagę liczby zmiennoprzecinkowe lub zera wiodące.

Powyżej większości odpowiedzi, które mają trywialny problem, jest to, że zmienna int może się przepełnić.

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

Umieść każdą pojedynczą cyfrę na stosie, a następnie zdejmij je. Jeśli tak samo do przodu i do tyłu, jest to palindrom.

Nie zauważyłem żadnych odpowiedzi, które rozwiązałyby ten problem bez dodatkowej spacji, tj. Wszystkie rozwiązania, które widziałem, używały ciągu znaków lub innej liczby całkowitej do odwrócenia liczby lub innych struktur danych.

Chociaż języki takie jak Java zawijają się przy przepełnieniu liczb całkowitych, to zachowanie jest niezdefiniowane w językach takich jak C. ( Spróbuj odwrócić 2147483647 (Integer.MAX_VALUE) w Javie ).
Obejściem może być użycie długiego lub czegoś podobnego, ale stylistycznie nie całkiem jak to podejście.

Otóż, koncepcja liczby palindromicznej polega na tym, że liczba powinna czytać to samo do przodu i do tyłu. Wspaniały. Korzystając z tych informacji, możemy porównać pierwszą cyfrę i ostatnią cyfrę. Sztuczka polega na tym, że dla pierwszej cyfry potrzebujemy kolejności numerów. Powiedzmy, 12321. Dzieląc to przez 10000 dostaniemy wiodącą 1. Końcową 1 można pobrać, biorąc mod z 10. Teraz, aby zredukować to do 232 (12321 % 10000)/10 = (2321)/10 = 232.. A teraz 10000 musiałoby zostać zmniejszone o współczynnik 2. A teraz przejdźmy do kodu Javy ...

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

Edytowane zgodnie z sugestią Hardika , aby objąć przypadki, w których w liczbie są zera.

W Pythonie istnieje szybki, iteracyjny sposób.

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

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

Zapobiega to również problemom z pamięcią z rekurencją (jak błąd StackOverflow w Javie)

Najszybszy sposób jaki znam:

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

Dla zabawy ten też działa.

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;

z wyjątkiem uczynienia liczby ciągiem, a następnie odwrócenia łańcucha.

Dlaczego odrzucać to rozwiązanie? Jest łatwy do wdrożenia i czytelny . Gdybyś został zapytany bez komputera, czy 2**10-23jest to palindrom dziesiętny, z pewnością przetestowałbyś go, zapisując go w systemie dziesiętnym.

Przynajmniej w Pythonie hasło „operacje na łańcuchach są wolniejsze niż arytmetyka” jest w rzeczywistości fałszywe. Porównałem algorytm arytmetyczny Sminka do prostego odwrócenia łańcuchów int(str(i)[::-1]). Nie było znaczącej różnicy w prędkości - zdarzyło się, że odwrócenie struny było nieznacznie szybsze.

W językach kompilowanych (C / C ++) slogan może się utrzymywać, ale przy dużych liczbach istnieje ryzyko przepełnienia.

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)

Wyniki w kilka sekund (im mniej, tym lepiej):

strung 1.50960231881 arytmetyka 1.69729960569

Odpowiedziałem na problem Eulera, używając bardzo brutalnej siły. Oczywiście, gdy dotarłem do nowego odblokowanego wątku powiązanego z forum, pojawił się znacznie inteligentniejszy algorytm. Mianowicie członek, który szedł przez uchwyt Begoner, miał na tyle nowatorskie podejście, że postanowiłem ponownie zaimplementować swoje rozwiązanie za pomocą jego algorytmu. Jego wersja była w Pythonie (używając zagnieżdżonych pętli) i ponownie zaimplementowałem ją w Clojure (używając pojedynczej pętli / recur).

Tutaj dla twojej rozrywki:

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

Były też odpowiedzi Common Lispa, ale były dla mnie niewdzięczne.

Oto wersja Scheme, która konstruuje funkcję, która będzie działać na dowolnej bazie. Ma kontrolę nadmiarowości: szybko zwraca fałsz, jeśli liczba jest wielokrotnością podstawy (kończy się na 0).
I nie odbudowuje całej odwróconej liczby, tylko połowę.
To wszystko, czego potrzebujemy.

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

Rekurencyjne rozwiązanie w Ruby, bez konwersji liczby na łańcuch.

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

palindrome?(55655)

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

Zdejmij pierwszą i ostatnią cyfrę i porównaj je, aż skończą się. Może zostać cyfra lub nie, ale tak czy inaczej, jeśli wszystkie wyskakujące cyfry pasują, jest to palindrom.

Oto jeszcze jedno rozwiązanie w języku C ++ przy użyciu szablonów. To rozwiązanie będzie działać przy porównywaniu ciągów palindromowych bez rozróżniania wielkości liter.

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

metoda z nieco lepszym współczynnikiem stałym niż metoda @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

oto wersja af #:

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

Liczba jest palindromiczna, jeśli jej reprezentacja łańcuchowa jest palindromiczna:

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

Aby sprawdzić podany numer to Palindrome lub nie (kod 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");
    }
}

Wiele z zamieszczonych tutaj rozwiązań odwraca liczbę całkowitą i przechowuje ją w zmiennej, która wykorzystuje dodatkową przestrzeń, którą jest O(n), ale tutaj jest rozwiązanie ze O(1)spacją.

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

Zawsze używam tego rozwiązania w Pythonie ze względu na jego zwartość.

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

Spróbuj tego:

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

Oto rozwiązanie wykorzystujące listy jako stosy w Pythonie:

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

zdejmowanie stosu bierze pod uwagę tylko prawą stronę liczby dla porównania i szybko nie udaje się zmniejszyć liczby sprawdzeń

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

Rekurencyjny sposób, niezbyt wydajny, po prostu zapewnia opcję

(Kod Pythona)

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)