Comment puis-je optimiser mon code terrible pour trouver le plus palindrome d'un numéro à 3 chiffres?

Question

est ce que je l'ai écrit jusqu'à présent. Il compile, et, pour autant que je peux dire, il faut « travailler » - si vous deviez donner votre ordinateur une quantité infinie de temps pour calculer la réponse!

Je me demandais si quelqu'un s'il vous plaît être en mesure de me donner un moyen d'optimiser cela pour que mon programme me dira le plus grand nombre palindrome (même à la fois avant et en arrière, par exemple, 91 * 99 = 9009;) formé par multipliant deux nombres à trois chiffres.

 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

Comme vous l'avez déjà deviné, le problème est dans la boucle imbriquée. Essayez de trouver quelques biens des numéros. Multiplication de deux numéro trois chiffres toujours donner un nombre ayant cinq ou six chiffres. Puisque vous êtes à la recherche du plus grand nombre, il est prévu d'être le numéro à six chiffres commençant par le numéro 9 et puisqu'il est palindrome, il se termine probablement avec le numéro 9 ainsi. En bref, vous vous attendez à des numéros sous la forme 9xyyx9.

Ensuite, toutes les paires de nombres peuvent être multipliés et se terminent par le numéro 9. xx3 et xx3 donnera xxxxx9, le fait XX1 et XX9; mais XX1 et XX8 ne seront jamais à multiplier xxxxx9.

Trouver des propriétés comme celles-ci, et essayer de filtrer ceux qui peuvent probablement être mis en œuvre facilement dans votre recherche.

Answer 2

Vos conditions de boucle de for est erroné:

LoopOfFirstNumber<=0

il devrait être:

LoopOfFirstNumber>=100

Vous devez continuer à boucle jusqu'à ce que vos compteurs de boucle sont >= 100 qui est le plus petit nombre à 3 chiffres.

En outre, une fois que vous trouverez un palindrome, vous devez casser les deux boucles. À l'heure actuelle, vous violez que la boucle intérieure. Pour corriger cela, vous devez utiliser break étiqueté .

Answer 3

La boucle intérieure pour ne pas besoin de commencer avec 999, il peut commencer par LoopOfSecondNumber = LoopOfFirstNumber:

Supposons qu'il y ait une solution pour laquelle LoopOfSecondNumber = x > LoopOfFirstNumber = y. Ensuite, il y aurait une solution où les deux numéros sont allumés. LoopOfFirstNumber = x, LoopOfSecondNumber = y => Cette solution aurait donc été trouvé plus tôt dans la boucle externe déjà

Cela ne vous apporte pas beaucoup d'optimisation si, dans le meilleur cas, il vous faut la moitié du temps le code d'origine a.

Answer 4

Pourquoi abordez-vous pas de l'autre côté?

Créer un ensemble de tous les devrait être assez facile nombre palindrome à partir de 1000000 (1000 * 1000) et en descendant,.

Et les factoriser alors - bien que je suppose que vous allez avoir besoin d'un algorithme pour cela: - (