Žaidėjų rikiavimas

Taškai: 6

Dvi komandos, kuriose yra po 15 žaidėjų, vilki marškinėlius su numeriais, kaip parodyta žemiau. Pirmosios komandos žaidėjai išsirikiavę pagal marškinėlių numerius, o antrosios – neišsirikiavę.
Pirmosios komandos žaidėjų numeriai: 1, 4, 5, 7, 9, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26.
 
Antrosios komandos žaidėjų numeriai: 8, 28, 12, 3, 24, 16, 23, 19, 14, 2, 11, 29, 27, 6, 13.
 
Kiek pirmosios komandos žaidėjų turi tokius pat numerius, kaip antrosios?
A.    1     B. 2     C. 3     D. 4

Paaiškinimas

Rikiuoto sąrašo elemento paieška daug spartesnė nei nerikiuoto. Šiuo uždaviniu parodoma, kad kur kas sparčiau randami antrosios komandos žaidėjų numeriai pirmojoje komandoje, o ne atvirkščiai. 
Jei tarsime, kad palyginti du numerius reikia 1 sekundės, tai šiam uždaviniui išspręsti reikės maždaug 45 sekundžių, kol bus ieškoma kiekvieno antrosios komandos žaidėjo numerio pirmojoje komandoje. O jei ieškotume kiekvieno pirmosios komandos žaidėjo numerio antrojoje komandoje, prireiktų maždaug 112 sekundžių.
Kuo sąrašai ilgesni, tuo labiau skiriasi sprendimo laikas. Jei turėtume tūkstančio numerių sąrašą, paieška rikiuotame sąraše būtų 50 kartų spartesnė nei nerikiuotame (nesvarbu, ar ieškotų kompiuteris, ar žmogus).
Paieška sąrašuose yra vienas pagrindinių informatikos uždavinių. Spręsdami šį uždavinį, tikriausiai rasite būdą, kaip ieškoti numerių pirmojoje komandoje. Galbūt tai bus vienas iš paieškos rikiuotame sąraše būdų, pavyzdžiui, blokinė paieška (angl. jump search) arba interpoliacinė paieška (angl. interpolate search).
Sąrašų rikiavimas yra būtinas informatiko įgūdis. Prieš paiešką patartina nerikiuotą sąrašą surikiuoti, ypač jei teks ieškoti daug kartų. Jei surikiuotume antrosios komandos žaidėjus pagal numerius, o ne pagal ūgį, gana greitai rastume tris vienodus žaidėjų numerius:
I komanda:
1, 4, 5, 7, 9, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26
II komanda:
2, 3, 6, 8, 11, 12, 13, 14, 16, 19, 23, 24, 27, 28, 29

Reikšminiai žodžiai: dvejetainė paieška, nuoseklioji paieška, rikiavimas.

Atsakymas

Teisingas atsakymas – 3.
Žaidėjų numeriai 14, 19 ir 23 yra abiejose komandose.
Todėl atsakymai A, B ir D neteisingi, o atsakymas C (sutampa trijų žaidėjų numeriai) yra teisingas.

 

 
Informacija atnaujinta 2016-10-18 10:55:36
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.