Algoritmy vyhľadávania - História úprav

Juraj na 20:15, 16. august 2010

2010-08-16T20:15:44Z

Juraj na 12:50, 30. júl 2010

2010-07-30T12:50:05Z

Juraj na 12:49, 30. júl 2010

2010-07-30T12:49:33Z

Juraj: /* Binárne vyhľadávanie */

2010-04-13T16:12:54Z

Binárne vyhľadávanie

Jumanji na 20:39, 21. marec 2010

2010-03-21T20:39:54Z

Juraj na 12:10, 1. marec 2010

2010-03-01T12:10:39Z

Juraj na 20:39, 28. február 2010

2010-02-28T20:39:17Z

Juraj na 22:00, 31. január 2010

2010-01-31T22:00:47Z

Juraj na 19:59, 27. január 2010

2010-01-27T19:59:39Z

Juraj na 20:22, 26. január 2010

2010-01-26T20:22:46Z

← Staršia verzia		Verzia zo dňa a času 20:15, 16. august 2010
Riadok 1:		Riadok 1:
−	~~[[Kategória:Študijné materiály]]~~
−	~~[[Kategória:Programovanie]]~~
−	~~[[Kategória:Informatika]]~~
	{{Draft}}		{{Draft}}
	{{Skripta programovanie}}		{{Skripta programovanie}}

@@ Riadok 3: / Riadok 3: @@
 [[Kategória:Informatika]]
 {{Draft}}
 {{Skripta programovanie}}
 __TOC__
+{{Cvicenie|Vyhľadávanie (riešené príklady)}}
 '''Vyhľadávanie'''

@@ Riadok 458: / Riadok 458: @@
+}
 </source>
 =Odkazy=
@@ Riadok 468: / Riadok 466: @@
 * http://www.dcc.uchile.cl/~rbaeza/handbook/search_a.html
 * http://www.cs.auckland.ac.nz/software/AlgAnim/searching.html

@@ Riadok 155: / Riadok 155: @@
 |}
 * pole[5] != x (23 != 18 )
-** platí že x<23 (resp. x<pole[stred])
+** platí že x<23 (resp. <nowiki>x<pole[stred])</nowiki>
 ** budeme vyhľadávať vľavo (žltá časť)
 *** lavy zostane nezmeneny (0)
-*** pravy=stred - 1 (4)
+*** pravy=stred - 1 <nowiki>(4)</nowiki>
 <source lang="c">
   stred=(lavy+pravy)/2 = (0+4)/2=2
   stred=2
 </source>
-{| class="wikitable" border=1 cellpadding=5
 |+pole=
 |- style="color:green;background-color:#DADADA"
@@ Riadok 182: / Riadok 184: @@
 |style="background-color:gray"|43
 |}
 * pole[2] != x  (6 != 18 )
 ** platí že x>6 (resp. x>pole[stred])
@@ Riadok 208: / Riadok 211: @@
 Keďže samotné definícia binárneho vyhľadávania je rekurzívna, uvádzame aj rekurzívnu verziu funkcie.
-{| class=wikitable border=1 cellpadding=5
-|+ Binárne vyhľadávanie - jazyk C
+'''Iteračná verzia'''
 <source lang="c">
 int hladajBinarne(int *pole,int dlzka, int x)
@@ Riadok 237: / Riadok 235: @@
 </source>
+'''Rekurzívna verzia'''
 <source lang="c">
 int hladajBinarneR(int *pole,int lavy, int pravy, int x)
@@ Riadok 257: / Riadok 255: @@
 </source>
 ==Ternárne vyhľadávanie==

@@ Riadok 112: / Riadok 112: @@
 #*Ak je ''x'' väčšie ako stredný prvok, tak hľadaj v pravej časti poľa
 #**lavy=stred+1, pravy zostava nezmenený (choď na krok 1)
-#*Ak je ''x'' väčšie ako stredný prvok, tak hľadaj v ľavej časti poľa
+#*Ak je ''x'' menšie ako stredný prvok, tak hľadaj v ľavej časti poľa
 #**lavy=zostava nezmenený, pravy = stred-1 (choď na krok 1)

@@ Riadok 5: / Riadok 5: @@
 {{Skripta programovanie}}
 __TOC__
 '''Vyhľadávanie'''
@@ Riadok 11: / Riadok 13: @@
 #Vyhľadávanie v usporiadaných zoznamoch (resp. poliach)
 #Vyhľadávanie v rekurzívnych štruktúrach
 =Sekvenčné vyhľadávanie=

@@ Riadok 113: / Riadok 113: @@
 Ukážme si konkrétny príklad (šedé políčka predstavujú indexy poľa, biele sú prvky poľa):
+<source lang="c">
   x=18
   n=10
 {| class="wikitable" border=1 cellpadding=5
 |+pole=
@@ Riadok 124: / Riadok 125: @@
 |}
 Pre implementáciu algoritmu binárneho vyhľadávania si musíme vypočítať hodnoty ľavého a pravého indexu poľa, v ktorom hľadáme. Na začiatok je to jednoduché:
+<source lang="c">
   lavy=0
   pravy=n-1
+</source>
 *Porovnajme hľadaný prvok x=18 so stredným prvkom:
   stred=(lavy+pravy)/2
   stred=5
 {| class="wikitable" border=1 cellpadding=5
 |+pole=
@@ Riadok 155: / Riadok 158: @@
 *Porovnajme hľadaný prvok x=18 so stredným prvkom:
   stred=(lavy+pravy)/2 = (0+4)/2=2
   stred=2
 {| class="wikitable" border=1 cellpadding=5
 |+pole=
@@ Riadok 181: / Riadok 186: @@
 *Porovnajme hľadaný prvok x=18 so stredným prvkom:
   stred=(lavy+pravy)/2 = (3+4)/2=3
   stred=3
+</source>
 * pole[3] == x (18 = 18 )
 *Stredný prvok je zhodný s hľadaným
@@ Riadok 280: / Riadok 285: @@
 Na začiatku máme:
+<source lang="c">
   i=0
   j=10
+</source>
 Vypočítame m1, m2
   m1=( i*2 + j ) / 3 = (0+10)/3 = 3
   m2=( i + j*2 ) / 3 = (0+20)/3 = 6
+</source>
 {| class="wikitable" border=1 cellpadding=5
 |+pole=
@@ Riadok 307: / Riadok 313: @@
 Teraz hľadáme v tretej tretine poľa:
   i=m2+1=7
   j=10
+</source>
 Vypočítame m1, m2
   m1=( i*2 + j ) / 3 = (14+10)/3 =8
   m2=( i + j*2 ) / 3 = (7+20)/3 = 9
+</source>
 {| class="wikitable" border=1 cellpadding=5
@@ Riadok 407: / Riadok 415: @@
 Pseudokód algoritmu vyhľadávania:
-<pre>
+<source lang="text">
 hľadaj(strom, x)
 uzol <- vrhol stromu strom
@@ Riadok 418: / Riadok 426: @@
 ak je hodnota uzla > x tak
    hľadaj(uzol->pravy,x)
-</pre>
+</source>
 značenie uzol->lavy, resp. uzol->pravy má význam, že ďalej budeme pracovať len s ľavou, resp. pravou časťou binárneho stromu.