2014 2015 2016 2017 2018

Spartusis kėlimas laipsniu

Taškai: 12

Reikia apskaičiuoti 237, o skaičiuotuvo įjungimo mygtukas neveikia. Norėdamas padėti, draugas pateikė tokias užuominas:

  • Kai laipsnio rodiklis yra lyginis, apskaičiuok 2, pakeltą laipsniu, lygiu pusei esamo laipsnio rodiklio, tada padaugink rezultatą iš jo paties, pavyzdžiui: 25 × 25 = 210.
  • Kai laipsnio rodiklis yra nelyginis, apskaičiuok 2, pakeltą laipsniu, kuris yra vienetu mažesnis už esamą, t. y. lyginis, o tada padaugink rezultatą iš 2, pavyzdžiui: 210 × 2 = 211.

Kiek daugybos veiksmų remiantis pateiktomis užuominomis reikia atlikti norint apskaičiuoti 237?

Paaiškinimas

Užuominos leidžia sukurti efektyvų daugybos veiksmų algoritmą. Prireiks septynių daugybos veiksmų. Palyginkime, kiek daugybos veiksmų reikėtų atlikti, jei mes nesinaudotume šiuo algoritmu:

237 = 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

Skirtumas daug įspūdingesnis, kai skaičiuojami didesni skaičiai. Jei tam tikras skaičius E turi k dvejetainių skaitmenų, tai reikia tik k daugybos veiksmų norint apskaičiuoti 2E (ar bet kurį kitą skaičių, pakeltą laipsniu E). Kitaip tariant, daugybos veiksmų skaičius yra apytiksliai E logaritmas pagrindu 2. Informatikai sako: „Tai algoritmų sudėtingumo klasė O(log2(E))“.

Užuominos seka iš laipsnių savybių: bn × bm = bn + m. Jei laipsnio rodiklis yra natūralusis skaičius, procesas baigtinis, nes:

  • Kiekvieną žingsnį (pritaikius užuominą) laipsnio rodiklis tampa bent vienetu mažesnis.
  • Kai laipsnio rodiklis pasiekia 1, galima sustoti, daugiau skaičiuoti nereikia.
  • Laipsnio rodiklis visada yra arba lyginis, arba nelyginis, taigi visada galima toliau skaičiuoti remiantis užuominomis.

Šis metodas dar vadinamas „kėlimas kvadratu ir dauginimas“. Jis žinomas jau 2200 metų.

Metodas, pasiūlytas draugo, yra rekursyvus: laipsniai skaičiuojami nuo mažesnio, įrašant rezultatą į didesnį laipsnį.

Yra ir spartesnių laipsnio skaičiavimo būdų, bet norint jais pasinaudoti reikia įsiminti ankstesnius rezultatus arba naudoti preliminariai apskaičiuotus rezultatus.

Reikšminiai žodžiai: algoritmas, sudėtingumas, rekursija, algoritmo analizė.

Atsakymas

Teisingas atsakymas yra 7.

Remiantis pateiktomis užuominomis galima taip suskaičiuoti daugybos veiksmus:

237= 236 × 2    (laipsnio rodiklis nelyginis, tinka antra užuomina)

Dabar reikia apskaičiuoti 236, o tai jau paprasčiau:

236 = 218 × 218    (laipsnio rodiklis lyginis, tinka pirma užuomina)

Norint tai išspręsti, reikia apskaičiuoti 218.. Vėl remiantis užuominomis tolesni žingsniai tokie:

218 = 29 × 29
29 = 28 × 2
28 = 24 × 24
24 = 22 × 22
22 = 2 × 2  

Paskutinio žingsnio skaičiavimus jau labai paprasta atlikti. Planas gali būti toks: galima pradėti iš apačios, įrašant rezultatus į kito žingsnio veiksmus su vis didesniais laipsnio rodikliais.

Iš viso yra 7 daugybos veiksmai.

Interaktyvi užduotis