Vyhľadávanie (riešené príklady) - História úprav

Juraj: /* Analýza úlohy */

2020-03-09T19:33:02Z

Analýza úlohy

Juraj na 20:27, 16. august 2010

2010-08-16T20:27:37Z

Juraj na 08:43, 23. marec 2010

2010-03-23T08:43:49Z

Juraj na 21:04, 28. február 2010

2010-02-28T21:04:35Z

Juraj: /* Riešenie v jazyku C */

2010-02-26T20:54:35Z

Riešenie v jazyku C

Juraj na 20:51, 26. február 2010

2010-02-26T20:51:23Z

Juraj: /* Vzorový vstup */

2010-02-25T07:32:45Z

Vzorový vstup

Juraj na 21:25, 24. február 2010

2010-02-24T21:25:40Z

Juraj na 21:01, 24. február 2010

2010-02-24T21:01:42Z

Juraj na 20:11, 24. február 2010

2010-02-24T20:11:00Z

@@ Riadok 19: / Riadok 19: @@
 počet čísel, ktoré tipujúci uhádol.
 ==Analýza úlohy==
-Pre potreby vyh2ad8vanie použijeme rekurzívnu verziu binárneho vyhľadávania.
+Pre potreby vyhľadávania použijeme rekurzívnu verziu binárneho vyhľadávania.
 ==Riešenie v jazyku C==

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

@@ Riadok 4: / Riadok 4: @@
 {{Draft}}
 {{Skripta programovanie (zbierka úloh)}}
 =Vyhľadávanie v usporiadanom zozname=

