Často k nám príjdu na návštevu priatelia. Vchod do domu sa nedá otvoriť z bytu, preto musíme ísť každého návštevníka vpustiť a potom zas vypustiť. To sa človek načaká na výťah...
Hádanka o výťahu
V Petržalke je veľa vysokých bytoviek. Predpokladajme, že žijete v osemposchodovom paneláku. Všetci susedia, okrem tých z prvého používajú výťah vždy keď niekam idú, aj keď sa vracajú domov. Susedia sú taký generický šedý priemer a všetci chodievajú von zhruba rovnako často. Výťah sa pohybuje rýchlosťou jedného poschodia za štyri sekundy. Obyvatelia ktorého poschodia sa v priemere načakajú najmenej? Koľko sekúnd?
Zaujímavé by mohlo byť vyriešiť úlohu aj vo všeobecnosti - pre n poschodí.
Samozrejme, ten úvodný problém s otváraním vstupnej brány pre návštevy sme vyriešili inak...
7 komentárov:
No, zapísal som dve A5ky, ale myslím, že som to vypočítal všeobecne.
Nechce sa mi to rozpisovať, ale pre 8 to vyšlo najvhodnejšie byť buď na 4. alebo 5. poschodí (pre obe doba čakania 80 sekúnd v priemere).
Všeobecne je najvýhodnejšie poschodie celočíselná hodnota nasledujúceho: (n+1)/2, kde n je počet poschodí. V prípade, že je (n+1) nepárny sa dá zaokrúhliť buď nahor alebo nadol, mali by vyjsť rovnaké doby čakanie, keďže ide o parabolu (funkcia čakania pri chcení ísť dole).
Ak by si chcel, môžem to spísať a poslať ti to mailom, ako som to počítal :)
Hodil som výpočet na Scribd: http://www.scribd.com/doc/39917349/Hadanka-o-v%C3%BD%C5%A5ahu
Cau metjush, tesim sa, ze ta uloha chytila. Pocuj, zda sa mi, ze si tam nastavil nejaky private setting, neda sa ten subor pozriet...
Ale zatial len taky common-sence check: 80 sekund je nejaky pridlhy cas, ved ked 4 sekundy trva 1 poschodie, tak cela cesta z prizemia na 8. poschodie trva 32 sekund...
No, kazdopadne som zvedavy na tie vypocty, urcite sa to bude dat doladit! :-)
Okej, dal som to už public, nejako mi ušlo, že je to ešte stále private.
A no... :D nejako mi nedošlo, že je to nejako veľa :P Ešte si to pozriem, či tam nenájdem nejakú chybičku.
asi to nie je sucastou tohto zadania, ale v reali ludia obcas cakaju aj kvoli tomu, ze niekto iny prave pouziva vytah, pripadne sa naakumulovali vacsie skupiny ludi a nezmestili sa vsetci naraz, tak musia chodit po davkach. Potom by v zadani bolo potrebne aj uviest, ako casto ludia chodia, ale tam zavisi aj od distribucie.
A este mi nie je celkom jasne, ci je tam aj prizemie a ci na nom niekto byva. Ked predpokladam ze vytahom sa dole chodi na prizemie a ak vytahom chodia aj ti, co byvaju na prvom, tak mi vyslo ze najvyhodnejsie je byvat na prvom nezavisle od poctu poschodi.
Ja som uvazoval nasledovne:
Na prizemi nikto nebyva, vytah je vzdy volny ked niekto niekam potrebuje ist a nahodne sa vyskytuje na poschodiach.
Dalsia mimoriadne dolezita uvaha je ze kedze ludia rovnako casto chodia von aj domov (kazdy kto vyjde von, musi sa aj vratit), tak s polovicnou pravdepodobnostou sa vytah nachadza na prizemi, teda 0. poschodi, a s polovicnou pravdepodobnostou na niektorom z poschodi 2 - 8. (Cize na kazdom s pravdepodobnostou 1/14 aby to dalo dokopy 1.)
Potom som si vyjadril tabulku casov, kolko musia cakat na vytah na kazdom z poschodi ak je vytah na lubovolnom inom poschodi a podla pravdepodobnosti som to zmiesal. Vyslo mi ze najmenej caka 2. poschodie a to v priemere 10 sekund, najviac 8. poschodie a to v priemere 22 sekund. Ostatne poschodia vysli v zlomkoch medzi tymito dvomi hodnotami vzostupne, cim vyssie poschodie, tym vyssi cas.
Dakujem za vsetky komentare. Jano H. to nakoniec zratal presne tak, ako som ulohu myslel :-)
Charon ME: hej, nemyslel som na vacsi pocet osob, a myslel som klasicku panelakovu situaciu - na prizemi sa nebyva a ludia z prveho chodievaju pesi (v niektorych druzstvach su dokonca vynati z platenia na vytah a vytahove dvere na 1. posch. su zamknute...).
Zverejnenie komentára