Сумма двух квадратов в C

Question

Мне удалось получить сумму из двух квадратов, но она все еще не работает, если, например, 10: мне нужно 9 и 1 ... Моя идея - скрыть все предыдущие квадраты и узнать сколько будет добавлено до ввода, (max = 4) ... но im застревает, когда возникают дубликаты, и когда мне нужно добавить 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; 
}