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

Question

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

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

Answer 1

Предполагая, что ведущие нули игнорируются. Ниже приведена реализация:

#include<bits/stdc++.h>
using namespace std;
vector<int>digits;
stack<int>digitsRev;
int d,number;
bool isPal=1;//initially assuming the number is palindrome
int main()
{
    cin>>number;
    if(number<10)//if it is a single digit number than it is palindrome
    {
        cout<<"PALINDROME"<<endl;
        return 0;
    }
    //if the number is greater than or equal to 10
    while(1)
    {
        d=number%10;//taking each digit
        number=number/10;
        //vector and stack will pick the digits
        //in reverse order to each other
        digits.push_back(d);
        digitsRev.push(d);
        if(number==0)break;
    }
    int index=0;
    while(!digitsRev.empty())
    {
        //Checking each element of the vector and the stack
        //to see if there is any inequality.
        //And which is equivalent to check each digit of the main
        //number from both sides
        if(digitsRev.top()!=digits[index++])
        {
            cout<<"NOT PALINDROME"<<endl;
            isPal=0;
            break;
        }
        digitsRev.pop();
    }
    //If the digits are equal from both sides than the number is palindrome
    if(isPal==1)cout<<"PALINDROME"<<endl;
}

Answer 2

Черт возьми, я злюсь! http://www.palindromelist.net/palindromes-d/
Пример одного шага: является ли 332 палиндромным числом?

n = 332
q = n / 10 = 33
r = n - 10 * q = 2
r > 0
r != q
n = q = 33
n > r
q = n / 10 = 3
r -= q = 4294967295
r *= 10 = 4294967286
r += n = 23
r != n
r != q
n = q = 3
n > r ? No, so 332 isn't a palindromic number.

Переполнение тоже не проблема. Было необходимо два деления, в коде (C #) они сделаны с умножением. N-значный номер: ~ n / 2 деления!

const ulong c0 = 0xcccccccdUL;
static bool isPal(uint n)
{
    if (n < 10) return true;
    uint q = (uint)(c0 * n >> 35);
    uint r = n - 10 * q;
    if (r == 0) return false;
    if (r == q) return true;
    n = q;
    while (n > r)
    {
        q = (uint)(c0 * n >> 35);
        r -= q;
        r *= 10;
        r += n;
        if (r == n || r == q) return true;
        n = q;
    }
    return false;
}

Существует 142948 палиндромных чисел <2 ^ 32, их сумма 137275874705916. </p>

using System;
class Program
{
    static void Main()  // take a break
    {
        uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
        n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal0(n--)) c++;
        Console.WriteLine(sw.Elapsed + " " + c);                  // 76 s
        n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal1(n--)) c++;
        Console.WriteLine(sw.Elapsed + " " + c);                  // 42 s
        n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal2(n--)) c++;
        Console.WriteLine(sw.Elapsed + " " + c);                  // 31 s
        Console.Read();
    }

    static bool isPal0(uint u)
    {
        uint n = u, rev = 0;
        while (n > 0) { uint dig = n % 10; rev = rev * 10 + dig; n /= 10; }
        return u == rev;
    }

    static bool isPal1(uint u)
    {
        uint n = u, r = 0;
        while (n >= 10) r = n + (r - (n /= 10)) * 10;
        return u == 10 * r + n;
    }

    static bool isPal2(uint n)
    {
        if (n < 10) return true;
        uint q = n / 10, r = n - 10 * q;
        if (r == 0 || r == q) return r > 0;
        while ((n = q) > r)
        {
            q /= 10; r -= q; r *= 10; r += n;
            if (r == n || r == q) return true;
        }
        return false;
    }
}

Кажется, этот быстрее.

using System;
class Program
{
    static void Main()
    {
        uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
        n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal(n--)) c++;
        Console.WriteLine(sw.Elapsed + " " + c);                 // 21 s
        Console.Read();
    }

    static bool isPal(uint n)
    {
        return n < 100 ? n < 10 || n % 11 == 0 :
              n < 1000 ? /*          */ n / 100 == n % 10 :
             n < 10000 ? n % 11 == 0 && n / 1000 == n % 10 && isP(n) :
            n < 100000 ? /*          */ n / 10000 == n % 10 && isP(n) :
           n < 1000000 ? n % 11 == 0 && n / 100000 == n % 10 && isP(n) :
          n < 10000000 ? /*          */ n / 1000000 == n % 10 && isP(n) :
         n < 100000000 ? n % 11 == 0 && n / 10000000 == n % 10 && isP(n) :
        n < 1000000000 ? /*          */ n / 100000000 == n % 10 && isP(n) :
                         n % 11 == 0 && n / 1000000000 == n % 10 && isP(n);
    }

    static bool isP(uint n)
    {
        uint q = n / 10, r = n - 10 * q;
        do { n = q; q /= 10; r -= q; r *= 10; r += n; } while (r < q);
        return r == q || r == n;
    }
}

С почти сбалансированным бинарным деревом поиска спагетти.

using System;
class Program
{
    static void Main()
    {
        uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
        n = c = 0; sw.Restart(); while (n < ~0u) if (isPal(n++)) c++;
        Console.WriteLine(sw.Elapsed + " " + c);              // 17 s
        Console.Read();
    }

