Как узнать все палиндромные числа

Question

A палиндромное число или цифра палиндром - это "симметричное" число, подобное 16461, которое остается тем же, когда его цифры обращены.

Термин палиндромный происходит от палиндрома, который относитсяк слову, подобному ротору, которое остается неизменным при обращении его букв.

Первые палиндромные числа (в десятичном виде):

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22,
33, 44, 55, 66, 77, 88, 99, 101, 111,
121, 131, 141, 151, 161, 171, 181,
191, ...

Как найти все палиндромные числа ниже, скажем,10000

Answer 1

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

Answer 2

Генерация всех палиндромов до определенного предела.

public static Set<Integer> allPalindromic(int limit) {

    Set<Integer> result = new HashSet<Integer>();

    for (int i = 0; i <= 9 && i <= limit; i++)
        result.add(i);

    boolean cont = true;
    for (int i = 1; cont; i++) {
        StringBuffer rev = new StringBuffer("" + i).reverse();
        cont = false;
        for (String d : ",0,1,2,3,4,5,6,7,8,9".split(",")) {
            int n = Integer.parseInt("" + i + d + rev);
            if (n <= limit) {
                cont = true;
                result.add(n);
            }
        }
    }

    return result;
}

Тестирование на палиндромность

Использование строк

public static boolean isPalindromic(String s, int i, int j) {
    return j - i < 1 || s.charAt(i) == s.charAt(j) && isPalindromic(s,i+1,j-1);
}

public static boolean isPalindromic(int i) {
    String s = "" + i;
    return isPalindromic(s, 0, s.length() - 1);
}

Использование целых чисел

public static boolean isPalindromic(int i) {
    int len = (int) Math.ceil(Math.log10(i+1));
    for (int n = 0; n < len / 2; n++)
        if ((i / (int) Math.pow(10, n)) % 10 !=
            (i / (int) Math.pow(10, len - n - 1)) % 10)
            return false;
    return true;
}

Answer 3

Существует метод грубой силы: вы просматриваете все числа и проверяете, палиндром они или нет. Для проверки поменяйте число и сравните. Сложность должна быть O (n log10 (n)). [Не то, что log10 () имеет значение, но ради полноты. ]

Другой способ - генерировать палиндромы в соответствии с количеством цифр. Допустим, вам нужно сгенерировать 5-значные палиндромы, они имеют форму ABCBA, поэтому просто переберите 0-9 и заполните все позиции. Теперь, если вы генерируете палиндромы ниже 10 ^ 4, то генерируйте палиндромы из 1,2,3 и 4 цифр.

Я написал быстрые (и грязные) коды C ++ для проверки скорости обоих алгоритмов (8-значный палиндром). Грубая сила: Ideone. (3,4 с) Лучший алгоритм: Идеально. (0с)

Я удалил операторы печати, потому что Ideone не разрешает вывод таких больших данных.

На моем компьютере время:

Brute force:
real    0m7.150s
user    0m7.052s
Better algorithm:
real    0m0.024s
user    0m0.012s

Я знаю, что вы упомянули язык как Java, но я не знаю Java, и эти коды просто показывают разницу между алгоритмами, и вы можете написать свой собственный код Java.

PS: я проверил свой код для 8-значных палиндромов с грубой силой, не могу быть уверен, что он дает неправильные значения для более чем 8 цифр, хотя используемый подход является общим. Кроме того, я хотел бы дать ссылки на код в комментариях, так как правильный подход уже упоминался, но у меня нет необходимых привилегий.

Answer 4

Один из подходов заключается в простой итерации всех чисел и проверке каждого числа: это палиндром или нет, что-то в этом роде:

public static boolean isPalindrome(Integer x) {
        String s = x.toString();
        int len = s.length();
        for (int i = 0;i<len;i+=2) {
            if (s.charAt(i) != s.charAt(len-i-1)) return false;
        }
        return true;
    }
public static void main(String[] args) {
        int N = 10000;
        for (Integer x = 0;x<N;x++) { 
            if (isPalindrome(x)) System.out.println(x);
        }
    } 

Answer 5

Циклы, аналогичные приведенным ниже, можно использовать для печати чисел палиндрома:

for(int i = 1; i <= 9; i++) {
        for(int j = 0; j <= 9; j++) {
            for(int k = 0; k <= 9; k++) {
                System.out.println("" + i + j + k + j + i);
            }
        }
    }

Answer 6

Подход с использованием грубой силы: создайте цикл по каждому элементу из 1… 10000 и проверьте на соответствие ограничениям.Еще проще преобразовать число в строку, обратить его и сравнить с исходным значением.Это неэффективно и неэффективно.

Лучший подход: подумайте о паттернах палиндрома.Подумайте о различных возможностях палиндромов, в зависимости от длины числа.Теперь предоставьте метод, который генерирует палиндромы заданной длины.(Я не буду этого делать, потому что это, очевидно, домашнее задание.)

Answer 7

import Queue
import copy

def printPalindromesTillK(K):
    q = Queue.Queue(K);
    for i in range(0, 10):
        q.put(str(i));
        q.put(str(i) + str(i));
    while(not q.empty()):
        elem = q.get();
        print  elem;
        for i in range(1, 10):
            item = str(i) + elem + str(i);
            if int(item) <= K:
               q.put(item); 

