Wyznaczyć minimalny zbior [Pascal]

[MgielkaCuba]

Każdą liczbę naturalną można przedstawić jako sumę kwadratów pewnych liczb naturalnych. Napisz procedurę w Pascalu, która dla zadanej liczby N wyznaczy minimalny zbiór liczb \(\displaystyle{ {n_{1}, n_{2}, . . . , n_{k}}}\) takich, że \(\displaystyle{ n_{1}^{2} +n_{2}^{2}+....+n_{k}^{2}=N}\)
Zakładamy, że argumentem procedury jest N, a wynik ma być wypisany na ekran.
Czy ma ktoś jakikolwiek pomysł ?

[abc666]

Jeśli dobrze rozumiem twój problem to

[Xitami]

A jakie może być N?

Może się przydać, do sprawdzenia, bo przenoszenia z Javy raczej nie polecam

[MgielkaCuba]

Właśnie nie było w poleceniu jakie ma byc N. Przyjęłam, że całkowite:

tab: array[1..n] of integer;
var i,x,N:integer;
BEGIN
writeln('Podaj N');
readln(N);

for i:1 to n do
begin
x:=tab;
if N<= sqr(n) then
begin
write(n);
N:=N-sqr(n);
end;

end;


i nie działa (

[Xitami]

[...]
i nie działa (

Pewnie nawet się nie kompiluje.

Przyjęcie, że N jest całkowite wydaje się słuszne, gdyby N było rzeczywiste w chyba większości przypadków obliczenie rozwiązania byłoby bardzo trudne czy nawet nie możliwe.
Ale i dla liczb całkowitych sprawa prosta nie jest.
Każdą liczbę całkowitą można zapisać jako sumę najwyżej czterech dodatnich liczb całkowitych.
Wato pooglądać (Sloane' ). Szczególnie od miejsca sums of squares and sums of cubes , sequences related to (start): .

Pamiętaj, Pascal nie rozróżnia wielkości liter, "N" oaz "n" to jest to samo, więc test \(\displaystyle{ n\le n^2}\) jest raczej bez sensu.

Korzystasz z tablicy tab[], a powiedz Mgiełko co w niej siedzi. Nic tam nie wstawiłaś więc wyciągnąć możesz tylko kurz i stare pajęczyny!

Jeżeli chcesz napisać tab: array[1..n] of integer; to już kompilator musi wiedzieć jakie jest "n", czyli wcześniej musisz napisać const n=...; w miejscu wielokropka musisz wstawić liczbę, np. 69. Lecz dalej piszesz var n:integer, tu kompilator obrazi się na ciebie za to, że robisz mu wodę z mózgu bo przecież "n" już zostało zadeklarowane wcześniej (jako stała), a tak w Pascalu nie można. Któreś "n" trzeba nazwać inaczej.

Próbujesz tu dość zachłannego podejścia ale ono nie doprowadzi cię do poprawnego rozwiązania, no może poza przypadkami gdy N jest kwadratem albo sumą dwu.
Zapisałbym to tak

Kod: Zaznacz cały

procedure sos(n:integer);
var i:integer;
begin
	write(n, ' = ');
	i:=trunc(sqrt(n));
	while n>1 do begin
		write(i, '^2 + ');
		n:= n - sqr(i);
		i:= trunc(sqrt(n));
	end;
	if 0 = n then writeln(#8#8#32)
	else writeln('1^2');
end;

Dla n=23 otrzymamy 23 = 4^2 + 2^2 + 1^2 + 1^2 + 1^2 (suma 5 kwadratów), ale poprawnym rozwiązaniem jest 23 = 3^2 + 3^2 + 2^2 + 1^2 (suma 4 ).

Dla małych liczb całkiem dobrze zadziałają 4 zagnieżdżone pętle

Kod: Zaznacz cały

procedure rozklad(n:integer);
var m,a,b,c,d:integer;
begin
	m:=trunc(sqrt(n));
	for a:=0 to m do 
		for b:=0 to m do
			for c:=0 to m do
				for d:=1 to m do
					if a*a + b*b + c*c + d*d = n then begin
						if a>0 then write(a, '^2 + ');
						if b>0 then write(b, '^2 + ');
						if c>0 then write(c, '^2 + ');
						write(d, '^2 + ');
						exit
					end
end;

Zależnie od tego jaki to dialekt Pascala typ integer może mieć 16 albo 32 bity, a to ogranicza dopuszczalne wartości N;
Tak czy siak, algorytm kosztowny \(\displaystyle{ O(n^2)}\)

[argv]

Robiąc porządki na dysku znalazłem kod dla Tw. Lagrange - nie pamietam skąd go przepisałem, ale na pewno z googla kiedyś.

Kod: Zaznacz cały

void Lagrange(int n)
{
    int liczba = n;
    int suma = 0;
    int tab[4] = {0};
    int i = 0;
    
    do {
        int pomoc = (int) sqrt(liczba);
        tab[i] = pomoc;
        liczba = liczba - pomoc*pomoc;
        i++;
        suma = tab[0]*tab[0] + tab[1]*tab[1] + 
               tab[2]*tab[2] + tab[3]*tab[3];
        if(i > 3 && suma != n) {
            tab[0] = tab[0] - 1;
            liczba = n - tab[0]*tab[0];
            i = 1;
        }    
    } while(suma != n);

    for(int i = 0; i < 4; i++) {
        cout << tab[i] << " ";
    }
    cout << endl;
}

Pomijajac koncowe zera, mamy rozklad na 0,1,2,3 lub 4 liczby. Lagrange gwaranruje ze kazda da sie rozlozyc na 4 wiec kazda wieksza liczba liczb nie bedzie ta minimalna.
Dla duzo wiekszych liczb oczywscie mozna zwiekszyc zakres na long long i potegowac szybkim potegowaniem czy innym mnozeniem ale ze wstepnych testow i ta wersja niezle smiga