2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Biblioteka

Taškai: 6

Kai knyga yra paskolinama skaitytojui, ji paimama iš lentynos, paliekant tuščią tarpą, kurio plotis sutampa su paimtos knygos storiu.

Kiekvieną dieną grąžintos knygos yra sukraunamos ant stalo. Prieš uždarant biblioteką, Daumilas ir Gabrielė knygas nuo stalo sudeda į lentyną, imdami po vieną nuo krūvos viršaus. Tai jie daro tol, kol sudeda visas knygas arba kuriai nors knygai neranda tinkamos vietos. Tačiau dėdami knygas jie laikosi skirtingų taisyklių:

• Daumilas peržiūri lentyną iš kairės į dešinę ir knygą įdeda į pirmąjį tinkamo pločio tuščią tarpą, prispausdamas prie kairio krašto.

• Gabrielė randa didžiausią tinkamą laisvą tarpą ir ten įdeda knygą, prispausdama prie kairio krašto. Jei tokių tarpų yra keli, pasirenkamas pirmas nuo kairės.

Pasibaigus dienai, lentynoje laisvos vietos yra žymimos centimetrais.

Grąžinamos knygos ant stalo yra trijų dydžių, kaip nurodyta lentelėje

Storis (cm)

1

2

3

Knyga

Išnagrinėkite toliau pateiktas grąžintų knygų krūvas. Knygos po vieną imamos nuo krūvos viršaus, pasukamos vertikaliai, o tada dedamos atgal į lentyną.

Kuriuo iš žemiau pateiktų knygų krūvos variantų Daumilas gali sudėti daugiau knygų negu Gabrielė?

A B C D
Paaiškinimas

Šio uždavinio analogija informatikoje yra atminties paskirstymas, kai į kompiuterio atmintį įkeliamos kelios programos, reikalaujančios skirtingo atminties kiekio. Baigta vykdyti programa iš atminties pašalinama tiksliai taip, kaip knygos pašalinamos iš lentynos. Pradedamą vykdyti naują programą kompiuterio operacinė sistema įkelia į vieną laisvos atminties zoną. Daumilo ir Gabrielės taikomi metodai atitinka dvi atminties valdymo strategijas, vadinamas „pirmas tinkamas“ ir „blogiausiai tinkamas“. Svarbu, kad vykdant atminties paskirstymą, „knygų krūva“ nėra iš anksto žinoma, todėl ne visada lengva nuspręsti, kokia strategija veikia geriau.

Raktiniai žodžiai: atminties paskirstymas, operacinė sistema.

Atsakymas

Teisingas atsakymas yra D.

Pagal Daumilo taisykles galima sudėti visas 5 knygas, o pagal Gabrielės – tik 4. Šioje lentelėje parodyta, kaip Daumilas ir Gabrielė išdėsto knygas pagal A, B, C ir D variantus, o knygų išdėstymo tvarka nurodoma numeriais nuo knygos viršaus:

 

Daumilas

Gabrielė

A

B

C

D