Izpitno vprašanje RAČ2PRA 3400

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka KatarinaRoškar.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Jure je tabeliral zvezno funkcijo na intervalu od 0 do 1000 s korakom 1 in njene vrednosti shranil v tabelo dolžine 1000. Če veš, da ima funkcija na tem intervalu natanko eno ničlo in sta predznaka funkcije v krajiščih intervala različna, poišči z uporabo bisekcije interval, na katerem funkcija doseže ničlo!

Odgovor

Po metodi bisekcije dani interval razdelimo na dva dela in rekurzivno izvajamo metodo le na tistem podintervalu, ki ima nasprotno predznačeni funkcijski vrednosti v krajiščih. Ker imamo tabelarično podano funkcijo, bo ustavitveni pogoj dolžina intervala 1, se pravi kos tabele z le dvema elementoma.

Pri pisanju metode v Javi si lahko pomagamo z že obstoječima metodama Math.signum(double x) ter Math.abs(double x).

Če bi Jure funkcijo tabeliral v točkah 0, 1, 2, ..., 1000, bi tabela imela 1001 podatkov. Ker pa je v tabeli le 1000 podatkov, lahko sklepamo tako:

  1. Jure je funkcijo tabeliral tako, da je v tabelo shranil povprečne vrednosti funkcije na podintervalih (ali pa vrednosti v središčih podintervalov): [0,1], [1,2], [2,3], ..., [998,999], [999,1000]. Namreč intervalov dolgih 1 na celotnem intervalu [0,1000], je ravno 1000. Spodaj je metoda, ki reši dani problem. Vrne interval, na katerem funkcija doseže ničlo (lahko je to tudi v krajišču vrnjenega intervala). Ob klicu je a = 0 in b = 999.
    1. public static int[] nicla(double[] f, int a, int b){
    2. int[] interval = new int[2];
    3. double signfa = Math.signum(f[a]);
    4. double signfb = Math.signum(f[b]);
    5. //problem majhen - interval dolg ena
    6. if(b == a+1){
    7. Boolean aa = false; //ali je a levo krajišče iskanega intervala
    8. if(Math.abs(f[a]) <= Math.abs(f[b])) aa = true; //če f[a] = -f[b], ali pa f[a] bliže 0
    9. interval[0] = (aa)? a: b;
    10. interval[1] = (aa)? b: b + 1;
    11. return interval;
    12. }
    13. //problem ni majhen:
    14. int s = (a+b)/2; //interval razdelimo na dva dela
    15. double signfs = Math.signum(f[s]);
    16. //če levo krajišče in sredina nasprotno predznačena:
    17. if(signfa == -signfs) return nicla(f,a,s); //iščemo naprej na levem delu prejšnjega intervala
    18. //če sredina in desno krajišče nasprotno predznačena:
    19. if(signfs == -signfb) return nicla(f,s,b); //iščemo naprej na desnem delu prejšnjega intervala
    20. //sicer zadeli ničlo:
    21. interval[0] = s; //v levem krajišču vrnjenega intervala je ničla
    22. interval[1] = s+1;
    23. return interval;
    24. }
  2. Morda pa se je Jure spomnil, da mu funkcijske vrednosti na koncu (ali pa začetku) intervala [0,1000] ni potrebno dati v tabelo, saj v algoritmu potrebujemo le predznak funkcije. Predznak funkcijske vrednosti na koncu intervala je določen s predznakom začetka intervala (in obratno): je nasprotno enak. Če poznamo enega, poznamo tudi drugega. Tako je lahko v tabelo dal le 1000 elementov. Vendar pa bi Jure na tak način le neznatno prihranil na času in prostoru v pomnilniku (poleg tega bi nam metodo po nepotrebnem zapletel), zato verjetno to ni bil razlog za en element manj.
  3. Lahko pa, da je Jure v resnici tabeliral vseh 1001 elementov, le preštel jih ni prav. Metoda bo tako malo drugačna. Spodaj je metoda. Vrne interval, na katerem funkcija doseže ničlo (lahko je to tudi v krajišču vrnjenega intervala). Ob klicu je a = 0 in b = 1000.
    1. public static int[] nicla(double[] f, int a, int b){
    2. int[] interval = new int[2];
    3. double signfa = Math.signum(f[a]);
    4. double signfb = Math.signum(f[b]);
    5. //problem majhen - interval dolg ena
    6. if(b == a+1){
    7. interval[0] = a;
    8. interval[1] = b;
    9. return interval;
    10. }
    11. //problem ni majhen:
    12. int s = (a+b)/2; //interval razdelimo na dva dela
    13. double signfs = Math.signum(f[s]);
    14. //če levo krajišče in sredina nasprotno predznačena:
    15. if(signfa == -signfs) return nicla(f,a,s); //iščemo naprej na levem delu prejšnjega intervala
    16. //če sredina in desno krajišče nasprotno predznačena:
    17. if(signfs == -signfb) return nicla(f,s,b); //iščemo naprej na desnem delu prejšnjega intervala
    18. //sicer zadeli ničlo:
    19. interval[0] = s; //v levem krajišču vrnjenega intervala je ničla
    20. interval[1] = s+1;
    21. return interval;
    22. }

Osebna orodja