MPZI_predavanje_13

Petlje (3)

 Petlja while

U pravilu se petlja while upotrebljava onda kada broj prolazaka kroz petlju nije poznat unaprijed, nego ovisi o ispunjenju nekog uvjeta.

Opći je oblik petlje while:

     while uvjet :

         tijelo petlje

Koraci petlje će se ponavljati tako dugo dok je uvjet ispunjen, tako da u tijelu petlje treba omogućiti promjenu vrijednostî o kojima ovisi ispunjenje uvjeta.

Metoda polovljenja

Metoda polovljenja jedan je od postupaka nalaženja nul–točke realne funkcije $f$ realne varijable $x$ u zadanom intervalu $[x_{\min}, x_{\max}]$. 

Pretpostavljamo da je funkcija na intervalu neprekinuta i da njezine vrijednosti u točkama $x_{\min}$ i $x_{\max}$ imaju različite predznake.  Ako su $f(x_{\min})$ i $f(x_{\max})$ različitih predznaka, onda je  $f(x_{\min})\cdot f(x_{\max}) < 0$. 

U tom slučaju graf funkcije $f$ u intervalu $[x_{\min}, x_{\max}]$ barem jednom siječe os $x$.  Vrijednost $f(x_{\mathrm{mid}})$ u polovištu intervala  $x_{\mathrm{mid}} = \dfrac{x_{\min}\! + x_{\max}}{2}$  imat će predznak kao $f(x_{\min})$ ili kao $f(x_{\max})$.  Ako $f(x_{\mathrm{mid}})$ i $f(x_{\min})$ imaju različite predznake (to jest, ako je  $f(x_{\mathrm{min}})\cdot f(x_{\mathrm{mid}}) < 0$), onda je barem jedna nul–točka u intervalu $[x_{\min}, x_{\mathrm{mid}}]$.  I obratno, ako $f(x_{\mathrm{mid}})$ i $f(x_{\max})$ imaju različite predznake (što znači da $f(x_{\mathrm{mid}})$ i $f(x_{\min})$ imaju isti predznak), barem je jedna nul–točka u intervalu $[x_{\mathrm{mid}}, x_{\max}]$.  Na taj ćemo način u svakom koraku prepoloviti interval u kojemu tražimo nul–točku. 

Postupak prekidamo onda kada se duljina intervala smanji ispod unaprijed zadanoga praga $\tau_x$, odnosno, koraci se ponavljaju tako dugo dok je duljina intervala veća od praga:

       dok je  $x_{\max}\!-x_{\min} > \tau_x$  :

               $x_{\mathrm{mid}} = \dfrac{x_{\min}\! + x_{\max}}{2}$

               ako je  $f(x_{\mathrm{min}})\cdot f(x_{\mathrm{mid}}) < 0$ :

                       tražimo u intervalu $[x_{\min}, x_{\mathrm{mid}}]$, pa je $x_{\mathrm{mid}}$ „novi” $x_{\max}$

               inače :

                       tražimo u intervalu $[x_{\mathrm{mid}}, x_{\max}]$, pa je $x_{\mathrm{mid}}$ „novi” $x_{\min}$

       rezultat je polovište posljednjega intervala, kraćeg od praga

Budući da se u svakom koraku duljina intervala raspolavlja, jasno je da će se prije ili kasnije smanjiti ispod zadanoga praga.

Intermezzo o indeksiranju

Binarno pretraživanje

Binarno je pretraživanje algoritam koji omogućava razmjerno brzo nalaženje položaja odabrane vrijednosti u uređenom nizu, primjerice, u rastućemu ili u padajućem nizu brojeva ili u nizu riječi svrstanih po abecedi (kao u rječnicima)...  Funkcija koju ćemo napisati tražit će zadani broj $k$ u rastućem nizu brojeva s mogućim ponavljanjima, nazvanom $a$.

Zamisao algoritma temelji se na intuitivnom načinu traženja riječi u rječniku, a neobično nalikuje na metodu polovljenja.

Umjesto da se, kao u takozvanu linearnom pretraživanju, zadani broj uspoređuje s brojevima niza redom, od njegova početka prema kraju, u algoritmu binarnoga pretraživanja broj se prvo uspoređuje s brojem u sredini niza.  Ako je zadani broj jednak „srednjemu” broju, pretraživanje je završeno — položaj je traženoga broja nađen (pritom, ako se broj ponavlja, možemo samo reći da smo ga našli, ali ne i jesmo li našli prvu, drugu ... ili zadnju njegovu pojavu u nizu).  Ako je pak zadani broj manji od „srednjega”, može se nalaziti samo u prvoj polovini niza, a ako je veći, samo u drugoj polovini.  U drugomu koraku s polovinom niza u kojoj se broj može nalaziti postupamo kao u prethodnu koraku s cijelim nizom: zadani broj uspoređujemo s brojem u sredini te polovine. Time smo interval u kojem ćemo (možda) morati nastaviti pretraživanje smanjili na četvrtinu nizu.  U sljedećemu ćemo ga koraku smanjiti na osminu nizu, pa na šesnaestinu, i tako dalje. 

Na početku je interval u kojemu tražimo cijeli niz, određen indeksima $0$ i $n$, gdje je $n$ broj brojeva u nizu.  Neka je $s$ indeks broja u sredini niza ako je $n$ neparan ili posljednjega broja u prvoj polovini niza ako je $n$ paran. Ako je  $a_s > k$,  onda pretraživanje nastavljamo u intervalu određenu indeksima $0$ i $s$, a ako je  $a_s < k$,  tražit ćemo u intervalu određenu indeksima  $s\!+\!1$  i  $n$.  I tako dalje.

Pretraživanje završava kad pronađemo traženi broj ili kad interval pretraživanja ostane prazan.  U prvom ćemo slučaju „izaći” ne samo iz petlje, nego i iz funkcije, vraćajući indeks položaja u nizu na kojemu se nalazi traženi broj.  U drugomu slučaju traženi broj nije u nizu — mogućnost da broj pronađemo postoji tako dugo dok interval pretraživanja sadrži barem jedan broj.  Ako broj nije u nizu, vratit ćemo vrijednost koja nije indeks broja u nizu, $-\infty$.

Varijacija na temu

U programsku funkciju za binarno pretraživanje unijet ćemo dvije promjene:

1. Rezultat će biti indeks prvoga položaja u nizu na koji se traženi broj može umetnuti a da se uređaj niza ne naruši.  Ako se traženi broj nalazi u nizu, to je indeks jedne njegove pojave.  Ako pak broj nije u nizu, to je indeks prve pojave prvoga većeg broja: traženi se broj može umetnuti na to mjesto tako da se broj koji je bio na tom mjestu i svi brojevi iza njega „pomaknu” za jedno mjesto „udesno”.  Budući da vraćeni indeks sada označava položaj u nizu neovisno o tome je li broj pronađen ili ne, nakon poziva funkcije treba provjeriti nalazi li se traženi broj na tom mjestu.
2. Unutar petlje ne treba ispitati je li „srednji” broj jednak traženom.  Zašto?

Napomena na kraju:  for i while

Petlja for može se lako zamijeniti petljom while: