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

Ответ 1

Создание всех палиндромов до определенного предела.

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

Ответ 2

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

Ответ 3

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

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

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

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

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

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

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

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

Ответ 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);
        }
    } 

Ответ 5

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

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

Ответ 6

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

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

Ответ 7

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

Я также включил некоторые методы поддержки, включая быстрый палиндромный тест, и его ценность указывает, что 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 
                // 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 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);
    }

Ответ 8

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