首页 文章

所有可能的不同完美正方形的总和等于给定数字的平方

提问于
浏览 次
0

我正在尝试编写一个程序来解决一个问题，该问题说明如下“打印所有可能的不同的完美正方形，其总和等于给定数字的平方” . 例如 -

输入

11

产量

1 4 16 36 64

1 4 16 100

4 36 81

我尝试了基本的递归方法，我的代码传递给小输入 . 当我尝试像116这样更大的数字时，它会永远运行 . 我的JAVA代码

public class SumOfPerfectSquare {
    public static void main(String args[]){
        generateSum(11);
    }

    private static void generateSum(int num) {
        int arr[] = new int[num];
        for(int i=1; i<num; i++){
            arr[i] = i*i;
        }
        findSum(arr, num*num, 1, 0, "");
    }

    private static void findSum(int arr[], int desiredSqr, int pointer, int currentSum, String sumStr) {
        if(pointer == arr.length || currentSum >= desiredSqr){
            if(currentSum == desiredSqr){
                System.out.println(sumStr);
            }
            return;
        }
        for(int i=pointer; i<arr.length; i++){
            findSum(arr, desiredSqr, i+1, currentSum+arr[i], sumStr+arr[i]+" ");
        }
    }
}

如果有更好的方法可以解决这个问题，请告诉我（时间复杂度更低）

algorithm math recursion perfect-square

2 回答

  • 0

    Memoization肯定有助于减少此问题的时间复杂性：

    const memoize = callback => {
    const memo = new Map;

    return function () {
        const length = arguments.length, last = length - 1;

        let map = memo;

        for (let i = 0; i < last; i++) {
            const argument = arguments[i];
            if (!map.has(argument)) map.set(argument, new Map);
            map = map.get(argument);
        }

        const argument = arguments[last];
        if (!map.has(argument)) map.set(argument, callback.apply(null, arguments));
        return map.get(argument);
    };
};

const generateSums = memoize((sum, xs, index) => {
    if (sum === 0) return [[]];

    const result = [], length = xs.length;

    for (let i = index; i < length; i++) {
        const x = xs[i], diff = sum - x;
        let j = i + 1; while (xs[j] > diff) j++;
        const xss = generateSums(diff, xs, j);
        for (const xs of xss) result.push([x].concat(xs));
    }

    return result;
});

const solve = n => {
    const xs = [];
    for (let x = n - 1; x > 0; x--) xs.push(x * x);
    return generateSums(n * n, xs, 0);
};

console.time("Generate sums for 50²");
console.log(solve(50).length);
console.timeEnd("Generate sums for 50²");

    如果没有备忘，则需要更长的时间（注意，它可能会导致浏览器崩溃）：

    const generateSums = (sum, xs, index) => {
    if (sum === 0) return [[]];

    const result = [], length = xs.length;

    for (let i = index; i < length; i++) {
        const x = xs[i], diff = sum - x;
        let j = i + 1; while (xs[j] > diff) j++;
        const xss = generateSums(diff, xs, j);
        for (const xs of xss) result.push([x].concat(xs));
    }

    return result;
};

const solve = n => {
    const xs = [];
    for (let x = n - 1; x > 0; x--) xs.push(x * x);
    return generateSums(n * n, xs, 0);
};

console.time("Generate sums for 50²");
console.log(solve(50).length);
console.timeEnd("Generate sums for 50²");

    解决116平方仍然需要太多时间，但这是一个开始 .

    回复于
  • 0

    这可以通过 O(n*sqrt(n)) 将其转换为subset sum problem来完成 . 怎么样？

    考虑所有小于或等于N的完美正方形 . 这些元素的数量将是sqrt（N） .

    现在问题在于我们可以通过多少种方式选择这些元素的子集，使得sum = N .

    这是关于这个问题的discussion，你可以在这里找到similar questions .

    如果 Dynamic Programming 解决问题的复杂性将是O（n * sqrt（n））

    打印所有这些组合将具有复杂性，因为它们可能是2 ^（sqrt（n））子集 . 我们必须检查这个子集是否有sum = N.

    现在，如果我们遍历从1到2 ^（srtn（N）-1）的所有数字 . 这个数字可以表示所有子集，它将是这个数字的设置位的索引 . 遍历此数字将花费O（sqrt（N））时间 .

    所以整体复杂度为O（sqrt（N）* 2 ^（sqrt（N））） .

    回复于

相关问题