0

我有一个程序来编写代码,它将求解一个 5-1 五阶丢番图方程,该方程基本上是 A^5 + B^5 + C^5 + D^5 + E^5 = F^5,其中 0 < A < = B <= C <= D <= E <= F <= N。我将要实现它的方式是预先计算给定 N 值的值,然后将其存储到数组中。因此,例如,如果 N 为 100,它会将 1 到 100 之间的值存储在一个数组中。

然后我将计算第一组 A^5 + B^5 + C^5 和第二组 F^5 - (D^5 + E^5) 的值,并比较第一组的值到第二个,看看它们是否匹配。如果匹配,则找到解决方案。

我的问题是,我将如何使用 1 到 N 之间的值数组来计算两组的所有可能值?我有这个想法,但是把它编码出来,我不知道如何处理它。谁能给我一些提示?我不是在询问如何编码的解决方案,我只是想要一些可以帮助我更好地理解编码过程的提示/提示。谢谢!

4

3 回答 3

4

我肯定会从计算每个数字 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)第三个循环,生成 D^5 的值,测试 F^5 的值 - (D^5 + E^5) 如果为负,那么你可以打破这个循环(但不是外循环

继续剩余 3 个循环,剩余 3 个值。如果你的方程每个循环将有越来越少的值来测试。因为我们可以在等式变为负数或达到已经使用过的数字时停止

方程等于 0 的任何解都是解。

时间分析很困难,如果 N^2 会导致前 2 个循环,但剩下的 4 个循环会小得多,甚至可能是 logn time 每个希望 nlogn time 一起

我用 n=600 进行了测试。它的最大解为
218^5 + 276^5 + 385^5 + 409^5 + 495^5 = 553^5 一个 N^6 方程将在 4E16 步中达到这个解,我的在 2E15 或 5 中达到它% 的时间。

不确定这是否会降低到 n^3logn 但它通过跳过大量不正确的解决方案让你更接近。

于 2012-11-10T18:07:01.710 回答
2

更好的解决方案,首先生成所有 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(3n),这个解决方案将是 O(3nlogn)

于 2012-11-11T01:08:53.553 回答
1

对@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 where开始

5*E^5 > F^5

并上升到F-1

在第三个循环(D)中,我们会遇到与上述不等式类似的不等式

 F^5 - E^5 = A^5 + B^5 + C^5 + D^5 < 4^D5

我们应该开始测试D满足这个条件的第一个。

这同样适用于其余的内部循环。

这看起来并不多,但同样的想法有助于解决一些竞争问题。

于 2012-11-17T01:09:27.193 回答