Блог

Мы пытаемся найти наибольшее число палиндрома, которое генерируется путем умножения двух 3-значных чисел. Номер палиндрома — это тот, который одинаково читается с обеих сторон (пример: 12345654321 или просто 9009). Следующий код компилируется правильно, но, очевидно, имеет место логическая ошибка, потому что результат равен 749947, когда он должен быть 906609. Если бы кто-нибудь мог помочь объяснить логику того, где я неправильно понимаю эту проблему, это было бы здорово.

 boolean valid = false;
for (int i = 999*999; i > 100*100; i--) {
  if (i / 100000 == i % 10 amp;amp;
      i / 10000 % 10 == i / 10 % 10 amp;amp;
      i / 1000 % 10 == i / 100 % 10) {
        int buffer = i;
        int total = 1;
        for (int k = 2; k < buffer; k  ) {
          if (buffer % k == 0) {
            buffer /= k;
            total *=k;
          }
        }
        if (buffer >= 100 amp;amp; buffer < 1000 amp;amp; total >=100 amp;amp; total < 1000 ) {
          System.out.println(i);
          System.out.println(total);
          System.out.println(buffer);
          break;
        }
     }
    }
  }
}
  

 906609  =  3 * 11 * 83 * 331  =  2739 * 331  =  913 * 993  =  ...
  

Ваш код преобразуется в buffer = 331, total = 2739 , что приводит к сбою вашего if оператора.

Предложение: вместо того, чтобы проверять все числа от 998001 до 10000 и пытаться найти 3-значные значения, которые приводят к числу при умножении, используйте двойной for цикл из 3-значных чисел и найдите наибольшее произведение, которое также является палиндромом.

Этому подходу легче следовать, и он работает.

 import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Palindrome
{
  private static List<Integer> palindromes = new ArrayList<Integer>();

  public static void main(String[] args)
  {
    for (int i = 999; i > 99; i--)
    {
      for (int j = 999; j > 99; j--)
      {
        if (isPalendrome(i * j))
        {
          palindromes.add(i * j);
        }
      }
    }
    if (!palindromes.isEmpty())
    {
      Collections.sort(palindromes);
      System.out.println(palindromes.get(palindromes.size() - 1));
    }
  }

  private static boolean isPalendrome(int number)
  {
    char[] word = String.valueOf(number).toCharArray();
    int i1 = 0;
    int i2 = word.length - 1;
    while (i2 > i1)
    {
      if (word[i1] != word[i2])
      {
        return false;
      }
        i1;
      --i2;
    }
    return true;
  }
}
  

Что ж, вам должно было быть проще объяснить, написав код, но мы должны вернуться к рассуждениям внутри него. Внешний цикл использует метод грубой силы, проверяя все числа на наличие палиндромных шаблонов, а затем применяя внутренний тест.

Этот внутренний тест — это то, где все идет наперекосяк. Он пытается быть умным, но выдает логическую ошибку. Я вижу, что он пытается разложить найденное число на buffer и total , предназначенное для двух трехзначных чисел. Однако позже он проверяет, что они являются трехзначными; они вычисляются без учета этого правила.

k используется в качестве потенциального фактора для передачи из buffer в total . Каждое число проверяется один раз, что исключает любое число с квадратными или более высокими коэффициентами мощности. Что еще более важно в этом случае, они проверяются от низкого до высокого, пока total не станут меньше buffer . Так что же происходит с 906609?

 (%i1) factor(906609);
(%o1) 3 11 83 331
  

Алгоритм останавливается на 3*11*83 * 331 , но 3*11*83 =2739, значит, неверное количество цифр. В искомом ответе используется другое разделение факторов: 3*331 * 11*83 . Подход факторизации выполним, но вам нужно будет проверить наличие групп факторов, которые, в свою очередь, дают трехзначные продукты.