    static bool isPal(uint n)
    {
        return n < 1000000 ? n < 10000 ? n < 1000 ? n < 100 ?
        n < 10 || n % 11 == 0 : n / 100 == n % 10 :
        n / 1000 == n % 10 && isP(n) : n < 100000 ?
        n / 10000 == n % 10 && isP(n) :
        n / 100000 == n % 10 && isP(n) :
        n < 100000000 ? n < 10000000 ?
        n / 1000000 == n % 10 && isP(n) :
        n % 11 == 0 && n / 10000000 == n % 10 && isP(n) :
        n < 1000000000 ? n / 100000000 == n % 10 && isP(n) :
        n % 11 == 0 && n / 1000000000 == n % 10 && isP(n);
    }

    static bool isP(uint n)
    {
        uint q = n / 10, r = n - 10 * q;
        do { n = q; q /= 10; r -= q; r *= 10; r += n; } while (r < q);
        return r == q || r == n;
    }
}

Неуравновешенный с ног на голову.

using System;
class Program
{
    static void Main()
    {
        uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
        n = c = 0; sw.Restart(); while (n < ~0u) if (isPal(n++)) c++;
        Console.WriteLine(sw.Elapsed + " " + c);              // 16 s
        Console.Read();
    }

    static bool isPal(uint n)
    {
        return
        n > 999999999 ? n % 11 == 0 && n / 1000000000 == n % 10 && isP(n) :
        n > 99999999 ? n / 100000000 == n % 10 && isP(n) :
        n > 9999999 ? n % 11 == 0 && n / 10000000 == n % 10 && isP(n) :
        n > 999999 ? n / 1000000 == n % 10 && isP(n) :
        n > 99999 ? n % 11 == 0 && n / 100000 == n % 10 && isP(n) :
        n > 9999 ? n / 10000 == n % 10 && isP(n) :
        n > 999 ? n % 11 == 0 && n / 1000 == n % 10 && isP(n) :
        n > 99 ? n / 100 == n % 10 :
        n < 10 || n % 11 == 0;
    }

    static bool isP(uint n)
    {
        uint q = n / 10, r = n - 10 * q;
        do { n = q; q /= 10; r -= q; r *= 10; r += n; } while (r < q);
        return r == q || r == n;
    }
}

Answer 3

Просто получите число цифр числа с помощью математических функций, а затем выполните итерацию, используя операции «/» и «%», как указано ниже. После x = (x% divider) / 10 мы должны разделить делитель на 100, так как мы сделали 2 операции с нулем.

public static boolean isPalindrome(int x) {
            if (x < 0) return false;
            if (x < 10) return true;

            int numDigits = (int)(Math.log10(x)+1);
            int divider = (int) (Math.pow(10, numDigits - 1));
            for (int i = 0; i < numDigits / 2; i++) {
                if (x / divider != x % 10)
                    return false;
                x = (x % divider) / 10;
                divider /= 100;
            }
            return true;
        }

Answer 4

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)

Answer 5

Это мой код Java. Сравнение первого и последнего значения строки и следующей пары внутренних значений и т. Д.

    /*Palindrome number*/
    String sNumber = "12321";
    int l = sNumber.length(); // getting the length of sNumber. In this case its 5
    boolean flag = true;
    for (int i = 0; i <= l; ++i) {
        if (sNumber.charAt(i) != sNumber.charAt((l--) -1)) { //comparing the first and the last values of the string
            System.out.println(sNumber +" is not a palindrome number");
            flag = false;
            break;
        }
        //l--; // to reducing the length value by 1 
    }
    if (flag) {
        System.out.println(sNumber +" is a palindrome number");
    }

Answer 6

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

Answer 7

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

Шаги:

1. Получить длину номера
2. Цикл от длины + 1 (первый) -> 0
3. Получить i-ую цифру и получить последнюю цифру
4. если обе цифры не равны, вернуть false, поскольку число не является палиндромом
5. я -
6. сбросить последнюю цифру из числа (число = число / 10)

7. end of loo return true

   func isPalindrom(_ input: Int) -> Bool {
          if input < 0 {
               return false
           }
   
           if input < 10 {
               return true
           }
   
           var num = input
           let length = Int(log10(Float(input))) + 1
           var i = length
   
           while i > 0 && num > 0 {
   
               let ithDigit = (input / Int(pow(10.0, Double(i) - 1.0)) ) % 10
               let r = Int(num % 10)
   
               if ithDigit != r {
                   return false
               }
   
               num = num / 10
               i -= 1
           }
   
           return true
       }
   

Answer 8

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

Answer 9

Это решение довольно эффективно, так как я использую StringBuilder, что означает, что класс StringBuilder реализован как изменяемая последовательность символов. Это означает, что вы добавляете новые строки или символы в StringBuilder.

 public static boolean isPal(String ss){
   StringBuilder stringBuilder = new StringBuilder(ss);
   stringBuilder.reverse();
   return ss.equals(stringBuilder.toString());
 }

Answer 10

Вот способ.

class Palindrome_Number{
    void display(int a){
        int count=0;
        int n=a;
        int n1=a;
        while(a>0){
            count++;
            a=a/10;
        }
        double b=0.0d;
        while(n>0){
            b+=(n%10)*(Math.pow(10,count-1));
            count--;
            n=n/10;
        }
        if(b==(double)n1){
            System.out.println("Palindrome number");
        }
        else{
            System.out.println("Not a palindrome number");            
        }
    }
}