كيف يمكنني تحسين رمزك الفظيع لإيجاد أعلى palindrome من رقم 3 أرقام؟

Question

هذا ما كتبته حتى الآن. إنه يجمع ، وبقدر ما أستطيع أن أقول ، يجب أن "يعمل" - إذا كنت ستمنح جهاز الكمبيوتر الخاص بك قدرًا لا حصر له من الوقت لحساب الإجابة!

كنت أتساءل فقط عما إذا كان أي شخص سيتمكن من إعطائي طريقة لتحسين هذا حتى يخبرني برنامجي بأعلى رقم palindromic (نفس الأمام والخلف على سبيل المثال ، 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 ولأنه palindromic ، فمن المحتمل أن ينتهي بالرقم 9 أيضًا. باختصار ، تتوقع أرقامًا في النموذج 9XYYX9.

بعد ذلك ، لا يمكن ضرب جميع أزواج الأرقام وإنهاء الرقم 9. XX3 و XX3 سيعطي XXXXX9 ، وكذلك XX1 و XX9 ؛ لكن XX1 و XX8 لن يتضاعفوا أبدًا مع XXXXX9.

ابحث عن خصائص مثل هذه ، وحاول تصفية ما يمكن تنفيذها بسهولة في البحث.

Answer 2

لك for شروط الحلقة خاطئة:

LoopOfFirstNumber<=0

يجب أن يكون:

LoopOfFirstNumber>=100

يجب أن تستمر في الحلقة حتى تكون عدادات الحلقة الخاصة بك >= 100 وهو أصغر رقم 3 أرقام.

بمجرد العثور على palindrome ، تحتاج إلى كسر كلتا الحلقات. حاليا أنت تحطم الحلقة الداخلية فقط. لإصلاح هذا تحتاج إلى استخدامه الاستراحة المسمى.

Answer 3

لا يحتاج INNER for Loop إلى البدء بـ 999 ، ويمكن أن يبدأ بـ LoopOfSecondNumber = LoopOfFirstNumber:

لنفترض أن هناك حلًا LoopOfSecondNumber = x > LoopOfFirstNumber = y. ثم سيكون هناك حل حيث يتم تبديل الرقمين: LoopOfFirstNumber = x, LoopOfSecondNumber = y => كان هذا الحل قد تم العثور عليه سابقًا في الحلقة الخارجية بالفعل.

هذا لا يجلب لك الكثير من التحسين ، في أفضل حالات يأخذك نصف الوقت الذي استغرقه الرمز الأصلي.

Answer 4

لماذا لا تعالجها من الجانب الآخر؟

قم بإنشاء مجموعة من جميع أرقام Palindrome بدءًا من 1000000 (1000*1000) والعمل لأسفل ، يجب أن يكون سهلاً إلى حد ما.

ثم قم بتوضيحهم - على الرغم من أنني أعتقد أنك ستحتاج إلى خوارزمية لهذا :-(