递归求解A^4 + B^4 + C^4 + D^4 = E^4
你如何写一个算法来找出哪些方格组合相等？
Asq + bsq + csq + dsq = esq
1+4+9+16=25假过大
1+4+9+16=36假太小
回答 2
Stack Overflow用户
发布于 2014-08-24 17:53:04
如果您想使用递归，那么首先应该创建一个方法，该方法：
- 将整数列表(Long)作为输入，
- 检查输入是否与条件匹配。
- 返回与等式匹配的
- 否则会增加一个输入值。
- 以更高的价值呼叫自己。
所以看起来是这样：
private void trySolutionRecursivly(final Long[] values)
{
System.out.println("a = " + values[0] + "; b = " + values[1] + "; c = " + values[2] + "; d = " + values[3] + "; e = " + values[4]);
if (conditionMet(values))
{
System.out.println("Met the condition!");
}
else
{
Long[] newValues = increaseValues(values);
trySolutionRecursivly(newValues);
}
}该方法的第一个调用如下所示(一个包含5个数组的数组)：
trySolutionRecursivly({1L, 1L, 1L, 1L, 1L});但是如果您尝试递归地执行这个操作，您将得到StackOverflowError，因为组合太多了，递归调用也太多了(我已经尝试过了)。因此，唯一的解决方案是在循环中依次调用该方法，例如：
private void findSolution()
{
Long[] newValues = {1L, 1L, 1L, 1L, 1L};
while (conditionNotMet(newValues))
{
newValues = increaseValues(values);
}
System.out.println("a = " + values[0] + "; b = " + values[1] + "; c = " + values[2] + "; d = " + values[3] + "; e = " + values[4]);
}现在的诀窍是，正确地增加值。
您的问题是结合重复，这意味着存在(k+n-1)!/(k!(n-1)!)，其中k=5和n=400(不能是100；)，所以在我们的例子中，its：(5+400-1)!/(5!(399)!)=404!/(5!399!)，这是400*401*402*403*404/120=87485400080可能的解决方案。这是相当多的，这就是为什么递归不能在这里工作(在最坏的情况下，程序必须存储大约87485400080个方法调用的信息)。
现在，结合重复的工作如下，4个价值和3个地方：
1;1;1
1;1;2
1;1;3
1;1;4
1;2;2
1;2;3
1;2;4
1;3;3
1;3;4
1;4;4
2;2;2
2;2;3
2;2;4
2;3;3
2;3;4
2;4;4
3;3;3
3;3;4
3;4;4
4;4;4您可以注意到，每次最后一个索引达到4(最大值)时，第二个到最后一个索引将增加一个，最后一个索引将设置为与第二个索引相同的值。所以这个实现应该是这样的：
private Long[] increaseValues(final Long[] values)
{
boolean reindexed = false;
for (int i = 0; i < values.length; i++)
{
if (values[i] == MAX_VALUE)
{
if (i > 0)
{
values[i-1]++;
reindex(i, values);
reindexed = true;
break;
}
else
{
throw new IllegalStateException("No solution found.");
}
}
}
if (!reindexed)
{
values[values.length-1]++;
}
return values;
}
private Long[] reindex(final Integer startIndex, final Long[] values)
{
Long startingValue = values[startIndex - 1];
for (int i = startIndex; i < values.length; i++)
{
values[i] = startingValue;
}
return values;
}扰流板警报
总之，这段代码会起作用，并给出答案。如果您想尝试并查看会发生什么，也会有注释过的递归代码。
public class Main
{
final static int MAX_VALUE = 400;
final static Long[] powers = new Long[MAX_VALUE + 1];
public static void main(String args[])
{
final Long[] values = {1L, 1L, 1L, 1L, 1L};
for (Integer i = 0; i <= MAX_VALUE; i++)
{
powers[i.intValue()] = Double.valueOf(Math.pow(i.doubleValue(), 4d)).longValue();
}
//new Main().trySolutionRecursivly(values);
new Main().findSolution(values);
}
private void findSolution(final Long[] values)
{
Long[] newValues = values;
while (conditionNotMet(newValues))
{
newValues = increaseValues(values);
}
System.out.println("a = " + values[0] + "; b = " + values[1] + "; c = " + values[2] + "; d = " + values[3] + "; e = " + values[4]);
}
private void trySolutionRecursivly(final Long[] values)
{
System.out.println("a = " + values[0] + "; b = " + values[1] + "; c = " + values[2] + "; d = " + values[3] + "; e = " + values[4]);
if (conditionMet(values))
{
System.out.println("Met the condition!");
}
else
{
Long[] newValues = increaseValues(values);
trySolutionRecursivly(newValues);
}
}
private boolean conditionNotMet(final Long[] values)
{
return !conditionMet(values);
}
private boolean conditionMet(final Long[] values)
{
return pow(values[0]) + pow(values[1]) + pow(values[2]) + pow(values[3]) == pow(values[4]);
}
private Long pow(final Long value)
{
return powers[value.intValue()];
//return Math.pow(value.doubleValue(), 4d);
}
private Long[] increaseValues(final Long[] values)
{
boolean reindexed = false;
for (int i = 0; i < values.length; i++)
{
if (values[i] == MAX_VALUE)
{
if (i > 0)
{
values[i-1]++;
reindex(i, values);
reindexed = true;
break;
}
else
{
throw new IllegalStateException("No solution found.");
}
}
}
if (!reindexed)
{
values[values.length-1]++;
}
return values;
}
private Long[] reindex(final Integer startIndex, final Long[] values)
{
Long startingValue = values[startIndex - 1];
for (int i = startIndex; i < values.length; i++)
{
values[i] = startingValue;
}
return values;
}
}扰流板
输出(得到它需要一段时间-我花了大约15分钟)：
a = 30; b = 120; c = 272; d = 315; e = 353这是证明，它是正确的。
，PS，，这实际上是一个很好的想法--在数组中存储功率值。在有这么多循环的情况下，它确实产生了不同的效果。此外，不要试图打印每一种情况--它会大大降低程序的速度。
Stack Overflow用户
发布于 2014-08-24 11:28:15
不要用一个来提高所有的值；相反，把ABCD当作基数为100的阿拉伯数字(“位”是整数1-100，1是你的“零”数字)，并编写生成所有这些数字的代码。基本上，
- 设定A.B.C.D为1.1.1.1；
- 计算和，在数组中搜索匹配；
- 增量D；
- 如果D大于100，则重置为1并增加C；
- 对B重复步骤3-4，然后是A；
- 当溢出时停止。
并且，停止对整数算术使用doubles，而使用longs。double只能精确地表示最多2^54 (或类似的)整数，而long可以使您达到2^64。除了范围之外，使用double还可以打开虚假否定的大门(有解决方案的ABCD的组合，但您的代码错过了它)。
https://stackoverflow.com/questions/25470920
复制相似问题
腾讯云开发者