print printPalindromesTillK(10000);

Answer 8

Я написал эти методы на C #, которые могут помочь.Основной метод строит точный список всех палиндромных чисел до заданного числа цифр.Это быстро и прокомментировано, чтобы помочь объяснить процессы, которые я использовал.

Я также включил некоторые методы поддержки, включая быстрый палиндромный тест, и стоит отметить, что pow10 [x] - это массив степеней 10 для дальнейшего улучшения скорости.

    public static List<ulong> GetPalindromicNumbers(ulong digits = 3) 
    {
        List<ulong> result = new List<ulong>(1000);
        ulong limit = pow10[digits] - 1;

        // Add the palindromes 1 to 9
        for ( ulong b = 1; b < 10; b++ )    
            result.Add( b );    

        ulong pow = 10; // Used to limit the creation of odd and even palindromes between powers of 10
        ulong a = 1;    // Working value which is used to set the next set of digits for abc
        ulong palindrome = 9;
        while ( palindrome < limit )
        {
            // Build even digit palindromes of the form abc + cba where abc is any number and cba is the same number with its digits reversed
            while ( a < pow  )
            {
                // If 'abc' has trailing 0s they will be lost if we try to reverse it. We need to overcome this sop we check for trailing 0's 
                // and add them to abc. eg if abc starts at 100, abc becomes 10000 and cba becomes 1 which when joined correctly forms 100001
                ulong abc = a;
                ulong cba = a;
                while ( cba % 10 == 0 )
                {
                    abc *= 10;
                    cba /= 10;
                }
                palindrome = MathExt.Concat( abc , MathExt.ReverseDigits( cba ) );        
                result.Add( palindrome );       // Add palindromes of the form abc + cba
                a++;
            }

            // Build odd digit palindromes of the form lhs + b + rhs where lhs is any number and rhs is the same number with its digits reversed
            a /= 10;
            if ( palindrome == limit ) break;   // Check to see if we have the required palindromic numbers
            while ( a < pow  )
            {
                // Handle the special case of when b = 0 
                // Increase leftside by a factor of 10 for each trailing zero as these 0s will be lost when the leftside is reversed
                // This approach does away with the need to convert numbers with trailing zeros to strings before they are reversed.
                ulong lhs = a;
                ulong rhs = a;
                while ( rhs % 10 == 0 )
                {
                    lhs *= 10;
                    rhs /= 10;
                }
                palindrome = MathExt.Concat( lhs * 10, MathExt.ReverseDigits( rhs ) );      // Multiplying the lhs by 10 is equivalent to adding b == 0
                result.Add( palindrome );       // Add numbers of the form aaa + 0 + aaa

                lhs = a;
                for ( ulong b = 1; b != 10; b++ )
                {
                    rhs = a * 10 + b; // Adding b before we reverse guarantees that there is no trailing 0s
                    palindrome = MathExt.Concat( lhs, MathExt.ReverseDigits( rhs ) );       // Works except when b == 0
                    result.Add( palindrome );       // Add numbers of the form aaa + b + aaa
                }
                a++;
            }
            pow *= 10;        // Each pass of the outer loop add an extra digit to aaa
        } 
        return (result);
    }


    /// <summary>
    ///  Reverses the digits in a number returning it as a new number. Trailing '0's will be lost.
    /// </summary>
    /// <param name="n">The number to reverse.</param>
    /// <param name="radix">The radix or base of the number to reverse.</param>
    /// <returns>The reversed number.</returns>
    static public ulong ReverseDigits( ulong n, uint radix = 10 )
    {
        // Reverse the number
        ulong result = 0;
        do
        {
            // Extract the least significant digit using standard modular arithmetric
            result *= radix;
            result += n % radix;
            n /= radix;
        } while ( n != 0 );
        return (result);
    }


/// <summary>
    /// Concaternates the specified numbers 'a' and 'b' forming a new number 'ab'.
    /// </summary>
    /// <example>If a = 1234 and b = 5678 then Concat(a,b) = 12345678.</example>
    /// <param name="a">The first number.</param>
    /// <param name="b">The second number.</param>
    /// <returns>The concaternated number 'ab'.</returns>
    public static ulong Concat( this ulong a, ulong b )
    {
        // Concaternate the two numbers by shifting 'a' to the left by the number of digits in 'b' and then adding 'b'
        return (a * pow10[NumberOfDigits( b )] + b);
    }

    /// <summary>
    /// Evaluate whether the passed integer is a palindrome in base 10 or not.
    /// </summary>
    /// <param name="n">Integer to test.</param>
    /// <returns>True - Palindrome, False - Non palindrome.</returns>
    static public bool IsPalindrome( this ulong n )
    {
        uint divisor = NumberOfDigits( n ) - 1;
        do
        {
            // Extract the most and least significant digits of (n)
            ulong msd = n / pow10[divisor];
            ulong lsd = n % 10;

            // Check they match!
            if ( msd != lsd )
                return (false);

            // Remove the msd and lsd from (n) and test the next most and least significant digits.
            n -= msd * pow10[divisor];  // Remove msd
            n /= 10;                    // Remove lsd
            divisor -= 2;               // Number has reduced in size by 2 digits 
        } while ( n != 0 );
        return (true);
    }