--> Archiwum Forum
Ziku90 [ Ziku ]
Informatyka
Witam,
mam problem z zadaniem z informatyki. Mianowicie muszę napisać we Free Pascalu dwa programy:
1. Dana jest liczba n należąca do naturalnych. Sprawdź, czy można ją przedstawić w postaci sumy kwadratów liczb naturalnych x i y, jeśli tak wypisz wszystkie pary takie, że x^2+y^2=n.
2. x^n sposobem:
jeśli n nieparzysta, to zmniejszamy o 1
jeśli parzysta, to x*x.
Za pierwszy w ogóle nie wiem, jak się zabrać. Jeśli chodzi o drugi, to algorytm był na klasówce, tylko była ona 1,5 miesiąca temu, więc już tego nie pamiętam. Podobno jest to jakieś "potęgowanie logarytmiczne". Na necie nic nie znalazłem.
Jeśli ktoś byłby w stanie pomóc...
DEXiu [ Generaďż˝ ]
Nie napisałeś jakiej złożoności toto ma być. Bo jeśli chodzi o pierwsze to chyba najprościej sprawdzać "na pałę". W pętli for x:=1 to trunc(sqrt(x))+1 patrzysz czy da się dobrać y z tego samego przedziału taki, aby w sumie kwadraty dawały n.
Co do drugiego to nie za bardzo rozumiem o co chodzi.
Ziku90 [ Ziku ]
Nie wiem jakiej złożoności to pierwsze ma być, jedyne co wiem to to, że ma działać...
A co do drugiego to chodzi o to, że jeśli wykładnik jest nieparzysty to zmniejszamy go o jeden, ale nie wiem co dalej...
Ziku90 [ Ziku ]
up
GBreal.II [ floydian ]
co do drugiego:
moze o to chodzi?
Ziku90 [ Ziku ]
Raczej o to, tylko jakby mi ktoś to jeszcze mógł przekształcić w miarę na kod do FPC, to byłbym bardzo wdzięczny...
DEXiu [ Generaďż˝ ]
Uproszczona wersja:
program power;
var
podstawa: Real;
wykladnik: Integer;
function potega(x:Real,n:Integer):Real;
begin
if n=0 then potega:=1
else
begin
if n mod 2 = 0 then potega:=potega(x,n/2)*potega(x,n/2);
if n mod 2 = 1 then potega:=x*potega(x,(n-1)/2)*potega(x,(n-1)/2);
end;
end;
begin
writeln('Podaj podstawe potegi');
readln(podstawa);
writeln('Podaj wykładnik potegi');
readln(wykladnik);
if wykladnik<0 then
begin
writeln('Zly wykladnik. Podaj liczbe nieujemna!')
readln(wykladnik);
end
else
writeln('Wynik to: ',potega(podstawa,wykladnik));
end.
Ziku90 [ Ziku ]
Dzięki DEXiu.
Tylko jeden mały problem:
function potega(x:Real,n:Integer):Real;
W tej linijce wywala błąd, co do przecinka pomiedzy Real a n...
A ja jeszcze wprowadzania funkcji nie miałem i nie za bardzo wiem co robić...
Ziku90 [ Ziku ]
little UP
DEXiu [ Generaďż˝ ]
Hm. Faktycznie coś się krzaczy. Ciekawe dlaczego...
GBreal.II [ floydian ]
Sprobuj zamiast przecinka wpisac srednik.
Ziku90 [ Ziku ]
Wtedy z kolei są błędy z typem zmiennych (nie moze dzielić Integer-a przez 2), a jak zmienię na inną to z kolei nie może zrobić mod (tylko dla Integer)...
GBreal.II [ floydian ]
Zobacz czy dziala (znaczy, czy bedzie dawac poprawne wyniki), gdy bedzie Integer, ale zamiast dzielenia "ukosnikiem" dasz polecenie "div" - jest to dzielenie calkowite).
[edit] - powinno zadzialac - mas zoba przypadki wyifowane, wiec raczej musi dzialac.
Nie wiem, czy DEXiu nie przepisal tego programu z C - bo tam dzielenie dostosowuje sie do typu zmiennej i argumenty dodawane do funkcji rozdziela sie przecinkami, w przeciwienstwie do Pascala
Ziku90 [ Ziku ]
Dzięki miszcze już wszystko działa :)