ΠΠΈΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΡΠΊΠ° (ΡΠ΅ΡΠ΅ΡΠ°Ρ)
ΠΠ½Π°ΠΉΠ΄Π΅ΠΌΠΎ ΠΌΡΠ½ΡΠΌΠ°Π»ΡΠ½Π΅ ΡΠ° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½Π΅ Π·Π½Π°ΡΠ΅Π½Π½Ρ Ρ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΈ ΡΠΎΡΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S ΡΠ° ΡΠΎΠ·ΡΠ±'ΡΠΌΠΎ Π²Π΅ΡΡΠΈΠΊΠ°Π»ΡΠ½Ρ ΠΏΠΎΠ»ΠΎΡΡ ΠΌΡΠΆ Π½ΠΈΠΌΠΈ Π½Π° k ΠΏΠΎΠ»ΠΎΡ ΡΡΠ²Π½ΠΎΡ ΡΠΈΡΠΈΠ½ΠΈ. Π ΠΊΠΎΠΆΠ½ΡΠΉ ΡΠ· ΡΠΈΡ k ΠΏΠΎΠ»ΠΎΡ ΡΡΠΊΠ°ΡΡΡΡΡ Π΄Π²Ρ ΡΠΎΡΠΊΠΈ, ΡΠΊΡ ΠΌΠ°ΡΡΡ ΠΌΡΠ½ΡΠΌΠ°Π»ΡΠ½Ρ ΡΠ° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½Ρ Ρ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΡ (ΠΎΠ±ΠΈΡΠ°ΡΡΡΡΡ 2k ΡΠΎΡΠΎΠΊ). ΠΠ±ΠΈΡΠ°ΡΡΡΡΡ ΡΠ°ΠΊΠΎΠΆ ΡΠΎΡΠΊΠΈ Π· Π΅ΠΊΡΡΡΠ΅ΠΌΠ°Π»ΡΠ½ΠΈΠΌΠΈ Π·Π½Π°ΡΠ΅Π½Π½ΡΠΌΠΈ Ρ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΈΡΠΊΡΠΎ ΡΡ Π΄Π΅ΠΊΡΠ»ΡΠΊΠ°, ΡΠΎ ΠΎΠ±ΠΈΡΠ°ΡΡΡΡΡ Π΄Π²Ρ ΡΠΎΡΠΊΠΈ Π· Π΅ΠΊΡΡΡΠ΅ΠΌΠ°Π»ΡΠ½ΠΈΠΌΠΈ Π·Π½Π°ΡΠ΅Π½Π½ΡΠΌΠΈ… Π§ΠΈΡΠ°ΡΠΈ ΡΠ΅ >
ΠΠΈΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΡΠΊΠ° (ΡΠ΅ΡΠ΅ΡΠ°Ρ) (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°)
Π Π΅ΡΠ΅ΡΠ°Ρ Π½Π° ΡΠ΅ΠΌΡ:
ΠΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ°
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. ΠΡΡΠ½Π½Π° Π³Π΅ΠΎΠΌΠ΅ΡΡΡΡ ΡΠΊΠ»Π°Π΄Π°ΡΡΡΡΡ Π· ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ ΡΠΊΠ°Π»ΡΡΡΠ² S (Π΄ΡΠΉΡΠ½ΠΈΡ ΡΠΈΡΠ΅Π»), ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ ΡΠΎΡΠΎΠΊ P ΡΠ° ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Π²ΡΠ»ΡΠ½ΠΈΡ Π²Π΅ΠΊΡΠΎΡΡΠ² V (Π°Π±ΠΎ ΠΏΡΠΎΡΡΠΎ Π²Π΅ΠΊΡΠΎΡΡΠ²). Π’ΠΎΡΠΊΠΈ Π²ΠΈΠΊΠΎΡΠΈΡΡΠΎΠ²ΡΡΡΡΡΡ Π΄Π»Ρ Π·Π°Π΄Π°Π½Π½Ρ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½Ρ, Π° Π²Π΅ΠΊΡΠΎΡΠΈ — Π΄Π»Ρ Π·Π°Π΄Π°Π½Π½Ρ Π½Π°ΠΏΡΡΠΌΠΊΡ ΡΠ° Π²Π΅Π»ΠΈΡΠΈΠ½, Ρ ΠΎΡΠ° Π²ΠΎΠ½ΠΈ Ρ Π½Π΅ ΠΌΠ°ΡΡΡ ΡΡΠΊΡΠΎΠ²Π°Π½ΠΎΠ³ΠΎ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½Ρ Ρ ΠΏΡΠΎΡΡΠΎΡΡ.
ΠΠΏΠ΅ΡΠ°ΡΡΡ Π°ΡΡΠ½Π½ΠΎΡ Π³Π΅ΠΎΠΌΠ΅ΡΡΡΡ:
1. Π΄ΠΎΠ±ΡΡΠΎΠΊ ΡΠΊΠ°Π»ΡΡΠ° Π½Π° Π²Π΅ΠΊΡΠΎΡ: S * V V;
2. Π΄ΠΎΠ΄Π°Π²Π°Π½Π½Ρ Π²Π΅ΠΊΡΠΎΡΡΠ²: V + V V;
3. Π²ΡΠ΄Π½ΡΠΌΠ°Π½Π½Ρ ΡΠΎΡΠΎΠΊ: P — P V;
4. Π΄ΠΎΠ΄Π°Π²Π°Π½Π½Ρ ΡΠΎΡΠΊΠΈ ΡΠ° Π²Π΅ΠΊΡΠΎΡΠ°: P + V P;
Π΄ΠΎΠ΄Π°Π²Π°Π½Π½Ρ Π²Π΅ΠΊΡΠΎΡΡΠ² Π²ΡΠ΄Π½ΡΠΌΠ°Π½Π½Ρ ΡΠΎΡΠΎΠΊ Π΄ΠΎΠ΄Π°Π²Π°Π½Π½Ρ ΡΠΎΡΠΎΠΊ ΡΠ° Π²Π΅ΠΊΡΠΎΡΠ° Π ΡΠ·Π½ΠΈΡΠ΅Ρ Π΄Π²ΠΎΡ ΡΠΎΡΠΎΠΊ p ΡΠ° q Π±ΡΠ΄Π΅ Π²Π΅ΠΊΡΠΎΡ, ΡΠΊΠΈΠΉ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π²ΠΎ Π· q Π΄ΠΎ p.
ΠΡΠ»ΡΠΊΡΡΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΡΠΉ ΠΌΠΎΠΆΠ½Π° ΡΠΎΠ·ΡΠΈΡΠΈΡΠΈ. ΠΠ°ΠΏΡΠΈΠΊΠ»Π°Π΄, ΡΡΠ·Π½ΠΈΡΡ Π²Π΅ΠΊΡΠΎΡΡΠ² ΠΌΠΎΠΆΠ½Π° Π²ΠΈΠ·Π½Π°ΡΠΈΡΠΈ ΡΠΊ u — v = u + (-1) * v, Π° Π΄ΡΠ»Π΅Π½Π½Ρ Π²Π΅ΠΊΡΠΎΡΠ° Π½Π° ΡΠΊΠ°Π»ΡΡ ΡΠΊ v / a = (1 / a) * v. ΠΠ»Π΅ Π½Π΅ ΠΌΠΎΠΆΠ½Π° Π΄ΠΎΠ΄Π°Π²Π°ΡΠΈ Π΄Π²Ρ ΡΠΎΡΠΊΠΈ Π°Π±ΠΎ ΠΌΠ½ΠΎΠΆΠΈΡΠΈ ΡΠΎΡΠΊΡ Π½Π° ΡΠΊΠ°Π»ΡΡ.
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. ΠΠ΅Ρ Π°ΠΉ Π² Ed Π·Π°Π΄Π°Π½ΠΎ k ΡΡΠ·Π½ΠΈΡ ΡΠΎΡΠΎΠΊ p1, p2, …, pk. ΠΠ½ΠΎΠΆΠΈΠ½Π° ΡΠΎΡΠΎΠΊ p ΡΠ°ΠΊΠΈΡ ΡΠΎ.
p = a1p1 + a2p2 + … + akpk (ai R, a1 + a2 + …+ ak = 1).
Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ Π°ΡΡΠ½Π½ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΎΡ, ΠΏΠΎΡΠΎΠ΄ΠΆΠ΅Π½ΠΎΡ ΡΠΎΡΠΊΠ°ΠΌΠΈ p1, p2, …, pk, Π° p Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ Π°ΡΡΠ½Π½ΠΎΡ ΠΊΠΎΠΌΠ±ΡΠ½Π°ΡΡΡΡ ΡΠΎΡΠΎΠΊ p1, p2, …, pk.
ΠΡΡΠ½Π½Π° ΠΊΠΎΠΌΠ±ΡΠ½Π°ΡΡΡ Ρ ΡΠ°ΡΡΠΊΠΎΠ²ΠΈΠΌ Π²ΠΈΠΏΠ°Π΄ΠΊΠΎΠΌ Π»ΡΠ½ΡΠΉΠ½ΠΎΡ ΠΊΠΎΠΌΠ±ΡΠ½Π°ΡΡΡ (Π²Π²ΠΎΠ΄ΠΈΡΡΡΡ Π΄ΠΎΠ΄Π°ΡΠΊΠΎΠ²Π° ΡΠΌΠΎΠ²Π° a1 + a2 + …+ ak = 1). ΠΡΠΈ k = 2 Π°ΡΡΠ½Π½Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π° — ΡΠ΅ ΠΏΡΡΠΌΠ°, ΡΠΎ ΠΏΡΠΎΡ ΠΎΠ΄ΠΈΡΡ ΡΠ΅ΡΠ΅Π· Π΄Π²Ρ ΡΠΎΡΠΊΠΈ p1 ΡΠ° p2.
ΠΡΠΈΠΊΠ»Π°Π΄. ΠΠ΅Ρ Π°ΠΉ Π΄Π°Π½ΠΎ Π΄Π²Ρ ΡΠΎΡΠΊΠΈ p1, p2 ΡΠ° ΡΠΈΡΠ»ΠΎ Π°. ΠΠΎΠ·Π½Π°ΡΠΈΠΌΠΎ ΡΠ΅ΡΠ΅Π· Aff (p0, p1, a) ΠΊΠΎΠΌΠ±ΡΠ½Π°ΡΡΡ (1 — a) * p1 + a * p2 = p1 + a * (p2 — p1). ΠΡΠ²Π° ΡΠ°ΡΡΠΈΠ½Π° ΡΡΠ²Π½ΠΎΡΡΡ ΠΌΡΡΡΠΈΡΡ Π½Π΅Π΄ΠΎΠΏΡΡΡΠΈΠΌΡ ΠΎΠΏΠ΅ΡΠ°ΡΡΡ (Π΄ΠΎΠ΄Π°Π²Π°Π½Π½Ρ ΡΠΎΡΠΎΠΊ), Π°Π»Π΅ Π΅ΠΊΠ²ΡΠ²Π°Π»Π΅Π½ΡΠ½ΠΈΠΉ ΡΠΉ Π°Π»Π³Π΅Π±ΡΠ°ΡΡΠ½ΠΈΠΉ Π²ΠΈΡΠ°Π· ΠΏΡΠ°Π²ΠΎΡ ΡΠ°ΡΡΠΈΠ½ΠΈ Ρ Π΄ΠΎΠΏΡΡΡΠΈΠΌΠΈΠΌ. Π―ΠΊΡΠΎ p1 p2, ΡΠΎ Aff (p0, p1, a) Π»Π΅ΠΆΠΈΡΡ Π½Π° ΠΏΡΡΠΌΡΠΉ p1p2. ΠΠΎΠ»ΠΈ, Π° ΠΏΡΠΎΠ±ΡΠ³Π°Ρ Π²ΡΡ Π΄ΡΠΉΡΠ½Ρ Π·Π½Π°ΡΠ΅Π½Π½Ρ, ΡΠΎ Π²ΠΈΡΠ°Π· Aff (p0, p1, a) ΠΏΡΠΎΠ±ΡΠ³Π°Ρ Π²ΡΡ ΡΠΎΡΠΊΠΈ ΠΏΡΡΠΌΠΎΡ p1p2. ΠΡΠΈ a [0- 1] Π·Π½Π°ΡΠ΅Π½Π½Ρ Aff (p0, p1, a) ΠΏΡΠΎΠ±ΡΠ³Π°Ρ Π²ΡΡ ΡΠΎΡΠΊΠΈ Π²ΡΠ΄ΡΡΠ·ΠΊΡ [pq].
ΠΠ»Ρ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Π½Ρ Π²Π΅ΠΊΡΠΎΡΡΠ² ΡΠ° ΡΠΎΡΠΎΠΊ Π² Π°ΡΡΠ½Π½ΠΎΠΌΡ ΠΏΡΠΎΡΡΠΎΡΡ Π²ΠΈΠΊΠΎΡΠΈΡΡΠΎΠ²ΡΡΡΡΡΡ Π³ΠΎΠΌΠΎΠ³Π΅Π½Π½Ρ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΈ. ΠΡΠΈ ΡΠΎΠ±ΠΎΡΡ Π· d Π²ΠΈΠΌΡΡΠ½ΠΈΠΌ Π°ΡΡΠ½Π½ΠΈΠΌ ΠΏΡΠΎΡΡΠΎΡΠΎΠΌ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΈ Π±ΡΠ΄Π΅ΠΌΠΎ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΠΈ (d + 1) — ΠΊΠΎΡΡΠ΅ΠΆΠ°ΠΌΠΈ Π΄ΡΠΉΡΠ½ΠΈΡ ΡΠΈΡΠ΅Π». ΠΠ΅ΡΡΠΈΠΉ Π΅Π»Π΅ΠΌΠ΅Π½Ρ ΠΊΠΎΡΡΠ΅ΠΆΠ° Π΄ΠΎΡΡΠ²Π½ΡΡ 1 Π΄Π»Ρ ΡΠΎΡΠΊΠΈ Ρ 0 Π΄Π»Ρ Π²Π΅ΠΊΡΠΎΡΠ°. ΠΠ½ΡΡ d Π΅Π»Π΅ΠΌΠ΅Π½ΡΡΠ² ΠΊΠΎΡΡΠ΅ΠΆΠ° Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π°ΡΡΡ Π±Π΅Π·ΠΏΠΎΡΠ΅ΡΠ΅Π΄Π½ΡΠΎ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠ°ΠΌ.
P (1- 1- 3), Q (1- 4- 1), u (0- 1- 2).
P — Q = (1−1- 1−4- 3−1) = (0- -3- 2).
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. Π’ΡΠΈ ΡΠΎΡΠΊΠΈ p, q, r Π½Π° ΠΏΠ»ΠΎΡΠΈΠ½Ρ ΠΌΠ°ΡΡΡ Π΄ΠΎΠ΄Π°ΡΠ½Ρ ΠΎΡΡΡΠ½ΡΠ°ΡΡΡ, ΡΠΊΡΠΎ Π²ΠΎΠ½ΠΈ ΡΡΠ²ΠΎΡΡΡΡΡ ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊ, ΠΎΡΡΡΠ½ΡΠΎΠ²Π°Π½ΠΈΠΉ ΠΏΡΠΎΡΠΈ Π³ΠΎΠ΄ΠΈΠ½Π½ΠΈΠΊΠΎΠ²ΠΎΡ ΡΡΡΡΠ»ΠΊΠΈ ΡΠ° Π²ΡΠ΄'ΡΠΌΠ½Ρ ΠΎΡΡΡΠ½ΡΠ°ΡΡΡ, ΡΠΊΡΠΎ ΠΎΠ±Ρ ΡΠ΄ ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊΠ° pqr Π²ΡΠ΄Π±ΡΠ²Π°ΡΡΡΡΡ Π·Π° Π³ΠΎΠ΄ΠΈΠ½Π½ΠΈΠΊΠΎΠ²ΠΎΡ ΡΡΡΡΠ»ΠΊΠΎΡ. Π’ΡΠΈ ΡΠΎΡΠΊΠΈ p, q, r ΠΌΠ°ΡΡΡ Π½ΡΠ»ΡΠΎΠ²Ρ ΠΎΡΡΡΠ½ΡΠ°ΡΡΡ, ΡΠΊΡΠΎ Π²ΠΎΠ½ΠΈ Π»Π΅ΠΆΠ°ΡΡ Π½Π° ΠΎΠ΄Π½ΡΠΉ ΠΏΡΡΠΌΡΠΉ.
Π΄ΠΎΠ΄Π°ΡΠ½Ρ Π½ΡΠ»ΡΠΎΠ²Π° Π²ΡΠ΄'ΡΠΌΠ½Π° ΠΡΡΡΠ½ΡΠ°ΡΡΡ Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡΡΡ Π·Π½Π°ΠΊΠΎΠΌ Π΄Π΅ΡΠ΅ΡΠΌΡΠ½Π°Π½ΡΠ°, Π²ΠΈΠ·Π½Π°ΡΠ΅Π½ΠΎΠ³ΠΎ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠ°ΠΌΠΈ ΡΡΡΠΎΡ ΡΠΎΡΠΎΠΊ Π² Π³ΠΎΠΌΠΎΠ³Π΅Π½Π½ΠΈΡ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠ°Ρ :
Orient (p, q, r) = .
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. ΠΠ΅Ρ Π°ΠΉ Π² ΠΏΡΠΎΡΡΠΎΡΡ Ed Π·Π°Π΄Π°Π½Π° ΠΏΡΠ΄ΠΌΠ½ΠΎΠΆΠΈΠ½Π° L. ΠΡΡΠ½Π½ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΎΡ aff (L) ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ L Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ Π½Π°ΠΉΠΌΠ΅Π½ΡΠ° Π°ΡΡΠ½Π½Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π°, ΡΠΊΠ° ΠΌΡΡΡΠΈΡΡ L.
ΠΡΡΠ½Π½ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΎΡ Π²ΡΠ΄ΡΡΠ·ΠΊΠ° Ρ ΠΏΡΡΠΌΠ°, Π°ΡΡΠ½Π½ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΎΡ ΠΏΠ»ΠΎΡΠΊΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° Ρ ΠΏΠ»ΠΎΡΠΈΠ½Π°.
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. ΠΠ΅Ρ Π°ΠΉ Π² Ed Π·Π°Π΄Π°Π½ΠΎ k ΡΡΠ·Π½ΠΈΡ ΡΠΎΡΠΎΠΊ p1, p2, …, pk. ΠΠ½ΠΎΠΆΠΈΠ½Π° ΡΠΎΡΠΎΠΊ p ΡΠ°ΠΊΠΈΡ ΡΠΎ.
p = a1p1 + a2p2 + … + akpk (ai R, ai 0, a1 + a2 + …+ ak = 1).
Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΎΡ, ΠΏΠΎΡΠΎΠ΄ΠΆΠ΅Π½ΠΎΡ ΡΠΎΡΠΊΠ°ΠΌΠΈ p1, p2, …, pk, Π° p Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΊΠΎΠΌΠ±ΡΠ½Π°ΡΡΡΡ ΡΠΎΡΠΎΠΊ p1, p2, …, pk.
ΠΠΏΡΠΊΠ»Π° ΠΊΠΎΠΌΠ±ΡΠ½Π°ΡΡΡ Ρ Π·Π²ΡΠΆΠ΅Π½Π½ΡΠΌ Π°ΡΡΠ½Π½ΠΎΡ ΠΊΠΎΠΌΠ±ΡΠ½Π°ΡΡΡ. ΠΡΠΈ k = 2 ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΎΡ Ρ Π²ΡΠ΄ΡΡΠ·ΠΎΠΊ, ΡΠΊΠΈΠΉ ΡΠΏΠΎΠ»ΡΡΠ°Ρ Π·Π°Π΄Π°Π½Ρ ΡΠΎΡΠΊΠΈ.
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. ΠΠ΅Ρ Π°ΠΉ Π² ΠΏΡΠΎΡΡΠΎΡΡ Ed Π·Π°Π΄Π°Π½Π° ΠΏΡΠ΄ΠΌΠ½ΠΎΠΆΠΈΠ½Π° L. ΠΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΎΡ conv (L) ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ L Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ Π½Π°ΠΉΠΌΠ΅Π½ΡΠ° ΠΎΠΏΡΠΊΠ»Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π°, ΡΠΊΠ° ΠΌΡΡΡΠΈΡΡ L.
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. ΠΠΎΠ»ΡΠ΅Π΄ΡΠ°Π»ΡΠ½ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΎΡ Π² Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ ΠΏΠ΅ΡΠ΅ΡΠΈΠ½ ΡΠΊΡΠ½ΡΠ΅Π½Π½ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Π·Π°ΠΌΠΊΠ½Π΅Π½ΠΈΡ ΠΏΡΠ²ΠΏΡΠΎΡΡΠΎΡΡΠ² (ΠΏΡΠ²ΠΏΡΠΎΡΡΡΡ — ΡΠ΅ ΡΠ°ΡΡΠΈΠ½Π° Ed, ΡΠΎΠ·ΡΠ°ΡΠΎΠ²Π°Π½Π° ΠΏΠΎ ΠΎΠ΄Π½Ρ ΡΡΠΎΡΠΎΠ½Ρ Π²ΡΠ΄ Π΄Π΅ΡΠΊΠΎΡ Π³ΡΠΏΠ΅ΡΠΏΠ»ΠΎΡΠΈΠ½ΠΈ).
ΠΠΎΠ»ΡΠ΅Π΄ΡΠ°Π»ΡΠ½Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π° Ρ ΠΎΠΏΡΠΊΠ»ΠΎΡ, ΠΎΡΠΊΡΠ»ΡΠΊΠΈ ΠΏΡΠ²ΠΏΡΠΎΡΡΡΡ Ρ ΠΎΠΏΡΠΊΠ»ΠΈΠΌ ΡΠ° ΠΏΠ΅ΡΠ΅ΡΠΈΠ½ ΠΎΠΏΡΠΊΠ»ΠΈΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ Ρ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΎΡ. ΠΠ»ΠΎΡΠΊΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠΈ ΡΠ° ΡΡΠΈΠ²ΠΈΠΌΡΡΠ½Ρ ΠΌΠ½ΠΎΠ³ΠΎΠ³ΡΠ°Π½Π½ΠΈΠΊΠΈ Ρ ΠΏΡΠΈΠΊΠ»Π°Π΄Π°ΠΌΠΈ ΡΠΊΡΠ½ΡΠ΅Π½Π½ΠΈΡ ΠΏΠΎΠ»ΡΠ΅Π΄ΡΠ°Π»ΡΠ½ΠΈΡ ΠΌΠ½ΠΎΠΆΠΈΠ½. Π‘ΠΊΡΠ½ΡΠ΅Π½Π½Ρ d — ΠΌΡΡΠ½Ρ ΠΏΠΎΠ»ΡΠ΅Π΄ΡΠ°Π»ΡΠ½Ρ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρ Π±ΡΠ΄Π΅ΠΌΠΎ Π½Π°Π·ΠΈΠ²Π°ΡΠΈ ΠΎΠΏΡΠΊΠ»ΠΈΠΌ d — ΠΏΠΎΠ»ΡΡΠΎΠΏΠΎΠΌ (Π°Π±ΠΎ ΠΏΡΠΎΡΡΠΎ ΠΏΠΎΠ»ΡΡΠΎΠΏΠΎΠΌ).
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΡΠΊΡΠ½ΡΠ΅Π½Π½ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ ΡΠΎΡΠΎΠΊ Π² Ρ ΠΎΠΏΡΠΊΠ»ΠΈΠΌ ΠΏΠΎΠ»ΡΡΠΎΠΏΠΎΠΌ. ΠΠΎΠΆΠ½ΠΈΠΉ ΠΎΠΏΡΠΊΠ»ΠΈΠΉ ΠΏΠΎΠ»ΡΡΠΎΠΏ Ρ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΎΡ Π΄Π΅ΡΠΊΠΎΡ ΡΠΊΡΠ½ΡΠ΅Π½Π½ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ ΡΠΎΡΠΎΠΊ.
ΠΠΏΡΠΊΠ»ΠΈΠΉ ΠΏΠΎΠ»ΡΡΠΎΠΏ Π·Π°Π΄Π°ΡΡΡΡΡ ΠΎΠΏΠΈΡΠΎΠΌ ΠΉΠΎΠ³ΠΎ Π³ΡΠ°Π½ΠΈΡΡ, ΡΠΊΠ° ΡΠΊΠ»Π°Π΄Π°ΡΡΡΡΡ Π· Π³ΡΠ°Π½Π΅ΠΉ. ΠΠΎΠΆΠ½Π° Π³ΡΠ°Π½Ρ ΠΎΠΏΡΠΊΠ»ΠΎΠ³ΠΎ ΠΏΠΎΠ»ΡΡΠΎΠΏΠ° Ρ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΎΡ (ΠΏΠΎΠ»ΡΡΠΎΠΏΠΎΠΌ Π½ΠΈΠ·ΡΠΊΠΎΡ ΡΠΎΠ·ΠΌΡΡΠ½ΠΎΡΡΡ). Π―ΠΊΡΠΎ ΠΏΠΎΠ»ΡΡΠΎΠΌ ΠΌΠ°Ρ Π²ΠΈΠΌΡΡΠ½ΡΡΡΡ d, ΡΠΎ ΠΉΠΎΠ³ΠΎ d — 1 Π³ΡΠ°Π½Ρ Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ Π³ΡΠΏΠ΅ΡΠ³ΡΠ°Π½ΡΠΌΠΈ, d — 2 Π³ΡΠ°Π½Ρ - ΠΏΡΠ΄Π³ΡΠ°Π½ΡΠΌΠΈ, 1 — Π³ΡΠ°Π½Ρ - ΡΠ΅Π±ΡΠ°ΠΌΠΈ, 0 — Π³ΡΠ°Π½Ρ - Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ. ΠΠ»Ρ 3 ΠΏΠΎΠ»ΡΡΠΎΠΏΠ° Π³ΡΠΏΠ΅ΡΠ³ΡΠ°Π½ΡΠΌΠΈ Ρ ΠΏΠ»ΠΎΡΠΊΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠΈ, Π° ΠΏΡΠ΄Π³ΡΠ°Π½Ρ ΡΠ° ΡΠ΅Π±ΡΠ° ΡΠΏΡΠ²ΠΏΠ°Π΄Π°ΡΡΡ. Π ΡΡΠΉ ΡΠ΅ΡΠΌΡΠ½ΠΎΠ»ΠΎΠ³ΡΡ ΠΏΠΎΡΠΎΠΆΠ½Ρ ΠΌΠ½ΠΎΠΆΠΈΠ½Π° ΡΡΠ°ΠΊΡΡΡΡΡΡΡ ΡΠΊ (-1) Π³ΡΠ°Π½Ρ.
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. d ΠΏΠΎΠ»ΡΡΠΎΠΏ Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ d ΡΠΈΠΌΠΏΠ»Π΅ΠΊΡΠΎΠΌ, ΡΠΊΡΠΎ Π²ΡΠ½ Ρ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΎΡ (d + 1) Π°ΡΡΠ½Π½ΠΎ Π½Π΅Π·Π°Π»Π΅ΠΆΠ½ΠΈΡ ΡΠΎΡΠΎΠΊ. ΠΠΎΠΆΠ½Π° ΠΏΡΠ΄ΠΌΠ½ΠΎΠΆΠΈΠ½Π° Π· ΡΠΈΡ d Π²Π΅ΡΡΠΈΠ½ Ρ ΡΠΈΠΌΠΏΠ»Π΅ΠΊΡΠΎΠΌ Ρ Ρ Π³ΡΠ°Π½Π½Ρ. ΠΠΎΠΆΠ½Π° k Π³ΡΠ°Π½Ρ ΠΌΡΡΡΠΈΡΡ 2k+1 Π³ΡΠ°Π½Π΅ΠΉ ΡΠΎΠ·ΠΌΡΡΠ½ΠΎΡΡΠ΅ΠΉ k, k-1, k-2, …, 0, -1.
ΠΡΠΈ d = 0, 1, 2, 3 Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π½ΠΈΠΉ ΡΠΈΠΌΠΏΠ»Π΅ΠΊΡ Ρ ΡΠΎΡΠΊΠΎΡ, ΡΠ΅Π±ΡΠΎΠΌ, ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊΠΎΠΌ ΡΠ° ΡΡΠΈΠΊΡΡΠ½ΠΎΡ ΠΏΡΡΠ°ΠΌΡΠ΄ΠΎΡ.
ΠΠ°ΠΏΡΠΈΠΊΠ»Π°Π΄, ΡΡΠΈΠΊΡΡΠ½Π° ΠΏΡΡΠ°ΠΌΡΠ΄Π° (3 Π³ΡΠ°Π½Ρ) ΠΌΡΡΡΠΈΡΡ ΠΎΠ΄Π½Ρ 3 Π³ΡΠ°Π½Ρ (ΡΠ°ΠΌΠ° ΠΏΡΡΠ°ΠΌΡΠ΄Π°), ΡΠΎΡΠΈΡΠΈ 2 Π³ΡΠ°Π½Ρ (ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊΠΈ), ΡΡΡΡΡ 1 Π³ΡΠ°Π½Π΅ΠΉ (ΡΠ΅Π±ΡΠ°), ΡΠΎΡΠΈΡΠΈ 0 Π³ΡΠ°Π½Π΅ΠΉ (Π²Π΅ΡΡΠΈΠ½ΠΈ) ΡΠ° ΠΎΠ΄Π½Ρ (-1) Π³ΡΠ°Π½Ρ (ΠΏΠΎΡΠΎΠΆΠ½Ρ ΠΌΠ½ΠΎΠΆΠΈΠ½Π°), ΡΠΎ ΡΠ°Π·ΠΎΠΌ ΡΠΊΠ»Π°Π΄Π°Ρ 16 = 24 Π³ΡΠ°Π½Π΅ΠΉ.
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. d ΠΏΠΎΠ»ΡΡΠΎΠΏ Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ ΡΠΈΠΌΠΏΠ»ΡΡΠΈΠ°Π»ΡΠ½ΠΈΠΌ, ΡΠΊΡΠΎ ΠΉΠΎΠ³ΠΎ ΠΊΠΎΠΆΠ½Π° Π³ΡΠΏΠ΅ΡΠ³ΡΠ°Π½Ρ Ρ ΡΠΈΠΌΠΏΠ»Π΅ΠΊΡΠΎΠΌ.
ΠΠ°Π΄Π°ΡΠ° 1. ΠΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ°. Π Ed Π·Π°Π΄Π°Π½ΠΎ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρ S, ΡΠΎ ΠΌΡΡΡΠΈΡΡ N ΡΠΎΡΠΎΠΊ. ΠΠ΅ΠΎΠ±Ρ ΡΠ΄Π½ΠΎ ΠΏΠΎΠ±ΡΠ΄ΡΠ²Π°ΡΠΈ ΡΡ ΠΎΠΏΡΠΊΠ»Ρ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡ (ΠΏΠΎΠ²Π½ΠΈΠΉ ΠΎΠΏΠΈΡ Π³ΡΠ°Π½ΠΈΡΡ CH (S)).
ΠΠ°Π΄Π°ΡΠ° 2. ΠΡΠ°ΠΉΠ½Ρ ΡΠΎΡΠΊΠΈ. Π Ed Π·Π°Π΄Π°Π½ΠΎ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρ S, ΡΠΎ ΠΌΡΡΡΠΈΡΡ N ΡΠΎΡΠΎΠΊ. ΠΠ΅ΠΎΠ±Ρ ΡΠ΄Π½ΠΎ Π²ΠΈΠ·Π½Π°ΡΠΈΡΠΈ ΡΡ Π· Π½ΠΈΡ , ΡΠΊΡ Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ conv (S).
ΠΠ°Π΄Π°ΡΠ° 3. ΠΠ΅ΡΠ΅Π²ΡΡΠΊΠ° ΠΊΡΠ°ΠΉΠ½ΠΎΡΡΡ ΡΠΎΡΠΎΠΊ ΠΏΠ»ΠΎΡΠΈΠ½ΠΈ. ΠΠ° ΠΏΠ»ΠΎΡΠΈΠ½Ρ Π·Π°Π΄Π°Π½ΠΎ N ΡΠΎΡΠΎΠΊ. ΠΠΈΠ·Π½Π°ΡΠΈΡΠΈ, ΡΠΈ Ρ Π²ΠΎΠ½ΠΈ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ ΡΠ²ΠΎΡΡ Π²Π»Π°ΡΠ½ΠΎΡ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠ°Π΄Π°ΡΠ° ΡΠΎΡΡΡΠ²Π°Π½Π½Ρ Π·Π²ΠΎΠ΄ΠΈΡΡΡΡ Π·Π° Π»ΡΠ½ΡΠΉΠ½ΠΈΠΉ ΡΠ°Ρ Π΄ΠΎ Π·Π°Π΄Π°ΡΡ ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ. ΠΠ»Ρ Π·Π½Π°Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ Π²ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²Π°Π½ΠΈΡ N ΡΠΎΡΠΎΠΊ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΏΠΎΡΡΡΠ±Π΅Π½ ΡΠ°Ρ O (N log N).
ΠΠΎΠ²Π΅Π΄Π΅Π½Π½Ρ. ΠΠ΅Ρ Π°ΠΉ Π΄Π°Π½ΠΎ N Π΄ΠΎΠ΄Π°ΡΠ½ΠΈΡ Π΄ΡΠΉΡΠ½ΠΈΡ ΡΠΈΡΠ΅Π» x1, x2, …, xN. ΠΠΎΡΡΠ°Π²ΠΈΠΌΠΎ Ρ Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π½ΡΡΡΡ ΡΠΎΡΡΡ xi ΡΠΎΡΠΊΡ (xi, xi+1) Ρ ΠΏΡΠΈΡΠ²ΠΎΡΠΌΠΎ ΡΠΉ Π½ΠΎΠΌΠ΅Ρ i. Π£ΡΠ²ΠΎΡΠ΅Π½Ρ ΡΠΎΡΠΊΠΈ Π»Π΅ΠΆΠ°ΡΡ Π½Π° ΠΏΠ°ΡΠ°Π±ΠΎΠ»Ρ y = x2. ΠΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΡΡΡΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ ΡΠΎΡΠΎΠΊ Π±ΡΠ΄Π΅ ΡΠΊΠ»Π°Π΄Π°ΡΠΈΡΡ Π·Ρ ΡΠΏΠΈΡΠΊΡ ΡΠΎΡΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ, Π²ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²Π°Π½ΠΎΠΌΡ Π·Π° Π·Π½Π°ΡΠ΅Π½Π½ΡΠΌ Π°Π±ΡΡΠΈΡΠΈ.
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. Π’ΠΎΡΠΊΠ° p ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ ΠΊΡΠ°ΠΉΠ½ΡΠΎΡ, ΡΠΊΡΠΎ Π½Π΅ ΡΡΠ½ΡΡ ΠΏΠ°ΡΠΈ ΡΠΎΡΠΎΠΊ a, b S ΡΠ°ΠΊΠΈΡ , ΡΠΎ Π»Π΅ΠΆΠΈΡΡ Π½Π° Π²ΡΠ΄ΠΊΡΠΈΡΠΎΠΌΡ Π²ΡΠ΄ΡΡΠ·ΠΊΡ ab.
ΠΠ½ΠΎΠΆΠΈΠ½Π° E ΠΊΡΠ°ΠΉΠ½ΡΡ ΡΠΎΡΠΎΠΊ S ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡ ΡΠΎΠ±ΠΎΡ Π½Π°ΠΉΠΌΠ΅Π½ΡΡ ΠΏΡΠ΄ΠΌΠ½ΠΎΠΆΠΈΠ½Ρ S, ΡΠΊΠ° ΠΌΠ°Ρ Π²Π»Π°ΡΡΠΈΠ²ΡΡΡΡ: conv (E) = conv (S), ΠΏΡΠΈ ΡΠΎΠΌΡ Π Π² ΡΠΎΡΠ½ΠΎΡΡΡ ΡΠΏΡΠ²ΠΏΠ°Π΄Π°Ρ Π· ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΎΡ Π²Π΅ΡΡΠΈΠ½ conv (S).
ΠΠ»Ρ Π·Π½Π°Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΡΠΊΡΠ½ΡΠ΅Π½Π½ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Π½Π΅ΠΎΠ±Ρ ΡΠ΄Π½ΠΎ Π²ΠΈΠΊΠΎΠ½Π°ΡΠΈ Π½Π°ΡΡΡΠΏΠ½Π΅:
1. ΠΠΈΠ·Π½Π°ΡΠΈΡΠΈ ΠΊΡΠ°ΠΉΠ½Ρ ΡΠΎΡΠΊΠΈ;
2. ΠΠΏΠΎΡΡΠ΄ΠΊΡΠ²Π°ΡΠΈ ΡΡ ΡΠΎΡΠΊΠΈ ΡΠ°ΠΊ, ΡΠΎΠ± Π²ΠΎΠ½ΠΈ ΡΡΠ²ΠΎΡΡΠ²Π°Π»ΠΈ ΠΎΠΏΡΠΊΠ»ΠΈΠΉ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. Π’ΠΎΡΠΊΠ° p Π½Π΅ Ρ ΠΊΡΠ°ΠΉΠ½ΡΠΎΡ ΠΏΠ»ΠΎΡΠΊΠΎΡ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S ΡΠΎΠ΄Ρ Ρ ΡΡΠ»ΡΠΊΠΈ ΡΠΎΠ΄Ρ, ΠΊΠΎΠ»ΠΈ Π²ΠΎΠ½Π° Π»Π΅ΠΆΠΈΡΡ Π² Π΄Π΅ΡΠΊΠΎΠΌΡ ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊΡ, Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ ΡΠΊΠΎΠ³ΠΎ Ρ ΡΠΎΡΠΊΠΈ Π· S, Π°Π»Π΅ ΡΠ°ΠΌΠ° Π²ΠΎΠ½Π° Π½Π΅ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΡ ΡΡΠΎΠ³ΠΎ ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊΠ°.
ΠΡΠ½ΡΡ O (N3) ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊΡΠ², ΡΠΊΡ Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡΡΡ N ΡΠΎΡΠΊΠ°ΠΌΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S. ΠΡΠΆΠ΅ Π·Π° ΡΠ°Ρ O (N3) ΠΌΠΎΠΆΠ½Π° Π²ΠΈΠ·Π½Π°ΡΠΈΡΠΈ, ΡΠΈ Ρ Π·Π°Π΄Π°Π½Π° ΡΠΎΡΠΊΠ° ΠΊΡΠ°ΠΉΠ½ΡΠΎΡ. ΠΠΎΠ²ΡΠΎΡΠ΅Π½Π½Ρ ΡΡΡΡ ΠΏΡΠΎΡΠ΅Π΄ΡΡΠΈ Π΄Π»Ρ Π²ΡΡΡ N ΡΠΎΡΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Π²ΠΈΠΌΠ°Π³Π°Ρ ΡΠ°ΡΡ O (N4).
Π’ΠΎΡΠΊΠ° P Π½Π΅ Ρ ΠΊΡΠ°ΠΉΠ½ΡΠΎΡ, ΠΎΡΠΊΡΠ»ΡΠΊΠΈ Π²ΠΎΠ½Π° Π»Π΅ΠΆΠΈΡΡ Π²ΡΠ΅ΡΠ΅Π΄ΠΈΠ½Ρ ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊΠ° P1P2P3.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΡΠΎΠΌΡΠ½Ρ, ΡΠΊΠΈΠΉ Π²ΠΈΡ ΠΎΠ΄ΠΈΡΡ ΡΠ· Π²Π½ΡΡΡΡΡΠ½ΡΠΎΡ ΡΠΎΡΠΊΠΈ ΠΎΠ±ΠΌΠ΅ΠΆΠ΅Π½ΠΎΡ Π·Π°ΠΌΠΊΠ½Π΅Π½ΠΎΡ ΡΡΠ³ΡΡΠΈ F, ΠΏΠ΅ΡΠ΅ΡΠΈΠ½Π°Ρ Π³ΡΠ°Π½ΠΈΡΡ F ΡΡΠ²Π½ΠΎ Π² ΠΎΠ΄Π½ΡΠΉ ΡΠΎΡΡΡ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½Ρ Π²Π΅ΡΡΠΈΠ½ΠΈ ΠΎΠΏΡΠΊΠ»ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° ΡΠΎΠ·ΡΠ°ΡΠΎΠ²Π°Π½Ρ Π² ΠΏΠΎΡΡΠ΄ΠΊΡ, ΡΠΊΠΎΠΌΡ Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π°Ρ Π·ΠΌΡΠ½Π° ΠΊΡΡΠ° Π²ΡΠ΄Π½ΠΎΡΠ½ΠΎ Π΄ΠΎΠ²ΡΠ»ΡΠ½ΠΎΡ Π²Π½ΡΡΡΡΡΠ½ΡΠΎΡ ΡΠΎΡΠΊΠΈ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. Π ΡΠΊΠΎΡΡΡ Π²Π½ΡΡΡΡΡΠ½ΡΠΎΡ ΡΠΎΡΠΊΠΈ q ΠΌΠΎΠΆΠ½Π° Π²Π·ΡΡΠΈ ΡΠ΅Π½ΡΡΠΎΡΠ΄ Π΄ΠΎΠ²ΡΠ»ΡΠ½ΠΈΡ ΡΡΡΠΎΡ Π½Π΅ΠΊΠΎΠ»ΡΠ½Π΅Π°ΡΠ½ΠΈΡ ΡΠΎΡΠΎΠΊ.
ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ Π±Π΅ΡΡΡΡΡΡ Π΄Π²Ρ Π΄ΠΎΠ²ΡΠ»ΡΠ½Ρ ΡΠΎΡΠΊΠΈ ΡΠ° ΡΡΠΊΠ°ΡΡΡΡΡ ΡΠ°ΠΊΠ° ΡΡΠ΅ΡΡ ΡΠΎΡΠΊΠ° Π· ΡΠ½ΡΠΈΡ N — 2 ΡΠΎΡΠΎΠΊ, ΡΠΊΠ° Π½Π΅ Π»Π΅ΠΆΠΈΡΡ Π½Π° ΠΏΡΡΠΌΡΠΉ, ΡΠΎ Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡΡΡ ΠΏΠ΅ΡΡΠΈΠΌΠΈ Π΄Π²ΠΎΠΌΠ°.
ΠΠ°Π΄Π°ΡΠ°. ΠΠ° ΠΏΠ»ΠΎΡΠΈΠ½Ρ Π΄Π°Π½ΠΎ Π΄Π²Ρ ΡΠΎΡΠΊΠΈ p1 ΡΠ° p2. Π―ΠΊΠ° Π· ΡΠΈΡ ΡΠΎΡΠΎΠΊ ΠΌΠ°Ρ Π±ΡΠ»ΡΡΠΈΠΉ ΠΏΠΎΠ»ΡΡΠ½ΠΈΠΉ ΠΊΡΡ?
p2 ΡΡΠ²ΠΎΡΡΡ Π· Π²ΡΡΡΡ ΠΡ ΡΡΡΠΎΠ³ΠΎ ΠΌΠ΅Π½ΡΠΈΠΉ ΠΏΠΎΠ»ΡΡΠ½ΠΈΠΉ ΠΊΡΡ, Π½ΡΠΆ p1 ΡΠΎΠ΄Ρ Ρ ΡΡΠ»ΡΠΊΠΈ ΡΠΎΠ΄Ρ, ΠΊΠΎΠ»ΠΈ ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊ (O, p2, p1) ΠΌΠ°Ρ ΡΡΡΠΎΠ³ΠΎ Π΄ΠΎΠ΄Π°ΡΠ½Ρ ΠΏΠ»ΠΎΡΡ (Π°Π±ΠΎ ΡΠΎΡΠΊΠ° P1 Π»Π΅ΠΆΠΈΡΡ Π·Π»ΡΠ²Π° Π²ΡΠ΄ ΠΏΡΡΠΌΠΎΡ OP2).
ΠΡΠΈΠΊΠ»Π°Π΄. ΠΠ»ΠΎΡΠ° ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊΠ° OP2P1 Π΄ΠΎΡΡΠ²Π½ΡΡ Π * P2 = Π * = Π * (30 — 6) = 12.
ΠΠ΅ΡΠΎΠ΄ ΠΎΠ±Ρ ΠΎΠ΄Π° ΠΡΠ΅Ρ Π΅ΠΌΠ° ΠΠ½Π°ΠΉΠ΄Π΅ΠΌΠΎ Π²Π½ΡΡΡΡΡΠ½Ρ ΡΠΎΡΠΊΡ O ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ ΡΠΎΡΠΎΠΊ S ΡΠ° ΠΏΠ΅ΡΠ΅ΡΠ²ΠΎΡΠΈΠΌΠΎ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΈ ΡΠ½ΡΠΈΡ ΡΠΎΡΠΎΠΊ ΡΠ°ΠΊ, ΡΠΎΠ± Π·Π½Π°ΠΉΠ΄Π΅Π½Π° Π²Π½ΡΡΡΡΡΠ½Ρ ΡΠΎΡΠΊΠ° ΡΡΠ°Π»Π° ΠΏΠΎΡΠ°ΡΠΊΠΎΠΌ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°Ρ. ΠΠΏΠΎΡΡΠ΄ΠΊΡΡΠΌΠΎ Π»Π΅ΠΊΡΠΈΠΊΠΎΠ³ΡΠ°ΡΡΡΠ½ΠΎ N ΡΠΎΡΠΎΠΊ Ρ Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π½ΠΎΡΡΡ Π·Ρ Π·Π½Π°ΡΠ΅Π½Π½ΡΠΌΠΈ ΠΏΠΎΠ»ΡΡΠ½ΠΎΠ³ΠΎ ΠΊΡΡΠ° ΡΠ° Π²ΡΠ΄ΡΡΠ°Π½Ρ Π²ΡΠ΄ ΠΏΠΎΡΠ°ΡΠΊΡ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°Ρ (ΠΏΡΠΈ ΡΡΠΎΠΌΡ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ΄ΠΈΡΠΈ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΈ ΡΠΎΡΠΎΠΊ Π΄ΠΎ ΠΏΠΎΠ»ΡΡΠ½ΠΎΡ ΡΠΈΡΡΠ΅ΠΌΠΈ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°Ρ Π½Π΅ ΡΡΠ΅Π±Π°).
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΡΠ΅Ρ Π΅ΠΌΠ° ΠΏΠΎΠ»ΡΠ³Π°Ρ Π² ΠΎΠ΄Π½ΠΎΠΊΡΠ°ΡΠ½ΠΎΠΌΡ ΠΏΠ΅ΡΠ΅Π³Π»ΡΠ΄Ρ Π²ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²Π°Π½ΠΎΡ ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΠΎΡΡΡ ΡΠΎΡΠΎΠΊ, Π² ΠΏΡΠΎΡΠ΅ΡΡ ΡΠΊΠΎΡ Π²ΠΈΠ΄Π°Π»ΡΡΡΡΡΡ Π²Π½ΡΡΡΡΡΠ½Ρ ΡΠΎΡΠΊΠΈ. ΠΠ΅ΡΠ΅Π³Π»ΡΠ΄ ΠΏΠΎΡΠΈΠ½Π°ΡΡΡΡΡ Π· ΡΠΎΡΠΊΠΈ p0, Π² ΡΠΊΠΎΡΡΡ ΡΠΊΠΎΡ ΠΌΠΎΠΆΠ½Π° Π²Π·ΡΡΠΈ ΡΠ°ΠΌΡ ΠΏΡΠ°Π²Ρ (Π· ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΡ Π°Π±ΡΡΠΈΡΠΎΡ) Π· Π½Π°ΠΉΠΌΠ΅Π½ΡΠΎΡ ΠΎΡΠ΄ΠΈΠ½Π°ΡΠΎΡ (Π²ΠΎΠ½Π° ΡΠΎΡΠ½ΠΎ Π½Π°Π»Π΅ΠΆΠΈΡΡ ΠΎΠΏΡΠΊΠ»ΡΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΡΡ). ΠΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΠΎ ΠΏΠ΅ΡΠ΅Π²ΡΡΡΡΡΡΡΡ ΡΡΡΠΉΠΊΠΈ ΡΠΎΡΠΎΠΊ p1p2p3, ΠΏΡΠΈ ΡΠΎΠΌΡ.
1. Π―ΠΊΡΠΎ ΡΡΡΠΉΠΊΠ° p1p2p3 ΡΡΠ²ΠΎΡΡΡ ΠΏΡΠ°Π²ΠΈΠΉ ΠΏΠΎΠ²ΠΎΡΠΎΡ, ΡΠΎ Π²ΠΈΠ΄Π°Π»ΠΈΡΠΈ Π²Π΅ΡΡΠΈΠ½Ρ p2 ΡΠ° ΠΏΠ΅ΡΠ΅Π²ΡΡΠΈΡΠΈ ΡΡΡΠΉΠΊΡ p0p1p3.
2. Π―ΠΊΡΠΎ ΡΡΡΠΉΠΊΠ° p1p2p3 ΡΡΠ²ΠΎΡΡΡ Π»ΡΠ²ΠΈΠΉ ΠΏΠΎΠ²ΠΎΡΠΎΡ, ΡΠΎ ΠΏΡΠΎΠ΄ΠΎΠ²ΠΆΡΠ²Π°ΡΠΈ ΠΏΠ΅ΡΠ΅Π³Π»ΡΠ΄, ΠΏΠ΅ΡΠ΅ΠΉΡΠΎΠ²ΡΠΈ Π΄ΠΎ ΡΡΡΠΉΠΊΠΈ p2p3p4.
ΠΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΠΡΠ΅Ρ Π΅ΠΌΠ°.
1. ΠΠ½Π°ΠΉΡΠΈ Π²Π½ΡΡΡΡΡΠ½Ρ ΡΠΎΡΠΊΡ q.
2. ΠΠΈΠΊΠΎΡΠΈΡΡΠΎΠ²ΡΡΡΠΈ q ΡΠΊ ΠΏΠΎΡΠ°ΡΠΎΠΊ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°Ρ, Π²ΠΏΠΎΡΡΠ΄ΠΊΡΠ²Π°ΡΠΈ Π»Π΅ΠΊΡΠΈΠΊΠΎΠ³ΡΠ°ΡΡΡΠ½ΠΎ ΡΠΎΡΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Ρ Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π½ΠΎΡΡΡ Π· ΠΏΠΎΠ»ΡΡΠ½ΠΈΠΌ ΠΊΡΡΠΎΠΌ ΡΠ° Π²ΡΠ΄ΡΡΠ°Π½Π½Ρ Π²ΡΠ΄ q. ΠΡΠ³Π°Π½ΡΠ·ΡΠ²Π°ΡΠΈ ΡΠΎΡΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Ρ Π²ΠΈΠ³Π»ΡΠ΄Ρ ΠΊΡΠ»ΡΡΠ΅Π²ΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΡ ΡΠ· Π²ΠΊΠ°Π·ΡΠ²Π½ΠΈΠΊΠ°ΠΌΠΈ NEXT, PREV ΡΠ° Π²ΠΊΠ°Π·ΡΠ²Π½ΠΈΠΊΠΎΠΌ ΠΠΠ§ΠΠ’ΠΠ Π½Π° ΠΏΠ΅ΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΠ½Π°ΡΠ΅Π½Π½Ρ TRUE Π»ΠΎΠ³ΡΡΠ½ΠΎΡ Π·ΠΌΡΠ½Π½ΠΎΡ f Π²ΠΊΠ°Π·ΡΡ Π½Π° ΡΠ΅, ΡΠΎ Π²Π΅ΡΡΠΈΠ½Π° ΠΠΠ§ΠΠ’ΠΠ Π΄ΠΎΡΡΠ³Π½ΡΡΠ° ΠΏΡΠΈ ΠΏΡΡΠΌΠΎΠΌΡ ΡΡΡΡ ΠΏΠΎ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΡΡ, Π° Π½Π΅ Π² ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ ΠΏΠΎΠ²Π΅ΡΡΠ°Π½Π½Ρ.
3. ΠΠ±Ρ ΡΠ΄.
begin.
v ΠΠΠ§ΠΠ’ΠΠw NEXT[v]- f FALSE;
while (NEXT[v] ΠΠΠ§ΠΠ’ΠΠ or f = FALSE) do.
begin.
if NEXT[v] = w then f E;
if (ΡΡΠΈ ΡΠΎΡΠΊΠΈ v, NEXT[v], NEXT[NEXT[v]] ΡΡΠ²ΠΎΡΡΡΡΡ Π»ΡΠ²ΠΈΠΉ ΠΏΠΎΠ²ΠΎΡΠΎΡ) then v NEXT[v];
else.
begin.
ΠΠΠΠΠΠΠ’Π NEXT[v];
v PREV[v];
end;
end;
end.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° N ΡΠΎΡΠΎΠΊ Π½Π° ΠΏΠ»ΠΎΡΠΈΠ½Ρ ΠΌΠΎΠΆΠ΅ Π±ΡΡΠΈ Π·Π½Π°ΠΉΠ΄Π΅Π½Π° Π·Π° ΡΠ°Ρ O (N * logN) ΠΏΡΠΈ Π²ΠΈΡΡΠ°ΡΠ°Ρ ΠΏΠ°ΠΌ’ΡΡΡ O (N).
ΠΠ΅ΡΠΎΠ΄ ΠΎΠ±Ρ ΠΎΠ΄Π° ΠΠΆΠ°ΡΠ²ΡΡΠ° Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΡΠ΄ΡΡΠ·ΠΎΠΊ l Ρ ΡΠ΅Π±ΡΠΎΠΌ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΡΠΎΠ΄Ρ Ρ ΡΡΠ»ΡΠΊΠΈ ΡΠΎΠ΄Ρ, ΠΊΠΎΠ»ΠΈ Π²ΡΡ ΡΠ½ΡΡ ΡΠΎΡΠΊΠΈ Π·Π°Π΄Π°Π½ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Π»Π΅ΠΆΠ°ΡΡ Π½Π° l Π°Π±ΠΎ Π· ΠΎΠ΄Π½ΠΎΡ ΡΡΠΎΡΠΎΠ½ΠΈ Π²ΡΠ΄ Π½ΡΠΎΠ³ΠΎ.
N ΡΠΎΡΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡ ΠΏΡΡΠΌΠΈΡ . ΠΠ»Ρ ΠΊΠΎΠΆΠ½ΠΎΡ ΡΡΡΡ ΠΏΡΡΠΌΠΎΡ ΠΌΠΎΠΆΠ½Π° Π²ΠΈΠ·Π½Π°ΡΠΈΡΠΈ Π·Π° Π»ΡΠ½ΡΠΉΠ½ΠΈΠΉ ΡΠ°Ρ ΡΠΎΠ·ΡΠ°ΡΡΠ²Π°Π½Π½Ρ ΡΠ½ΡΠΈΡ N-2 ΡΠΎΡΠΎΠΊ Π²ΡΠ΄Π½ΠΎΡΠ½ΠΎ ΡΡΡΡ ΠΏΡΡΠΌΠΎΡ, ΡΠΈΠΌ ΡΠ°ΠΌΠΈΠΌ ΠΏΠ΅ΡΠ΅Π²ΡΡΠΈΠ²ΡΠΈ ΡΠΈ Π·Π°Π΄ΠΎΠ²ΡΠ»ΡΠ½ΡΡ ΠΏΡΡΠΌΠ° ΡΠΌΠΎΠ²Ρ ΡΠ΅ΠΎΡΠ΅ΠΌΠΈ. ΠΠ° ΡΠ°Ρ O (N3) ΠΌΠΎΠΆΠ½Π° Π·Π½Π°ΠΉΡΠΈ Π²ΡΡ ΠΏΠ°ΡΠΈ ΡΠΎΡΠΎΠΊ, ΡΠΎ Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡ ΡΠ΅Π±ΡΠ° ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΡΠ° ΡΠΎΠ·ΡΠ°ΡΡΠ²Π°ΡΠΈ ΡΡ ΡΠΎΡΠΊΠΈ Ρ Π²ΠΈΠ³Π»ΡΠ΄Ρ ΡΠΏΠΈΡΠΊΡ ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ.
ΠΠΆΠ°ΡΠ²ΡΡ ΠΏΠΎΠΊΡΠ°ΡΠΈΠ² ΡΠ΅ΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠΌΡΡΠΈΠ²ΡΠΈ, ΡΠΎ ΡΠΊΡΠΎ Π²ΡΠ΄ΡΡΠ·ΠΎΠΊ pq Ρ ΡΠ΅Π±ΡΠΎΠΌ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, ΡΠΎ ΠΏΠΎΠ²ΠΈΠ½Π½ΠΎ ΡΡΠ½ΡΠ²Π°ΡΠΈ ΡΠ½ΡΠ΅ ΡΠ΅Π±ΡΠΎ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Π· ΠΊΡΠ½ΡΠ΅ΠΌ Π² ΡΠΎΡΡΡ q. ΠΠ΅Ρ Π°ΠΉ Π·Π½Π°ΠΉΠ΄Π΅Π½ΠΎ ΡΠΎΡΠΊΡ p1, ΡΠΊΠ° Π½Π°Π»Π΅ΠΆΠΈΡΡ ΠΎΠΏΡΠΊΠ»ΡΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΡΡ (ΡΠΊΠ°, Π½Π°ΠΏΡΠΈΠΊΠ»Π°Π΄, ΠΌΠ°Ρ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½Ρ Ρ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΡΠ° ΡΠΊΡΠΎ ΡΠ°ΠΊΠΈΡ ΡΠΎΡΠΎΠΊ Π΄Π΅ΠΊΡΠ»ΡΠΊΠ° — ΡΠΎ ΡΠ΅ΡΠ΅Π΄ Π½ΠΈΡ Π²Π·ΡΡΠΈ ΡΠΎΡΠΊΡ Π· ΠΌΡΠ½ΡΠΌΠ°Π»ΡΠ½ΠΎΡ Ρ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΎΡ). ΠΠ°ΡΡΡΠΏΠ½Π° ΡΠΎΡΠΊΠ° p2 ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ — ΡΠ΅ ΡΠΎΡΠΊΠ°, ΡΠΊΠ° ΠΌΠ°Ρ Π½Π°ΠΉΠΌΠ΅Π½ΡΠΈΠΉ Π΄ΠΎΠ΄Π°ΡΠ½ΠΈΠΉ ΠΏΠΎΠ»ΡΡΠ½ΠΈΠΉ ΠΊΡΡ Π²ΡΠ΄Π½ΠΎΡΠ½ΠΎ ΡΠΎΡΠΊΠΈ p1 ΡΠΊ ΠΏΠΎΡΠ°ΡΠΊΡ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°Ρ. Π ΡΠ°ΠΊ Π΄Π°Π»Ρ ΡΡΠΊΠ°ΡΡΡΡΡ Π½Π°ΡΡΡΠΏΠ½Ρ ΡΠΎΡΠΊΠΈ ΡΠ»ΡΡ ΠΎΠΌ ΠΏΡΠΎΡ ΠΎΠ΄Ρ Π²ΠΊΡΡΠ³ΠΎΠ²Ρ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, ΠΏΠΎΡΠΎΠ΄ΠΆΡΡΡΠΈ Ρ ΠΏΠΎΡΡΡΠ±Π½ΠΎΠΌΡ ΠΏΠΎΡΡΠ΄ΠΊΡ ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΡΡΡΡ ΠΊΡΠ°ΠΉΠ½ΡΡ ΡΠΎΡΠΎΠΊ, ΠΏΠΎ ΠΎΠ΄Π½ΡΠΉ Π½Π° ΠΊΠΎΠΆΠ½ΠΎΠΌΡ ΠΊΡΠΎΡΡ.
ΠΠ±Ρ ΡΠ΄ ΠΠΆΠ°ΡΠ²ΡΡΠ°.
p[1] ΡΠΎΡΠΊΠ° Π· Π½Π°ΠΉΠΌΠ΅Π½ΡΠΎΡ y ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΎΡ;
p[2] ΡΠΎΡΠΊΠ° Π· ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S, Π΄Π»Ρ ΡΠΊΠΎΡ ΠΊΡΡ ΠΌΡΠΆ ΠΏΡΡΠΌΠΎΡ p[2] - p[1] ΡΠ° Π²ΡΡΡΡ Ox Π½Π°ΠΉΠΌΠ΅Π½ΡΠΈΠΉ;
print (p[1], p[2]);
i 2;
while (p[i] p[1]) do.
begin.
p[i + 1] ΡΠΎΡΠΊΠ° Π· ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S, Π΄Π»Ρ ΡΠΊΠΎΡ ΠΊΡΡ p[i — 1] p[i] p[i + 1] Ρ Π½Π°ΠΉΠ±ΡΠ»ΡΡΠΈΠΌ;
i i + 1;
print (p[i]);
end.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. Π§Π°ΡΠΎΠ²Π° ΠΎΡΡΠ½ΠΊΠ° ΠΎΠ±Ρ ΠΎΠ΄Ρ ΠΠΆΠ°ΡΠ²ΡΡΠ° Π΄ΠΎΡΡΠ²Π½ΡΡ O (N2).
ΠΡΠΊΡΠ»ΡΠΊΠΈ Π²ΡΡ N ΡΠΎΡΠΎΠΊ ΠΌΠΎΠΆΡΡΡ Π»Π΅ΠΆΠ°ΡΠΈ Π½Π° ΠΎΠΏΡΠΊΠ»ΡΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΡΡ, Π° Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΠΆΠ°ΡΠ²ΡΡΠ° Π²ΠΈΠΌΠ°Π³Π°Ρ Π»ΡΠ½ΡΠΉΠ½ΠΈΠΉ ΡΠ°Ρ Π΄Π»Ρ Π·Π½Π°Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ ΠΊΠΎΠΆΠ½ΠΎΡ Π½Π°ΡΡΡΠΏΠ½ΠΎΡ ΡΠΎΡΠΊΠΈ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, ΡΠΎ Π² Π½Π°ΠΉΠ³ΡΡΡΠΎΠΌΡ Π²ΠΈΠΏΠ°Π΄ΠΊΡ ΡΠ°ΡΠΎΠ²Π° ΠΎΡΡΠ½ΠΊΠ° Π΄ΠΎΡΡΠ²Π½ΡΡ O (N2). ΠΠ±Ρ ΡΠ΄ ΠΠΆΠ°ΡΠ²ΡΡΠ° Ρ Π΅ΡΠ΅ΠΊΡΠΈΠ²Π½ΠΈΠΌ, ΡΠΊΡΠΎ ΠΊΡΠ»ΡΠΊΡΡΡΡ Π²Π΅ΡΡΠΈΠ½ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ h Ρ ΠΌΠ°Π»ΠΎΡ Ρ ΠΏΠΎΡΡΠ²Π½ΡΠ½Π½Ρ Π·Ρ Π·Π½Π°ΡΠ΅Π½Π½ΡΠΌ N — ΡΠ°ΡΠΎΠ²Π° ΠΎΡΡΠ½ΠΊΠ° Ρ ΡΡΠΎΠΌΡ Π²ΠΈΠΏΠ°Π΄ΠΊΡ Π΄ΠΎΡΡΠ²Π½ΡΠ²Π°ΡΠΈΠΌΠ΅ O (N * h).
ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π°ΠΏΡΠΎΠΊΡΠΈΠΌΠ°ΡΡΡ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΡΠΈ Π·Π½Π°Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ Π½Π°Π±Π»ΠΈΠΆΠ΅Π½ΠΎΡ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΌΠΈ ΡΠΎΠ·ΠΌΡΠ½ΡΡΠΌΠΎ ΡΠΎΡΠ½ΡΡΡΡ Π½Π° ΠΏΡΠΎΡΡΠΎΡΡ ΡΠ° Π΅ΡΠ΅ΠΊΡΠΈΠ²Π½ΡΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ.
ΠΠ½Π°ΠΉΠ΄Π΅ΠΌΠΎ ΠΌΡΠ½ΡΠΌΠ°Π»ΡΠ½Π΅ ΡΠ° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½Π΅ Π·Π½Π°ΡΠ΅Π½Π½Ρ Ρ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΈ ΡΠΎΡΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S ΡΠ° ΡΠΎΠ·ΡΠ±'ΡΠΌΠΎ Π²Π΅ΡΡΠΈΠΊΠ°Π»ΡΠ½Ρ ΠΏΠΎΠ»ΠΎΡΡ ΠΌΡΠΆ Π½ΠΈΠΌΠΈ Π½Π° k ΠΏΠΎΠ»ΠΎΡ ΡΡΠ²Π½ΠΎΡ ΡΠΈΡΠΈΠ½ΠΈ. Π ΠΊΠΎΠΆΠ½ΡΠΉ ΡΠ· ΡΠΈΡ k ΠΏΠΎΠ»ΠΎΡ ΡΡΠΊΠ°ΡΡΡΡΡ Π΄Π²Ρ ΡΠΎΡΠΊΠΈ, ΡΠΊΡ ΠΌΠ°ΡΡΡ ΠΌΡΠ½ΡΠΌΠ°Π»ΡΠ½Ρ ΡΠ° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½Ρ Ρ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΡ (ΠΎΠ±ΠΈΡΠ°ΡΡΡΡΡ 2k ΡΠΎΡΠΎΠΊ). ΠΠ±ΠΈΡΠ°ΡΡΡΡΡ ΡΠ°ΠΊΠΎΠΆ ΡΠΎΡΠΊΠΈ Π· Π΅ΠΊΡΡΡΠ΅ΠΌΠ°Π»ΡΠ½ΠΈΠΌΠΈ Π·Π½Π°ΡΠ΅Π½Π½ΡΠΌΠΈ Ρ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΈΡΠΊΡΠΎ ΡΡ Π΄Π΅ΠΊΡΠ»ΡΠΊΠ°, ΡΠΎ ΠΎΠ±ΠΈΡΠ°ΡΡΡΡΡ Π΄Π²Ρ ΡΠΎΡΠΊΠΈ Π· Π΅ΠΊΡΡΡΠ΅ΠΌΠ°Π»ΡΠ½ΠΈΠΌΠΈ Π·Π½Π°ΡΠ΅Π½Π½ΡΠΌΠΈ Ρ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΠΈ (ΠΌΠ°ΠΊΡΠΈΠΌΡΠΌ ΠΎΠ±ΠΈΡΠ°ΡΡΡΡΡ 4 ΡΠΎΡΠΊΠΈ). ΠΠ±ΡΠ°Π½Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π° ΠΌΡΡΡΠΈΡΡ Π½Π΅ Π±ΡΠ»ΡΡ Π½ΡΠΆ 2k + 4 ΡΠΎΡΠΎΠΊ Ρ ΠΏΠΎΠ·Π½Π°ΡΠΈΠΌΠΎ ΡΡ ΡΠ΅ΡΠ΅Π· S*. ΠΠ°Π»Ρ ΠΌΠΎΠΆΠ½Π° Π·Π°ΡΡΠΎΡΡΠ²Π°ΡΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΡΠ΅Ρ Π΅ΠΌΠ° ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Π΄Π»Ρ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ ΡΠΎΡΠΎΠΊ S*.
ΠΡΠΈΠΊΠ»Π°Π΄. ΠΠ½ΠΎΠΆΠΈΠ½Ρ ΡΠΎΡΠΎΠΊ S ΡΠΎΠ·Π±ΠΈΡΠΎ Π½Π° k = 4 ΠΏΠΎΠ»ΠΎΡΠΈ. Π ΠΊΠΎΠΆΠ½ΡΠΉ ΠΏΠΎΠ»ΠΎΡΡ ΠΎΠ±ΡΠ°Π½ΠΎ Π΄Π²Ρ ΡΠΎΡΠΊΠΈ. ΠΠ»Ρ ΡΡΠ²ΠΎΡΠ΅Π½ΠΎΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S* ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²Π°Π½ΠΎ ΠΎΠΏΡΠΊΠ»Ρ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠΎΠ²ΡΠ»ΡΠ½Π° ΡΠΎΡΠΊΠ° p S, ΡΠΊΠ° Π½Π΅ ΠΏΠΎΠΏΠ°Π»Π° Π²ΡΠ΅ΡΠ΅Π΄ΠΈΠ½Ρ Π½Π°Π±Π»ΠΈΠΆΠ΅Π½ΠΎΡ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, Π·Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡΡ Π½Π° Π²ΡΠ΄ΡΡΠ°Π½Ρ, Π½Π΅ Π±ΡΠ»ΡΡΠΎΡ Π·Π° Π·Π½Π°ΡΠ΅Π½Π½Ρ (xmax — xmin) / k.
Π¨Π²ΠΈΠ΄ΠΊΡ ΠΌΠ΅ΡΠΎΠ΄ΠΈ ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Π ΠΎΠ·ΡΠ±'ΡΠΌΠΎ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρ S Π· N ΡΠΎΡΠΎΠΊ Π½Π° Π΄Π²Ρ ΠΏΡΠ΄ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ, ΠΊΠΎΠΆΠ½Π° Π· ΡΠΊΠΈΡ Π±ΡΠ΄Π΅ ΠΌΡΡΡΠΈΡΠΈ ΠΎΠ΄Π½Ρ Π· Π΄Π²ΠΎΡ Π»Π°ΠΌΠ°Π½ΠΈΡ , ΠΎΠ±'ΡΠ΄Π½Π°Π½Π½Ρ ΡΠΊΠΈΡ Π΄Π°Ρ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ. ΠΠΎΡΠ°ΡΠΊΠΎΠ²Π΅ ΡΠΎΠ·Π±ΠΈΡΡΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ ΡΠΎΡΠΎΠΊ Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡΡΡ ΠΏΡΡΠΌΠΎΡ, ΡΠΎ ΠΏΡΠΎΡ ΠΎΠ΄ΠΈΡΡ ΡΠ΅ΡΠ΅Π· Π΄Π²Ρ ΡΠΎΡΠΊΠΈ l ΡΠ° r, ΡΠΊΡ ΠΌΠ°ΡΡΡ Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π½ΠΎ Π½Π°ΠΉΠΌΠ΅Π½ΡΡ ΡΠ° Π½Π°ΠΉΠ±ΡΠ»ΡΡΡ Π°Π±ΡΡΠΈΡΡ. ΠΠΎΠ·Π½Π°ΡΠΈΠΌΠΎ ΡΠ΅ΡΠ΅Π· S1 ΠΏΡΠ΄ΠΌΠ½ΠΎΠΆΠΈΠ½Ρ ΡΠΎΡΠΎΠΊ, ΡΠΊΠ° ΡΠΎΠ·ΡΠ°ΡΠΎΠ²Π°Π½Π° Π²ΠΈΡΠ΅ Π°Π±ΠΎ Π½Π° ΠΏΡΡΠΌΡΠΉ, Π° ΡΠ΅ΡΠ΅Π· S2 — ΠΏΡΠ΄ΠΌΠ½ΠΎΠΆΠΈΠ½Ρ ΡΠΎΡΠΎΠΊ, ΡΠΊΠ° ΡΠΎΠ·ΡΠ°ΡΠΎΠ²Π°Π½Π° Π½ΠΈΠΆΡΠ΅ Π°Π±ΠΎ Π½Π° ΠΏΡΡΠΌΡΠΉ. Π―ΠΊΡΠΎ Π±ΡΡΠΈ ΡΠΎΡΠ½ΠΈΠΌ, ΡΠΎ {S1, S2} Π½Π΅ Ρ ΡΠΎΠ·Π±ΠΈΡΡΡΠΌ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S, ΠΎΡΠΊΡΠ»ΡΠΊΠΈ {l, r} S1 S2. ΠΠ°Π»Ρ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S1 ΡΠ° S2 ΠΎΠ±ΡΠΎΠ±Π»ΡΡΡΡΡΡ Π½Π°ΡΡΡΠΏΠ½ΠΈΠΌ ΡΠΈΠ½ΠΎΠΌ (ΡΠΎΠ·Π³Π»ΡΠ½Π΅ΠΌΠΎ Π½Π° ΠΏΡΠΈΠΊΠ»Π°Π΄Ρ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S1).
ΠΠ½Π°ΠΉΠ΄Π΅ΠΌΠΎ ΡΠΎΡΠΊΡ h, Π΄Π»Ρ ΡΠΊΠΎΡ ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊ lhr ΠΌΠ°Ρ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½Ρ ΠΏΠ»ΠΎΡΡ ΡΠ΅ΡΠ΅Π΄ ΡΡΡΡ ΡΠ½ΡΠΈΡ ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊΡΠ² (ΡΠΊΡΠΎ ΡΠ°ΠΊΠΈΡ ΡΠΎΡΠΎΠΊ Π΄Π΅ΠΊΡΠ»ΡΠΊΠ°, ΡΠΎ ΠΎΠ±ΠΈΡΠ°ΡΠΌΠΎ ΡΡ, Π² ΡΠΊΡΠΉ ΠΊΡΡ hlr Π±ΡΠ»ΡΡΠΈΠΉ). Π’ΠΎΡΠΊΠ° h Π³Π°ΡΠ°Π½ΡΠΎΠ²Π°Π½ΠΎ Π½Π°Π»Π΅ΠΆΠΈΡΡ ΠΎΠΏΡΠΊΠ»ΡΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΡΡ. Π―ΠΊΡΠΎ ΠΏΡΠΎΠ²Π΅ΡΡΠΈ ΡΠ΅ΡΠ΅Π· h ΠΏΡΡΠΌΡ, ΠΏΠ°ΡΠ°Π»Π΅Π»ΡΠ½Ρ lr, ΡΠΎ Π½Π°Π΄ Π½ΡΠΉ Π½Π΅ Π±ΡΠ΄Π΅ ΠΆΠΎΠ΄Π½ΠΎΡ ΡΠΎΡΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S. Π―ΠΊΡΠΎ Π½Π° ΡΡΠΉ ΠΏΡΡΠΌΡΠΉ Π»Π΅ΠΆΠ°ΡΡ Π΄Π΅ΠΊΡΠ»ΡΠΊΠ° ΡΠΎΡΠΎΠΊ, ΡΠΎ Π·Π³ΡΠ΄Π½ΠΎ Π· ΠΏΡΠΈΠΏΡΡΠ΅Π½Π½ΡΠΌ ΡΠΎΡΠΊΠ° h Π±ΡΠ΄Π΅ ΡΠ°ΠΌΠΎΡ Π»ΡΠ²ΠΎΡ Π· Π½ΠΈΡ .
ΠΡΠ΄ΡΡΠΌΠΎ Π΄Π²Ρ ΠΏΡΡΠΌΡ: L1 (ΡΠΏΠΎΠ»ΡΡΠ°Ρ ΡΠΎΡΠΊΠΈ l ΡΠ° h) ΡΠ° L2 (ΠΏΡΠΎΡ ΠΎΠ΄ΠΈΡΡ ΡΠ΅ΡΠ΅Π· ΡΠΎΡΠΊΠΈ h ΡΠ° r). ΠΠ»Ρ ΠΊΠΎΠΆΠ½ΠΎΡ ΡΠΎΡΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S1 Π²ΠΈΠ·Π½Π°ΡΠ°ΡΠΌΠΎ ΡΡ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½Ρ Π²ΡΠ΄Π½ΠΎΡΠ½ΠΎ ΡΠΈΡ ΠΏΡΡΠΌΠΈΡ . Π’ΠΎΡΠΊΠΈ, ΡΠΊΡ ΠΏΠΎΠΏΠ°Π»ΠΈ Π² ΡΡΠΈΠΊΡΡΠ½ΠΈΠΊ lhr, ΠΌΠΎΠΆΡΡΡ Π±ΡΡΠΈ Π²ΠΈΠ»ΡΡΠ΅Π½Ρ Π· ΠΏΠΎΠ΄Π°Π»ΡΡΠΎΡ ΠΎΠ±ΡΠΎΠ±ΠΊΠΈ. ΠΠΎΠ΄Π½Π° Π· ΡΠΎΡΠΎΠΊ Π½Π΅ Π·Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡΡ Π·Π»ΡΠ²Π° Π²ΡΠ΄ L1 ΡΠ° Π·Π»ΡΠ²Π° Π²ΡΠ΄ L2 (Π½Π°ΠΏΡΡΠΌΠΊΠΈ ΠΏΡΡΠΌΠΈΡ Π²ΠΊΠ°Π·Π°Π½ΠΎ Π½Π° ΡΠΈΡΡΠ½ΠΊΡ). Π’ΠΎΡΠΊΠΈ, ΡΠΎΠ·ΡΠ°ΡΠΎΠ²Π°Π½Ρ Π·Π»ΡΠ²Π° Π²ΡΠ΄ L1 ΡΠΈ Π½Π° Π½ΡΠΉ, ΡΡΠ²ΠΎΡΡΡΡΡ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρ S11. ΠΠ½Π°Π»ΠΎΠ³ΡΡΠ½ΠΎ ΡΡΠ²ΠΎΡΡΡΡΡΡΡ ΠΌΠ½ΠΎΠΆΠΈΠ½Π° S12. Π£ΡΠ²ΠΎΡΠ΅Π½Ρ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S11 ΡΠ° S12 ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡΡΡΡ Π΄Π°Π»Ρ Π½Π° Π½Π°ΡΡΡΠΏΠ½ΠΈΠΉ ΡΡΠ²Π΅Π½Ρ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎΡ ΠΎΠ±ΡΠΎΠ±ΠΊΠΈ.
ΠΠΈΠ±ΡΡ ΠΏΠΎΡΠ°ΡΠΊΠΎΠ²ΠΈΡ Π·Π½Π°ΡΠ΅Π½Ρ {l0, r0} ΡΠΎΡΠΎΠΊ l ΡΠ° r ΠΌΠΎΠΆΠ½Π° ΡΠΏΡΠΎΡΡΠΈΡΠΈ. Π ΡΠΊΠΎΡΡΡ l Π²ΡΠ·ΡΠΌΠ΅ΠΌΠΎ ΡΠΎΡΠΊΡ (x0, y0), ΡΠΊΠ° ΠΌΠ°Ρ Π½Π°ΠΉΠΌΠ΅Π½ΡΡ Π°Π±ΡΡΠΈΡΡ, Π° Π² ΡΠΊΠΎΡΡΡ r Π²ΡΠ·ΡΠΌΠ΅ΠΌΠΎ ΡΠΎΡΠΊΡ (x0, y0 — e), Π΄Π΅ e — ΠΌΠ°Π»Π΅ Π΄ΠΎΠ΄Π°ΡΠ½Π΅ ΡΠΈΡΠ»ΠΎ. ΠΠ΅ΡΡΠΈΠΊΠ°Π»ΡΠ½Π° ΠΏΡΡΠΌΠ°, ΡΠΎ ΠΏΡΠΎΡ ΠΎΠ΄ΠΈΡΡ ΡΠ΅ΡΠ΅Π· l, Π±ΡΠ΄Π΅ ΠΏΠ΅ΡΡΠΎΡ ΠΏΡΡΠΌΠΎΡ, ΡΠΊΠ° ΡΠΎΠ·Π±ΠΈΠ²Π°Ρ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρ ΡΠΎΡΠΎΠΊ S. ΠΡΡΠ³ΠΎΡ ΠΏΡΡΠΌΠΎΡ Π±ΡΠ΄Π΅ ΠΏΡΡΠΌΠ°, ΡΠΎ ΠΏΡΠΎΡ ΠΎΠ΄ΠΈΡΡ ΡΠ΅ΡΠ΅Π· ΡΠΎΡΠΊΠΈ Π· Π΅ΠΊΡΡΡΠ΅ΠΌΠ°Π»ΡΠ½ΠΈΠΌΠΈ Π°Π±ΡΡΠΈΡΠ°ΠΌΠΈ.
Π§Π΅ΡΠ΅Π· * Π΄Π°Π»Ρ ΠΏΠΎΠ·Π½Π°ΡΠ΅Π½ΠΎ ΠΎΠΏΠ΅ΡΠ°ΡΡΡ ΠΊΠΎΠ½ΠΊΠ°ΡΠ΅Π½Π°ΡΡΡ ΡΠΏΠΈΡΠΊΡΠ².
Π¨Π²ΠΈΠ΄ΠΊΠ° ΠΎΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° (S, l, r).
if (S = {l, r}) then return (l, r) /* ΠΎΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΡΠΊΠ»Π°Π΄Π°ΡΡΡΡΡ Π· ΡΠ΄ΠΈΠ½ΠΎΠ³ΠΎ ΠΎΡΡΡΠ½ΡΠΎΠ²Π°Π½ΠΎΠ³ΠΎ ΡΠ΅Π±ΡΠ° */.
else.
begin.
h ΡΠ°ΠΌΠ° Π΄Π°Π»ΡΠ½Ρ ΡΠΎΡΠΊΠ° (S, l, r);
S1 ΡΠΎΡΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S, ΡΠΎΠ·ΡΠ°ΡΠΎΠ²Π°Π½Ρ Π·Π»ΡΠ²Π° Π²ΡΠ΄ ΠΏΡΡΠΌΠΎΡ lh ΡΠΈ Π½Π° Π½ΡΠΉ;
S2 ΡΠΎΡΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S, ΡΠΎΠ·ΡΠ°ΡΠΎΠ²Π°Π½Ρ Π·Π»ΡΠ²Π° Π²ΡΠ΄ ΠΏΡΡΠΌΠΎΡ hr ΡΠΈ Π½Π° Π½ΡΠΉ;
return Π¨Π²ΠΈΠ΄ΠΊΠ° ΠΎΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° (S1, l, r) * (Π¨Π²ΠΈΠ΄ΠΊΠ° ΠΎΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° (S2, h, r) — h);
end;
begin.
l0 (x0, y0) ΡΠΎΡΠΊΠ° ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Π· Π½Π°ΠΉΠΌΠ΅Π½ΡΠΎΡ Π°Π±ΡΡΠΈΡΠΎΡ;
r0 (x0, y0 — e);
Π¨Π²ΠΈΠ΄ΠΊΠ° ΠΎΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° (S, l0, r0);
Π²ΠΈΠ΄Π°Π»ΠΈΡΠΈ ΡΠΎΡΠΊΡ r0 /* ΡΠ΅ Π΅ΠΊΠ²ΡΠ²Π°Π»Π΅Π½ΡΠ½ΠΎ ΡΠΎΠΌΡ, ΡΠΊΡΠΎ ΠΏΠΎΠΊΠ»Π°ΡΡΠΈ e = 0 */.
end.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠΈΠΏΡ ΡΠΎΠ·Π΄ΡΠ»ΡΠΉ ΡΠ° ΠΏΠ°Π½ΡΠΉ ΠΡΠΈΠΏΡΡΡΠΈΠΌΠΎ, ΡΠΎ ΠΏΡΠΈ ΡΠΎΠ·Π²’ΡΠ·ΠΊΡ Π·Π°Π΄Π°ΡΡ ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΏΠΎΡΠ°ΡΠΊΠΎΠ²Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π° ΡΠΎΡΠΎΠΊ S Π±ΡΠ»Π° ΡΠΎΠ·Π±ΠΈΡΠ° Π½Π° Π΄Π²Ρ ΡΠ°ΡΡΠΈΠ½ΠΈ S1 ΡΠ° S2, ΠΊΠΎΠΆΠ½Π° Π· ΡΠΊΠΈΡ ΠΌΡΡΡΠΈΡΡ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Ρ ΡΠΎΡΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S. Π―ΠΊΡΠΎ ΡΠ΅ΠΏΠ΅Ρ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ Π·Π½Π°ΠΉΡΠΈ CH (S1) ΡΠ° CH (S2), ΡΠΎ ΠΎΠΏΡΠΊΠ»Ρ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S ΠΌΠΎΠΆΠ½Π° Π·Π½Π°ΠΉΡΠΈ Π· ΡΡΠ²Π½ΠΎΡΡΡ: CH (S1) = CH (CH (S1) (S2)). ΠΡΠΈ ΡΡΠΎΠΌΡ ΡΡΠ΅Π±Π° ΠΏΠ°ΠΌ’ΡΡΠ°ΡΠΈ, ΡΠΎ CH (S1) ΡΠ° CH (S2) — ΡΠ΅ ΠΎΠΏΡΠΊΠ»Ρ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠΈ. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΠ·Π΄ΡΠ»ΡΠΉ ΡΠ° ΠΏΠ°Π½ΡΠΉ ΠΌΠ°Ρ Π½Π°ΡΡΡΠΏΠ½ΠΈΠΉ Π²ΠΈΠ³Π»ΡΠ΄:
1. Π―ΠΊΡΠΎ |S| k (k — Π½Π΅Π²Π΅Π»ΠΈΠΊΠ΅ ΡΡΠ»Π΅ ΡΠΈΡΠ»ΠΎ), ΡΠΎ ΠΏΠΎΠ±ΡΠ΄ΡΠ²Π°ΡΠΈ ΠΎΠΏΡΠΊΠ»Ρ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡ ΠΎΠ΄Π½ΠΈΠΌ ΡΠ· ΠΏΡΡΠΌΠΈΡ ΠΌΠ΅ΡΠΎΠ΄ΡΠ² ΡΠ° Π·ΡΠΏΠΈΠ½ΠΈΡΠΈΡΡΡΠ½Π°ΠΊΡΠ΅ ΠΏΠ΅ΡΠ΅ΠΉΡΠΈ Π΄ΠΎ ΠΊΡΠΎΠΊΡ 2.
2. Π ΠΎΠ·Π±ΠΈΡΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρ S Π΄ΠΎΠ²ΡΠ»ΡΠ½ΠΈΠΌ ΡΠΈΠ½ΠΎΠΌ Π½Π° Π΄Π²Ρ ΠΏΡΠΈΠ±Π»ΠΈΠ·Π½ΠΎ ΡΡΠ²Π½Ρ Π·Π° ΠΏΠΎΡΡΠΆΠ½ΡΡΡΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S1 ΡΠ° S2.
3. Π Π΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ Π·Π½Π°ΠΉΡΠΈ ΠΎΠΏΡΠΊΠ»Ρ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ CH (S1) ΡΠ° CH (S2).
4. ΠΠ»ΠΈΡΠΈ Π΄Π²Ρ ΠΎΡΡΠΈΠΌΠ°Π½Ρ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, ΡΡΠ²ΠΎΡΠΈΠ²ΡΠΈ CH (S).
ΠΠ°Π΄Π°ΡΠ°. ΠΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΠΎΠ±'ΡΠ΄Π½Π°Π½Π½Ρ ΠΎΠΏΡΠΊΠ»ΠΈΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΡΠ². ΠΠ°Π½ΠΎ Π΄Π²Π° ΠΎΠΏΡΠΊΠ»ΠΈΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° P1 ΡΠ° P2. ΠΠ½Π°ΠΉΡΠΈ ΠΎΠΏΡΠΊΠ»Ρ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡ ΡΡ ΠΎΠ±'ΡΠ΄Π½Π°Π½Π½Ρ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π¨Π΅ΠΉΠΌΠΎΡΠ°.
1. ΠΠ½Π°ΠΉΡΠΈ Π΄Π΅ΡΠΊΡ Π²Π½ΡΡΡΡΡΠ½Ρ ΡΠΎΡΠΊΡ p ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° P1 — Π½Π°ΠΏΡΠΈΠΊΠ»Π°Π΄, ΡΠ΅Π½ΡΡΠΎΡΠ΄ ΡΡΡΠΎΡ Π΄ΠΎΠ²ΡΠ»ΡΠ½ΠΈΡ Π²Π΅ΡΡΠΈΠ½ P1. Π¦Ρ ΡΠΎΡΠΊΠ° Π±ΡΠ΄Π΅ Π²Π½ΡΡΡΡΡΠ½ΡΠΎΡ ΡΠΎΡΠΊΠΎΡ CH (P1).
2. ΠΠΈΠ·Π½Π°ΡΠΈΡΠΈ, ΡΠΈ Ρ p Π²Π½ΡΡΡΡΡΠ½ΡΠΎΡ ΡΠΎΡΠΊΠΎΡ P2. Π―ΠΊΡΠΎ p Π½Π΅ Ρ Π²Π½ΡΡΡΡΡΠ½ΡΠΎΡ ΡΠΎΡΠΊΠΎΡ P2, ΡΠΎ ΠΏΠ΅ΡΠ΅ΠΉΡΠΈ Π΄ΠΎ ΠΊΡΠΎΠΊΡ 4.
3. p Ρ Π²Π½ΡΡΡΡΡΠ½ΡΠΎΡ ΡΠΎΡΠΊΠΎΡ P2. ΠΠ΅ΡΡΠΈΠ½ΠΈ P1 ΡΠ° P2 Ρ Π²ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²Π°Π½ΠΈΠΌΠΈ Ρ Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π½ΠΎΡΡΡ Π·Ρ Π·Π½Π°ΡΠ΅Π½Π½ΡΠΌ ΠΏΠΎΠ»ΡΡΠ½ΠΎΠ³ΠΎ ΠΊΡΡΠ° Π²ΡΠ΄Π½ΠΎΡΠ½ΠΎ ΡΠΎΡΠΊΠΈ p. ΠΠ° ΡΠ°Ρ O (N) ΠΌΠΎΠΆΠ½Π° Π·Π»ΠΈΡΠΈ ΡΠΏΠΈΡΠΎΠΊ Π²Π΅ΡΡΠΈΠ½ ΡΠΈΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΡΠ², ΠΎΡΡΠΈΠΌΠ°Π²ΡΠΈ Π²ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²Π°Π½ΠΈΠΉ ΡΠΏΠΈΡΠΎΠΊ Π²Π΅ΡΡΠΈΠ½ ΡΠΊ P1, ΡΠ°ΠΊ Ρ P2. ΠΠ΅ΡΠ΅ΠΉΡΠΈ Π΄ΠΎ ΠΊΡΠΎΠΊΡ 5.
4. p Π½Π΅ Ρ Π²Π½ΡΡΡΡΡΠ½ΡΠΎΡ ΡΠΎΡΠΊΠΎΡ P2. Π―ΠΊΡΠΎ Π΄ΠΈΠ²ΠΈΡΠΈΡΡ Π· ΡΠΎΡΠΊΠΈ p, ΡΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊ P2 Π»Π΅ΠΆΠΈΡΡ Ρ ΠΊΠ»ΡΠ½Ρ Π· ΠΊΡΡΠΎΠΌ ΡΠΎΠ·Π²ΠΎΡΠΎΡΡ ΠΌΠ΅Π½ΡΠΈΠΌ ΡΠΈ ΡΡΠ²Π½ΠΈΠΌ Π¦Π΅ΠΉ ΠΊΠ»ΠΈΠ½ Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡΡΡ Π΄Π²ΠΎΠΌΠ° Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ u ΡΠ° v ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° P2, ΡΠΊΡ ΠΌΠΎΠΆΡΡΡ Π±ΡΡΠΈ Π·Π½Π°ΠΉΠ΄Π΅Π½Ρ Π·Π° Π»ΡΠ½ΡΠΉΠ½ΠΈΠΉ ΡΠ°Ρ Π·Π° ΠΎΠ΄ΠΈΠ½ ΠΎΠ±Ρ ΡΠ΄ Π²Π΅ΡΡΠΈΠ½ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° P2. Π¦Ρ Π²Π΅ΡΡΠΈΠ½ΠΈ ΡΠΎΠ·Π±ΠΈΠ²Π°ΡΡΡ Π³ΡΠ°Π½ΠΈΡΡ P2 Π½Π° Π΄Π²Π° Π»Π°Π½ΡΡΠ³Π° Π²Π΅ΡΡΠΈΠ½, ΡΠΊΡ Ρ ΠΌΠΎΠ½ΠΎΡΠΎΠ½Π½ΠΈΠΌΠΈ Π²ΡΠ΄Π½ΠΎΡΠ½ΠΎ Π·ΠΌΡΠ½ΠΈ ΠΏΠΎΠ»ΡΡΠ½ΠΎΠ³ΠΎ ΠΊΡΡΠ° Π· ΠΏΠΎΡΠ°ΡΠΊΠΎΠΌ Π² p. ΠΡΠΈ ΡΡΡΡ ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΌΡ Π»Π°Π½ΡΡΠ³Ρ ΠΊΡΡ Π·Π±ΡΠ»ΡΡΡΡΡΡΡΡ, ΠΏΡΠΈ ΡΡΡΡ ΠΏΠΎ Π΄ΡΡΠ³ΠΎΠΌΡ — Π·ΠΌΠ΅Π½ΡΡΡΡΡΡΡ. ΠΠ΄ΠΈΠ½ Π· Π»Π°Π½ΡΡΠ³ΡΠ², ΡΠΊΠΈΠΉ Ρ ΠΎΠΏΡΠΊΠ»ΠΈΠΌ ΠΏΠΎ Π½Π°ΠΏΡΡΠΌΠΊΡ Π΄ΠΎ ΡΠΎΡΠΊΠΈ p, ΠΌΠΎΠΆΠ΅ Π±ΡΡΠΈ Π²ΠΈΠ΄Π°Π»Π΅Π½ΠΈΠΉ, ΠΎΡΠΊΡΠ»ΡΠΊΠΈ ΠΉΠΎΠ³ΠΎ Π²Π΅ΡΡΠΈΠ½ΠΈ Π±ΡΠ΄ΡΡΡ Π²Π½ΡΡΡΡΡΠ½ΡΠΌΠΈ ΡΠΎΡΠΊΠ°ΠΌΠΈ CH (P1). ΠΡΡΠ³ΠΈΠΉ Π»Π°Π½ΡΡΠ³ P2 ΡΠ° Π³ΡΠ°Π½ΠΈΡΡ P1 ΠΌΠΎΠΆΠ½Π° Π·Π»ΠΈΡΠΈ Π² ΠΎΠ΄ΠΈΠ½ Π²ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²Π°Π½ΠΈΠΉ ΡΠΏΠΈΡΠΎΠΊ (Π·Π° ΠΏΠΎΠ»ΡΡΠ½ΠΈΠΌ ΠΊΡΡΠΎΠΌ Π²ΡΠ΄Π½ΠΎΡΠ½ΠΎ ΡΠΎΡΠΊΠΈ p) Π·Π° Π»ΡΠ½ΡΠΉΠ½ΠΈΠΉ ΡΠ°Ρ.
5. ΠΠΎ ΠΎΡΡΠΈΠΌΠ°Π½ΠΎΠ³ΠΎ Π²ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²Π°Π½ΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΡ Π²Π΅ΡΡΠΈΠ½ Π·Π°ΡΡΠΎΡΡΠ²Π°ΡΠΈ ΠΌΠ΅ΡΠΎΠ΄ ΠΎΠ±Ρ ΠΎΠ΄Ρ ΠΡΠ΅Ρ Π΅ΠΌΠ°, ΡΠΊΠΈΠΉ Π²ΠΈΠΌΠ°Π³Π°Ρ Π»ΡΠ½ΡΠΉΠ½ΠΈΠΉ ΡΠ°Ρ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΠΎΠ±'ΡΠ΄Π½Π°Π½Π½Ρ Π΄Π²ΠΎΡ ΠΎΠΏΡΠΊΠ»ΠΈΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΡΠ² ΠΌΠΎΠΆΠ΅ Π±ΡΡΠΈ Π·Π½Π°ΠΉΠ΄Π΅Π½Π° Π·Π° ΡΠ°Ρ, ΠΏΡΠΎΠΏΠΎΡΡΡΠΉΠ½ΠΈΠΉ ΡΡΠΌΠ°ΡΠ½ΡΠΉ ΠΊΡΠ»ΡΠΊΠΎΡΡΡ ΡΡ Π²Π΅ΡΡΠΈΠ½.
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. ΠΠΏΠΎΡΠ½ΠΎΡ ΠΏΡΡΠΌΠΎΡ Π΄ΠΎ ΠΎΠΏΡΠΊΠ»ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ ΠΏΡΡΠΌΠ° l, ΡΠΊΠ° ΠΏΡΠΎΡ ΠΎΠ΄ΠΈΡΡ ΡΠ΅ΡΠ΅Π· Π΄Π΅ΡΠΊΡ Π²Π΅ΡΡΠΈΠ½Ρ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° P ΡΠ°ΠΊΠΈΠΌ ΡΠΈΠ½ΠΎΠΌ, ΡΠΎ Π²Π½ΡΡΡΡΡΠ½Ρ ΡΠ°ΡΡΠΈΠ½Π° P ΡΡΠ»ΠΊΠΎΠΌ Π·Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡΡ ΠΏΠΎ ΠΎΠ΄Π½Ρ ΡΡΠΎΡΠΎΠ½Ρ Π²ΡΠ΄ l.
ΠΠΎΠ±ΡΡΠ½ΠΈΠΌ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠΎΠΌ ΠΎΠΏΠΈΡΠ°Π½ΠΎΠ³ΠΎ ΠΌΠ΅ΡΠΎΠ΄Π° Π·Π»ΠΈΡΡΡ Ρ Π·Π½Π°Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ ΠΎΠΏΠΎΡΠ½ΠΈΡ ΠΏΡΡΠΌΠΈΡ Π΄Π»Ρ Π΄Π²ΠΎΡ ΠΎΠΏΡΠΊΠ»ΠΈΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΡΠ². ΠΠ²Π° ΠΎΠΏΡΠΊΠ»ΠΈΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° P1 ΡΠ° P2 Π· n ΡΠ° m Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π½ΠΎ, ΡΠ°ΠΊΠΈΡ ΡΠΎ ΠΎΠ΄ΠΈΠ½ Π½Π΅ Π»Π΅ΠΆΠΈΡΡ ΡΡΠ»ΠΊΠΎΠΌ Π²ΡΠ΅ΡΠ΅Π΄ΠΈΠ½Ρ ΡΠ½ΡΠΎΠ³ΠΎ, ΠΌΠ°ΡΡΡ Π½Π΅ Π±ΡΠ»ΡΡ Π½ΡΠΆ 2 * min (n, m) ΠΎΠΏΠΎΡΠ½ΠΈΡ ΠΏΡΡΠΌΠΈΡ . Π―ΠΊΡΠΎ Π²ΠΆΠ΅ ΠΎΡΡΠΈΠΌΠ°Π½ΠΎ ΠΎΠΏΡΠΊΠ»Ρ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡ ΠΎΠ±'ΡΠ΄Π½Π°Π½Π½Ρ P1 ΡΠ° P2, ΡΠΎ ΠΎΠΏΠΎΡΠ½Ρ ΠΏΡΡΠΌΡ ΠΎΠ±ΡΠΈΡΠ»ΡΡΡΡΡΡ Π² ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ ΠΏΠ΅ΡΠ΅Π³Π»ΡΠ΄Ρ ΡΠΏΠΈΡΠΊΡ Π²Π΅ΡΡΠΈΠ½ CH (P1).
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠΎΠΆΠ½Π° ΠΏΠ°ΡΠ° ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½ CH (P1), ΠΎΠ΄Π½Π° Π· ΡΠΊΠΈΡ Π½Π°Π»Π΅ΠΆΠΈΡΡ P1, Π° Π΄ΡΡΠ³Π° P2, Π²ΠΈΠ·Π½Π°ΡΠ°Ρ ΠΎΠΏΠΎΡΠ½Ρ ΠΏΡΡΠΌΡ.
ΠΠΎΠ±ΡΠ΄ΠΎΠ²Π° ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΏΡΠΎΡΡΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΡ. ΠΠ΅Ρ Π°ΠΉ p1 — ΡΠ°ΠΌΠ° Π»ΡΠ²Π° Π²Π΅ΡΡΠΈΠ½Π° Π·Π°Π΄Π°Π½ΠΎΠ³ΠΎ ΠΏΡΠΎΡΡΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° P, Π° (p1, p2, …, pN) — Π²ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²Π°Π½Π° ΡΠΈΠΊΠ»ΡΡΠ½Π° ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΡΡΡΡ ΠΉΠΎΠ³ΠΎ Π²Π΅ΡΡΠΈΠ½ (Π·Π° Π²Π΅ΡΡΠΈΠ½ΠΎΡ pN ΠΉΠ΄Π΅ p1). ΠΠ½ΡΡΡΡΡΠ½ΡΡΡΡ P Π·Π°Π»ΠΈΡΠ°ΡΡΡΡΡ ΠΏΠΎ ΠΏΡΠ°Π²Ρ ΡΡΠΎΡΠΎΠ½Ρ ΠΏΡΠΈ ΠΎΠ±Ρ ΠΎΠ΄Ρ ΠΉΠΎΠ³ΠΎ Π³ΡΠ°Π½ΠΈΡΡ Π² ΡΠΊΠ°Π·Π°Π½ΠΎΠΌΡ ΠΏΠΎΡΡΠ΄ΠΊΡ. ΠΠ΅Ρ Π°ΠΉ pM — ΡΠ°ΠΌΠ° ΠΏΡΠ°Π²Π° Π²Π΅ΡΡΠΈΠ½Π°. p1 ΡΠ° pM Ρ Π³ΡΠ°Π½ΠΈΡΠ½ΠΈΠΌΠΈ ΡΠΎΡΠΊΠ°ΠΌΠΈ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° P. ΠΠΎΠ½ΠΈ ΡΠΎΠ·Π±ΠΈΠ²Π°ΡΡΡ ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΡΡΡΡ Π²Π΅ΡΡΠΈΠ½ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° Π½Π° Π΄Π²Π° Π»Π°Π½ΡΡΠ³ΠΈ: ΠΎΠ΄ΠΈΠ½ Π²ΡΠ΄ p1 Π΄ΠΎ pM, Π΄ΡΡΠ³ΠΈΠΉ — Π²ΡΠ΄ pM Π΄ΠΎ p1. ΠΠΎΡΡΠ°ΡΠ½ΡΠΎ Π΄ΠΎΡΠ»ΡΠ΄ΠΈΡΠΈ ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²Ρ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Π΄Π»Ρ Π»Π°Π½ΡΡΠ³Π° (p1, p2, …, pM), ΡΠΊΡ Π±ΡΠ΄Π΅ΠΌΠΎ Π½Π°Π·ΠΈΠ²Π°ΡΠΈ Π²Π΅ΡΡ Π½ΡΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΎΡ.
ΠΠ΅Ρ Π°ΠΉ (q1, q2, …, qR) — ΠΏΡΠ΄ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΡΡΡΡ (p1, p2, …, pM), Π² ΡΠΊΡΠΉ q1 = p1 ΡΠ° qR = pM — ΡΡΠΊΠ°Π½Π° ΠΎΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ°. ΠΠΎΠΆΠ½Π΅ ΡΠ΅Π±ΡΠΎ qiqi+1 Ρ «ΠΊΡΠΈΡΠΊΠΎΡ ΠΊΠ°ΡΠΌΠ°Π½Π°» Ki, Π΄Π΅ ΠΊΠ°ΡΠΌΠ°Π½ Ki — ΡΠ΅ Π»Π°Π½ΡΡΠ³ ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΠΎΡΡΡ (p1, p2, …, pM), ΠΏΠ΅ΡΡΠΎΡ ΡΠ° ΠΎΡΡΠ°Π½Π½ΡΠΎΡ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ ΡΠΊΠΎΡ Ρ qi ΡΠ° qi+1 Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π½ΠΎ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΡ ΠΏΡΠΎΡ ΠΎΠ΄ΠΈΡΡ Π»Π°Π½ΡΡΠ³ ΡΠ° ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΠΎ Π±ΡΠ΄ΡΡ ΠΊΡΠΈΡΠΊΠΈ ΡΡΡΡ ΠΊΠ°ΡΠΌΠ°Π½ΡΠ². ΠΡΠΈΡΠΈΡΠ½ΠΎΡ Π±ΡΠ΄Π΅ΠΌΠΎ Π½Π°Π·ΠΈΠ²Π°ΡΠΈ Π²Π΅ΡΡΠΈΠ½Ρ, ΡΠΊΠ° Π· ΠΎΡΡΠ°Π½Π½ΡΠΎΡ Π·Π½Π°ΠΉΠ΄Π΅Π½ΠΎΡ Π²Π΅ΡΡΠΈΠ½ΠΎΡ ΡΠΈΠΏΡ q ΡΡΠ²ΠΎΡΡΡ ΠΊΠ°ΡΠΌΠ°Π½. ΠΠ»Π΅ Π½Π΅ ΠΊΠΎΠΆΠ½Π° ΠΊΡΠΈΡΠΈΡΠ½Π° Π²Π΅ΡΡΠΈΠ½Π° Π½Π°Π»Π΅ΠΆΠΈΡΡ ΠΊΡΠ½ΡΠ΅Π²ΡΠΉ ΠΎΠΏΡΠΊΠ»ΡΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΡΡ. ΠΡΠΎΠΊΠΎΠΌ ΠΏΡΠΎΡΡΠ½Π΅Π½Π½Ρ Π±ΡΠ΄Π΅ΠΌΠΎ Π½Π°Π·ΠΈΠ²Π°ΡΠΈ ΠΏΠ΅ΡΠ΅Ρ ΡΠ΄ Π²ΡΠ΄ ΠΎΠ΄Π½ΡΡΡ ΠΊΡΠΈΡΠΈΡΠ½ΠΎΡ Π²Π΅ΡΡΠΈΠ½ΠΈ Π΄ΠΎ ΡΠ½ΡΠΎΡ. ΠΠ°ΠΏΡΠΈΠΊΠ»Π°Π΄, Π½Π° ΡΡΠ΅ΡΡΠΎΠΌΡ ΠΊΡΠΎΡΡ ΠΊΡΠΈΡΠΈΡΠ½ΠΎΡ ΡΠΎΡΠΊΠΎΡ Ρ p4. ΠΠ°ΡΡΡΠΏΠ½ΠΎΡ ΠΊΡΠΈΡΠΈΡΠ½ΠΎΡ ΡΠΎΡΠΊΠΎΡ Π±ΡΠ΄Π΅ p7. ΠΡΠΈ ΡΡΠΎΠΌΡ ΠΊΡΠΈΡΠΈΡΠ½Π° ΡΠΎΡΠΊΠ° p4 Π½Π΅ Π½Π°Π»Π΅ΠΆΠΈΡΡ ΠΎΠΏΡΠΊΠ»ΡΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΡΡ.
1 ΠΊΡΠΎΠΊ 2 ΠΊΡΠΎΠΊ 3 ΠΊΡΠΎΠΊ 4 ΠΊΡΠΎΠΊ.
ΠΡΠΈΠΏΡΡΡΠΈΠΌΠΎ, ΡΠΎ Π³ΡΠ°Π½ΠΈΡΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° ΠΏΡΠΎΠ³Π»ΡΠ½ΡΡΠ° Π²ΡΠ΄ Π²Π΅ΡΡΠΈΠ½ΠΈ p1 Π΄ΠΎ ps (s M) Ρ Π²Π΅ΡΡΠΈΠ½Π° ps = qi Ρ ΠΊΡΠΈΡΠΈΡΠ½ΠΎΡ. ΠΠΎΠ·Π½Π°ΡΠΈΠΌΠΎ ΡΠ΅ΡΠ΅Π· u Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°Π½ΠΈΡΡ Π , ΡΠΊΠ° Ρ ΠΏΠΎΠΏΠ΅ΡΠ΅Π΄Π½ΡΠΎΡ Π΄ΠΎ qi. Π Π·Π°Π»Π΅ΠΆΠ½ΠΎΡΡΡ Π²ΡΠ΄ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½Ρ u Π²ΡΠ΄Π½ΠΎΡΠ½ΠΎ ΠΎΡΡΡΠ½ΡΠΎΠ²Π°Π½ΠΎΠ³ΠΎ Π²ΡΠ΄ΡΡΠ·ΠΊΠ° qMqi ΠΌΠ°ΡΡΡ ΠΌΡΡΡΠ΅ Π΄Π²Π° Π²ΠΈΠΏΠ°Π΄ΠΊΠΈ:
1. ΠΠ΅ΡΡΠΈΠ½Π° u Π·Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡΡ ΡΠΏΡΠ°Π²Π° Π²ΡΠ΄ qMqi Π°Π±ΠΎ Π½Π° Π½ΡΠΎΠΌΡ. Π’ΠΎΠ΄Ρ ΡΡΠ΅Π±Π° Π΄ΠΎΡΠ»ΡΠ΄ΠΈΡΠΈ ΡΡΠΈ ΠΎΠ±Π»Π°ΡΡΡ, ΡΠΊΡ Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡΡΡ: ΠΏΡΡΠΌΠΎΡ, ΡΠΎ ΠΏΡΠΎΡ ΠΎΠ΄ΠΈΡΡ ΡΠ΅ΡΠ΅Π· ΡΠΎΡΠΊΠΈ qi-1 ΡΠ° qiΠΏΡΠΎΠΌΡΠ½Π΅ΠΌ, ΡΠΊΠΈΠΉ Ρ ΠΏΡΠΎΠ΄ΠΎΠ²ΠΆΠ΅Π½Π½ΡΠΌ Π²ΡΠ΄ΡΡΠ·ΠΊΡ qiu ΡΠ° ΡΠ°ΡΡΠΈΠ½ΠΎΡ ΡΠ° ΡΠ°ΡΡΠΈΠ½ΠΎΡ Π³ΡΠ°Π½ΠΈΡΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° P, ΡΠΊΠ° Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π°Ρ ΠΊΠ°ΡΠΌΠ°Π½Ρ Ki-1.
2. ΠΠ΅ΡΡΠΈΠ½Π° u Π·Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡΡ Π·Π»ΡΠ²Π° Π²ΡΠ΄ qMqi. ΠΠΎ Π΄ΠΎΡΠ»ΡΠ΄ΠΆΠ΅Π½Π½Ρ ΡΡΠ΅Π±Π° Π΄ΠΎΠ΄Π°ΡΠΈ ΡΠ΅ΡΠ²Π΅ΡΡΡ ΠΎΠ±Π»Π°ΡΡΡ.
ΠΠΎΠ·Π½Π°ΡΠΈΠΌΠΎ ΡΠ΅ΡΠ΅Π· v Π²Π΅ΡΡΠΈΠ½Ρ, ΡΠΊΠ° ΠΉΠ΄Π΅ Π·Π° qi Π½Π° Π³ΡΠ°Π½ΠΈΡΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° P. Π¦Ρ Π²Π΅ΡΡΠΈΠ½Π° v ΠΌΠΎΠΆΠ΅ Π·Π½Π°Ρ ΠΎΠ΄ΠΈΡΠΈΡΡ Π² ΠΎΠ΄Π½ΡΠΉ ΡΠ· ΠΎΠ±Π»Π°ΡΡΠ΅ΠΉ, ΡΠΊΡ Π²ΠΈΠ·Π½Π°ΡΠ΅Π½ΠΎ Π²ΠΈΡΠ΅. Π ΠΎΠ±Π»Π°ΡΡΡΡ 2 ΡΠ° 3 Π²Π΅ΡΡΠΈΠ½Π° v Π±ΡΠ΄Π΅ ΠΊΡΠΈΡΠΈΡΠ½ΠΎΡ, Π² ΡΠ½ΡΠΈΡ — Π½Ρ. ΠΠΎΡΠ»ΡΠ΄ΠΈΠΌΠΎ Π²ΠΈΠΏΠ°Π΄ΠΊΠΈ ΡΠΎΠ·ΡΠ°ΡΡΠ²Π°Π½Π½Ρ Π²Π΅ΡΡΠΈΠ½ΠΈ v Π² ΠΊΠΎΠΆΠ½ΡΠΉ ΡΠ· ΡΠΈΡ ΠΎΠ±Π»Π°ΡΡΠ΅ΠΉ.
ΠΠ±Π»Π°ΡΡΡ 1. ΠΡΠ°Π½ΠΈΡΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° Π·Π°Ρ ΠΎΠ΄ΠΈΡΡ Π΄ΠΎ ΠΊΠ°ΡΠΌΠ°Π½Ρ. Π ΡΡ Π°ΡΠΌΠΎΡΡ ΠΏΠΎ Π³ΡΠ°Π½ΠΈΡΡ Π΄ΠΎ ΡΠΈΡ ΠΏΡΡ, ΠΏΠΎΠΊΠΈ Π½Π΅ Π΄ΠΎΡΡΠ³Π½Π΅ΠΌΠΎ ΠΏΠ΅ΡΡΠΎΠ³ΠΎ ΡΠ΅Π±ΡΠ° Π³ΡΠ°Π½ΠΈΡΡ, ΠΎΠ΄Π½Π° Π· Π²Π΅ΡΡΠΈΠ½ w ΡΠΊΠΎΠ³ΠΎ Π·Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡΡ Π·ΠΎΠ²Π½Ρ ΠΊΠ°ΡΠΌΠ°Π½Π° (ΡΠΎΠ±ΡΠΎ Π² ΠΎΠ±Π»Π°ΡΡΡ 2). Π¦Π΅ ΠΎΠ±ΠΎΠ²’ΡΠ·ΠΊΠΎΠ²ΠΎ Π²ΡΠ΄Π±ΡΠ΄Π΅ΡΡΡΡ, ΠΎΡΠΊΡΠ»ΡΠΊΠΈ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊ ΠΏΡΠΎΡΡΠΈΠΉ.
ΠΠ±Π»Π°ΡΡΡ 2. Π¨ΡΠΊΠ°ΡΡΡΡΡ ΠΎΠΏΠΎΡΠ½Π° ΠΏΡΡΠΌΠ° Π· Π²Π΅ΡΡΠΈΠ½ΠΈ v Π΄ΠΎ Π»Π°Π½ΡΡΠ³Π° (q1, q2, …, qi-1). Π―ΠΊΡΠΎ ΡΡ ΠΏΡΡΠΌΠ° ΠΌΡΡΡΠΈΡΡ qr (r < i), ΡΠΎ Π²Π΅ΡΡΠΈΠ½ΠΈ (qr+1, qr+2, …, qi) Π²ΠΈΠ΄Π°Π»ΡΡΡΡΡΡ, Π° v Π±Π΅ΡΠ΅ΡΡΡΡ Π² ΡΠΊΠΎΡΡΡ Π½ΠΎΠ²ΠΎΡ qr+1.
ΠΠ±Π»Π°ΡΡΡ 3. ΠΠ΅ΡΡΠΈΠ½Π° v Ρ ΠΊΡΠΈΡΠΈΡΠ½ΠΎΡ Ρ Π±Π΅ΡΠ΅ΡΡΡΡ Π² ΡΠΊΠΎΡΡΡ qi+1.
ΠΠ±Π»Π°ΡΡΡ 4. ΠΡΠ°Π½ΠΈΡΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° Π·Π°Ρ ΠΎΠ΄ΠΈΡΡ Π²ΡΠ΅ΡΠ΅Π΄ΠΈΠ½Ρ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ. Π―ΠΊ Ρ Π² ΠΏΠ΅ΡΡΠΎΠΌΡ Π²ΠΈΠΏΠ°Π΄ΠΊΡ Π±ΡΠ΄Π΅ΠΌΠΎ ΡΡΡ Π°ΡΠΈΡΡ ΠΏΠΎ Π³ΡΠ°Π½ΠΈΡΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° Π΄ΠΎ ΡΠΈΡ ΠΏΡΡ, ΠΏΠΎΠΊΠΈ Π½Π΅ Π΄ΠΎΡΡΠ³Π½Π΅ΠΌΠΎ ΠΏΠ΅ΡΡΠΎΠ³ΠΎ ΡΠ΅Π±ΡΠ°, ΡΠΊΠ΅ ΠΌΠ°Ρ Π½Π°ΡΡΡΠΏΠ½Ρ Π²Π»Π°ΡΡΠΈΠ²ΠΎΡΡΡ: ΠΎΠ΄Π½Π° Π· ΠΉΠΎΠ³ΠΎ Π²Π΅ΡΡΠΈΠ½ Ρ Π·ΠΎΠ²Π½ΡΡΠ½ΡΠΎΡ ΠΏΠΎ Π²ΡΠ΄Π½ΠΎΡΠ΅Π½Π½Ρ Π΄ΠΎ ΠΎΠ±Π»Π°ΡΡΡ 4 Π°Π±ΠΎ ΡΠΏΡΠ²ΠΏΠ°Π΄Π°Ρ Π· qM.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΠΏΡΠΎΡΡΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° Π· N Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ ΠΌΠΎΠΆΠ΅ Π±ΡΡΠΈ ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²Π°Π½Π° Π·Π° ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΈΠΉ ΡΠ°Ρ O (N) Π· Π²ΠΈΠΊΠΎΡΠΈΡΡΠ°Π½Π½ΡΠΌ ΠΏΠ°ΠΌ’ΡΡΡ ΠΎΠ±'ΡΠΌΠΎΠΌ O (N).
ΠΠΈΠ½Π°ΠΌΡΡΠ½Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΈ ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. ΠΠ»Π³ΠΎΡΠΈΡΠΌ, ΡΠΊΠΈΠΉ ΠΎΠ±ΡΠΎΠ±Π»ΡΡ Π΄Π°Π½Ρ ΠΏΠΎ ΠΌΡΡΡ ΡΡ Π½Π°Π΄Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ, Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ Π²ΡΠ΄ΠΊΡΠΈΡΠΈΠΌ. ΠΠ»Π³ΠΎΡΠΈΡΠΌ, ΡΠΊΠΈΠΉΠΎΠ±ΡΠΎΠ±Π»ΡΡ Π²ΡΡ ΡΡΠΊΡΠΏΠ½ΡΡΡΡ Π΄Π°Π½ΠΈΡ Π²ΡΡΠ»ΠΎΠΌΡ, Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ Π·Π°ΠΊΡΠΈΡΠΈΠΌ.
ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. Π§Π°ΡΠΎΠ²ΠΈΠΉ ΠΏΡΠΎΠΌΡΠΆΠΎΠΊ ΠΌΡΠΆ Π²Π²ΠΎΠ΄ΠΎΠΌ Π΄Π²ΠΎΡ ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΠΈΡ Π΅Π»Π΅ΠΌΠ΅Π½ΡΡΠ² Π΄Π°Π½ΠΈΡ Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ Π·Π°ΡΡΠΈΠΌΠΊΠΎΡ Π½Π°Π΄Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ Π΄Π°Π½ΠΈΡ .
ΠΠ°Π΄Π°ΡΠ°. ΠΡΠ΄ΠΊΡΠΈΡΠΈΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π΄Π»Ρ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ. ΠΠ° ΠΏΠ»ΠΎΡΠΈΠ½Ρ Π·Π°Π΄Π°Π½Π° ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΡΡΡΡ N ΡΠΎΡΠΎΠΊ p1, p2, …, pN. ΠΠ΅ΠΎΠ±Ρ ΡΠ΄Π½ΠΎ Π·Π½Π°ΠΉΡΠΈ ΡΡ ΠΎΠΏΡΠΊΠ»Ρ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡ ΡΠ°ΠΊΠΈΠΌ ΡΠΈΠ½ΠΎΠΌ, ΡΠΎΠ± ΠΏΡΡΠ»Ρ ΠΎΠ±ΡΠΎΠ±ΠΊΠΈ ΡΠΎΡΠΊΠΈ pi Π±ΡΠ»Π° ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²Π°Π½Π° CH (p1, p2, …, pi). ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠ²ΠΈΠ½Π΅Π½ ΠΏΡΠ΄ΡΡΠΈΠΌΡΠ²Π°ΡΠΈ Π΄Π΅ΡΠΊΠ΅ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Π½Ρ ΠΏΠΎΡΠΎΡΠ½ΠΎΡ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΡΠ° ΠΊΠΎΡΠ΅ΠΊΡΡΠ²Π°ΡΠΈ ΠΉΠΎΠ³ΠΎ ΠΏΠΎ ΠΌΡΡΡ Π½Π°Π΄Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ ΡΠΎΡΠΎΠΊ.
Π―ΠΊΡΠΎ Π½Π΅ Π±ΡΠ°ΡΠΈ Π΄ΠΎ ΡΠ²Π°Π³ΠΈ ΡΠ°ΡΠΎΠ²Ρ ΠΎΡΡΠ½ΠΊΡ, ΡΠΎ ΠΌΠΎΠΆΠ½Π° Π·Π°ΠΏΡΠΎΠΏΠΎΠ½ΡΠ²Π°ΡΠΈ Π½Π°ΡΡΡΠΏΠ½ΠΈΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ:
1. ΠΠ²ΠΎΠ΄ΠΈΡΠΈ ΡΠΎΡΠΊΠΈ ΠΏΠΎΠΊΠΈ Π½Π΅ Π±ΡΠ΄Π΅ Π·Π½Π°ΠΉΠ΄Π΅Π½ΠΎ ΡΡΠΈ Π½Π΅ΠΊΠΎΠ»ΡΠ½Π΅Π°ΡΠ½Ρ ΡΠΎΡΠΊΠΈ. ΠΡ ΡΠ΅Π½ΡΡΠΎΡΠ΄ Π±ΡΠ΄Π΅ Π²Π½ΡΡΡΡΡΠ½ΡΠΎΡ ΡΠΎΡΠΊΠΎΡ ΠΊΡΠ½ΡΠ΅Π²ΠΎΡ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, Π° ΠΎΡΠΆΠ΅ ΠΏΡΠ΄Ρ ΠΎΠ΄ΠΈΡΡ Π² ΡΠΊΠΎΡΡΡ ΠΏΠΎΡΠ°ΡΠΊΡ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°Ρ, Π²ΡΠ΄Π½ΠΎΡΠ½ΠΎ ΡΠΊΠΎΠ³ΠΎ Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡΡΡ ΠΏΠΎΠ»ΡΡΠ½Ρ ΠΊΡΡΠΈ ΡΠΎΡΠΎΠΊ ΠΏΡΠΈ ΡΠΎΡΡΡΠ²Π°Π½Π½Ρ.
2. ΠΡΠ΄ΡΡΠΈΠΌΡΠ²Π°ΡΠΈ Π·Π²’ΡΠ·Π°Π½ΠΈΠΉ ΡΠΏΠΈΡΠΎΠΊ Π²ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²Π°Π½ΠΈΡ ΠΊΡΠ°ΠΉΠ½ΡΡ ΡΠΎΡΠΎΠΊ. ΠΡΠΈ Π½Π°Π΄Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ ΡΠΎΡΠΊΠΈ pi Π²ΡΡΠ°Π²ΠΈΡΠΈ ΡΡ Ρ ΡΠΏΠΈΡΠΎΠΊ Π²ΡΠ΄ΠΏΠΎΠ²ΡΠ΄Π½ΠΎ Π΄ΠΎ ΡΡ ΠΏΠΎΠ»ΡΡΠ½ΠΎΠ³ΠΎ ΠΊΡΡΠ°, Π²ΠΈΡΡΠ°ΡΠΈΠ²ΡΠΈ ΡΠ°Ρ O (i).
3. ΠΠΈΠΊΠΎΠ½Π°ΡΠΈ ΠΏΠ΅ΡΠ΅Π³Π»ΡΠ΄ Π·Π²’ΡΠ·Π°Π½ΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΡ ΠΊΡΠ°ΠΉΠ½ΡΡ ΡΠΎΡΠΎΠΊΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΡΠ΅Ρ Π΅ΠΌΠ°. ΠΠΎΠΆΠ»ΠΈΠ²Ρ ΡΡΠΈ Π²Π°ΡΡΠ°Π½ΡΠΈ ΡΡΠΎΠ³ΠΎ ΠΊΡΠΎΠΊΡ:
Π°) ΡΠΎΡΠΊΠ° pi Ρ ΠΊΡΠ°ΠΉΠ½ΡΠΎΡ Ρ ΡΡ Π²ΠΊΠ»ΡΡΠ΅Π½Π½Ρ Π²ΠΈΠΊΠ»ΠΈΠΊΠ°Ρ Π²ΠΈΠ΄Π°Π»Π΅Π½Π½Ρ Π΄Π΅ΡΠΊΠΈΡ ΡΠ½ΡΠΈΡ ΡΠΎΡΠΎΠΊ;
Π±) ΡΠΎΡΠΊΠ° pi Ρ ΠΊΡΠ°ΠΉΠ½ΡΠΎΡ, Π°Π»Π΅ ΡΡ Π²ΠΊΠ»ΡΡΠ΅Π½Π½Ρ Π½Π΅ Π²ΠΈΠΊΠ»ΠΈΠΊΠ°Ρ Π²ΠΈΠ΄Π°Π»Π΅Π½Π½Ρ ΡΠ½ΡΠΈΡ ΡΠΎΡΠΎΠΊ;
Π²) ΡΠΎΡΠΊΠ° pi Ρ Π²Π½ΡΡΡΡΡΠ½ΡΠΎΡ Ρ ΡΠΎΠΌΡ Π²ΠΎΠ½Π° Π²ΠΈΠ΄Π°Π»ΡΡΡΡΡΡ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠΎΠ²ΡΠ»ΡΠ½ΠΈΠΉ Π²ΡΠ΄ΠΊΡΠΈΡΠΈΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡΠΊΠ»ΠΎΡ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Π² Π½Π°ΠΉΠ³ΡΡΡΠΎΠΌΡ Π²ΠΈΠΏΠ°Π΄ΠΊΡ ΠΏΠΎΠ²ΠΈΠ½Π΅Π½ Π²ΠΈΡΡΠ°ΡΡΠ²Π°ΡΠΈ Π½Π° ΠΎΠ±ΡΠΎΠ±ΠΊΡ ΠΌΡΠΆ Π½Π°Π΄Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½ΡΠΌ ΠΏΠΎΡΠ»ΡΠ΄ΠΎΠ²Π½ΠΈΡ Π΅Π»Π΅ΠΌΠ΅Π½ΡΡΠ² Π΄Π°Π½ΠΈΡ ΡΠ°Ρ O (log N).
ΠΡΠ΅ΠΊΡΠΈΠ²Π½ΡΡΡΡ Π²ΡΠ΄ΠΊΡΠΈΡΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΏΠΎΠ»ΡΠ³Π°Ρ Ρ ΠΌΠΎΠΆΠ»ΠΈΠ²ΠΎΡΡΡ ΡΠ²ΠΈΠ΄ΠΊΠΎ Π±ΡΠ΄ΡΠ²Π°ΡΠΈ Π΄Π²Ρ ΠΎΠΏΠΎΡΠ½Ρ ΠΏΡΡΠΌΡ Π΄ΠΎ ΠΎΠΏΡΠΊΠ»ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ°, ΡΠΎ ΠΏΡΠΎΡ ΠΎΠ΄ΡΡΡ ΡΠ΅ΡΠ΅Π· Π·Π°Π΄Π°Π½Ρ ΡΠΎΡΠΊΡ. ΠΠΎΠ·Π½Π°ΡΠΈΠΌΠΎ ΡΠ΅ΡΠ΅Π· Ci-1 ΠΎΠΏΡΠΊΠ»Ρ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ {p1, p2, …, pi-1}. ΠΠ΅ΠΎΠ±Ρ ΡΠ΄Π½ΠΎ ΠΏΠΎΠ±ΡΠ΄ΡΠ²Π°ΡΠΈ Π· ΡΠΎΡΠΊΠΈ pi ΠΎΠΏΠΎΡΠ½Ρ ΠΏΡΡΠΌΡ Π΄ΠΎ Ci-1, ΡΠΊΡΠΎ Π²ΠΎΠ½ΠΈ ΡΡΠ½ΡΡΡΡ (ΠΊΠΎΠ»ΠΈ pi Ρ Π·ΠΎΠ²Π½ΡΡΠ½ΡΠΎΡ Π΄Π»Ρ Ci-1). ΠΡΠ΄Π΅ΠΌΠΎ Π½Π°Π·ΠΈΠ²Π°ΡΠΈ ΠΎΠΏΠΎΡΠ½Ρ ΠΏΡΡΠΌΡ Π»ΡΠ²ΠΎΡ ΡΠΈ ΠΏΡΠ°Π²ΠΎΡ Π² Π·Π°Π»Π΅ΠΆΠ½ΠΎΡΡΡ Π²ΡΠ΄ ΡΠΎΠ³ΠΎ, ΠΏΠΎ ΡΠΊΡ ΡΡΠΎΡΠΎΠ½Ρ Π²ΠΎΠ½Π° Π·Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡΡ ΡΠΊΡΠΎ Π΄ΠΈΠ²ΠΈΡΠΈΡΡ Π· ΡΠΎΡΠΊΠΈ pi Π½Π° Ci-1.
p.
.p.
.v.
.v.
.v.
..ΠΎΠΏΡΠΊΠ»Π°.
.ΠΎΠΏΠΎΡΠ½Π°.
.Π²ΠΎΠ³Π½ΡΡΠ°.
..ΠΠ·Π½Π°ΡΠ΅Π½Π½Ρ. ΠΠ΅ΡΡΠΈΠ½Π° v Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ Π²ΠΎΠ³Π½ΡΡΠΎΡ, ΡΠΊΡΠΎ Π²ΡΠ΄ΡΡΠ·ΠΎΠΊ pv ΠΏΠ΅ΡΠ΅ΡΠΈΠ½Π°Ρ Π²Π½ΡΡΡΡΡΠ½Ρ ΡΠ°ΡΡΠΈΠ½Ρ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ°. Π―ΠΊΡΠΎ Π΄Π²Ρ ΡΡΠΌΡΠΆΠ½Ρ Π· v Π²Π΅ΡΡΠΈΠ½ΠΈ Π»Π΅ΠΆΠ°ΡΡ ΠΏΠΎ ΠΎΠ΄Π½Ρ ΡΡΠΎΡΠΎΠ½Ρ Π²ΡΠ΄ ΠΏΡΡΠΌΠΎΡ, ΡΠΎ ΠΏΡΠΎΡ ΠΎΠ΄ΠΈΡΡ ΡΠ΅ΡΠ΅Π· p ΡΠ° v, ΡΠΎ Π²Π΅ΡΡΠΈΠ½Π° Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ ΠΎΠΏΠΎΡΠ½ΠΎΡ. ΠΠ½Π°ΠΊΡΠ΅ Π²Π΅ΡΡΠΈΠ½Π° Π½Π°Π·ΠΈΠ²Π°ΡΡΡΡΡ ΠΎΠΏΡΠΊΠ»ΠΎΡ.
Π―ΠΊΡΠΎ v — ΠΎΠΏΠΎΡΠ½Π° Π²Π΅ΡΡΠΈΠ½Π°, ΡΠΎ ΡΠΎΠ·Π²’ΡΠ·ΠΎΠΊ Π·Π°Π΄Π°ΡΡ Π·Π°Π²Π΅ΡΡΡΡΡΡΡΡ. ΠΠ½Π°ΠΊΡΠ΅ Π±ΡΠ΄ΡΡΠΌΠΎ ΠΎΠΏΠΎΡΠ½Ρ ΠΏΡΡΠΌΡ. ΠΠ»Ρ Π·Π½Π°Ρ ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ, Π½Π°ΠΏΡΠΈΠΊΠ»Π°Π΄, Π»ΡΠ²ΠΎΡ ΠΎΠΏΠΎΡΠ½ΠΎΡ ΠΏΡΡΠΌΠΎΡ, Π½Π΅ΠΎΠ±Ρ ΡΠ΄Π½ΠΎ ΡΡΡ Π°ΡΠΈΡΡ ΠΏΠΎ Π²Π΅ΡΡΠΈΠ½Π°ΠΌ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΡΠ½ΠΈΠΊΠ° ΠΏΡΠΎΡΠΈ ΡΠΈ Π·Π° Π³ΠΎΠ΄ΠΈΠ½Π½ΠΈΠΊΠΎΠ²ΠΎΡ ΡΡΡΡΠ»ΠΊΠΎΡ (Π² Π·Π°Π»Π΅ΠΆΠ½ΠΎΡΡΡ Π²ΡΠ΄ ΠΎΠΏΡΠΊΠ»ΠΎΡΡΡ ΡΠΈ Π²ΠΎΠ³Π½ΡΡΠΎΡΡΡ Π²Π΅ΡΡΠΈΠ½ΠΈ v). Π’Π°ΠΊΠΈΠΌ ΡΠΈΠ½ΠΎΠΌ Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡΡΡ Π΄Π²Ρ ΠΎΠΏΠΎΡΠ½Ρ ΡΠΎΡΠΊΠΈ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠΏΡΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Π· N ΡΠΎΡΠΎΠΊ Π½Π° ΠΏΠ»ΠΎΡΠΈΠ½Ρ ΠΌΠΎΠΆΠ΅ Π±ΡΡΠΈ ΠΏΠΎΠ±ΡΠ΄ΠΎΠ²Π°Π½Π° Π·Π° Π΄ΠΎΠΏΠΎΠΌΠΎΠ³ΠΎΡ Π²ΡΠ΄ΠΊΡΠΈΡΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ Π·Π° ΡΠ°Ρ O (N * log N) Π· ΡΠ°ΡΠΎΠΌ ΠΊΠΎΡΠ΅ΠΊΡΡΡ O (log N).