U ,,Dabarlendu“ imamo čarobne tunele. Kada kolona dabrova uđe u crni tunel, iz njega izađu u obrnutom redosledu.
Kada kolona dabrova uđe u beli tunel, zamene se prvi i zadnji dabar u koloni.
Družina dabrova prolazi kroz tri tunela.
U kom redosledu će izaći iz njih?
1.
2.
3.
4.
Rešnje
Označite dabrove brojevima od 1 do 4, tako da najmanji bude 1, a najveći 4. Početni redosled (s leva na desno) je 4-3-2-1. Po izlasku iz prvog tunela redosled je 1-2-3-4. Drugi tunel zamenjuje mesto prvom i poslednjem, tako da dobijamo 4-2-3-1. Treći ponovo daje obrnuti redosled u odnosu na ulazak u njega, tako da dobijamo 1-3-2-4.
Zadatak može da se reši jos jednostavnije, uz sledeće razmišljanje. Crni tunel zamenjuje prvog sa poslednjim i drugog sa trećim. Beli tunel zamenjuje prvog sa poslednjim. Dakle, tako će prvi i poslednji zameniti mesta tri puta (po jednom u svakom tunelu), što je isto kao da su jednom zamenili mesta. Drugi i treći će se zameniti prilikom prolaska kroz oba crna tunela, to jest, zameniće se dva puta, što je isto kao da se nisu ni zamenili. Redosled tunela je crni-beli-crni, tako da će na kraju biti zamenjeni samo prvi i poslednji od četiri dabra.
Računarska pozadina
Tuneli predstavljaju komande za rad sa nizovima: crni obrću raspored, beli zamenjuju prvi i poslednji element. Grupa tunela predstavlja program. Zadatak pita-šta će uraditi “program” koji se sastoji od tri komande, gde na “ulazu” dobije određeni niz.
U zadatku se skriva metafora za prostore, koje računar ponekad koristi za čuvanje podataka, ili, recimo, poslove koji ga čekaju. Kada, na primer, prikazuje web stranu, koja sadrži više slika, može sastaviti spisak datoteka koje moraju biti preuzete sa servera da bi ste mogli da prikažete stranicu. „Zahtevi“ su postavljeni u red i sakupljaju od strane kompjutera jedna za drugom.
Osnovni tipovi prostora za skladištenje su ,,Prvi ušao, prvi izašao“ (first in, first out ili FIFO), pri čemu se zahtev koji se nalazi prvi u nizu realizuje poslednji, i ,,Poslednji ušao, prvi izašao“ (Last in, first out ili LIFO). Crni tunel predstavlja vrstu tipa LIFO, gde dabar, koji je poslednji ušao u tunel izlazi prvi iz njega. A beli tunel predstavlja vrstu tipa FIFO, gde dabar, koji je prvi ušao u tunel izlazi zadnji iz njega.
Detaljnije o Stek – Memoriji
Stek-memorija ili magacinska memorija jeste bezadresna registarska memorija sa sekvencijalnim pristupom. Kod ove memorije registri formiraju jednodimenzionalni niz u kome su susedni registri povezani kolima za paralelni prenos binarnih reči tako da se u njima upis i čitanje vrši po principu „poslednji upisan – prvi pročitan“ (eng. LIFO – Last In – First Out). Drugim rečima, ako je neki niz podataka upisan u stek, tada će pri čitanju redosled tih podataka biti obrnut od onog pri unosu (slika a).
Upis u stek i čitanje iz steka vrši se samo na jednom mestu, u gornjoj ćeliji koja se naziva vrh steka, tako da pri korišćenju steka nema potrebe zadavati adrese. Pri upisu podataka u stek sadržaji svih registra steka se pomeraju u susedne ćelije za jedno mesto „naniže“, a pri čitanju se pomeraju za jedno mesto „naviše“. Operacija upisa naziva se PUSH (eng. push – gurnuti, ubaciti), a operacija čitanja naziva se POP (eng. pop – izgurati, izbaciti).
Stek se koristi kod izračunavanja vrednosti aritmetičkih izraza, pri realizaciji programskih prevodilaca i u mnogim drugim slučajevima. U džepnim kalkulatorima koristi se unutražnji stek za izračunavanje vrednosti aritmetičkih izraza. Korišćenjem steka za pamćenje operanada i rezultata moguće je realizovati centralni procesor u kome instrukcije nemaju adresni deo ( to su tzv. bezadresne instrukcije).
Memorija tipa reda (Slika b) jeste registarska memorija slična steku, samo se podaci u nju upisuju i iz nje čitaju po principu „prvi upisan – prvi pročitan“ (eng. FIFO – First In – First Out). Koristi se pri opsluživanju po principu redova čekanja.
Osim realizacije steka pomoću registara, vrlo se često stek realizuje i u operativnoj memoriji. Radi toga se u procesor uvodi poseban adresni registar za vrh steka koji se naziva pokazivač steka. Ovako organizovan stek u operativnoj memoriji prikazan je na slici c. Kod ovakve realizacije steka pri upisu i čitanju steku se pristupa na osnovu sadržaja pokazivača steka, koji pokazuje na vrh steka proko njegove memorijske adrese. Pri tome nema fizičkog pomeranja sadržaja steka, već se samo podešava novi sadržaj pokazivača steka povećanjem ili smanjenjem adrese za 1.