如何编写算法来查找哪些平方组合彼此相等
Asq + bsq + csq + bsq = esq
1+4+9+16=25假太大
1+4+9+16=36 false 太小
最佳答案
如果您想使用递归,首先您应该从创建一个方法开始:
- 将获取整数列表(长整型)作为输入,
- 检查输入是否符合条件
- 如果匹配方程则返回
- 否则增加输入值之一
- 称自己具有更高的值(value)。
所以它看起来像这样:
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]);
}
现在的技巧是,正确地增加值。
您的问题是combination with repetition这意味着将有 (k+n-1)!/(k!(n-1)!)
其中 k=5
和 n=400
(不能是 100;))所以在我们的例子中是:(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(最大值)时,倒数第二个索引就会增加 1,并且最后一个索引将设置为与倒数第二个索引相同的值。 所以实现看起来像这样:
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
这是proof它是正确的。
PS 您所做的实际上是个好主意 - 将功率值存储在数组中。在有这么多循环的情况下,它确实会产生影响。此外,不要尝试打印每个案例 - 它会大大减慢程序速度。
关于java - 递归求解 A^4 + B^4 + C^4 + D^4 = E^4,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25470920/