Генерация значений для диофантовых уравнений в Java?
У меня есть программа для кодирования, где она будет решать 5-1 диофантово уравнение пятого порядка, которое в основном представляет собой A^5 + B^5 + C^5 + D^5 + E^5 = F^5, где 0 Затем я вычислю значения первой группы A ^ 5 + B ^ 5 + C ^ 5 и второй группы F^5 - (D^5 + E^5) и сравню значения из первой группы. второй, чтобы увидеть, если они совпадают. Если это соответствует, то решение найдено. Мой вопрос заключается в том, как мне рассчитать все возможные значения двух групп, используя массив значений от 1 до N? У меня есть идея, но, кодируя ее, я не уверен, как к ней подойти. Кто-нибудь может дать мне несколько советов? Я не спрашиваю решения относительно того, как его кодировать, я просто хочу несколько советов / подсказок, которые могут помочь мне лучше понять процесс кодирования. Спасибо!
3 ответа
Лучшее решение - сначала сгенерировать все значения 5-го порядка и сохранить их в массиве.
Затем используйте 3 вложенных цикла для создания каждой комбинации F^5-E^5-D^5 и сохраните все эти комбинации
Затем используйте 3 различных вложенных цикла, чтобы сгенерировать каждую комбинацию A^5+B^5+C^5 и сохранить все эти значения.
Используйте 2 вложенных цикла для сравнения значений F^5-E^5-D^5 и A^5+B^5+C^5. если они одинаковы, у вас есть решение. выведите соответствующие значения a,b,c,d,e и f.
мы используем только 2 пары из 3 вложенных циклов. это решение будет O(3nlogn), если не O(3n)
Я бы определенно начал с вычисления всех значений 5-го порядка для каждого числа от 1 до N, затем я бы начал со стороны F^5 - (A ^ 5 + B ^ 5 + C ^ 5 + D ^ 5 + E ^ 5),
1) внешний цикл, генерация значений для F^5 начинается с максимально возможных значений, к счастью, мы знаем, что наименьшее значение F составляет 72. Lander and Parkin (1967)
для остальных циклов начните с самых низких значений,
2) второй цикл, генерировать значения для E ^ 5
3) 3-й цикл, генерировать значения для D^5, тестовое значение для F^5 - (D^5 + E^5), если отрицательное значение, вы можете разорвать этот цикл (но не внешние циклы)
продолжить с 3 оставшимися циклами для 3 оставшихся значений. Если ваше уравнение каждого цикла будет иметь все меньше и меньше значений для проверки. так как мы можем остановиться, когда уравнение станет отрицательным или мы достигнем числа, которые уже были использованы
любое решение, где уравнение равно нулю, является решением.
анализ времени труден, первые 2 цикла будут получены, если N^2, но остальные 4 цикла будут намного меньше, возможно, даже время входа в систему, каждый из которых, надеюсь, не будет времени вместе
Я тестировал с n=600. который имеет самое большое решение
218^5 + 276^5 + 385^5 + 409^5 + 495^5 = 553^5 уравнение N^6 пришло бы к этому решению за 4E16 шагов, а мое достигнет его через 2E15 или 5% времени.
Я не уверен, что это приведет к n^3logn, но это приблизит вас, пропуская огромное количество неправильных решений.
Небольшое улучшение по сравнению с решением @Gregory могло бы побрить несколько ценностей здесь и там.
1.
Я не понимаю, почему мы должны останавливаться, когда данное уравнение отрицательно, поскольку мы знаем, что каждая буква меньше предыдущей. В этом случае, например, первые два цикла должны проходить (N^2/2) шагов.
2.
Во втором цикле (E) мы можем учитывать тот факт, что
F^5 = A^5 + B^5 + C^5 + D^5 + E^5 < 5*E^5
поэтому в цикле E нам не нужно начинать с 0, но мы можем начать с первого E где
5*E^5 > F^5
и подняться на F-1,
В третьем цикле (D) у нас было бы неравенство, подобное приведенному выше
F^5 - E^5 = A^5 + B^5 + C^5 + D^5 < 4^D5
и мы должны начать тестирование для первого D который выполняет это условие.
То же самое относится и к остальным внутренним циклам.
Это не очень похоже, но та же идея помогла в некоторых проблемах конкуренции.