C中两个方块的总和

Question

我已经设法得到两个正方形的总和,但它仍然无法工作,如果例如10:我需要9和1 ...我的想法是seacrch所有以前的方块,并找出有多少将加入输入, (max = 4)...但是当重复发生并且我需要添加3件事时我会陷入困境...对于4件事我只想添加一个else语句.关于如何改进我的算法的任何想法/建议？

Answer 1

假设您不应该使用复杂的算法，我建议您循环遍历所有选项，并检查平方和是否达到您需要的数字。在计算时，您可能还希望将数字保存在全局数组中，以简化getsquare

编辑：因为这是一个好问题，所以我写了一些代码。（警告：我没有检查）

int root[4];

int isqrt(int i) {return (int)floor(sqrt((double)i));}

// check if n is sum of s squares. assume s<=4
int canbesum(int s,int n) {
    if (s==0) return n==0;
    int i;
    for (i=isqrt(n);i;i--)
        if (canbesum(s-1,n-i*i)) {
            root[s-1]=i;
            return 1;
        }
    return 0;
}

int sumofsquares (int x) {
    int i;
    for (i=0;i<=4;i++) if (canbesum(i,x)) return i;
}