Vítej na našich stránkách! Jsme rádi, že tě úloha zaujala.
Pojďme se podívat, jak ji správně vyřešit. Zadání znělo následovně:
Tunely
V daleké zemi existují dva druhy tunelů. Když několik lidí vstoupí jeden po druhém do černého tunelu, vyjdou z něho v opačném pořadí.
Když ale vstoupí jeden po druhém do bílého tunelu, při vycházení si první z nich vymění místo s posledním.
Rodina Robotova prochází takto třemi tunely.
V jakém pořadí vyjdou z posledního tunelu?
Řešení
Všechny členy rodiny si očíslujeme (1-žlutá, 2-zelený, 3-červená, 4-modrý ).
Připomeňme, že černý tunel mění pořadí všech (1-2-3-4 → 4-3-2-1), bílý tunel prohodí prvního s posledním (1-2-3-4 → 4-2-3-1).
Můžeme pak snadno sledovat změny:
start: 4-3-2-1 → černý tunel: 1-2-3-4 → bílý tunel: 4-2-3-1 → černý tunel: 1-3-2-4
Správný obrázek pořadí, ve kterém vyjde rodina Robotova z tunelu je tedy tento:
Lze to ukázat i jednodušeji:
Bílý tunel promíchá velké a malé lidi, protože je zařazen jen jednou. Musí být na konci lidé promíchaní, nemohou být dva velcí vedle sebe.
Modrý člověk změní své pořadí pokaždé, když projde bílým nebo černým tunelem. Vchází jako poslední a protože tunely jsou tři, vycházet z posledního tunelu musí jako první.
Co má tato úloha společného s informatikou
Tato úloha s tunely nám ukazuje, jakým způsobem můžeme v informatice manipulovat s daty. Můžeme si představit, že osoby vstupující do tunelu jsou data, která ukládáme, a osoby vystupující z tunelu jako data, která čteme.
Například černý tunel funguje obdobně jako datová struktura zásobník. Data, která uložíme jako poslední, budou čtena jako první (jako když vkládáme jablka do punčochy nebo když vjíždějí jednotlivé vagóny vlaku na slepou kolej). Používá se také výraz LIFO, z anglického „Last In – First Out“.
Normální tunel, který v úloze nemáme, by fungoval na principu FIFO („First In - First Out“), tak funguje třeba fronta u lékaře nebo tisková fronta dokumentů k vytištění na síťové tiskárně (a tato datová struktura se také nazývá fronta).
Úloha Bobříka informatiky z roku: 2013 , kategorie: Benjamin
obtížnost: Těžká, kód úlohy: 2013-JP-02
autor: Yukio Idosaka
