2014 2015 2016 2017 2018

Rankų paspaudimai

Taškai: 6

Bebrai mėgsta žaisti airių žaidimą harlingą. Kai žaidimas baigiasi, kiekvienos komandos žaidėjai išsirikiuoja į eilę vienas paskui kitą ir eina kitos komandos link. Prasilenkdami jie spaudžia varžovui ranką ir sako „Dėkui už žaidimą!“.
Iš pradžių tik du pirmieji komandų žaidėjai spaudžia rankas. Paskui pirmasis žaidėjas spaudžia ranką antrajam žaidėjui (žr. paveikslą). Ir taip toliau, kol kiekvienas komandos žaidėjas paspaudžia ranką kiekvienam priešingos komandos žaidėjui.
 
Harlingo komandą sudaro 15 žaidėjų. Jei kiekvienas žaidėjas, spausdamas ranką kitam žaidėjui, užtrunka vieną sekundę, kiek sekundžių reikės, kol visi žaidėjai paspaus rankas?

Paaiškinimas

Šis uždavinys iliustruoja lygiagrečiųjų procesų paradigmą, vadinamą komandų grandinės apdorojimu. Komandų grandinės apdorojimas – efektyvus būdas greitai spręsti užduotį, panaudojus daug kompiuterių vienu metu. Tačiau tai gali užimti nemažai laiko. Panašiai šio uždavinio atveju: eilės gale esantys žaidėjai laukia, kada galės paspausti ranką.
Algoritmo vykdymo laiko analizavimas yra sudėtinga kompiuterių mokslo sritis, vadinama skaičiavimų sudėtingumo analize. Šiame uždavinyje žinoma, kad komandos dydis yra 15 žaidėjų, iš to galima išsamprotauti, kad rankų paspaudimo algoritmo „vykdymo laikas“ yra 29 sekundės. Tačiau skaičiavimų sudėtingumo analizėje reikia sužinoti vykdymo laiką nepriklausomai nuo komandos dydžio. Darome išvadą, kad rankų paspaudimo algoritmas užtruks 2N – 1 sekundes bet kuriai komandai, kurios žaidėjų skaičius yra N, kur N yra natūralusis skaičius, nelygus nuliui.

Reikšminiai žodžiai: komandų grandinės lygiagretusis apdorojimas, algoritmo sudėtingumas, skaičiavimų laikas.

Atsakymas

Teisingas atsakymas – 29.
Rankų paspaudimai užtruks tiek sekundžių, kiek yra žaidėjų vienoje eilėje (15), pridėjus žaidėjų skaičių kitoje eilėje (15) ir atėmus vieną. 
Tarkime, kad komandose yra tik po vieną žaidėją. Tada rankų paspaudimai užtruks vieną sekundę. Įsivaizduokime, kad komandose yra po du žaidėjus. Per pirmą sekundę tik pirmieji žaidėjai paspaus rankas, per antrą – kiekvienos komandos pirmasis žaidėjas paspaus ranką kitos komandos antrajam žaidėjai, o per trečiąją sekundę paspaus rankas kiekvienos komandos antrieji žaidėjai. Tai užtruks tris sekundes.
Kai kiekvienoje komandoje yra po 15 žaidėjų, rankų paspaudimai truks 15 + 15 – 1 = 29 sekundes.

Interaktyvi užduotis