Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
- Hlavní strana
- » Algoritmy a programování
- » Potkávání vlaků v jedné stanici. (TOTO TÉMA JE VYŘEŠENÉ)
#1 09. 11. 2012 09:09 — Editoval eldest (09. 11. 2012 09:13)
Potkávání vlaků v jedné stanici.
Zdravím,
mám tu v C naprogramovat aplikaci, která bude počítat potkávání vlaků v jedné stanici. Vlak v této stanici nezastavuje, jen projíždí. U každého vlaku mám čas, kdy dorazí do stanice (tzn. že každý vlak je v tuto chvíli někde na cestě) a interval jeho návratu do stanice po projetí. Jde mi o to, jak určit, že se ty vlaky nikdy v této stanici nemohou potkat? Konkrétně pro tyto vstupy se nepotkají:
Počet vlaků: 3
Interval vlaku 1: 0:15
Vlak 1 přijede do stanice za: 0:02
Interval vlaku 2: 2:30
Vlak 2 přijede do stanice za: 0:37
Interval vlaku 3: 1:20
Vlak 3 přijede do stanice za: 1:07
Celý program mi funguje správně, ale nevím jak zjistit, že se vlaky nesetkají a čekat na přetečení datového typu je hodně dlouhé. Děkuji za všechnu pomoc.
Pokud jsem Vám pomohl vyřešit příklad, dejte prosím palec :)
Offline
- (téma jako vyřešené označil(a) eldest)
#3 09. 11. 2012 11:01 — Editoval Pavel Brožek (09. 11. 2012 11:04)
- Pavel Brožek
- Místo: Praha
- Příspěvky: 5694
- Škola: Informatika na MFF UK
- Pozice: Student
- Reputace: 194
Re: Potkávání vlaků v jedné stanici.
↑ Stýv:
Je to efektivní řešení? Rozhodně lepší než čekat do přetečení, ale pokud budou dva vlaky, jeden přijede v 0:00, druhý v 0:01 a budou mít intervaly třeba 1000000000:00 a 1000000000:02, tak se asi načekáme :-)
↑ eldest:
Jak jsi to řešil v případě, kdy se potkají? Třeba by to šlo trochu upravit a tuhle variantu, kdy se nepotkají, tam odchytit.
1. ročník FIT na ČVUT, hádám správně? :-)
Offline
#4 09. 11. 2012 11:31 — Editoval eldest (09. 11. 2012 11:40)
Re: Potkávání vlaků v jedné stanici.
↑ Pavel Brožek:
Ano hadate spravne. :) Zatim jsem vsechny progtesty vyresil bez dotazu ale nad timhle premyslim uz asi tyden a nejde to. Resil jsem to dost blbe, ale nic lepsiho me nenapadlo zatim. Mam while cyklus dokud se prommena delitelne nerovna N (pocet vlaku). v nem mam for cyklus, ktery projede vsechny vlaky v poli, tj. for(i = 0; i<n; i++) a v tomto cyklu mam podminku: if(!((max-prvni_prijezd[i])%intervaly[i])), kde max = maximalni hodnota z tech vlaku (interval + prvni prujezd - to je za jak dlouho vlak prijede poprve do stanice). Pokud tahle podminka je true, tak dam delitelne++; a vim, ze tyto dva se setkaji. A takhle dal. Pokud ta podminka je false, pak dam max += interval vlaku[pozice_max] a break;
Pokud jsem Vám pomohl vyřešit příklad, dejte prosím palec :)
Offline
#5 09. 11. 2012 12:02
- Pavel Brožek
- Místo: Praha
- Příspěvky: 5694
- Škola: Informatika na MFF UK
- Pozice: Student
- Reputace: 194
Re: Potkávání vlaků v jedné stanici.
↑ eldest:
Nechápu to řešení úplně do detailu, ale zhruba to je asi tak, že máš nějaký čas (asi to max), který postupně zvyšuješ a testuješ, jestli se v tom čase už všechny vlaky setkaly. Je to tak?
To není zrovna efektivní řešení. Zkusil ses nad tím zamyslet matematicky? Celý problém se dá přepsat do rovnic, jejichž řešení se budeš snažit najít.
Offline
#6 09. 11. 2012 12:07 — Editoval eldest (09. 11. 2012 12:07)
Re: Potkávání vlaků v jedné stanici.
↑ Pavel Brožek:
Presne tak to je. Max postupne zvysuji o interval vlaku s maximalnim (prvni_prujezd + interval). A testuji, jestli jednotlive intervaly deli toto max beze zbytku. Matematicky a do rovnic me vubec nenapada, jak by to mohlo jit. Tyhle typy prikladu mi v matematice nikdy nesly :D. Jakoze tohle a kdy se potkaji dva cyklisti, kteri vyrazi pozdeji z jednoho mista a tak.
Pokud jsem Vám pomohl vyřešit příklad, dejte prosím palec :)
Offline
#7 09. 11. 2012 12:15
- Pavel Brožek
- Místo: Praha
- Příspěvky: 5694
- Škola: Informatika na MFF UK
- Pozice: Student
- Reputace: 194
Re: Potkávání vlaků v jedné stanici.
↑ eldest:
Tak to asi nemá smysl, abych tě k tomu řešení naváděl, není to úplně triviální. Asi bude lepší, když to uděláš, jak píše Stýv, třeba to progtestem projde (ale asi nedostaneš bonus za rychlost :-) ). A po termínu odevzdání tu třeba napíšu to efektivnější řešení celého problému, když budeš chtít.
Offline
#8 09. 11. 2012 12:18 — Editoval eldest (09. 11. 2012 12:19)
Re: Potkávání vlaků v jedné stanici.
↑ Stýv: ↑ Pavel Brožek:
Dekuji obema za rady.
Pokud jsem Vám pomohl vyřešit příklad, dejte prosím palec :)
Offline
#9 09. 11. 2012 13:37 — Editoval mák (09. 11. 2012 18:21)
Re: Potkávání vlaků v jedné stanici.
Já bych to udělal stejně, jak napsal Stýv.
Stačí tedy testovat do doby než se situace opakuje. To znamená vypočítat nejmenší společný násobek jednotlivých intervalů projíždějících vlaků (funkce lcm). Ten vyjde 1200 minut. Po této době se situace opakuje a není potřeba dále testovat. Výpočet je rychlý a není třeba čekat na přetečení.
Pro vlak 1 jsou příjezdy (v minutách):
[2,17,32,47,62,77,92,107,122,137,152,167,182,197,212,227,242,257, ... a tak dále, ..., 1187]
Pro vlak 2 jsou příjezdy (v minutách):
[37,187,337,487,637,787,937,1087]
Pro vlak 3 jsou příjezdy (v minutách):
[67,147,227,307,387,467,547,627,707,787,867,947,1027,1107,1187]
Pokud se budou čísla shodovat (je-li člen jedné skupině obsažen i ve druhé), pak se vlaky potkají.
Offline
Stránky: 1
- Hlavní strana
- » Algoritmy a programování
- » Potkávání vlaků v jedné stanici. (TOTO TÉMA JE VYŘEŠENÉ)