#1 25. 01. 2008 20:52
- 14slunicko
- Zelenáč
- Příspěvky: 6
- Reputace: 0
algoritmus
Je dáno n reálných čísel (čísla jsou v dm) a úkolem je spočítat, kolik kruhů o průměru 6dm
je zapotřebí k překrytí všech čísel. :-(
Offline
#4 26. 01. 2008 11:37
Re: algoritmus
No s těmi body by to rozhodně zajímavé bylo. Pokud se jedná jen i čísla, tak to chápu tak, že jde o body na přímce. Pak by se kruh dal zjednodušit na úsečku…
Offline
#5 27. 01. 2008 14:02 — Editoval 14slunicko (27. 01. 2008 14:03)
- 14slunicko
- Zelenáč
- Příspěvky: 6
- Reputace: 0
Re: algoritmus
Všechny body leží na jedné přímce.Středy kruhů leží na stejné přímce jako body. Úkolem je určit, kolik nejméně kruhů potřebujeme k překrytí všech bodů.
Kruh jako úsečka...to mě nenapadlo. :-)
Offline
#8 27. 01. 2008 19:16
Re: algoritmus
Protože operujeme jen v jednom rozměru, tak je kruh v podstatě úsečka.
Můj návrh - začneme od nejmenšího (popř. největšího) bodü a umístíme první úsečku tak, aby tento bod byl krajní bod té úsečky a její druhý krajní bod byl blíže dalším bodům. Přeskočíme body, které jsme takto překryli a provedeme totéž s dalším nepřekrytým. Takto pokračujeme, dokud nejsou všechny body překryty.
Offline
#9 28. 01. 2008 19:14
- 14slunicko
- Zelenáč
- Příspěvky: 6
- Reputace: 0
Re: algoritmus
No to jo, ale jak to napsat nějak "odborně".Když třeba zadám body : 1.2 5.7 3.2 10.0 tak kolik potřebuji kruhů?(podle mě 2) Pro pár čísel je to jednoduché,ale co když jich bude 200?
Offline
#10 29. 01. 2008 00:48
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: algoritmus
Nejprve čísla seřadíme nějakým efektivním algoritmem (Quicksort, Heapsort, Mergesort,...).
Počítadlo kruhů k na začátku nastavíme na nulu, iterátor i na 1.
Pak budeme postupovat v krocích.
V každém kroku provedeme následující akce
* zvětšíme k o 1
* zjistíme hodnotu h i-tého prvku pole
* budeme zvětšovat iterátor i, dokud hodnota i-tého prvku nebude větší než h+6
* pokud při tomto zvětšování iterátoru dorzíme za konec pole, algoritmus ukončíme
Výsledný počet kruhů je uložen v k.
Složitost algoritmu:
časová: O(Nlog(N))
pamě?ová: O(N)
— řešení dodatečně publikováno 4. 2. —
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#11 30. 01. 2008 18:31
Re: algoritmus
hm, jak tak koukam, tak se lide nesnazi zneuzit, toto forum jenom k reseni matematickych olympiad, ale i korespondencnich seminaru (korespondencni seminar informatiky - http://ganymed.math.muni.cz/ks/ksi2007/ - 3. sada pr. 1) ... to jen tak pro zajimavost...
Offline
