Matematické Fórum

houfn · 17. 10. 2014 19:42

Zdravím,

mám úlohu:

Máme kružnici o obvodu M s N body umístěnými na kružnici.

Úkol: jak lze nejefektivněji spočítat počet všech možných trojúhelníků, které lze z těchto bodů udělat tak, aby trojúhelník obsahoval střed kružnice.

Postup by měl být nejhůře O(n*logn) složitý. Zatím sem nevymyslel, méně než O(n*n).

Díky mnohokrát za pomoc. Pro ilustraci přikládám obrázek.

//forum.matweb.cz/upload3/img/2014-10/67700_10689830_4702347692755_4269484197861187937_n%2B%25281%2529.jpg

jelena · 18. 10. 2014 00:12

Zdravím,

pokud jsem správně pochopila, počet bodů (3 a více) a obvod může být zadán libovolně a není žádná další podmínka v umístění bodů. Cílem je vytvořit algoritmus, podle kterého budeš sestrojovat jen ostroúhlé trojúhelníky + pravoúhlé - střed kružnice je buď uvnitř trojúhelníku nebo na přeponě. Tupoúhlé vyřadíš. Vycházel jsi ze stejného předpokladu?

Jakou techniku jsi tedy zvolil pro třídění bodů? A tradiční dotaz - odkud je úloha? Děkuji.

houfn · 18. 10. 2014 18:50 — Editoval houfn (18. 10. 2014 18:54)

↑ jelena:

Ahoj,

1) Úloha pochází ze školy, jako DÚ.
2) zadání je pochopeno naprosto správně a ano, z tohoto předpokladu jsem vycházel.

Můj postup je následující:

A) Vím, že spojuji některé 3 body na kružnici (a,b,c).
B) Tudíž vím, že jeden z bodů (a) musí ležet na kružnici v intervalu (0;M/2>
C) Druhý bod (b) tudíž musí ležet v intervalu (a;a+M/2>
D) A třetí bod (c) je tudíž v intervalu <a+M/2;b+M/2>
E) Počet bodů v |<a+M/2;b+M/2>| je vždy výsledek pro dané a,b,c.

Tento můj postup funguje 100% správně. Avšak jeho složitost je příliš vysoká, pro velká data trvá výpočet dlouho a k požadovaným O(n*logn) to má daleko. Neb cyklicky v programu procházím vždy všechny možné body z výše uvedených intervalů.

Díky.

jelena · 18. 10. 2014 21:36

↑ houfn:

děkuji, snad se chytnu :-) Viděla bych tak - první bod (a) volím libovolně, tedy mám N možností, druhý bod B bych také mohla volit libovolně ze zbývajících (N-1) možností, ale zde může omezovat směr obcházení trojúhelníku (tedy v tomto kroku zvolím B nebo C (nebo jinak musím ošetřit, že trojúhelníky ABC a ACB jsou jen jeden)).

Teď z těchto zvolených bodů mám tětivu nad určitým středovým úhlem (a tento středový úhel musí být do 180 stupňů včetně), potom jemu odpovídající (poloviční) obvodový musí poslat poslední bod do "větší nebo stejné poloroviny", která mi vznikla dělením kružnice první tětivou. Toto by se dalo ošetřit ve Tvém algoritmu?

Ještě pro upřesnění - nepracujeme se souřadnici bodů v kartézské soustavě, ale v parametrickém vyjádření (tedy poloha bodu se odvíjí od od úhlu otočení po kružnici), zjednodušeně - pracujeme s "ciferníkem".

houfn · 18. 10. 2014 22:11

Zdravím,

Díky.. ano, nepracujeme v kartézské soustavě.

Ještě jsem zapomněl dodat, že nesmím používat žádné fce (sin, cos, tan, atd..). Mám k dispozici základní aritm. operace (+, -, *, \, %)...

Napadá mě, nešlo by to řešit pomocí kombinatoriky? Když mám n bodů na kružnici, tak vím, že počet všech trojúhelníků je (n nad 3).. Nejde například kombinatoricky vyjádřit počet tupoúhlých trojúhelníků v kruhu, nebo půlkruhu?? A pak takovýto počet jen odečíst od všech možností?

Díky.

jelena · 18. 10. 2014 23:58

↑ houfn:

děkuji, o souřadnicích jsem doplnila jen pro případ, aby nebylo nejednoznačného pohledu na jejich zápis a kdyby někdo z kolegů měl poznámku ke způsobu vyjádření souřadnic.

nešlo by to řešit pomocí kombinatoriky? Když mám n bodů na kružnici, tak vím, že počet všech trojúhelníků je (n nad 3).. Nejde například kombinatoricky vyjádřit počet tupoúhlých trojúhelníků v kruhu, nebo půlkruhu?? A pak takovýto počet jen odečíst od všech možností?

ano, k tomu to snad směřuje. Půjde Tobě pro vyloučení procházením vyřadit všechny trojúhelníky, u kterých budeš mít počáteční bod $a$ , potom $a<b<c$ , zároveň $c<\frac{M}{2}$ nebo $a<b<c$ , zároveň $b>\frac{M}{2}$ , zároveň $c<M$ (což mi vycházení trojúhelníky v "menších polorovinách" a tedy tupoúhlé).

Jak to vidíš? Minimálně problém je ujasněn a již se může zapojit někdo z odborně zdatnějších kolegů. Kolegům děkuji.

Matematické Fórum

#1 17. 10. 2014 19:42

Trojúhelníky

#2 18. 10. 2014 00:12

Re: Trojúhelníky

#3 18. 10. 2014 18:50 — Editoval houfn (18. 10. 2014 18:54)

Re: Trojúhelníky

#4 18. 10. 2014 21:36

Re: Trojúhelníky

#5 18. 10. 2014 22:11

Re: Trojúhelníky

#6 18. 10. 2014 23:58

Re: Trojúhelníky

Zápatí