Šta je novo?

rekurzivna funkcija puca

jddipqd

Čuven
Učlanjen(a)
17.10.2000
Poruke
2,561
Poena
725
U stvari me puca uvek, već samo za n>6 gde izbacuje 'Invalid Floating Point Operation'. Za n<6 radi savršeno normalno.
Nije mi jasno u čemu je problem...
Nije valjda da rekurzija potroši suviše resursa?

[code:1]
function delta_y(n, i: integer; var pocetni: skup_arg_ptr): extended;
var pomocna: extended;
begin
if n > 1 then
pomocna := delta_y(n-1, i+1, pocetni) - delta_y(n-1, i, pocetni)
else
pomocna := f_x(citaj(i+1, pocetni)) - f_x(citaj(i, pocetni));
delta_y := pomocna;
end;
[/code:1]

Evo su relevantni definisani tipovi podataka i procedure:
[code:1]
type skup_arg_ptr = ^skup_arg;
skup_arg = record
x: extended;
sled: skup_arg_ptr;
end;

function f_x(x: extended): extended;
begin
f_x := x*ln(x);
end;

function citaj(index: integer; var pocetni: skup_arg_ptr): extended;
var rezultat: extended;
lista: skup_arg_ptr;
begin
lista := pocetni;
while (index+1) > 0 do
begin
rezultat := lista^.x;
lista := lista^.sled;
dec(index);
end;
citaj := rezultat;
end;
[/code:1]

Ovo treba da predam u nedelju ujutro, tako da bi mi dobro došla neka pomoć.
 
Meni na prvi pogled ne izgleda da je potencijalni problem u funkciji delta_y, nego u funkciji citaj. Naime, posto reaguje greskom na n-ti element, bilo bi dobro da proveravas kakav je taj sledeci element koji si uzeo. Poslednji node u listi treba da ima vrednost za skup_arg_ptr^.sled = nil, pa bi bilo dobro da liniju lista:=lista^.sled uvezes u proveru da nisi dobio nil tj, da ne ides i dalje nakon poslednjeg elementa, posto ga snabdevas indexom kao "pripremljenim" brojem. Mozda cak i u uslovu da probas sa necim kao "While (index+1>0) and (lista<>nil) do" ili da stavis jedan if kod citanja sledeceg elementa, pa ako je nil, vratis kontrolnu vrednost i lupis break da izadjes iz petlje (posto radis "citaj, pa pokazi na sledeceg" - mogao si to i da zamenis). Ukoliko ne proveravas za nil (ili poslednji element ne sadrzi ^.sled=nil) 'ladno ces dobiti neko djubre sa sledece memorijske lokacije i proslediti ga svojim funkcijama.

Drugo, u delta_y radis rekurziju sa oduzimanjem vrednosti, a nisi naveo da li su brojevi u listi sortirani (od najveceg ka najmanjem ili slicno) ili random. Moze li se desiti da za rezultat "pomocna" dobijes negativnu vrednost ?

Trece, funkcija Citaj ne menja parametar "pocetni" (verovatno element-glava liste). Cim ga ne menja, nema nikakve potrebe da ga definises kao var parametar. Bas naprotiv, stavi const pocetni ... da ga funkcija moze samo koristiti, ali ne i slucajno promeniti (osnovna zastita globalnih varijabli).


Generalno, uzmes debugger i propustis ga kroz 5-ti (regularni) loop, pa vidis sta se desava u tom sestom.
Ako nemas debugger (a trebao bi da ga imas), onda uzmi "Srpski debugger", tj papir i olovku, pa simuliraj vrednosti crno na belo.
 
Zaboravih ...

Mozes da stavis i celo racunanje u funkciji delta_y u try...except blok, pa kada naleti taj exception "invalid floating point...", da prikazes na ekranu tekuce vrednosti. Nisam siguran, ali mislim da za ovu vrstu greske odgovara EInvalidOp exception. Dakle, nesto poput:

[code:1]
begin
result := 0;
try
if n > 1 then
result := delta_y(n-1, i+1, pocetni) - delta_y(n-1, i, pocetni)
else
result := f_x(citaj(i+1, pocetni)) - f_x(citaj(i, pocetni));
except
on EInvalidOp do
begin
Writeln('Vrednost n : '+intToStr(n));
Writeln('Vrednost i : '+intToStr(i));
...
end;
end;
[/code:1]

Mozes i drugacije da uradis; ove floatingpoint exception klase poticu od EMathError, pa mozes da hvatas taj izuzetak (mrzim ove glupe prevode) i pomocu RTTI-ja vidis koja je od njih - na isti princip kako TObject moze biti parametar funkcije koji prihvata pointer na objekat bilo koje klase. Dakle, blok bi izgleda nesto poput (pisem iz glave):

