算法:返回求和y的x次方的最小项数

Question

当我读到这个极客reading页面时，http://www.geeksforgeeks.org/minimum-number-of-power-terms-with-sum-equal-to-n/

我开始想，如果我们稍微改变一下这个问题，我们写一个函数minPower( power，sum )，而不是得到sum等于n的最小幂项数：

minPower(2,7)返回4，因为7= 2^2+1^2+1^2+1^2

minPower(2,9)返回1，因为9=3^2

minPower(3,9)返回2，因为9=2^3+1^3

我该如何编写这样的函数呢？

Answer 1

解决这个问题的最简单方法是使用递归贪婪算法，删除最大数m <= sum，其中m = p^n，直到sum为0，在这种情况下，您已经找到了解决方案，或者是负的，在这种情况下，您将p减去1。接受具有最小项数的解决方案。

您可以使用术语pow(10, log10(sum)/n)查找p的最大可能值

下面是一些用于说明的Java代码：

public static void main(String[] args)
{       
    minPower(2, 7);
}

public static void minPower(int n, int sum)
{
    if(n < 1) throw new IllegalArgumentException();

    int maxPow = (int)Math.pow(10, Math.log10(sum)/n);

    List<Integer> min = new ArrayList<>();
    LinkedList<Integer> terms = new LinkedList<>();
    powers(n, sum, maxPow, terms, min);     
    System.out.println(min);
}

private static void powers(int n, int sum, int m, LinkedList<Integer> terms, List<Integer> min)
{
    if(sum == 0) 
    {
        if(min.isEmpty() || terms.size() < min.size())
        {
            min.clear();
            min.addAll(terms);
        }
        return;
    }
    else if(sum < 0) return;

    for(int i=m; i>0; i--)
    {
        terms.addLast(i);
        powers(n, sum - (int)Math.pow(i, n), i, terms, min);
        terms.removeLast();
    }
}   

输出：

2,7
[2, 1, 1, 1]

2, 9
[3]

3, 9
[2, 1]

3, 32
[2, 2, 2, 2]