2014 2015 2016 2017 2018
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