[code:1]
try
...
except
on E:EMathError do
begin
writeln('podignut exception : '+E.ClassName);

end;
end;
...
[/code:1]

Tako hvatas sve excpetione koji poticu od ovog osnovnog matematickog izuzetka za fp:

- EInvalidArgument
- EInvalidOp
- EOverflow
- EUnderflow
- EZeroDivide

I lepo ti se ispise koji od njih je podignut, pa i ti onda mozes da suzis uzrok problema.

Ono za "srpski debugger" vazi samo kao krajnje resenje, kada nista drugo ne upali i uhvatis se za glavu.
 
silverglider je napisao(la):
Drugo, u delta_y radis rekurziju sa oduzimanjem vrednosti, a nisi naveo da li su brojevi u listi sortirani (od najveceg ka najmanjem ili slicno) ili random. Moze li se desiti da za rezultat "pomocna" dobijes negativnu vrednost ?

Generalno, uzmes debugger i propustis ga kroz 5-ti (regularni) loop, pa vidis sta se desava u tom sestom.
Ako nemas debugger (a trebao bi da ga imas), onda uzmi "Srpski debugger", tj papir i olovku, pa simuliraj vrednosti crno na belo.
U vezi prvog, proverio sam i citaj nigde ne pokušava da nađe nepostojeći element.
Što se tiče drugog, brojevi u listi su strogo rastući, znači nema ni jednakih...
U vezi onoga što si rekao u drugom postu... Nisam napomenuo, ali nije u pitanju delphi nego borland pascal 7.0 (real mode) tako da mi priča sa try...except ne znači mnogo. :(
Debugger koristim samo integrisani, i to jedino Watch opciju.
 
Tol'ko filozofiranja ni oko čega .... idi lepo u Options -> Compiler pa pod Numeric Processing štrikliraj polje 8087/80287. To bi trebalo da reši stvar. :)
 
magick je napisao(la):
Tol'ko filozofiranja ni oko čega .... idi lepo u Options -> Compiler pa pod Numeric Processing štrikliraj polje 8087/80287. To bi trebalo da reši stvar. :)
Na početku programa već stoji jedno {$N+} :(
 
Ne, da je opcija za FPU u pitanju, zapeo bi vec na prvom racunanju, a ne tek na sestom ili sedmom.

Probaj onda sledece:

1. proveri kolika je vrednost varijable kad pukne, cisto da znas da ne prelazi max vrednost definisanog tipa. Mada, radi se o extended, tu bi trebalo da stane sve i svasta. No ipak ...

2. idi u project options i pogledaj gde su opcije za velicinu stack buffera, te ga digni na vecu vrednost. Ukoliko ima fin broj rekurzivnih poziva, zbog bacanja parametara i medjurezultata na stek moze da dodje do stack overflowa.
Ukoliko pozivas IDE sa BP (ili TPX u TurboPascalu), stavi stek na minimum 1MB. Ukoliko radis sa Turbo, vidi do koliko ide.

3. try...except konstrukcija je feature Object Pascala, a ne Delphija, kao takvog. Mislim da bi trebao da bi i u Borland Pascalu 7 trebalo da radi (i u real i u protected modu). Za Turbo seriju ispod v6 ne verujem da radi.
 
silverglider je napisao(la):
2. idi u project options i pogledaj gde su opcije za velicinu stack buffera, te ga digni na vecu vrednost. Ukoliko ima fin broj rekurzivnih poziva, zbog bacanja parametara i medjurezultata na stek moze da dodje do stack overflowa.
Ukoliko pozivas IDE sa BP (ili TPX u TurboPascalu), stavi stek na minimum 1MB. Ukoliko radis sa Turbo, vidi do koliko ide.
Maksimalno može za stek 65520 bajtova za real a 65536 za protected mode :( Default je 16K ali ni 64K nije dosta ni da bi zavrsio sedmu iteraciju...

silverglider je napisao(la):
3. try...except konstrukcija je feature Object Pascala, a ne Delphija, kao takvog. Mislim da bi trebao da bi i u Borland Pascalu 7 trebalo da radi (i u real i u protected modu). Za Turbo seriju ispod v6 ne verujem da radi.
Kompajler je ne prepoznaje...

Ali više nema veze... rešio sam problem :) Iskompajlirao sam program kao delphi konzolnu aplikaciju i sve radi savršeno.
 
Probaj da rastavis dvostruki poziv rekurzivne funkcije.
Umesto delta_y=delta_y(...)+delta_y(...) stavi
temp1:=delta_y(...);
temp2:=delta_y(...);
delta_y:=temp1+temp2;

Izgleda ludo ali radi u TP7.

Inace objasnjenje zasto mora ovako pogledaj u primeru sa
Fibonacijevim brojevima. Dobijas ga uz TP7 full install.

:)
 
Nazad
Vrh Dno