如何优化我糟糕的代码来查找 3 位数的最大回文数？

Question

这是我到目前为止所写的。它可以编译，并且据我所知，它应该“工作”——如果你给你的计算机无限的时间来计算答案！

我只是想知道是否有人能够给我一种优化方法，以便我的程序会告诉我由任意两个相乘形成的最高回文数（向前和向后都相同，例如 91 * 99 = 9009；）三位数。

 public class HighestPalindrome {
     public static void main(String[] args) {
    int number=0;
    int answer=0;

    search:
    for(int LoopOfFirstNumber=999;LoopOfFirstNumber<=100;LoopOfFirstNumber -= 3){
      for(int LoopOfSecondNumber=LoopOfFirstNumber;LoopOfSecondNumber<=100;LoopOfSecondNumber-=3)
      {
        number = LoopOfFirstNumber * LoopOfSecondNumber;
        if (number == reverse(number))
         {
          answer=number;
          System.out.println(answer);
          break search;
         }
      }
    }
  }

     //The code after this works fine, I believe. It will reverse any number given very quickly, I think the problem
     //is above....with the two for loops!

    private static int reverse(int n, int r) {
      if (n == 0) return r;
      System.out.println("This iteration returns " + n/10 + " and  " + 10*r+n%10);
      return reverse(n/10, 10*r+n%10);
    }

    public static int reverse(int n) {
     return reverse(n, 0);
    }

Answer 1

正如您已经猜到的，问题出在嵌套循环中。尝试找出数字的一些属性。两个三位数相乘总是会得到一个五位或六位数字。由于您正在寻找最大的数字，因此预计它是以数字 9 开头的六位数字，并且由于它是回文，因此它也可能以数字 9 结尾。简而言之，您期望得到 9xyyx9 形式的数字。

接下来，并非所有数字对都可以相乘并以数字 9 结尾。 xx3 和 xx3 将得到 xxxxx9，xx1 和 xx9 也是如此；但 xx1 和 xx8 永远不会乘以 xxxxx9。

找到这样的属性，并尝试过滤哪些属性可能可以轻松地实现到您的搜索中。

Answer 2

您的 for 循环条件是错误的：

LoopOfFirstNumber<=0

应该是：

LoopOfFirstNumber>=100

您应该继续循环，直到循环计数器为 >= 100 （最小的 3 位数字）。

此外，一旦找到回文，您就需要打破两个循环。目前您只打破了内部循环。要解决此问题，您需要使用带标签的中断。

Answer 3

内部 for 循环不需要从 999 开始，它可以从 LoopOfSecondNumber = LoopOfFirstNumber 开始：

让我们假设有一个解决方案，其 LoopOfSecondNumber = x > > LoopOfFirstNumber = y。那么就会有一个解决方案，将两个数字交换：LoopOfFirstNumber = x, LoopOfSecondNumber = y =>;因此，这个解决方案已经在外循环的较早阶段找到了。

但这并没有给你带来太多的优化，在最好的情况下，它只花费原始代码一半的时间。

Answer 4

为什么不从另一边解决呢？

创建一组从 1000000 (1000*1000) 开始并向下计算的所有回文数应该相当容易。

然后对它们进行因式分解 - 虽然我猜你需要一个算法:-(