Program na wypisywanie liczby jako dowolna suma kwadratów

Question

Utowrzyłem program na wyszukiwanie liczby w postaci sumy kwadratów dwóch liczb, jednak nie wiem jak zrobić by program zwracał każdą możliwą sumę kwadratów z każdej możliwej liczby, która podniesiona do kwadratu jest mniejsza od n i dodanie poprzednich kwadratów tak, żeby otrzymać n. Myślałem nad utworzeniem dynamicznej tablicy, w której będą wszystkie dzielniki danej liczby. Nie wiem jednak jak powielać te liczby, aby otrzymać każdą możliwą kombinację. Poniżej przestawiam program wyświetlający liczbę jako sumę kwadratów dwóch liczb mniejszych od n. 

Przykładowo dla 50 :

Zacząć od 50 x 1 do 2, 
Kończyć na 7do 2 + 1 do 2

#include <iostream>

using namespace std;
int rozklad(int n)
{
    int a=0, b=0;

    for(int i=n; i>0; i--)
    {

        for(int j=n; j>i; j--)
        {

         if((i*i)+(j*j)==n)
         {

         cout<<"liczba"<<n<<"to podniesione do kwadratu liczby"<<i<<","<<j<<endl;

         }



        }
        for (int k=n; k>0; k--)
        {
        if((i==k) && ((i*i)+(k*k)==n))
        cout <<"Istnieje takze rozklad, w ktorym"
                "liczby sa takie same"<<k<<","<<i<<endl;
        }
    }
    return n;
}
 int powtarzalnosc(int m)
 {

 }

int main()
{
    int liczba;
    cout << "Podaj liczbe"
            ", ktora ma zostac rozlozona" << endl;
    cin >>liczba;
    cout <<"Rozdklad wynosi"<<rozklad(liczba)<<endl;
    return 0;
}

 

Answer 1

Co do twojego programu:

- w 6 linijce masz zadeklarowane dwie nieużywane zmienne;

- te warunki w pętli które masz:

for(int i = n; i > 0; i--)
for(int j = n; j > i; j--)

i w ten sposób i lata od n do 1 oraz j on n do i, myślę ze taki zapis zmniejszył by troszkę ilość operacji:

for(int i = 0; i * i <= n; i++)
for(int j = i;  j * j < n; j++)

- w if'ie (w 18 linijce) możesz wstawić break, bo jak znajdzie jedną liczbę to po co ma szukać dalej,

- ten drugi for (ten z k) jest bez sensu - moje pętle to uwzględniają więc wystarczy jeden if jak badzo chcesz to mieć wyróżnione - najlepiej przed lub po pętlach, żeby oddzielnie sprawdziło bo to jest proste sprawdzenie które spełnia jedna liczba po co je robić tysiąc razy,

- nie rozumiem po co ta funkcja zwraca n, ale to już inna sprawa (według mnie taka funkcja miała by sens gdyby była void lub zwracała te liczby),

- generalnie mógłbyś to ładniej napisać - łatwiej by się czytało 

Co do twojego pytania to można to zrobić na kilka sposobów - ten trudny ale krótki to rekurencja - od liczby odejmujesz kwadrat i rozkładasz to co zostało i jak dojdziesz do zera to wypisujesz - możesz rozkminić, inny jest taki (będziesz potrzebował sprawdzać czy liczba jest kwardatem) - masz pętlę for(int i = 1; ...) i odejmujesz od liczby n i*i tak długo aż dojdziesz do n <=0  jeżeli n = 0 to wyświetlasz - jednocześnie sprawdzasz czy ta reszta jest kwadratem liczby całkowitej, jeżeli tak wyświetlasz i tak aż do momentu gdy i*i > n - algorytm jest

Comments

Tam gdzie jest ta pętla w pętli miałem wykluczyć i!=j żeby nie mieć dwa razy tego samego rozkładu tylko z innymi miejscami, to jednak uniemożliwiło mi wypisanie rozkładu w którym dwei takie same liczby podniesione do kwadratu dawały n.