从两个三位数的乘积优化最大回文? [英] Optimizing the largest palindrome from product of two three digit numbers?

问题描述

我正在处理一个面试问题，有人问我应该写一个程序来从两个三位数的乘积中找到最大的回文.

I am working on an interview question which I was asked in which I was supposed to write a program to find the largest palindrome from product of two three digit numbers.

这是问题

我想出了一种从底层开始的蛮力方法.

I came up with this brute force approach which starts from bottom.

public class LargestPalindromeQuestion {

    public static void main(String[] args) {
        int value = 0;
        for (int i = 100; i <= 999; i++) {
            for (int j = i; j <= 999; j++) {
                int value1 = i * j;
                if (isPalindrome(value1) && value < value1) {
                    value = value1;
                }
            }
        }
        System.out.println(value);
    }

    private static boolean isPalindrome(final int product) {
        int p = product;
        int reverse = 0;
        while (p != 0) {
            reverse *= 10;
            reverse += p % 10;
            p /= 10;
        }
        return reverse == product;
    }
}

他们问我在此程序中可以做哪些优化?我提到过，我们可以尝试修剪搜索空间并优化搜索空间中每个项目的检查步骤，但是我很困惑如何在上述解决方案中完成这项工作?

They asked me what are the optimizations I can do in this program? I mentioned that we can try pruning the search space and optimize checking step for each item in the search space but then I am confuse how would I make this work in my above solution?

我们可以在此程序中进行哪些优化?现在，它正在执行 810000 步骤以找到最大的回文.

What are the optimizations we can do in this program? Right now it is executing 810000 steps to find the largest palindrome.

在两个三位数的数字中找到最大回文的最小步骤数是什么?

What is the least number of steps we can execute to find the largest palindrome in two three digit numbers?

推荐答案

该程序对我来说很好.我会让 i 循环计数从 999 减少到 100 ，而我只会检查 j 的值，实际上给出的产品大于当前的最大值.

The program looks very good to me. I would make the i loop count from 999 down to 100, and I would only check j values that would actually give a larger product than the current maximum.

确切地说，该程序能够以惊人的速度完成，代码为 i == 952 .这样做的数学原因是，一旦找到解决方案 906609 ( 993 * 913 )，就不再可能找到较大回文，而较大因子较少比 906609 的平方根，即 952.160 ... .

This program is able to finish surprisingly soon, at i == 952 to be precise. The mathematical reason for this is that once the solution 906609 (993 * 913) is found, it will no longer be possible to find a larger palindrome where the larger factor is less than the square-root of 906609, which is 952.160....

public static void main(String[] args) {
    int value = 0;
    for (int i = 999; i >= 100; i--) {
        int r = value / i;
        if (r >= i) {
            System.out.println("We broke at i = " + i);
            break;
        }
        for (int j = i; j > r; j--) {
            int value1 = i * j;
            if (isPalindrome(value1)) {
                value = value1;
                break;
            }
        }
    }
    System.out.println(value);
}

这篇关于从两个三位数的乘积优化最大回文?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！