ΠΠΈΠΏΠ΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΈΠΌΠ΅Π΅Ρ ΠΌΠ΅ΡΡΠΎ ΠΏΡΠΈ Π²ΡΠ±ΠΎΡΠΎΡΠ½ΠΎΠΌ ΠΊΠΎΠ½ΡΡΠΎΠ»Π΅ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠΉ ΡΠΎΠ²ΠΎΠΊΡΠΏΠ½ΠΎΡΡΠΈ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΎΠ±ΡΠ΅ΠΌΠ° N ΠΏΠΎ Π°Π»ΡΡΠ΅ΡΠ½Π°ΡΠΈΠ²Π½ΠΎΠΌΡ ΠΏΡΠΈΠ·Π½Π°ΠΊΡ. ΠΠ°ΠΆΠ΄ΡΠΉ ΠΊΠΎΠ½ΡΡΠΎΠ»ΠΈΡΡΠ΅ΠΌΡΠΉ ΠΎΠ±ΡΠ΅ΠΊΡ ΠΊΠ»Π°ΡΡΠΈΡΠΈΡΠΈΡΡΠ΅ΡΡΡ Π»ΠΈΠ±ΠΎ ΠΊΠ°ΠΊ ΠΎΠ±Π»Π°Π΄Π°ΡΡΠΈΠΉ ΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠΌ Π, Π»ΠΈΠ±ΠΎ ΠΊΠ°ΠΊ Π½Π΅ ΠΎΠ±Π»Π°Π΄Π°ΡΡΠΈΠΉ ΡΡΠΈΠΌ ΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠΌ. ΠΠΈΠΏΠ΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΈΠΌΠ΅Π΅Ρ ΡΠ»ΡΡΠ°ΠΉΠ½Π°Ρ Π²Π΅Π»ΠΈΡΠΈΠ½Π° Π£, ΡΠ°Π²Π½Π°Ρ ΡΠΈΡΠ»Ρ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ², ΠΎΠ±Π»Π°Π΄Π°ΡΡΠΈΡ
ΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠΌ Π Π² ΡΠ»ΡΡΠ°ΠΉΠ½ΠΎΠΉ Π²ΡΠ±ΠΎΡΠΊΠ΅ ΠΎΠ±ΡΠ΅ΠΌΠ° ΠΏ, Π³Π΄Π΅ ΠΏ < N. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, ΡΠΈΡΠ»ΠΎ Π£ Π΄Π΅ΡΠ΅ΠΊΡΠ½ΡΡ
Π΅Π΄ΠΈΠ½ΠΈΡ ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ Π² ΡΠ»ΡΡΠ°ΠΉΠ½ΠΎΠΉ Π²ΡΠ±ΠΎΡΠΊΠ΅ ΠΎΠ±ΡΠ΅ΠΌΠ° ΠΏ ΠΈΠ· ΠΏΠ°ΡΡΠΈΠΈ ΠΎΠ±ΡΠ΅ΠΌΠ° N ΠΈΠΌΠ΅Π΅Ρ Π³ΠΈΠΏΠ΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅, Π΅ΡΠ»ΠΈ ΠΏ < N. ΠΡΡΠ³ΠΎΠΉ ΠΏΡΠΈΠΌΠ΅Ρ — Π»ΠΎΡΠ΅ΡΠ΅Ρ. ΠΡΡΡΡ ΠΏΡΠΈΠ·Π½Π°ΠΊ Π Π±ΠΈΠ»Π΅ΡΠ° — ΡΡΠΎ ΠΏΡΠΈΠ·Π½Π°ΠΊ «Π±ΡΡΡ Π²ΡΠΈΠ³ΡΡΡΠ½ΡΠΌ». ΠΡΡΡΡ Π²ΡΠ΅Π³ΠΎ Π±ΠΈΠ»Π΅ΡΠΎΠ² N, Π° Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ΅ Π»ΠΈΡΠΎ ΠΏΡΠΈΠΎΠ±ΡΠ΅Π»ΠΎ ΠΏ ΠΈΠ· Π½ΠΈΡ
. Π’ΠΎΠ³Π΄Π° ΡΠΈΡΠ»ΠΎ Π²ΡΠΈΠ³ΡΡΡΠ½ΡΡ
Π±ΠΈΠ»Π΅ΡΠΎΠ² Ρ ΡΡΠΎΠ³ΠΎ Π»ΠΈΡΠ° ΠΈΠΌΠ΅Π΅Ρ Π³ΠΈΠΏΠ΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅.
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π΅ΡΠ»ΠΈ Π² ΠΏΠ°ΡΡΠΈΠΈ ΠΈΠ· N ΠΈΠ·Π΄Π΅Π»ΠΈΠΉ ΠΈΠΌΠ΅Π΅ΡΡΡ Π ΡΡΠ°Π½Π΄Π°ΡΡΠ½ΡΡ
(Π < ΠΠ ΠΈ ΠΈΠ· ΠΏΠ°ΡΡΠΈΠΈ ΡΠ»ΡΡΠ°ΠΉΠ½ΠΎ ΠΎΡΠ±ΠΈΡΠ°ΡΡ ΠΏ ΠΈΠ·Π΄Π΅Π»ΠΈΠΉ (ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΠΈΠ·Π΄Π΅Π»ΠΈΠ΅ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΈΠ·Π²Π»Π΅ΡΠ΅Π½ΠΎ Ρ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎΠΉ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΡΡ), ΠΏΡΠΈΡΠ΅ΠΌ ΠΎΡΠΎΠ±ΡΠ°Π½Π½ΠΎΠ΅ ΠΈΠ·Π΄Π΅Π»ΠΈΠ΅ ΠΏΠ΅ΡΠ΅Π΄ ΠΎΡΠ±ΠΎΡΠΎΠΌ ΡΠ»Π΅Π΄ΡΡΡΠ΅Π³ΠΎ Π½Π΅ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅ΡΡΡ Π² ΠΏΠ°ΡΡΠΈΡ, ΡΠΎ ΡΠΎΡΠΌΡΠ»Π° ΠΠ΅ΡΠ½ΡΠ»Π»ΠΈ Π·Π΄Π΅ΡΡ Π½Π΅ ΠΏΡΠΈΠΌΠ΅Π½ΠΈΠΌΠ°.
ΠΠ±ΠΎΠ·Π½Π°ΡΠΈΠ² ΡΠ΅ΡΠ΅Π· X ΡΠ»ΡΡΠ°ΠΉΠ½ΡΡ Π²Π΅Π»ΠΈΡΠΈΠ½Ρ — ΡΠΈΡΠ»ΠΎ Ρ ΡΡΠ°Π½Π΄Π°ΡΡΠ½ΡΡ
ΠΈΠ·Π΄Π΅Π»ΠΈΠΉ ΡΡΠ΅Π΄ΠΈ ΠΏ ΠΎΡΠΎΠ±ΡΠ°Π½Π½ΡΡ
(Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΠΌΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌΠΈ X.
Π±ΡΠ΄ΡΡ 0, 1, 2… min (Π, ΠΏ)), ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠΈ, ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌ, ΡΡΠΎ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΡ ΡΠΎΠ³ΠΎ, ΡΡΠΎ ΡΡΠ΅Π΄ΠΈ ΠΏ ΠΎΡΠΎΠ±ΡΠ°Π½Π½ΡΡ
ΠΈΠ·Π΄Π΅Π»ΠΈΠΉ ΡΠΎΠ²Π½ΠΎ Ρ ΡΡΠ°Π½Π΄Π°ΡΡΠ½ΡΡ
Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½Π°.
ΠΠΈΡΠΊΡΠ΅ΡΠ½Π°Ρ ΡΠ»ΡΡΠ°ΠΉΠ½Π°Ρ Π²Π΅Π»ΠΈΡΠΈΠ½Π° ΠΈΠΌΠ΅Π΅Ρ Π³ΠΈΠΏΠ΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅, Π΅ΡΠ»ΠΈ Π΅Π΅ Π·Π°ΠΊΠΎΠ½ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΠΈΠΌΠ΅Π΅Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΉ Π²ΠΈΠ΄:
Π³Π΄Π΅ Ρ = 0, 1, 2, min (M, ΠΏ).
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π³ΠΈΠΏΠ΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ ΡΡΠ΅ΠΌΡ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠ°ΠΌΠΈ — ΠΎΠ±ΡΠ΅ΠΌΠΎΠΌ Π³Π΅Π½Π΅ΡΠ°Π»ΡΠ½ΠΎΠΉ ΡΠΎΠ²ΠΎΠΊΡΠΏΠ½ΠΎΡΡΠΈ N, ΡΠΈΡΠ»ΠΎΠΌ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² Π Π² Π½Π΅ΠΉ, ΠΎΠ±Π»Π°Π΄Π°ΡΡΠΈΡ
ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΠΌΡΠΌ ΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠΌ Ρ, ΠΈ ΠΎΠ±ΡΠ΅ΠΌΠΎΠΌ Π²ΡΠ±ΠΎΡΠΊΠΈ ΠΏ.
Π€ΡΠ½ΠΊΡΠΈΡ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠΈ Π³ΠΈΠΏΠ΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Π° Π½Π° ΡΠΈΡ. 9.21.
Π ΠΈΡ. 9.21. Π€ΡΠ½ΠΊΡΠΈΡ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠΈ Π³ΠΈΠΏΠ΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΠΏΡΠΈ N = 60, Π = 20.
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠΈ ΠΏΡΠΈ Π³ΠΈΠΏΠ΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠΌ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ. Π‘ΡΠ΅Π΄ΠΈ 50 Π°Π½ΠΊΠ΅Ρ 20 Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Ρ Π»ΠΈΡΠ°ΠΌΠΈ Ρ Π²ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ. ΠΠ°ΠΉΡΠΈ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΡ ΡΠΎΠ³ΠΎ, ΡΡΠΎ ΡΡΠ΅Π΄ΠΈ Π½Π°ΡΠ΄Π°ΡΡ ΠΈΠ·Π²Π»Π΅ΡΠ΅Π½Π½ΡΡ
5 Π°Π½ΠΊΠ΅Ρ ΠΎΠΊΠ°ΠΆΠ΅ΡΡΡ ΡΠΎΠ²Π½ΠΎ 3 Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Π½ΡΡ
Π»ΠΈΡΠ°ΠΌΠΈ Ρ Π²ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ. ΠΠΎ ΡΡΠ»ΠΎΠ²ΠΈΡ, Π₯ = 50, Π = 20, ΠΏ = 5, Ρ — 3. ΠΡΠΊΠΎΠΌΠ°Ρ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΡ ΡΠ°Π²Π½Π°.
Π ΡΡΠ°ΡΠΈΡΡΠΈΡΠ΅ΡΠΊΠΈΡ
ΠΌΠ΅ΡΠΎΠ΄Π°Ρ
ΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ ΠΊΠ°ΡΠ΅ΡΡΠ²ΠΎΠΌ ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ ΠΏΠΎΠ΄Π»Π΅ΠΆΠ°ΡΠΈΠΌ ΠΎΡΠ΅Π½ΠΈΠ²Π°Π½ΠΈΡ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠΌ Π³ΠΈΠ½Π΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠΈΡΠ»ΠΎ Π΄Π΅ΡΠ΅ΠΊΡΠ½ΡΡ
Π΅Π΄ΠΈΠ½ΠΈΡ ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ Π² ΠΏΠ°ΡΡΠΈΠΈ (?)) Π²ΡΠ±ΠΎΡΠΊΠΈ (ΠΏ) ΠΈΠ· Π³Π΅Π½Π΅ΡΠ°Π»ΡΠ½ΠΎΠΉ ΡΠΎΠ²ΠΎΠΊΡΠΏΠ½ΠΎΡΡΠΈ (Π). ΠΠΎΡΡΠΎΠΌΡ Ρ
Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΡΡΠΈΠΊΠΎΠΉ Π³ΠΈΠΏΠ΅ΡΠ³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΡΠΎΠ²Π΅Π½Ρ Π΄Π΅ΡΠ΅ΠΊΡΠ½ΠΎΡΡΠΈ (Π/Π).