1

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

我只是想知道是否有人可以给我一种优化它的方法，以便我的程序会告诉我通过将任意两个相乘形成的最高回文数（向前和向后都相同，例如 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);
    }
4

4 回答 4

3

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

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

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

于 2010-10-25T10:54:33.723 回答
1

您的for循环条件错误：

LoopOfFirstNumber<=0

它应该是：

LoopOfFirstNumber>=100

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

此外，一旦你找到回文，你需要打破两个循环。目前，您只打破内部循环。要解决此问题，您需要使用标记的 break。

于 2010-10-25T10:36:42.630 回答
1

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

让我们假设有一个解决方案LoopOfSecondNumber = x > LoopOfFirstNumber = y。然后会有一个切换两个数字的解决方案：LoopOfFirstNumber = x, LoopOfSecondNumber = y=> 因此，该解决方案早在外循环中就已经找到了。

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

于 2010-10-25T10:49:03.350 回答
1

你为什么不从另一边解决它？

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

然后对它们进行因式分解——尽管我想你需要一个算法来解决这个问题:-(

于 2010-10-25T10:59:33.417 回答