BEBRO konkurso užduotys 2017

 

Šakų rikiavimas

Taškai: 9

Kuo daugiau lapų ant šakos, tuo ji skanesnė. Deivis ketina surikiuoti šakas pagal skonį, bet tam reikės ir šalia esančio šakų laikiklio.

Padėk surikiuoti šakas taip, kad arčiausiai Deivio būtų skaniausia šaka.

Paaiškinimas

Metodas, kuriuo dvi medžio šakos palyginamos ir, padėjus ant laikiklio, sukeičiamos vietomis, taikomas ir informatikoje. Dažniausiai „laikikliai“ yra kintamieji. Siekiant pakeisti dviejų kintamųjų (pavyzdžiui, a ir b) reikšmes, reikia a reikšmę priskirti laikinam kintamajam t, ba ir tb. Dažniausia užrašoma taip:

t ← a

a ← b

b ← t

Jei atmintis yra ribota, naudojamas rikiavimo algoritmas, vadinamas atrankiniu rikiavimo algoritmu (angl. selection sort). Pirma, randamas mažiausias elementas ir atidedamas į šoną. Antra, randamas mažiausias elementas iš likusiųjų ir taip pat atidedamas į šoną. Tai kartojama, kol visi elementai surikiuojami (taip elementai rikiuojami nuo mažiausio iki didžiausio).

Raktiniai žodžiai:  rikiavimas, kintamųjų keitimas.

Atsakymas

Teisingas atsakymas yra:

Šio uždavinio sprendimo metodų yra daug. Paprasčiausias iš jų – dėti šaką ant šakų laikiklio ir taip sukeisti šakų poras.

Mažiausiai lapų turinčią šaką padėti ant laikiklio.

Šaką, turinčią daugiausia lapų, padėti į atsiradusią tuščią vietą.

Šaką nuo laikiklio perkelti į tuščią vietą.

Šiuo metodu keičiant šakų poras galima sukurti bet kokią seką, kuria surikiuojamos visos šakos.

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.