Как я могу оптимизировать мой ужасный код, чтобы найти самый высокий палиндром из трехзначного числа? - PullRequest
Новая
       18

Как я могу оптимизировать мой ужасный код, чтобы найти самый высокий палиндром из трехзначного числа?

1 голос
/ 25 октября 2010

Это то, что я написал до сих пор. Он компилируется, и, насколько я могу судить, он должен «работать» - если бы вы дали своему компьютеру бесконечное количество времени для вычисления ответа!

Мне просто интересно, сможет ли кто-нибудь дать мне способ оптимизировать это так, чтобы моя программа сообщала мне самое высокое палиндромное число (одинаковое как для прямого, так и для обратного направления, например, 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 ]

3 голосов
/ 25 октября 2010

Как вы уже догадались, проблема во вложенном цикле.Попробуйте выяснить несколько свойств чисел.Умножение двух трехзначного числа всегда дает число, имеющее пять или шесть цифр.Поскольку вы ищете наибольшее число, то ожидается, что это будет шестизначное число, начинающееся с цифры 9, и, поскольку оно является палиндромным, вероятно, оно также заканчивается числом 9.Короче говоря, вы ожидаете числа в форме 9xyyx9.

Далее, не все пары чисел могут быть умножены и заканчиваться числом 9. xx3 и xx3 дадут xxxxx9, также как xx1 и xx9;но xx1 и xx8 никогда не умножатся на xxxxx9.

Найдите подобные свойства и попробуйте отфильтровать, какие из них могут быть легко внедрены в ваш поиск.

1 голос
/ 25 октября 2010

Почему бы вам не заняться этим с другой стороны?

Создать набор из всех чисел палиндрома, начиная с 1000000 (1000 * 1000) и работая вниз, должно быть довольно просто.

А затем разложить их на множители - хотя, думаю, вам понадобится алгоритм для этого: - (

1 голос
/ 25 октября 2010

Внутренний цикл for не обязательно должен начинаться с 999, он может начинаться с LoopOfSecondNumber = LoopOfFirstNumber:

Предположим, что существует решение, для которого LoopOfSecondNumber = x > LoopOfFirstNumber = y. Тогда было бы решение, в котором два числа поменялись местами: LoopOfFirstNumber = x, LoopOfSecondNumber = y => Таким образом, это решение уже было бы найдено ранее во внешнем цикле.

Это не принесет вам особой оптимизации, в лучшем случае это займет половину времени, которое потребовался исходному коду.

1 голос
/ 25 октября 2010

Неправильные условия вашего for цикла: 

LoopOfFirstNumber<=0

должно быть: 

LoopOfFirstNumber>=100

Вы должны продолжать цикл до тех пор, пока ваши счетчики циклов не станут >= 100, что является наименьшим трехзначным числом.

Также, как только вы найдете палиндром, вам нужно разорвать обе петли. В настоящее время вы нарушаете только внутренний цикл. Чтобы это исправить, вам нужно использовать с надписью break .

...