如何确定一个数是否是一些平方数的和？

Question

我有一道算法题：我们如何确定一个数是否等于一些不同平方数的总和？例如： 50 = 4*4 + 5*5 + 3*3

而且，如果它是真的，我怎样才能找到我们可以写成几个不同平方和的状态数？

25 = 5^2 + 0 或 3^2 + 4^2 并且它有 2 个状态。

我可以接受 2 个数字，我知道我们可以用递归来解决它。

这是我在 java 中用于 2 个数字的代码：

import java.util.Scanner;

public class SemiCharismatic {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number = input.nextInt();
        input.close();
        if (isSquare(number) == true) {
            System.out.print("YES");
            System.exit(0);
        } else {
            for (int i = 1; i < number; i++) {
                int j = number - i;
                if (isSquare(i) == true && isSquare(j) == true) {
                    System.out.print("YES");
                    System.exit(0);
                }
            }
            System.out.print("NO");
        }
    }

    static boolean isSquare(int number) {
        boolean result = false;
        if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0) {
            result = true;
        }
        return result;
    }
}

Answer 1

此问题是 Subset sum problem 的变体。

在这里你必须自己创建一组（下面会解释），你的数字就是问题的目标总和。

要创建一个集合，请形成一个数字数组 [square of numbers from {1 to sqrt(n)}]

因此您的数组将如下所示：[1,4,9... sqrt(n)^2]

解释为什么sqrt(n): 任何大于 sqrt(n) 的数的平方也将大于 n。因此，添加更多内容不会导致解决方案。

然后应用 subset-set 算法，如解释的那样 here

isSubsetSum(set, n, sum) 
= isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0

Answer 2

这可以看作是硬币兑换问题（参见here）。

解决硬币交换问题的一种方法是递归，正如另一个答案所建议的：

def is_sum_squared_rec(number, candidates=None, idx=None):
    if candidates is None:
        candidates = np.arange(1, int(np.floor(np.sqrt(number)))+1) ** 2
        idx = len(candidates) - 1
    if (number > 0 and idx == -1) or number < 0:
        return False
    if number == 0:
        return True
    return is_sum_squared_rec(number, candidates, idx-1) or is_sum_squared_rec(number-candidates[idx], candidates, idx-1)

但是在这种情况下实现硬币交换问题的另一种非递归方法如下：

def is_sum_squared(number):
    counts = [1] + [0] * number
    candidates = np.arange(1, int(np.floor(np.sqrt(number))) + 1) ** 2
    for candidate in candidates:
        for jj in range(number, candidate-1, -1):
            counts[jj] += counts[jj - candidate]
    return counts[number] > 0

这种方法避免了冗余计算，应该比递归方法更快。

non-recursive 方法可以进一步改进，因为我们不需要整个计数，只要它可以分解为候选的总和即可。因此我们可以引入提前停止条件：

def is_sum_squared_early_stop(number):
    counts = [1] + [0] * number
    candidates = np.arange(1, int(np.floor(np.sqrt(number))) + 1) ** 2
    for candidate in candidates:
        for jj in range(number, candidate-1, -1):
            counts[jj] += counts[jj - candidate]
            if counts[number] > 0:
                return True
    return counts[number] > 0

non-recursive算法的运行时间为O(n*sqrt(n))，scape要求为O(n)。

时机

对于 number = 400，计时结果如下：

%timeit is_sum_squared_rec(400)
1.88 ms ± 177 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit is_sum_squared(400)
1.05 ms ± 76.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit is_sum_squared_early_stop(400)
796 µs ± 127 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

几乎提高了 3 倍。使用 number=3000 检查时，我们得到：

%timeit is_sum_squared_rec(3000)
1.81 s ± 152 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit is_sum_squared(3000)
24.5 ms ± 581 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit is_sum_squared_early_stop(3000)
14.3 ms ± 556 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

而且我们有超过2个数量级的差异

如何确定一个数是否是一些平方数的和？

How can you determine if a number is sum of some squared numbers?

algorithm

recursion

时机