2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Laimės ratas

Taškai: 6

Bebriukas gali pasukti laimės ratą į dešinę arba į kairę. Kaskart pasukus ratą, rodyklė pajuda tik per vieną sektorių. Paveiksle parodytas pavyzdys.

Pradžia Pasukus vieną kartą į kairę

Kiek mažiausiai kartų reikia pasukti ratą, kad bebriukas laimėtų monetas? Pradedama nuo pradžios.

  1. 3
  2. 4
  3. 6
  4. 8
Paaiškinimas

Norint išspręsti šią problemą kompiuteriu, reikia išsiaiškinti, kaip laimės ratas atrodo: kiek yra sektorių, kokios jie spalvos ir kur yra monetos. Todėl reikia duomenų struktūros, vadinamos cikliniu dvikrypčiu sąrašu.

Viena iš pagrindinių šios duomenų struktūros operacijų yra sąrašo perrinkimas, pradedant nuo to paties taško. Dvikrypčio sąrašo perrinkimas gali vykti abiem kryptimis.

Raktiniai žodžiai: Ciklinis dvikryptis sąrašas, perrinkimas.

Atsakymas

Teisingas atsakymas yra 4.

Trumpiausias būdas laimėti monetas yra keturis kartus pasukti laimės ratą pagal laikrodžio rodyklę į dešinę. Sukant į kairę, reikėtų 8 kartų.