[C++] Rozkład liczby na sumy kwadratów

[strefa61]

Programuję w c++. Za pomocą funkcji (najlepiej bez rekurencji) oraz pętli (for, while) i if-ów, czyli podstaw podstaw mam wykonać zadanie (te ograniczenia wynikają z tego, że zadanie jest w książce prawie na samym początku, gdy jeszcze nawet tablice nie są przerobione): Funkcja ma rozłożyć dowolną liczbę naturalną n i wypisać wszystkie możliwe liczby naturalne, których kwadraty zesumowane dadzą liczbę n.
Dla sumy dwóch kwadratów sprawa jest prosta, bo wystarczą dwie pętle "for":

Kod: Zaznacz cały

void rozklad (long double n){
for (long double i = 0; i<=n; i++){
    for (long double p = i; p<=n; p++){
        int s = i*i + p*p;
        if (s==n){
            cout << i << " oraz " << p << '\n';
        }
    }
}

,
ale nie mam pojęcia jak zrobić, żeby te pętle wykonywały się na przykład n-razy dla [1^2] (bo sumy tego kwadratu zawsze dadzą n) oraz, żeby wykonywały się inną ilość razy dla innych szukanych kombinacji liczb.

[Takahashi]

Bez rekurencji rozwiązanie tego zadania będzie skrajnie nieczytelne. Z rekurencją jest bardzo prosto. W Haskellu to trzy linijki

Kod: Zaznacz cały

import Data.List
squares n = takeWhile (<= n) $ map (^2) [1..]
sums 1 = [[1]]
sums n = nub $ map sort [x:xs | x <- squares n, xs <- sums (n-x)]

-- sums 10 zwraca wynik:
-- [[1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,4],[1,1,4,4],[1,9]]