← Staršia verzia		Verzia zo dňa a času 21:04, 28. február 2010
Riadok 269:		Riadok 269:
	====int hladajBinarne(SCas *pole,int dlzka, SCas x)====		====int hladajBinarne(SCas *pole,int dlzka, SCas x)====
	Algoritmus binárneho vyhľadávania je opísaný na stránke [[Algoritmy vyhľadávania]]. V tejto variante je namiesto poľa celých čísel pole štruktúr typu SCas. Teda budeme vyhľadávať prvok x (tiež musí byť rovnakého typu ako sú všetky prvky poľa ''pole'', teda SCas). Pre účely porovnávania hodnôt bola vytvorená funkcia ''porovnajCas''.		Algoritmus binárneho vyhľadávania je opísaný na stránke [[Algoritmy vyhľadávania]]. V tejto variante je namiesto poľa celých čísel pole štruktúr typu SCas. Teda budeme vyhľadávať prvok x (tiež musí byť rovnakého typu ako sú všetky prvky poľa ''pole'', teda SCas). Pre účely porovnávania hodnôt bola vytvorená funkcia ''porovnajCas''.
		+
		+	=Porovnanie efektívnosti vyhľadávacích algoritmov=
		+	==Úloha==
		+	Porovnajte efektívnosť iteračnej a rekurzívnej verzie binárneho vyhľadávania. Pole, v ktorom budete vyhľadávať použite z predchádzajúceho príkladu. Ako kritérium pri porovnávaní zvoľte čas vykonania algoritmu. Výsledky porovnania zdôvodnite.
		+	==Analýza úlohy==
		+	Algoritmy binárneho vyhľadávania sú v časti [[Algoritmy_vyhľadávania#Bin.C3.A1rne_vyh.C4.BEad.C3.A1vanie_-_zdrojov.C3.BD_k.C3.B3d_v_jazyku_C\|Algoritmy vyhľadávania]]. Podľa zadania budeme vyhľadávať v poli štruktúr typu SCas.
		+
		+	V programe potrebuje odmerať čas, za ktorý sa algoritmus skončí. Využijeme na to funkciu [http://www.cplusplus.com/reference/clibrary/ctime/clock/ ''clock()''] zadefinovanú v knižnici ''time.h'', ktorá nám vráti počet taktov procesora od štartu programu. Tento [daj prevedieme na sekundy tak, že túto hodnotu vydelíme hodnotou makra [http://www.cplusplus.com/reference/clibrary/ctime/CLOCKS_PER_SEC/ CLOCKS_PER_SEC].
		+
		+	Pri meraní trvania jedného vyhľadávania však zistíme, že daný čas sa nám nepodarí odmerať. Preto musíme vyhľadávanie opakovať n-krát a výsledný čas ešte podeliť hodnotou n.
		+
		+	==Riešenie v jazyku C==
		+	<source lang="c" line>
		+	#include <iostream.h>
		+	#include <stdio.h>
		+	#include <time.h>
		+	int main()
		+	{
		+	clock_t start, end;
		+	double elapsed;
		+	start = clock();
		+
		+	// beh algoritmu
		+
		+	end = clock();
		+	elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;
		+
		+	cout<<elapsed<<endl;
		+	}
		+	</source>

@@ Riadok 245: / Riadok 245: @@
      i++;
   }while(!in.eof());
   int mesiac;
   cin>>x.den>>mesiac>>x.rok>>x.hod>>x.min>>x.sek;

@@ Riadok 29: / Riadok 29: @@
 Prvou úlohou je spracovať vstupné údaje. Vstupné údaje sú uložené v súbore (predpokladajme súbor [http://httpd.apache.org/docs/2.0/logs.html access.log]). V súbore treba prečítať všetky riadky. Toto jednoducho implementujeme tak, že budeme zo súboru čítať až potiaľ, pokiaľ neprečítame všetky riadky.
 ===Návrh vhodnej dátovej štruktúry===
@@ Riadok 122: / Riadok 124: @@
 Na vstupe bude mesiac reprezentovaný ako číselný údaj (poradie mesiaca v roku) ale v súbore access.log je reprezentovaný ako 3-znaková skratka. Treba teda previesť číslo mesiaca na skratku. Toto docielime jednoduchým zápisom:
 <source lang="c" line>
-  SCas c; // c je struktura typu CSas
+  SCas c; // c je struktura typu SCas
   int mesiac=3; //nacitany mesiac zo suboru
@@ Riadok 128: / Riadok 130: @@
   char mesiace[12][4]={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"};
-  //do casti 'mesiac' struktury c (typu CScas) skopirujem retazec z pola mesiace na indexe mesiac-1
+  //do casti 'mesiac' struktury c (typu SCas) skopirujem retazec z pola mesiace na indexe mesiac-1
   strcpy(c.mesiac,mesiace[mesiac-1]);
 </source>

@@ Riadok 26: / Riadok 26: @@
 ==Analýza úlohy==
-Webový server ukladá záznamy do súboru postupne, pričom každý nový pridaný záznam má hodnotu času väčšiu ako záznam pred ním. Môžeme teda povedať že tento súbor je usporiadaný vzhľadom na čas udalosti. Keďže sú vstupné dáta usporiadané môžeme použiť algoritmus binárneho vyhľadávania (je možné použiť aj algoritmus lineárneho vyhľadávania, ale bolo by to neefektívne).
+Webový server ukladá záznamy do súboru postupne, pričom každý nový pridaný záznam má hodnotu času väčšiu ako záznam pred ním. Môžeme teda povedať že tento súbor je usporiadaný vzhľadom na čas udalosti. Keďže sú vstupné dáta usporiadané môžeme použiť algoritmus [[Algoritmy_vyh%C4%BEad%C3%A1vania#Bin.C3.A1rne_vyh.C4.BEad.C3.A1vanie|binárneho vyhľadávania]] (je možné použiť aj algoritmus lineárneho vyhľadávania, ale bolo by to neefektívne).
-Prvou úlohou je spracovať vstupné údaje. Vstupné údaje sú uložené v súbore (predpokladajme súbor access.log). V súbore treba prečítať všetky riadky. Toto jednoducho implementujeme tak, že budeme zo súboru čítať až potiaľ, pokiaľ neprečítame všetky riadky.
+Prvou úlohou je spracovať vstupné údaje. Vstupné údaje sú uložené v súbore (predpokladajme súbor [http://httpd.apache.org/docs/2.0/logs.html access.log]). V súbore treba prečítať všetky riadky. Toto jednoducho implementujeme tak, že budeme zo súboru čítať až potiaľ, pokiaľ neprečítame všetky riadky.
 ===Návrh vhodnej dátovej štruktúry===
@@ Riadok 39: / Riadok 39: @@
 };
 </source>
-Všetky položky sú celé čísla, okrem mesiaca, pretože ten je v logovacom súbore vyjadrený ako 3-znaková skratka mesiaca. Keďže prvá časť log záznamu má premenlivú dĺžku (rôzna IP adresa), nemôžeme si jednoducho vypočítať index prvého znaku v dátume. Vždy ale vieme, že dátum začína za znakom ‘[’. Stačí teda zisťiť, kde sa nachádza znak ‘[’a potom už môžeme jednoducho zistiť dátum a čas udalosti. Pre zistenie pozície znaku ‘[’ použijeme funkciu strchr. Funkcia vráti smerník na prvý výskyt znaku z reťazci.
+Všetky položky sú celé čísla, okrem mesiaca, pretože ten je v logovacom súbore vyjadrený ako 3-znaková skratka mesiaca. Keďže prvá časť log záznamu má premenlivú dĺžku (rôzna IP adresa), nemôžeme si jednoducho vypočítať index prvého znaku v dátume. Vždy ale vieme, že dátum začína za znakom ‘[’. Stačí teda zisťiť, kde sa nachádza znak ‘[’a potom už môžeme jednoducho zistiť dátum a čas udalosti. Pre zistenie pozície znaku ‘[’ použijeme funkciu [http://www.cplusplus.com/reference/clibrary/cstring/strchr/ strchr]. Funkcia vráti smerník na prvý výskyt znaku z reťazci.
 ===Získanie dátumu a času z riadku súboru===
 Zápisom

@@ Riadok 89: / Riadok 89: @@
    return cas;
+}
 </source>

@@ Riadok 30: / Riadok 30: @@
 Prvou úlohou je spracovať vstupné údaje. Vstupné údaje sú uložené v súbore (predpokladajme súbor access.log). V súbore treba prečítať všetky riadky. Toto jednoducho implementujeme tak, že budeme zo súboru čítať až potiaľ, pokiaľ neprečítame všetky riadky.
 Súbor budeme  čítať po riadkoch, ale pri ukladaní načítaných údajov sa budeme snažiť čo najviac minimalizovať pamäťové nároky. Podľa zadania úlohy si nemusíme pamätať stránku ktorá je v danom riadku, zaujíma nás len čas a dátum prístupu. Vytvorme si teda dátovú štruktúru reprezentujúce tieto údaje:
 <source lang="c">
@@ Riadok 39: / Riadok 40: @@
 </source>
 Všetky položky sú celé čísla, okrem mesiaca, pretože ten je v logovacom súbore vyjadrený ako 3-znaková skratka mesiaca. Keďže prvá časť log záznamu má premenlivú dĺžku (rôzna IP adresa), nemôžeme si jednoducho vypočítať index prvého znaku v dátume. Vždy ale vieme, že dátum začína za znakom ‘[’. Stačí teda zisťiť, kde sa nachádza znak ‘[’a potom už môžeme jednoducho zistiť dátum a čas udalosti. Pre zistenie pozície znaku ‘[’ použijeme funkciu strchr. Funkcia vráti smerník na prvý výskyt znaku z reťazci.
+===Získanie dátumu a času z riadku súboru===
 Zápisom
 <source lang="c">
@@ Riadok 61: / Riadok 62: @@
 *Rok, hodinu, minútu a sekundu získame podobne ako deň.
 V nasledujúcom zdrojovom kóde je vytvorená funkcia, ktorej parametrom je načítaný riadok z log súboru a funkcia vráti dátum a čas (štruktúra SCas) z tohoto záznamu:
-<source lang="c">
+<source lang="c" line>
 SCas dajCas(char *data)
+{