最大的回文产品 - 欧拉项目 [英] Largest palindrome product - euler project

问题描述

我试图解决项目Euler 问题4 ，即：

I was trying to solve project Euler problem 4 which is:

回文数字的读取方式相同。由两个2位数字的乘积制成的最大回文是9009 = 91×99.
找到由两个3位数字的乘积制成的最大回文。

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

这是我的解决方案，它的输出是997799，但这不是正确答案，我想知道问题出在哪里：

Here is my solution , it's output is 997799 , however that's not the correct answer ,I wonder where is the problem:

package projecteuler;

public class Pro4 {

    public static void main(String[] args) {

        for(int i=999*999;i>=100*100;i--){
            if(isPalindrome(i)==true){
                System.out.println(i);
                break;
            }
        }
    }

    static boolean isPalindrome(int x){
        int[] bits = new int[7];
        int index=1;
        while(x>0){
            bits[index]=x%10;
            index++;
            x/=10;
        }
        for(int i=1;i<=index/2;i++){
            if(bits[i]!=bits[index-i]){
                return false;
            }
        }
        return true;
    }

}

推荐答案

这是一个不会遍历所有6位数字的解决方案：

Here is a solution that doesn't iterate through all the 6-digit numbers:

public static boolean isPalindrome(int nr) {
    int rev = 0;                    // the reversed number
    int x = nr;                     // store the default value (it will be changed)
    while (x > 0) {
        rev = 10 * rev + x % 10;
        x /= 10;
    }
    return nr == rev;               // returns true if the number is palindrome
}

public static void main(String[] args) {

    int max = -1;

    for ( int i = 999 ; i >= 100 ; i--) {
        for (int j = 999 ; j >= 100 ; j-- ) {
            int p = i * j;
            if ( max < p && isPalindrome(p) ) {
                max = p;
            }
        }
    }
    System.out.println(max > -1? max : "No palindrome found");
}

修改：

main 方法的改进解决方案（根据Peter Schuetze所说）可能是：

An improved solution for the main method ( according to Peter Schuetze ) could be:

public static void main(String[] args) {

    int max = -1;

    for ( int i = 999 ; i >= 100 ; i--) {
        if ( max >= i*999 ) { 
            break;
        }
        for (int j = 999 ; j >= i ; j-- ) {             
            int p = i * j;
            if ( max < p && isPalindrome(p) ) {
                max = p;
            }
        }
    }       
    System.out.println(max > -1? max : "No palindrome found");
}

对于这个特殊的例子，时间大约是2倍，但如果你有更大的数字，改善将更加显着。

For this particular example, the time is about 2 times better, but if you have bigger numbers, the improvement will be more significant.

输出：

906609

这篇关于最大的回文产品 - 欧拉项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！