java - 递归求解 A^4 + B^4 + C^4 + D^4 = E^4

Question

如何编写算法来查找哪些平方组合彼此相等

Asq + bsq + csq + bsq = esq

1+4+9+16=25假太大

1+4+9+16=36 false 太小

Answer 1

如果您想使用递归，首先您应该从创建一个方法开始:

1. 将获取整数列表(长整型)作为输入，
2. 检查输入是否符合条件
3. 如果匹配方程则返回
4. 否则增加输入值之一
5. 称自己具有更高的值(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您所做的实际上是个好主意 - 将功率值存储在数组中。在有这么多循环的情况下，它确实会产生影响。此外，不要尝试打印每个案例 - 它会大大减慢程序速度。