Algoritmy a datové struktury

Pokračování přednášky TIN060 Algoritmy a datové struktury I
stdhoom

Algoritmy a datové struktury

Příspěvek od stdhoom »

Ahoj,

prosim o pomoc s príkladem:
Pracujete s databazi, ktera obsahuje informace o studentech a studijnich oborech. Kazdy student studuje prave jeden studijni obor. Kazdy studijni obor muze studovat vice studentu. Rekneme, ze dva studenti jsou spoluzaci, prave kdyz studuji stejny studujni obor.
Vasim ukolem je zjistit, zda v souboru N studentu existuje skupina alespon N/2 spoluzaku, tj. studentu studujicich stejny studijni obor. Problem je, ze jediny databazovy dotaz, ktery k tomu muzete vyuzit, je dotaz na dva studenty; jako odpoved obdrzite pouze informaci zda jsou anebo nejsou spoluzaci.
Navrhnete algoritmus, ktery nalezne pozadovanou odpoved a pritom pocet provedenych dotazu bude O(N log N). Pri navrhu algoritmu pouzijte techniku rozdel a panuj.
Nejsem schopen dosahnout slozitost nlogn
icerna
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 21. 4. 2015 22:00
Typ studia: Nestuduji MFF UK

Re: Algoritmy a datové struktury

Příspěvek od icerna »

"Problémy můžete řešit buď samostatně anebo ve dvojicích (pak odevzdáte jenom jedno řešení a body získají oba spoluřešitelé)."
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“