BEBRO konkurso užduotys 2017

 

Šunų susikeitimas

Taškai: 6

Dviejų veislių šunys stovi eilėje:

Susikeitimas įvyksta, kai du greta stovintys šunys pasikeičia vietomis.

Po keleto susikeitimų trys didesni šunys atsistojo vienas greta kito.

Kiek mažiausiai susikeitimų turėjo įvykti?

A. 5 B. 6 C. 7 D. 8
Paaiškinimas

Duomenys yra saugomi kompiuterio atmintyje. Kompiuterio atmintis susideda iš vidinės, dažnai vadinamos RAM, ir išorinės, kuri, pavyzdžiui, gali būti standusis diskas ar atmintukas. Kompiuteriai gali labai greitai pasiekti duomenis vidinėje atmintyje, tačiau laikyti duomenis išorinėje atmintyje yra daug ekonomiškiau. Tai reiškia, kad šiuolaikiniai kompiuteriai dažniausiai turi daug daugiau išorinės atminties, bet kompiuterininkai bando rasti būdų kuo geriau išnaudoti vidinę atmintį.

Siekdami išspręsti šią problemą, kompiuterininkai domisi susikeitimo operacija. Jei įsivaizduosime, kad šunys – tai kompiuteryje laikoma informacija, tai susikeitimas pakeičia dviejų įrašų (duomenų dalių) laikymo vietą. Jei šie duomenys laikomi išorinėje atmintyje, siekdami kuo greičiau atlikti užduotį, turime suskaičiuoti mažiausią reikiamų susikeitimų skaičių.

Susikeitimas taip pat naudojamas kai kuriuose rikiavimo algoritmuose, siekiant surikiuoti duomenis didėjimo ar mažėjimo tvarka. Pavyzdžiui, rikiuojant duomenis burbulo metodu, kiekviename žingsnyje yra sukeičiami greta esantys nesurikiuoti duomenys.

Raktiniai žodžiai: susikeitimas, vidinė atmintis, išorinė atmintis.

Atsakymas

Teisingas atsakymas yra 6 (B).

Trys didesnieji šunys gali sustoti greta, kai:

  • pirmasis didesnis šuo du kartus susikeičia su šunyčiais iš dešinės ir
  • paskutinis didesnis šuo keturis kartus susikeičia su šunyčiais iš kairės.

Susikeičiant turi dalyvauti kiekvienas šunytis, nes jie visi stovi tarp didesnių šunų. Dviejų šunyčių susikeitimas nekeičia didesnio šuns stovėjimo vietos, tad nėra naudingas. Kiekvienas naudingas susikeitimas turi įvykti tarp šunyčio ir didesnio šuns. Kadangi yra šeši šunyčiai, vadinasi, siekiant didesnius šunis sustatyti greta, reikia mažiausiai šešių susikeitimų.

Atkreipkite dėmesį, kad, norint visus tris didesnius šunis perkelti į kairę arba į dešinę, reikia daugiau nei šešių susikeitimų.

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39
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.