ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ Π½Π° Π³ΡΠ°ΡΠ°Ρ
.
ΠΠ΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠ΅ ΠΈ Π΄ΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠΈΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°
ΠΡΠ½ΠΎΠ²Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π² Π²ΡΠ±ΠΎΡΠ΅ ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ°. ΠΠ²Π΅Π΄Π΅ΠΌ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ Gg Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ Π½ΠΎΠΌΠ΅ΡΠΎΠ² Π²Π΅ΡΡΠΈΠ½ — ΠΊΠ°Π½Π΄ΠΈΠ΄Π°ΡΠΎΠ² Π½Π° ΡΠ°ΡΡΠΈΡΠ΅Π½ΠΈΠ΅ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ. ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠΎΡΠΌΠΈΡΡΠ΅ΡΡΡ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ k. Π§ΡΠΎ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠ΅ΠΉ Π΄Π»Ρ ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ Gg? ΠΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, ΡΡΠΎ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½, ΡΠ²ΠΎΠ΅ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ°Π³Π° (ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ) Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°. ΠΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈ ΠΏΡΠ°Π²ΠΎΠΌΠ΅ΡΠ½ΠΎ ΡΠ°Π·Π±ΠΈΡΡ ΡΡΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ Π½Π° Π³ΡΠ°ΡΠ°Ρ . ΠΠ΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠ΅ ΠΈ Π΄ΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠΈΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΡΡΡΠΎΠ²Π°Ρ ΡΠ°Π±ΠΎΡΠ°
" ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ Π½Π° Π³ΡΠ°ΡΠ°Ρ . ΠΠ΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠ΅ ΠΈ Π΄ΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠΈΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°"
ΠΠΏΡΠ΅Π΄Π΅Π»ΠΈΠΌ Π³ΡΠ°Ρ ΠΊΠ°ΠΊ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ V ΠΈ Π½Π°Π±ΠΎΡ E Π½Π΅ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΡ ΠΈ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΡ ΠΏΠ°Ρ Π²Π΅ΡΡΠΈΠ½ ΠΈ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠΈΠΌ G=(V, E). ΠΠΎΡΠ½ΠΎΡΡΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² V ΠΈ E Π±ΡΠ΄Π΅ΠΌ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°ΡΡ Π±ΡΠΊΠ²Π°ΠΌΠΈ N ΠΈ M. ΠΠ΅ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½Π°Ρ ΠΏΠ°ΡΠ° Π²Π΅ΡΡΠΈΠ½ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠ΅Π±ΡΠΎΠΌ, Π° ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½Π°Ρ ΠΏΠ°ΡΠ° — Π΄ΡΠ³ΠΎΠΉ. ΠΡΠ°Ρ, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΠΉ ΡΠΎΠ»ΡΠΊΠΎ ΡΠ΅Π±ΡΠ°, Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌ; Π³ΡΠ°Ρ, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΠΉ ΡΠΎΠ»ΡΠΊΠΎ Π΄ΡΠ³ΠΈ, — ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌ, ΠΈΠ»ΠΈ ΠΎΡΠ³ΡΠ°ΡΠΎΠΌ. ΠΠ΅ΡΡΠΈΠ½Ρ, ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π½ΡΠ΅ ΡΠ΅Π±ΡΠΎΠΌ, Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΡΠΌΠ΅ΠΆΠ½ΡΠΌΠΈ. Π Π΅Π±ΡΠ°, ΠΈΠΌΠ΅ΡΡΠΈΠ΅ ΠΎΠ±ΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ, ΡΠ°ΠΊΠΆΠ΅ Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΡΠΌΠ΅ΠΆΠ½ΡΠΌΠΈ. Π Π΅Π±ΡΠΎ ΠΈ Π»ΡΠ±Π°Ρ ΠΈΠ· Π΅Π³ΠΎ Π΄Π²ΡΡ Π²Π΅ΡΡΠΈΠ½ Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΡΠΌΠΈ. ΠΠΎΠ²ΠΎΡΡΡ, ΡΡΠΎ ΡΠ΅Π±ΡΠΎ (u, v) ΡΠΎΠ΅Π΄ΠΈΠ½ΡΠ΅Ρ Π²Π΅ΡΡΠΈΠ½Ρ u ΠΈ v. ΠΠ°ΠΆΠ΄ΡΠΉ Π³ΡΠ°Ρ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠ΅Π΄ΡΡΠ°Π²ΠΈΡΡ Π½Π° ΠΏΠ»ΠΎΡΠΊΠΎΡΡΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ ΡΠΎΡΠ΅ΠΊ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΡ Π²Π΅ΡΡΠΈΠ½Π°ΠΌ, ΠΊΠΎΡΠΎΡΡΠ΅ ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Ρ Π»ΠΈΠ½ΠΈΡΠΌΠΈ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΌΠΈ ΡΠ΅Π±ΡΠ°ΠΌ. Π ΡΡΠ΅Ρ ΠΌΠ΅ΡΠ½ΠΎΠΌ ΠΏΡΠΎΡΡΡΠ°Π½ΡΡΠ²Π΅ Π»ΡΠ±ΠΎΠΉ Π³ΡΠ°Ρ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠ΅Π΄ΡΡΠ°Π²ΠΈΡΡ ΡΠ°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΡΡΠΎ Π»ΠΈΠ½ΠΈΠΈ (ΡΠ΅Π±ΡΠ°) Π½Π΅ Π±ΡΠ΄ΡΡ ΠΏΠ΅ΡΠ΅ΡΠ΅ΠΊΠ°ΡΡΡΡ.
Π‘ΠΏΠΎΡΠΎΠ±Ρ ΠΎΠΏΠΈΡΠ°Π½ΠΈΡ. ΠΡΠ±ΠΎΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ ΡΡΡΡΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ Π΄Π»Ρ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡ Π³ΡΠ°ΡΠ° ΠΈΠΌΠ΅Π΅Ρ ΠΏΡΠΈΠ½ΡΠΈΠΏΠΈΠ°Π»ΡΠ½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΏΡΠΈ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠ΅ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ². ΠΡΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠΈ Π·Π°Π΄Π°Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΡΠ΅ΡΡΡΠ΅ ΠΎΡΠ½ΠΎΠ²Π½ΡΡ ΡΠΏΠΎΡΠΎΠ±Π° ΠΎΠΏΠΈΡΠ°Π½ΠΈΡ Π³ΡΠ°ΡΠ°: ΠΌΠ°ΡΡΠΈΡΠ° ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠΈΠΉ; ΠΌΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ; ΡΠΏΠΈΡΠΊΠΈ ΡΠ²ΡΠ·ΠΈ ΠΈ ΠΏΠ΅ΡΠ΅ΡΠ½ΠΈ ΡΠ΅Π±Π΅Ρ. ΠΡ Π±ΡΠ΄Π΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΠΎΠ»ΡΠΊΠΎ Π΄Π²Π°: ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΈ ΠΏΠ΅ΡΠ΅ΡΠ΅Π½Ρ ΡΠ΅Π±Π΅Ρ.
ΠΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ — ΡΡΠΎ Π΄Π²ΡΠΌΠ΅ΡΠ½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² ΡΠ°Π·ΠΌΠ΅ΡΠ½ΠΎΡΡΠΈ N*N.
A [i, j]=
ΠΠ»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ ΠΏΠ΅ΡΠ΅ΡΠ½Ρ ΡΠ΅Π±Π΅Ρ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌ Π΄Π²ΡΠΌΠ΅ΡΠ½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² R ΡΠ°Π·ΠΌΠ΅ΡΠ½ΠΎΡΡΠΈ M*2. Π‘ΡΡΠΎΠΊΠ° ΠΌΠ°ΡΡΠΈΠ²Π° ΠΎΠΏΠΈΡΡΠ²Π°Π΅Ρ ΡΠ΅Π±ΡΠΎ.
1. ΠΠ΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°
ΠΠ°Π΄Π°ΡΠ° ΠΏΠΎΠΈΡΠΊΠ° ΠΏΠΎΠ΄ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π²Π΅ΡΡΠΈΠ½ V Π³ΡΠ°ΡΠ° G, ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΡΡΡΠΈΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΌ ΡΡΠ»ΠΎΠ²ΠΈΡΠΌ, ΡΠ²ΠΎΠΉΡΡΠ²Π°ΠΌ, Π²ΠΎΠ·Π½ΠΈΠΊΠ°Π΅Ρ Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ ΡΠ°ΡΡΠΎ.
ΠΠ°Π½ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ Π³ΡΠ°Ρ G=(V, E). ΠΠ΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π΅ΡΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ° G, ΡΠ°ΠΊΠΎΠ΅, ΡΡΠΎ Π»ΡΠ±ΡΠ΅ Π΄Π²Π΅ Π²Π΅ΡΡΠΈΠ½Ρ Π² Π½Π΅ΠΌ Π½Π΅ ΡΠΌΠ΅ΠΆΠ½Ρ, ΡΠΎ Π΅ΡΡΡ Π½ΠΈΠΊΠ°ΠΊΠ°Ρ ΠΏΠ°ΡΠ° Π²Π΅ΡΡΠΈΠ½ Π½Π΅ ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π° ΡΠ΅Π±ΡΠΎΠΌ. Π‘Π»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, Π»ΡΠ±ΠΎΠ΅ ΠΏΠΎΠ΄ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ S, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠ΅Π΅ΡΡ Π² V, ΠΈ ΡΠ°ΠΊΠΎΠ΅, ΡΡΠΎ ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ S Ρ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ Π²Π΅ΡΡΠΈΠ½ ΡΠΌΠ΅ΠΆΠ½ΡΡ Ρ S ΠΏΡΡΡΠΎ, ΡΠ²Π»ΡΠ΅ΡΡΡ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ Π²Π΅ΡΡΠΈΠ½.
ΠΡΠΈΠΌΠ΅Ρ.
ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π²Π΅ΡΡΠΈΠ½ (1, 2), (3, 4, 5), (4, 7), (5, 6) — Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠ΅. ΠΠ΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ, ΠΊΠΎΠ³Π΄Π° Π½Π΅Ρ Π΄ΡΡΠ³ΠΎΠ³ΠΎ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°, Π² ΠΊΠΎΡΠΎΡΠΎΠ΅ ΠΎΠ½ΠΎ Π±Ρ Π²Ρ ΠΎΠ΄ΠΈΠ»ΠΎ. ΠΡΠ»ΠΈ Q ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ΅ΠΌΠ΅ΠΉΡΡΠ²ΠΎΠΌ Π²ΡΠ΅Ρ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² Π³ΡΠ°ΡΠ° G, ΡΠΎ ΡΠΈΡΠ»ΠΎ
[G]=maxS
SQ
Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΈΡΠ»ΠΎΠΌ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ Π³ΡΠ°ΡΠ° G, Π° ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ S*, Π½Π° ΠΊΠΎΡΠΎΡΠΎΠΌ ΡΡΠΎΡ ΠΌΠ°ΠΊΡΠΈΠΌΡΠΌ Π΄ΠΎΡΡΠΈΠ³Π°Π΅ΡΡΡ, Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΌ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ. ΠΠ»Ρ Π½Π°ΡΠ΅Π³ΠΎ ΠΏΡΠΈΠΌΠ΅ΡΠ° [G]=3, Π° S* Π΅ΡΡΡ (3, 4, 5).
ΠΠΎΠ½ΡΡΠΈΠ΅, ΠΏΡΠΎΡΠΈΠ²ΠΎΠΏΠΎΠ»ΠΎΠΆΠ½ΠΎΠ΅ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌΡ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠΌΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Ρ, Π΅ΡΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΠΎΠ»Π½ΡΠΉ ΠΏΠΎΠ΄Π³ΡΠ°Ρ (ΠΊΠ»ΠΈΠΊΠ°). Π ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π΅ Π½Π΅Ρ ΡΠΌΠ΅ΠΆΠ½ΡΡ Π²Π΅ΡΡΠΈΠ½, Π² ΠΊΠ»ΠΈΠΊΠ΅ Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΠΎΠΏΠ°ΡΠ½ΠΎ ΡΠΌΠ΅ΠΆΠ½Ρ. ΠΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π³ΡΠ°ΡΠ° G ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ ΠΊΠ»ΠΈΠΊΠ΅ Π³ΡΠ°ΡΠ° G', Π³Π΄Π΅ G' - Π΄ΠΎΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π³ΡΠ°ΡΠ° G.
ΠΠ»Ρ Π½Π°ΡΠ΅Π³ΠΎ ΠΏΡΠΈΠΌΠ΅ΡΠ° Π΄ΠΎΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ G' ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½ΠΎ Π½Π° ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ ΡΠΈΡΡΠ½ΠΊΠ΅, ΠΊΠ»ΠΈΠΊΠ° Π³ΡΠ°ΡΠ° G' ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌΡ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠΌΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Ρ Π³ΡΠ°ΡΠ° G. Π§ΠΈΡΠ»ΠΎ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ Π³ΡΠ°ΡΠ° G' ΡΠ°Π²Π½ΠΎ 4, ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ (2, 5, 7, 8), Π΅ΠΌΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ ΠΊΠ»ΠΈΠΊΠ° Π³ΡΠ°ΡΠ° G.
2. ΠΠ΅ΡΠΎΠ΄ Π³Π΅Π½Π΅ΡΠ°ΡΠΈΠΈ Π²ΡΠ΅Ρ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΡ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² Π³ΡΠ°ΡΠ°
ΠΠ°Π΄Π°ΡΠ° ΡΠ΅ΡΠ°Π΅ΡΡΡ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠΎΠΌ Π²Π°ΡΠΈΠ°Π½ΡΠΎΠ². «ΠΠ·ΡΠΌΠΈΠ½ΠΊΠΎΠΉ» ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΡΡΡΡΡΡΠ²ΠΈΠ΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎΡΡΠΈ Π·Π°ΠΏΠΎΠΌΠΈΠ½Π°ΡΡ Π³Π΅Π½Π΅ΡΠΈΡΡΠ΅ΠΌΡΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Ρ ΡΠ΅Π»ΡΡ ΠΏΡΠΎΠ²Π΅ΡΠΊΠΈ ΠΈΡ Π½Π° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΡΡΡ ΠΏΡΡΠ΅ΠΌ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡ Ρ ΡΠ°Π½Π΅Π΅ ΡΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°ΠΌΠΈ. ΠΠ΄Π΅Ρ Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΠΌ ΡΠ°ΡΡΠΈΡΠ΅Π½ΠΈΠΈ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° (k — Π½ΠΎΠΌΠ΅Ρ ΡΠ°Π³Π° ΠΈΠ»ΠΈ Π½ΠΎΠΌΠ΅Ρ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ Π² ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ). ΠΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, ΡΡΠΎ Π΅ΡΠ»ΠΈ ΠΌΡ Π½Π΅ ΠΌΠΎΠΆΠ΅ΠΌ ΡΠ°ΡΡΠΈΡΠΈΡΡ ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅, ΡΠΎ Π½Π°ΠΉΠ΄Π΅Π½ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ. ΠΡΠ²Π΅Π΄Π΅ΠΌ Π΅Π³ΠΎ ΠΈ ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠΈΠΌ ΠΏΡΠΎΡΠ΅ΡΡ ΠΏΠΎΠΈΡΠΊΠ°. ΠΡΠ΄Π΅ΠΌ Ρ ΡΠ°Π½ΠΈΡΡ ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Ss (Ss:array [1..N] of integer), Π΅Π³ΠΎ ΠΏΠ΅ΡΠ²ΡΠ΅ k ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. ΠΠΎΠ³ΠΈΠΊΠ° Π²ΡΠ²ΠΎΠ΄Π°.
procedure Print (k:integer);
var i: byte;
begin
writeln; for i:=1 to k do write (Ss[i], ' `);
end;
Π ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π½Π°ΠΌ ΠΏΡΠΈΠ΄Π΅ΡΡΡ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΠ°ΡΠ½ΠΎ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ°, ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Ρ Π΄Π°Π½Π½ΠΎΠΉ. ΠΡΠΈ ΠΎΠΏΠΈΡΠ°Π½ΠΈΠΈ Π³ΡΠ°ΡΠ° ΠΌΠ°ΡΡΠΈΡΠ΅ΠΉ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ — ΡΡΠΎ ΠΏΡΠΎΡΠΌΠΎΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ ΡΡΡΠΎΠΊΠΈ, ΠΏΡΠΈ ΠΎΠΏΠΈΡΠ°Π½ΠΈΠΈ ΡΠΏΠΈΡΠΊΠ°ΠΌΠΈ ΡΠ²ΡΠ·ΠΈ — ΠΏΡΠΎΡΠΌΠΎΡΡ ΡΠΏΠΈΡΠΊΠ°. Π£ΠΏΡΠΎΡΡΠΈΠΌ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ ΡΠΌΠ΅ΠΆΠ½ΡΡ Π²Π΅ΡΡΠΈΠ½ Π·Π° ΡΡΠ΅Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ Π½ΠΎΠ²ΠΎΠ³ΠΎ ΡΠΏΠΎΡΠΎΠ±Π° ΠΎΠΏΠΈΡΠ°Π½ΠΈΡ Π³ΡΠ°ΡΠ°. ΠΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π΅Π½Π½ΡΠΉ ΡΠΈΠΏ Π΄Π°Π½Π½ΡΡ . ΠΠ²Π΅Π΄Π΅ΠΌ ΡΠΈΠΏ Π΄Π°Π½Π½ΡΡ :
type Sset=set of 1. N; ΠΈ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ
var A: array [1.N] of Sset;.
ΠΡΠ°ΠΊ, ΡΡΠΎΠ±Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ°, ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ i, Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΡΠΎΡΡΠΎ Π²ΡΠ·Π²Π°ΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΠ²Π° A.
ΠΡΠΈΠΌΠ΅Ρ.
ΠΡΠ½ΠΎΠ²Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π² Π²ΡΠ±ΠΎΡΠ΅ ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ°. ΠΠ²Π΅Π΄Π΅ΠΌ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ Gg Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ Π½ΠΎΠΌΠ΅ΡΠΎΠ² Π²Π΅ΡΡΠΈΠ½ — ΠΊΠ°Π½Π΄ΠΈΠ΄Π°ΡΠΎΠ² Π½Π° ΡΠ°ΡΡΠΈΡΠ΅Π½ΠΈΠ΅ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ. ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠΎΡΠΌΠΈΡΡΠ΅ΡΡΡ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ k. Π§ΡΠΎ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠ΅ΠΉ Π΄Π»Ρ ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ Gg? ΠΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, ΡΡΠΎ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½, ΡΠ²ΠΎΠ΅ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ°Π³Π° (ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ) Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°. ΠΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈ ΠΏΡΠ°Π²ΠΎΠΌΠ΅ΡΠ½ΠΎ ΡΠ°Π·Π±ΠΈΡΡ ΡΡΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π½Π° Π½Π΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Π½ΡΠ΅ ΡΠ°Π½Π΅Π΅ (Qp) ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Π½ΡΠ΅ ΡΠ°Π½Π΅Π΅ (Qm). ΠΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ Qp ΠΈ Qm ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡ ΠΏΡΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ΅ Π½Π° Π²ΡΠ±ΠΎΡ k-Π³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°. ΠΡ Π²ΡΠ±ΠΈΡΠ°Π»ΠΈ Π½Π° k ΡΠ°Π³Π΅, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π²Π΅ΡΡΠΈΠ½Ρ Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ i, ΠΈ Π΅ΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎ ΠΈΡΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ Π΅Π΅ ΠΈΠ· Qp ΠΈ Qm ΠΏΡΠΈ ΠΏΠΎΠΈΡΠΊΠ΅ ΡΠ»Π΅Π΄ΡΡΡΠ΅Π³ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°. ΠΡΠΎΠΌΠ΅ ΡΠΎΠ³ΠΎ, ΠΏΡΠΈ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄Π΅ ΠΊ ΡΠ°Π³Ρ Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ (k+1) ΠΈΠ· ΡΠ΅ΠΊΡΡΠΈΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² Qp ΠΈ Qm Π΄Π»Ρ ΡΠ»Π΅Π΄ΡΡΡΠ΅Π³ΠΎ ΡΠ°Π³Π° Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΈΡΠΊΠ»ΡΡΠΈΡΡ Π²Π΅ΡΡΠΈΠ½Ρ, ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ i, Π²ΡΠ±ΡΠ°Π½Π½ΠΎΠΉ Π½Π° Π΄Π°Π½Π½ΠΎΠΌ ΡΠ°Π³Π΅ (ΠΈΠ· ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°) ΠΈ, ΡΠ°Π·ΡΠΌΠ΅ΡΡΡ, ΡΠ°ΠΌΡ Π²Π΅ΡΡΠΈΠ½Ρ i. ΠΡΠ°ΠΊ, ΠΎΠ±ΡΠ°Ρ Π»ΠΎΠ³ΠΈΠΊΠ°.
procedure Find (k:integer; Qp, Qm: Sset);
var Gg: Sset;
i:byte;
begin
if (Qp=[]) and (Qm=[]) then begin Print (k); exit end;
{ΡΠ΅ΡΠ½ΡΠΉ ΡΡΠΈΠΊ Π}
<οΏ½ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΠΊΠ°Π½Π΄ΠΈΠ΄Π°ΡΠΎΠ² Gg Π΄Π»Ρ ΡΠ°ΡΡΠΈΡΠ΅Π½ΠΈΡ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ (k ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Ss) ΠΏΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌ Qp ΠΈ Qm>;
i:=1;
while i<=N do begin
if i in Gg then begin
Ss[k]: =i;
Find (k+1, Qp-A[i] - [i], Qm-A[i] - [i]);
{ΡΠ΅ΡΠ½ΡΠΉ ΡΡΠΈΠΊ Π}
<οΏ½ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Qp, Qm Π΄Π»Ρ ΡΡΠΎΠ³ΠΎ ΡΡΠΎΠ²Π½Ρ (Π·Π½Π°ΡΠ΅Π½ΠΈΡ k) ΠΈ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ, ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΠΊΠ°Π½Π΄ΠΈΠ΄Π°ΡΠΎΠ² Gg>;
end;
Inc (i);
end; {while}
end; {Find}
ΠΡΠΎΠ΄ΠΎΠ»ΠΆΠΈΠΌ ΡΡΠΎΡΠ½Π΅Π½ΠΈΠ΅ Π»ΠΎΠ³ΠΈΠΊΠΈ. ΠΠ°ΠΌ ΠΏΠΎΡΡΠ΅Π±ΡΠ΅ΡΡΡ ΠΏΡΠΎΡΡΠ°Ρ ΡΡΠ½ΠΊΡΠΈΡ ΠΏΠΎΠ΄ΡΡΠ΅ΡΠ° ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π² ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΡΠΈΠΏΠ° Sset.
function Number (A: Sset):byte;
var i, cnt: byte;
begin
cnt:=0; for i:=1 to N do if i in A then Inc (cnt); Number:=cnt;
end;
ΠΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌ ΠΌΠ΅ΡΠΎΠ΄ ΡΡΠ°ΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π΄Π»Ρ ΡΠΎΠ³ΠΎ, ΡΡΠΎΠ±Ρ Π½Π°ΠΉΡΠΈ Π΄Π°Π»ΡΠ½Π΅ΠΉΡΡΡ Π»ΠΎΠ³ΠΈΠΊΡ ΡΡΠΎΡΠ½Π΅Π½ΠΈΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ. ΠΡΠ΄Π΅ΠΌ Π΄Π΅Π»Π°ΡΡ ΡΠ°Π·ΡΡΠ²Ρ ΡΠ°Π±Π»ΠΈΡΡ Π΄Π»Ρ Π²Π½Π΅ΡΠ΅Π½ΠΈΡ ΠΏΠΎΡΡΠ½Π΅Π½ΠΈΠΉ Π² ΡΠ°Π±ΠΎΡΡ ΡΠ΅ΡΠ½ΡΡ ΡΡΠΈΠΊΠΎΠ².
k | Qp | Qm | Gg | Ss | ΠΡΠΈΠΌΠ΅ΡΠ°Π½ΠΈΡ | |
[1.5] | [] | [1.5] | (1) | ΠΡΠ±ΠΈΡΠ°Π΅ΠΌ ΠΏΠ΅ΡΠ²ΡΡ Π²Π΅ΡΡΠΈΠ½Ρ | ||
[4,5] | [] | [4,5] | (1,4) | ΠΡΠ°ΠΊ, ΠΏΠ΅ΡΠ²ΠΎΠ΅ ΡΡΠΎΡΠ½Π΅Π½ΠΈΠ΅ ΡΠ΅ΡΠ½ΠΎΠ³ΠΎ ΡΡΠΈΠΊΠ° Π. | ||
if Qm<>[] then <οΏ½ΡΠ΅ΡΠ½ΡΠΉ ΡΡΠΈΠΊ ΠΠ >
else Gg:=Qp;
ΠΠ³ΠΎ ΡΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎ Π΅ΡΠ»ΠΈ Π²ΡΠ±ΠΈΡΠ°ΡΡ ΠΈΠ· ΡΠ°Π½Π΅Π΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Π½ΡΡ Π²Π΅ΡΡΠΈΠ½ Π½Π΅ΡΠ΅Π³ΠΎ, ΡΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΊΠ°Π½Π΄ΠΈΠ΄Π°ΡΠΎΠ² ΡΠΎΠ²ΠΏΠ°Π΄Π°Π΅Ρ ΡΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ Qp, ΠΈ Π΄Π°Π»Π΅Π΅ ΠΏΠΎ Π»ΠΎΠ³ΠΈΠΊΠ΅ ΠΌΡ «ΡΡΠΏΠΎ» Π²ΡΠ±ΠΈΡΠ°Π΅ΠΌ ΠΏΠ΅ΡΠ²ΡΡ Π²Π΅ΡΡΠΈΠ½Ρ ΠΈΠ· Qp. ΠΠ΅ΡΠ΅Ρ ΠΎΠ΄ΠΈΠΌ ΠΊ ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌΡ Π²ΡΠ·ΠΎΠ²Ρ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ Find.
[] | [] | [] | (1,4) | ΠΡΠ²ΠΎΠ΄ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΠΈ Π²ΡΡ ΠΎΠ΄ Π² ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΡΡ ΠΊΠΎΠΏΠΈΡ Find. | ||
[5] | [4] | [5] | (1,5) | ΠΡΠΊΠ»ΡΡΠ°Π΅ΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 4 ΠΈΠ· Qp ΠΈ Π²ΠΊΠ»ΡΡΠ°Π΅ΠΌ Π΅Π΅ Π² Qm. | ||
ΠΡΠΎΠ΄ΠΎΠ»ΠΆΠ°Π΅Ρ ΡΠ°Π±ΠΎΡΡ ΡΠΈΠΊΠ» while ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ Find. ΠΡΠ±ΠΈΡΠ°Π΅ΠΌ ΡΠ»Π΅Π΄ΡΡΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ — ΡΡΠΎ Π²Π΅ΡΡΠΈΠ½Π° 5. Π Π²ΡΠ·ΡΠ²Π°Π΅ΠΌ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ Find Ρ Π΄ΡΡΠ³ΠΈΠΌΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌΠΈ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ².
[] | [] | [] | (1,5) | ΠΡΠ²ΠΎΠ΄ Π²ΡΠΎΡΠΎΠ³ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°. | ||
[] | [4,5] | [] | Π¦ΠΈΠΊΠ» while Π·Π°ΠΊΠΎΠ½ΡΠ΅Π½, Π²ΡΡ ΠΎΠ΄ Π² ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΡΡ ΠΊΠΎΠΏΠΈΡ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ Find. | |||
Π£ΡΠΎΡΠ½Π΅Π½ΠΈΠ΅ ΡΠ΅ΡΠ½ΠΎΠ³ΠΎ ΡΡΠΈΠΊΠ° Π. ΠΠ΅ΡΠ²ΠΎΠ΅: Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΈΡΠΊΠ»ΡΡΠΈΡΡ Π²Π΅ΡΡΠΈΠ½Ρ i ΠΈΠ· Qp ΠΈ Π²ΠΊΠ»ΡΡΠΈΡΡ Π΅Π΅ Π² Qm. ΠΡΠΎΡΠΎΠ΅: ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΎΡΠΊΠΎΡΡΠ΅ΠΊΡΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Gg. ΠΡΠ±ΠΎΡ Π½Π° ΡΡΠΎΠΌ ΡΠ°Π³Π΅ Π²Π΅ΡΡΠΈΠ½, Π½Π΅ ΡΠΌΠ΅ΠΆΠ½ΡΡ Ρ i, ΠΏΡΠΈΠ²Π΅Π΄Π΅Ρ ΠΊ Π³Π΅Π½Π΅ΡΠ°ΡΠΈΠΈ ΠΏΠΎΠ²ΡΠΎΡΡΡΡΠΈΡ ΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΡ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ², ΠΏΠΎΡΡΠΎΠΌΡ ΡΠ»Π΅Π΄ΡΠ΅Ρ Π²ΡΠ±ΠΈΡΠ°ΡΡ Π²Π΅ΡΡΠΈΠ½Ρ ΠΈΠ· ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² Qp ΠΈ A[i]. ΠΡΠ°ΠΊ, ΡΠ΅ΡΠ½ΡΠΉ ΡΡΠΈΠΊ Π.
Qp:=Qp — [i]; Qm:=Qm+[i];
if Number (Qp*A[i])
[2.5] | [1] | [1.5] | ΠΠ΄Π½Π°ΠΊΠΎ ΠΏΠΎΡΠ»Π΅ ΡΠ°Π±ΠΎΡΡ ΡΠ΅ΡΠ½ΠΎΠ³ΠΎ ΡΡΠΈΠΊΠ° Π ΠΈΠΌΠ΅Π΅ΠΌ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ | |||
[2.5] | [1] | [2.3] | (2) | |||
[3,5] | [] | [3,5] | (2,3) | |||
[5] | [] | [5] | (2,3,5) | |||
[] | [] | [] | ΠΡΠ²ΠΎΠ΄ ΡΡΠ΅ΡΡΠ΅Π³ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°. | |||
[] | [5] | [] | ||||
[5] | [3] | [] | Π‘ΠΎΠ³Π»Π°ΡΠ½ΠΎ Π»ΠΎΠ³ΠΈΠΊΠ΅ ΡΠ΅ΡΠ½ΠΎΠ³ΠΎ ΡΡΠΈΠΊΠ° Π ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΊΠ°Π½Π΄ΠΈΠ΄Π°ΡΠΎΠ² Gg ΡΡΠ°Π½ΠΎΠ²ΠΈΡΡΡ ΠΏΡΡΡΡΠΌ. | |||
[3.5] | [1,2] | [2,3] | (3) | |||
[5] | [2] | ΠΡΠ°ΠΊ, ΠΌΡ ΠΏΠ΅ΡΠ²ΡΠΉ ΡΠ°Π· ΠΏΠΎΠΏΠ°Π΄Π°Π΅ΠΌ Π² ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ Find, ΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Gm ΠΏΡΠΈ ΡΡΠΎΠΌ Π½Π΅ ΠΏΡΡΡΠΎ. | ||||
ΠΠΎΠ»ΠΆΠ½Π° ΡΠ°Π±ΠΎΡΠ°ΡΡ Π»ΠΎΠ³ΠΈΠΊΠ° ΡΠ΅ΡΠ½ΠΎΠ³ΠΎ ΡΡΠΈΠΊΠ° ΠΠ. ΠΠ°ΠΌΠ΅ΡΠ°Π½ΠΈΠ΅ 1. ΠΡΠ»ΠΈ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π²Π΅ΡΡΠΈΠ½Π° j, ΠΏΡΠΈΠ½Π°Π΄Π»Π΅ΠΆΠ°ΡΠ°Ρ Qm, ΡΠ°ΠΊΠ°Ρ, ΡΡΠΎ ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ A[j] ΠΈ Qp ΠΏΡΡΡΠΎ, ΡΠΎ Π΄Π°Π»ΡΠ½Π΅ΠΉΡΠ΅Π΅ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π±Π΅ΡΡΠΌΡΡΠ»Π΅Π½Π½ΠΎ — Π²Π΅ΡΡΠΈΠ½Ρ ΠΈΠ· A[j] Π½Π΅ ΠΏΠΎΠΏΠ°Π΄ΡΡ Π² Π½Π΅Π³ΠΎ. ΠΠ°ΠΌΠ΅ΡΠ°Π½ΠΈΠ΅ 2. ΠΡΠ»ΠΈ Π½Π΅Ρ Π²Π΅ΡΡΠΈΠ½ ΠΈΠ· Qm, ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΡΡΡΠΈΡ ΠΏΠ΅ΡΠ²ΠΎΠΌΡ Π·Π°ΠΌΠ΅ΡΠ°Π½ΠΈΡ, ΡΠΎ ΠΊΠ°ΠΊΡΡ Π²Π΅ΡΡΠΈΠ½Ρ ΠΈΠ· Qp ΡΠ»Π΅Π΄ΡΠ΅Ρ Π²ΡΠ±ΠΈΡΠ°ΡΡ? ΠΡΠ²Π΅Ρ: Π²Π΅ΡΡΠΈΠ½Ρ i (QpA[j]) Π΄Π»Ρ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ jQm, ΠΏΡΠΈΡΠ΅ΠΌ ΠΌΠΎΡΠ½ΠΎΡΡΡ ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² A[j] ΠΈ Qp ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½Π°. ΠΠ°Π½Π½ΡΠΉ Π²ΡΠ±ΠΎΡ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΡΠΎΠΊΡΠ°ΡΠΈΡΡ ΠΏΠ΅ΡΠ΅Π±ΠΎΡ. ΠΡΠ°ΠΊ, Π»ΠΎΠ³ΠΈΠΊΠ° ΡΠ΅ΡΠ½ΠΎΠ³ΠΎ ΡΡΠΈΠΊΠ° ΠΠ.
begin
delt:=N+1;
for j:=1 to N do if j in Qm then if Number (A[j]*Qp)
begin i:=j; delt:=Number (A[j]*Qp); end;
Gg:=Qp*A[i];
end
ΠΠ°ΠΊΠΎΠ½ΡΠΈΠΌ ΡΡΠ°ΡΡΠΈΡΠΎΠ²ΠΊΡ ΠΏΡΠΈΠΌΠ΅ΡΠ°.
[5] | [2] | [] | ||||
[5] | [1,2,3] | [] | ΠΡΡ ΠΎΠ΄ Π² ΠΎΡΠ½ΠΎΠ²Π½ΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ. | |||
ΠΡ Π½Π°ΡΠ»ΠΈ Π²ΡΠ΅ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠ΅ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°.
3. ΠΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠΈΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°
ΠΠ»Ρ Π³ΡΠ°ΡΠ° G=(V, E) Π΄ΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠ΅Π΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π΅ΡΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ SV, ΡΠ°ΠΊΠΎΠ΅, ΡΡΠΎ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ j, Π½Π΅ Π²Ρ ΠΎΠ΄ΡΡΠ΅ΠΉ Π² S, ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΠ΅Π±ΡΠΎ, ΠΈΠ΄ΡΡΠ΅Π΅ ΠΈΠ· Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° S Π² Π²Π΅ΡΡΠΈΠ½Ρ j. ΠΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠ΅Π΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ, Π΅ΡΠ»ΠΈ Π½Π΅Ρ Π΄ΡΡΠ³ΠΎΠ³ΠΎ Π΄ΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠ΅Π³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠ΅Π³ΠΎΡΡ Π² Π½Π΅ΠΌ.
ΠΡΠΈΠΌΠ΅Ρ.
ΠΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠΈΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° (1, 2, 3), (4, 5, 6, 7, 8, 9), (1, 2, 3, 8, 9), (1,2, 3, 7) ΠΈ Ρ. Π΄. ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° (1, 2, 3), (4, 5, 6, 7, 8, 9) ΡΠ²Π»ΡΡΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌΠΈ. ΠΡΠ»ΠΈ Q — ΡΠ΅ΠΌΠ΅ΠΉΡΡΠ²ΠΎ Π²ΡΠ΅Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΡ Π΄ΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠΈΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² Π³ΡΠ°ΡΠ°, ΡΠΎ ΡΠΈΡΠ»ΠΎ [G]=minS
SQ
Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΈΡΠ»ΠΎΠΌ Π΄ΠΎΠΌΠΈΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π³ΡΠ°ΡΠ°, Π° ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ S*, Π½Π° ΠΊΠΎΡΠΎΡΠΎΠΌ ΡΡΠΎΡ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ Π΄ΠΎΡΡΠΈΠ³Π°Π΅ΡΡΡ, Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΠΌ Π΄ΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠΈΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ. ΠΠ»Ρ Π½Π°ΡΠ΅Π³ΠΎ ΠΏΡΠΈΠΌΠ΅ΡΠ° [G]=3.
ΠΠ°Π΄Π°ΡΠ°. ΠΡΡΡΡ Π³ΠΎΡΠΎΠ΄ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΠ·ΠΎΠ±ΡΠ°Π·ΠΈΡΡ ΠΊΠ°ΠΊ ΠΊΠ²Π°Π΄ΡΠ°Ρ, ΡΠ°Π·Π΄Π΅Π»Π΅Π½Π½ΡΠΉ Π½Π° 16 ΡΠ°ΠΉΠΎΠ½ΠΎΠ². Π‘ΡΠΈΡΠ°Π΅ΡΡΡ, ΡΡΠΎ ΠΎΠΏΠΎΡΠ½ΡΠΉ ΠΏΡΠ½ΠΊΡ ΠΌΠΈΠ»ΠΈΡΠΈΠΈ, ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½ΡΠΉ Π² ΠΊΠ°ΠΊΠΎΠΌ-Π»ΠΈΠ±ΠΎ ΡΠ°ΠΉΠΎΠ½Π΅, ΠΌΠΎΠΆΠ΅Ρ ΠΊΠΎΠ½ΡΡΠΎΠ»ΠΈΡΠΎΠ²Π°ΡΡ Π½Π΅ ΡΠΎΠ»ΡΠΊΠΎ ΡΡΠΎΡ ΡΠ°ΠΉΠΎΠ½, Π½ΠΎ ΠΈ Π³ΡΠ°Π½ΠΈΡΠ°ΡΠΈΠ΅ Ρ Π½ΠΈΠΌ ΡΠ°ΠΉΠΎΠ½Ρ. Π’ΡΠ΅Π±ΡΠ΅ΡΡΡ Π½Π°ΠΉΡΠΈ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΏΡΠ½ΠΊΡΠΎΠ² ΠΌΠΈΠ»ΠΈΡΠΈΠΈ ΠΈ ΠΌΠ΅ΡΡΠ° ΠΈΡ ΡΠ°Π·ΠΌΠ΅ΡΠ΅Π½ΠΈΡ, ΡΠ°ΠΊΠΈΠ΅, ΡΡΠΎΠ±Ρ ΠΊΠΎΠ½ΡΡΠΎΠ»ΠΈΡΠΎΠ²Π°Π»ΡΡ Π²Π΅ΡΡ Π³ΠΎΡΠΎΠ΄.
ΠΡΠ΅Π΄ΡΡΠ°Π²ΠΈΠΌ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ°ΠΉΠΎΠ½ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ Π³ΡΠ°ΡΠ° ΠΈ ΡΠ΅Π±ΡΠ°ΠΌΠΈ ΡΠΎΠ΅Π΄ΠΈΠ½ΠΈΠΌ ΡΠΎΠ»ΡΠΊΠΎ ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ, ΠΊΠΎΡΠΎΡΡΠ΅ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡ ΡΠΎΡΠ΅Π΄Π½ΠΈΠΌ ΡΠ°ΠΉΠΎΠ½Π°ΠΌ. ΠΠ°ΠΌ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π½Π°ΠΉΡΠΈ ΡΠΈΡΠ»ΠΎ Π΄ΠΎΠΌΠΈΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π³ΡΠ°ΡΠ° ΠΈ Ρ ΠΎΡΡ Π±Ρ ΠΎΠ΄Π½ΠΎ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π΅ Π΄ΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠ΅Π΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ. ΠΠ»Ρ Π΄Π°Π½Π½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ [G]=4, ΠΈ ΠΎΠ΄Π½ΠΎ ΠΈΠ· Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² Π΅ΡΡΡ (3, 5, 12, 14). ΠΡΠΈ Π²Π΅ΡΡΠΈΠ½Ρ Π²ΡΠ΄Π΅Π»Π΅Π½Ρ Π½Π° ΡΠΈΡΡΠ½ΠΊΠ΅.
4. ΠΠ°Π΄Π°ΡΠ° ΠΎ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΌ ΠΏΠΎΠΊΡΡΡΠΈΠΈ
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ Π³ΡΠ°Ρ. ΠΠ° ΡΠΈΡΡΠ½ΠΊΠ΅ ΠΏΠΎΠΊΠ°Π·Π°Π½Π° Π΅Π³ΠΎ ΠΌΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ, Π ΠΈ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½Π½Π°Ρ ΠΌΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ Ρ Π΅Π΄ΠΈΠ½ΠΈΡΠ½ΡΠΌΠΈ Π΄ΠΈΠ°Π³ΠΎΠ½Π°Π»ΡΠ½ΡΠΌΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ Π*. ΠΠ°Π΄Π°ΡΠ° ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ Π΄ΠΎΠΌΠΈΠ½ΠΈΡΡΡΡΠ΅Π³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π³ΡΠ°ΡΠ° G ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½ΡΠ½Π° Π·Π°Π΄Π°ΡΠ΅ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΡΠ°ΠΊΠΎΠ³ΠΎ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΡΡΠΎΠ»Π±ΡΠΎΠ² Π²
ΠΌΠ°ΡΡΠΈΡΠ΅ Π*, ΡΡΠΎ ΠΊΠ°ΠΆΠ΄Π°Ρ ΡΡΡΠΎΠΊΠ° ΠΌΠ°ΡΡΠΈΡΡ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ Π΅Π΄ΠΈΠ½ΠΈΡΡ Ρ ΠΎΡΡ Π±Ρ Π² ΠΎΠ΄Π½ΠΎΠΌ ΠΈΠ· Π²ΡΠ±ΡΠ°Π½Π½ΡΡ ΡΡΠΎΠ»Π±ΡΠΎΠ². ΠΠ°Π΄Π°ΡΡ ΠΎ ΠΏΠΎΠΈΡΠΊΠ΅ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΡΡΠΎΠ»Π±ΡΠΎΠ², «ΠΏΠΎΠΊΡΡΠ²Π°ΡΡΠ΅Π³ΠΎ» Π²ΡΠ΅ ΡΡΡΠΎΠΊΠΈ ΠΌΠ°ΡΡΠΈΡΡ, Π½Π°Π·ΡΠ²Π°ΡΡ Π·Π°Π΄Π°ΡΠ΅ΠΉ ΠΎ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΌ ΠΏΠΎΠΊΡΡΡΠΈΠΈ. Π ΠΎΠ±ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΌΠ°ΡΡΠΈΡΠ° Π½Π΅ ΠΎΠ±ΡΠ·Π°ΡΠ΅Π»ΡΠ½ΠΎ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠΉ, ΠΊΡΠΎΠΌΠ΅ ΡΠΎΠ³ΠΎ, Π²Π΅ΡΡΠΈΠ½Π°ΠΌ Π³ΡΠ°ΡΠ° (ΡΡΠΎΠ»Π±ΡΠ°ΠΌ) ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΏΡΠΈΠΏΠΈΡΠ°Π½ Π²Π΅Ρ, Π² ΡΡΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π½Π°ΠΉΡΠΈ ΠΏΠΎΠΊΡΡΡΠΈΠ΅ Ρ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΉ ΠΎΠ±ΡΠ΅ΠΉ ΡΡΠΎΠΈΠΌΠΎΡΡΡΡ. ΠΡΠ»ΠΈ Π²Π²Π΅Π΄Π΅Π½ΠΎ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ΅ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΠ΅, ΡΡΡΡ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π² ΡΠΎΠΌ, ΡΡΠΎΠ±Ρ Π»ΡΠ±Π°Ρ ΠΏΠ°ΡΠ° ΡΡΠΎΠ»Π±ΡΠΎΠ² Π½Π΅ ΠΈΠΌΠ΅Π»Π° ΠΎΠ±ΡΠΈΡ Π΅Π΄ΠΈΠ½ΠΈΡ Π² ΠΎΠ΄Π½ΠΈΡ ΠΈ ΡΠ΅Ρ ΠΆΠ΅ ΡΡΡΠΎΠΊΠ°Ρ , ΡΠΎ Π·Π°Π΄Π°ΡΡ Π½Π°Π·ΡΠ²Π°ΡΡ Π·Π°Π΄Π°ΡΠ΅ΠΉ ΠΎ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΌ ΡΠ°Π·Π±ΠΈΠ΅Π½ΠΈΠΈ.
ΠΠ°ΠΌΠ΅ΡΠ°Π½ΠΈΠ΅. 1. ΠΡΠ»ΠΈ Π½Π΅ΠΊΠΎΡΠΎΡΠ°Ρ ΡΡΡΠΎΠΊΠ° ΠΌΠ°ΡΡΠΈΡΡ Π* ΠΈΠΌΠ΅Π΅Ρ Π΅Π΄ΠΈΠ½ΠΈΡΡ Π² Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΠΌ ΡΡΠΎΠ»Π±ΡΠ΅, ΡΠΎ Π΅ΡΡΡ Π±ΠΎΠ»ΡΡΠ΅ Π½Π΅Ρ ΡΡΠΎΠ»Π±ΡΠΎΠ², ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΡ Π΅Π΄ΠΈΠ½ΠΈΡΡ Π² ΡΡΠΎΠΉ ΡΡΡΠΎΠΊΠ΅, ΡΠΎ Π΄Π°Π½Π½ΡΠΉ ΡΡΠΎΠ»Π±Π΅Ρ ΡΠ»Π΅Π΄ΡΠ΅Ρ Π²ΠΊΠ»ΡΡΠ°ΡΡ Π² Π»ΡΠ±ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. 2. Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΡΠΎΠ»Π±ΡΠΎΠ² ΠΌΠ°ΡΡΠΈΡΡ Π*, ΠΈΠΌΠ΅ΡΡΠΈΡ Π΅Π΄ΠΈΠ½ΠΈΡΡ Π² ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅. ΠΠ»Ρ Π½Π°ΡΠ΅Π³ΠΎ ΠΏΡΠΈΠΌΠ΅ΡΠ°: U1=(1, 6, 7, 8), U2=(1, 2, 5, 8), U3=(2, 3, 5), U4=(3, 4), U5=(2, 3, 4, 5), U6=(5, 6), U7=(6, 7), U8=(7,8). ΠΠΈΠ΄ΠΈΠΌ, ΡΡΠΎ U4U5. ΠΠ· ΡΡΠΎΠ³ΠΎ ΡΠ»Π΅Π΄ΡΠ΅Ρ, ΡΡΠΎ 5-Ρ ΡΡΡΠΎΠΊΡ ΠΌΠΎΠΆΠ½ΠΎ Π½Π΅ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡ, ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ Π»ΡΠ±ΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΡΠΎΠ»Π±ΡΠΎΠ², ΠΏΠΎΠΊΡΡΠ²Π°ΡΡΠ΅Π΅ 4-Ρ ΡΡΡΠΎΠΊΡ, Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΠΏΠΎΠΊΡΡΠ²Π°ΡΡ ΠΈ 5-Ρ. Π§Π΅ΡΠ²Π΅ΡΡΠ°Ρ ΡΡΡΠΎΠΊΠ° Π΄ΠΎΠΌΠΈΠ½ΠΈΡΡΠ΅Ρ Π½Π°Π΄ ΠΏΡΡΠΎΠΉ.
5. ΠΠ΅ΡΠΎΠ΄ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°ΡΠΈ ΠΎ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΌ ΡΠ°Π·Π±ΠΈΠ΅Π½ΠΈΠΈ
ΠΠΎΠΏΡΡΠ°Π΅ΠΌΡΡ ΠΎΡΠΎΠ·Π½Π°ΡΡ ΠΌΠ΅ΡΠΎΠ΄ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°ΡΠΈ, ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Ρ, ΠΊΠ°ΠΊ ΠΎΠ±ΡΡΠ½ΠΎ, ΠΏΡΠΈΠΌΠ΅Ρ. Π£ Π½Π°Ρ Π΅ΡΡΡ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ Π³ΡΠ°Ρ, Π΅Π³ΠΎ ΠΌΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΈ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½Π½Π°Ρ ΠΌΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ Ρ Π΅Π΄ΠΈΠ½ΠΈΡΠ½ΡΠΌΠΈ Π΄ΠΈΠ°Π³ΠΎΠ½Π°Π»ΡΠ½ΡΠΌΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ. ΠΡΡΠ»Π΅Π΄ΡΠ΅ΠΌ ΡΡΡΡΠΊΡΡΡΡ ΠΌΠ°ΡΡΠΈΡΡ Π*. ΠΠ°Ρ ΠΈΠ½ΡΠ΅ΡΠ΅ΡΡΠ΅Ρ, ΠΊΠ°ΠΊΠΈΠ΅ ΡΡΠΎΠ»Π±ΡΡ ΡΠΎΠ΄Π΅ΡΠΆΠ°Ρ Π΅Π΄ΠΈΠ½ΠΈΡΡ Π² ΠΏΠ΅ΡΠ²ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅, ΠΊΠ°ΠΊΠΈΠ΅ ΡΡΠΎΠ»Π±ΡΡ ΡΠΎΠ΄Π΅ΡΠΆΠ°Ρ Π΅Π΄ΠΈΠ½ΠΈΡΡ Π²ΠΎ Π²ΡΠΎΡΠΎΠΉ ΡΡΡΠΎΠΊΠ΅ ΠΈ Π½Π΅ ΡΠΎΠ΄Π΅ΡΠΆΠ°Ρ Π² ΠΏΠ΅ΡΠ²ΠΎΠΉ ΠΈ ΡΠ°ΠΊ Π΄Π°Π»Π΅Π΅. Π‘ ΡΡΠΎΠΉ ΡΠ΅Π»ΡΡ ΠΌΠΎΠΆΠ½ΠΎ Π±ΡΠ»ΠΎ Π±Ρ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π²Π»ΡΡΡ ΡΡΠΎΠ»Π±ΡΡ Π² ΠΌΠ°ΡΡΠΈΡΠ΅ Π*, Π½ΠΎ ΠΎΡΡΠ°Π²ΠΈΠΌ Π΅Π΅ «Π² ΠΏΠΎΠΊΠΎΠ΅». ΠΡΠ΄Π΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ Bl, Π΅Π΅ ΡΠΈΠΏ:
type Pr=array [1.MaxN, 1. MaxN+1] of integer;
var Bl: Pr;, Π³Π΄Π΅ MaxN — ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½Π°Ρ ΡΠ°Π·ΠΌΠ΅ΡΠ½ΠΎΡΡΡ Π·Π°Π΄Π°ΡΠΈ. ΠΠΎΡΠ΅ΠΌΡ ΠΏΠ»ΡΡ Π΅Π΄ΠΈΠ½ΠΈΡΠ° (ΡΠ΅Ρ Π½ΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΡΠΈΠ΅ΠΌ — «Π±Π°ΡΡΠ΅Ρ»), Π±ΡΠ΄Π΅Ρ ΡΡΠ½ΠΎ ΠΈΠ· ΠΏΠΎΡΠ»Π΅Π΄ΡΡΡΠ΅Π³ΠΎ ΠΈΠ·Π»ΠΎΠΆΠ΅Π½ΠΈΡ (ΠΏΡΠΎΡΠ΅Π΄ΡΡΠ° Press).
ΠΡΠΈ ΠΈΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΌΠ°ΡΡΠΈΡΠ° Bl Π΄ΠΎΠ»ΠΆΠ½Π° ΠΈΠΌΠ΅ΡΡ Π²ΠΈΠ΄:
Π² ΠΏΠ΅ΡΠ²ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅ — [1 2 3. № 0];
Π²ΡΠ΅ ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΡΠ°Π²Π½Ρ Π½ΡΠ»Ρ.
Π’ΠΎ Π΅ΡΡΡ Π½Π°ΡΠ΅ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ΅ ΠΏΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎ Π²ΡΠ΅ ΡΡΠΎΠ»Π±ΡΡ ΠΌΠ°ΡΡΠΈΡΡ Π* ΠΈΠΌΠ΅ΡΡ Π΅Π΄ΠΈΠ½ΠΈΡΡ Π² ΠΏΠ΅ΡΠ²ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅. ΠΡΠΎΠ²Π΅ΡΠΈΠΌ Π΅Π³ΠΎ. ΠΡΠ΄Π΅ΠΌ ΠΏΡΠΎΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠΉ ΡΡΡΠΎΠΊΠΈ (i) ΠΌΠ°ΡΡΠΈΡΡ Bl. ΠΡΠ»ΠΈ Bl [i, j]<>0, ΡΠΎ ΡΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ Bl [i, j], ΠΊΠ°ΠΊ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ ΡΡΠΎΠ»Π±ΡΠ° ΠΌΠ°ΡΡΠΈΡΡ A*, ΠΏΡΠΎΠ²Π΅ΡΠΈΠΌ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π*. ΠΡΠΈ Π΅Π³ΠΎ Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ²Π΅ Π½ΡΠ»Ρ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Bl ΠΎΡΡΠ°Π΅ΡΡΡ Π½Π° ΡΠ²ΠΎΠ΅ΠΌ ΠΌΠ΅ΡΡΠ΅, ΠΈΠ½Π°ΡΠ΅ ΠΎΠ½ ΠΏΠ΅ΡΠ΅ΠΏΠΈΡΡΠ²Π°Π΅ΡΡΡ Π² ΡΠ»Π΅Π΄ΡΡΡΡΡ ΡΡΡΠΎΠΊΡ ΠΌΠ°ΡΡΠΈΡΡ Bl, Π° ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΡΠ΅ΠΊΡΡΠ΅ΠΉ ΡΡΡΠΎΠΊΠΈ Bl ΡΠ΄Π²ΠΈΠ³Π°ΡΡΡΡ Π²ΠΏΡΠ°Π²ΠΎ, ΡΠΆΠΈΠΌΠ°ΡΡΡΡ (Press). ΠΡΠ°ΠΊ, Π΄Π»Ρ N-1 ΡΡΡΠΎΠΊΠΈ ΠΌΠ°ΡΡΠΈΡΡ Bl. ΠΠ»Ρ Π½Π°ΡΠ΅Π³ΠΎ ΠΏΡΠΈΠΌΠ΅ΡΠ° ΠΌΠ°ΡΡΠΈΡΠ° Bl ΠΏΠΎΡΠ»Π΅ ΡΡΠΎΠ³ΠΎ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΡ Π±ΡΠ΄Π΅Ρ ΠΈΠΌΠ΅ΡΡ Π²ΠΈΠ΄:
… | ||||||||
… | ||||||||
Bl= | … | |||||||
… | ||||||||
4 3 6 1 0… 0
5 7 2 0… 0
Bl= 0 0
…
0 … 0
Π Π½Π°ΡΠ΅ΠΉ Π·Π°Π΄Π°ΡΠ΅ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Ρ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ° ΠΈΠ»ΠΈ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ ΡΡΠΎΠ»Π±ΡΠΎΠ² ΠΌΠ°ΡΡΠΈΡΡ Π*, ΠΈ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π½Π°ΠΉΡΠΈ ΡΠ°Π·Π±ΠΈΠ΅Π½ΠΈΠ΅ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΉ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ. ΠΡΡΡΡ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ ΠΎΠΏΠΈΡΡΠ²Π°ΡΡΡΡ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Price (Price:array [1..MaxN] of integer) ΠΈ Π΄Π»Ρ ΠΏΡΠΈΠΌΠ΅ΡΠ° Π½Π° ΡΠΈΡΡΠ½ΠΊΠ΅ ΠΈΠΌΠ΅ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡ [15 13 4 3 8 9 10]. ΠΡΡΠ°Π»Π°ΡΡ ΡΠΈΡΡΠΎ ΡΠ΅Ρ Π½ΠΈΡΠ΅ΡΠΊΠ°Ρ Π΄Π΅ΡΠ°Π»Ρ — ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΡΡΠΎΠΊΠΈ ΠΌΠ°ΡΡΠΈΡΡ Bl ΠΏΠΎ Π²ΠΎΠ·ΡΠ°ΡΡΠ°Π½ΠΈΡ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΡ ΡΡΠΎΠ»Π±ΡΠΎΠ² ΠΌΠ°ΡΡΠΈΡΡ Π. ΠΠΎΠ³ΠΈΠΊΠ° ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Π° Π½ΠΈΠΆΠ΅ ΠΏΠΎ ΡΠ΅ΠΊΡΡΡ (Blocs).
procedure Blocs; {Π²ΡΠ΄Π΅Π»Π΅Π½ΠΈΡ Π±Π»ΠΎΠΊΠΎΠ²}
{Bl — Π³Π»ΠΎΠ±Π°Π»ΡΠ½Π°Ρ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ}
procedure Sort;
{Price ΠΈ Bl — Π³Π»ΠΎΠ±Π°Π»ΡΠ½ΡΠ΅ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΠ΅}
begin
…
end;
procedure Press (i, j: integer); {Π‘Π΄Π²ΠΈΠ³Π°Π΅ΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΡΡΡΠΎΠΊΠΈ Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ i, Π½Π°ΡΠΈΠ½Π°Ρ Ρ ΠΏΠΎΠ·ΠΈΡΠΈΠΈ (ΡΡΠΎΠ»Π±ΡΠ°) j, Π½Π° ΠΎΠ΄Π½Ρ ΠΏΠΎΠ·ΠΈΡΠΈΡ Π²ΠΏΡΠ°Π²ΠΎ}
{Bl — Π³Π»ΠΎΠ±Π°Π»ΡΠ½Π°Ρ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ}
var k: integer;
begin
k:=j;
while Bl [i, k]<>0 do begin {ΠΠΎΡΡΠΎΠΌΡ ΡΠ°Π·ΠΌΠ΅ΡΠ½ΠΎΡΡΡ ΠΌΠ°ΡΡΠΈΡΡ Ρ ΠΏΠ»ΡΡ Π΅Π΄ΠΈΠ½ΠΈΡΠ΅ΠΉ. Π ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅ΠΌ ΡΡΠΎΠ»Π±ΡΠ΅ ΡΡΡΠΎΠΊΠΈ Π²ΡΠ΅Π³Π΄Π° Π·Π°ΠΏΠΈΡΠ°Π½ 0.}
Bl [i, k]: =Bl [i, k+1];
Inc (k);
end; {while}
end; {Press}
var i, j, cnt: integer;
begin
FillChar (Bl, SizeOf (Bl), 0);
for i:=1 to N do Bl [1, i]: =i; {ΠΏΡΠ΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π΅ΡΡΡ, ΡΡΠΎ Π² ΠΏΠ΅ΡΠ²ΠΎΠΌ Π±Π»ΠΎΠΊΠ΅ Π²ΡΠ΅ ΡΡΠΎΠ»Π±ΡΡ}
for i:=1 to N-1 do begin
j:=1; cnt:=0;
while Bl [i, j]<>0 do begin
if A*[i, Bl [i, j]]=0 then begin {ΡΡΠΎΠ»Π±Π΅Ρ Π½Π΅ Π² ΡΡΠΎΠΌ Π±Π»ΠΎΠΊΠ΅}
Inc (cnt);
Bl [i+1, cnt]: =Bl [i, j]; {ΠΏΠ΅ΡΠ΅ΠΏΠΈΡΠ°ΡΡ Π² ΡΠ»Π΅Π΄ΡΡΡΡΡ ΡΡΡΠΎΠΊΡ}
Press (i, j);
Dec (j);
end; {if}
Inc (j);
end; {while}
end; {for}
Sort;
end; {Blocs}
ΠΠΎΡΠ»Π΅ ΡΡΠΎΠΉ ΠΏΡΠ΅Π΄Π²Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ°Π±ΠΎΡΡ ΠΌΡ ΠΈΠΌΠ΅Π΅ΠΌ Π²ΠΏΠΎΠ»Π½Π΅ «ΠΏΡΠΈΠ»ΠΈΡΠ½ΡΡ» ΠΎΡΠ³Π°Π½ΠΈΠ·Π°ΡΠΈΡ Π΄Π°Π½Π½ΡΡ Π΄Π»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°ΡΠΈ ΠΏΡΡΠ΅ΠΌ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠ° Π²Π°ΡΠΈΠ°Π½ΡΠΎΠ². ΠΠ°ΡΡΠΈΡΠ° Bl ΡΠ°Π·Π±ΠΈΡΠ° Π½Π° Π±Π»ΠΎΠΊΠΈ, ΠΈ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π²ΡΠ±ΡΠ°ΡΡ ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΌΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ (Π΅ΡΠ»ΠΈ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠ΅ ΡΡΡΠΎΠΊΠΈ Π΅ΡΡ Π½Π΅ ΠΏΠΎΠΊΡΡΡΡ) ΠΈΠ· ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π±Π»ΠΎΠΊΠ°. ΠΡΠΎΡΠ΅ΡΡ Π²ΡΠ±ΠΎΡΠ° ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠ°ΡΡ Π΄ΠΎ ΡΠ΅Ρ ΠΏΠΎΡ, ΠΏΠΎΠΊΠ° Π½Π΅ Π±ΡΠ΄ΡΡ Π²ΠΊΠ»ΡΡΠ΅Π½Ρ Π² «ΠΏΠΎΠΊΡΡΡΠΈΠ΅» Π²ΡΠ΅ ΡΡΡΠΎΠΊΠΈ ΠΈΠ»ΠΈ ΠΎΠΊΠ°ΠΆΠ΅ΡΡΡ, ΡΡΠΎ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΡΡΠΎΠΊΡ Π½Π΅Π»ΡΠ·Ρ Π²ΠΊΠ»ΡΡΠΈΡΡ.
ΠΡΠΎΠ΄ΠΎΠ»ΠΆΠΈΠΌ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½ΠΈΠ΅ ΠΌΠ΅ΡΠΎΠ΄Π°. ΠΡΠ»ΠΈ ΠΏΡΠΈ ΠΏΠΎΠΈΡΠΊΠ΅ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² ΠΌΡ ΡΠ»ΠΈ «ΡΠ²Π΅ΡΡ Ρ Π²Π½ΠΈΠ·», ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ ΡΡΠΎΡΠ½ΡΡ Π»ΠΎΠ³ΠΈΠΊΡ, ΡΠΎ ΡΠ΅ΠΉΡΠ°Ρ ΠΏΠΎΠΏΡΠΎΠ±ΡΠ΅ΠΌ ΠΈΠ΄ΡΠΈ «ΡΠ½ΠΈΠ·Ρ Π²Π²Π΅ΡΡ », ΡΠΊΠ»Π°Π΄ΡΠ²Π°Ρ ΠΎΠΊΠΎΠ½ΡΠ°ΡΠ΅Π»ΡΠ½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΠΈΠ· ΡΠ΄Π΅Π»Π°Π½Π½ΡΡ «ΠΊΠΈΡΠΏΠΈΡΠΈΠΊΠΎΠ²». ΠΠ°ΠΊ ΠΎΠ±ΡΡΠ½ΠΎ, ΡΠ»Π΅Π΄ΡΠ΅Ρ Π½Π°ΡΠ°ΡΡ ΡΠΎ ΡΡΡΡΠΊΡΡΡ Π΄Π°Π½Π½ΡΡ . ΠΠΎ-ΠΏΠ΅ΡΠ²ΡΡ , ΠΌΡ ΠΈΡΠ΅ΠΌ Π»ΡΡΡΠ΅Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅, ΡΠΎ Π΅ΡΡΡ ΡΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΡΠΎΠ»Π±ΡΠΎΠ², ΠΊΠΎΡΠΎΡΠΎΠ΅ ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΡΠ΅Ρ ΡΡΠ»ΠΎΠ²ΠΈΡΠΌ Π·Π°Π΄Π°ΡΠΈ (Π½Π΅ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΠΈ «ΠΏΠΎΠΊΡΡΡΠΈΠ΅» Π²ΡΠ΅Π³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΡΡΡΠΎΠΊ), ΠΈ ΡΡΠΌΠΌΠ°ΡΠ½Π°Ρ ΡΡΠΎΠΈΠΌΠΎΡΡΡ ΡΡΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½Π°. ΠΠ½Π°ΡΠΈΡ, Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠ° ΡΡΡΡΠΊΡΡΡΠ° Π΄Π°Π½Π½ΡΡ Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ ΡΡΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΡ Π½Π°ΠΈΠ»ΡΡΡΠ΅ΠΉ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ ΠΈ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ, ΡΡΡΡΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ (ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠ³ΠΎ) ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΈ Π΅Π³ΠΎ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ. ΠΠΎ-Π²ΡΠΎΡΡΡ , Π² ΡΠ΅ΡΠ΅Π½ΠΈΠΈ ΡΡΡΠΎΠΊΠ° ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΈΠ»ΠΈ Π½Π΅ Π±ΡΡΡ. Π‘Π»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, Π½Π°ΠΌ ΡΡΠ΅Π±ΡΠ΅ΡΡΡ ΠΊΠ°ΠΊ-ΡΠΎ ΡΠΈΠΊΡΠΈΡΠΎΠ²Π°ΡΡ ΡΡΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΡ. ΠΡΠ°ΠΊ, Π΄Π°Π½Π½ΡΠ΅.
type Model=array [1.MaxN] of boolean;
var Sbetter: Model; Pbetter: integer; {Π»ΡΡΡΠ΅Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅}
S: Model; P: integer; {ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅}
R: Model; {R[i]=true — ΠΏΡΠΈΠ·Π½Π°ΠΊ ΡΠΎΠ³ΠΎ, ΡΡΠΎ ΡΡΡΠΎΠΊΠ° i «ΠΏΠΎΠΊΡΡΡΠ°» ΡΠ΅ΠΊΡΡΠΈΠΌ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ΠΌ}
ΠΠΎΠ³ΠΈΠΊΠ° Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΡ (ΠΈΡΠΊΠ»ΡΡΠ΅Π½ΠΈΡ) ΡΡΠΎΠ»Π±ΡΠ° Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ k Π² ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ (ΠΈΠ· ΡΠ΅ΡΠ΅Π½ΠΈΡ) ΠΈΠΌΠ΅Π΅Ρ Π²ΠΈΠ΄:
procedure Include (k:integer); {Π²ΠΊΠ»ΡΡΠΈΡΡ ΡΡΠΎΠ»Π±Π΅Ρ Π² ΡΠ΅ΡΠ΅Π½ΠΈΠ΅}
{A*, R, Price, S, P — Π³Π»ΠΎΠ±Π°Π»ΡΠ½ΡΠ΅ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΠ΅}
var j: integer;
begin
P:=P+Price[k]; {ΡΠ΅ΠΊΡΡΠ°Ρ ΡΠ΅Π½Π° ΡΠ΅ΡΠ΅Π½ΠΈΡ}
S[k]: =true; {ΡΡΠΎΠ»Π±Π΅Ρ Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ k Π² ΡΠ΅ΡΠ΅Π½ΠΈΠ΅}
for j:=1 to N do
if A*[j, k]=1 then R[j]: =true; {ΡΡΡΠΎΠΊΠΈ, «ΠΏΠΎΠΊΡΡΡΡΠ΅» ΡΡΠΎΠ»Π±ΡΠΎΠΌ k}
end; {Include}
procedure Exclude (k:integer); {ΠΈΡΠΊΠ»ΡΡΠΈΡΡ ΡΡΠΎΠ»Π±Π΅Ρ ΠΈΠ· ΡΠ΅ΡΠ΅Π½ΠΈΡ}
var j: integer;
begin
p:=p-Price[k];
S[k]:=false;
for j:=1 to N do if (A*[j, k]=1) and R[j] then R[j]: =false;
end; {Exclude}
ΠΡΠΎΠ²Π΅ΡΠΊΠ°, ΡΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΎ Π»ΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅, Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎΠ±Ρ ΠΏΡΠΎΡΠΌΠΎΡΡΠ΅ΡΡ ΠΌΠ°ΡΡΠΈΠ² R ΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ, Π²ΡΠ΅ Π»ΠΈ Π΅Π³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΡΠ°Π²Π½Ρ ΠΈΡΡΠΈΠ½Π΅.
function Result: boolean;
var j: integer;
begin
j:=1;
while (j<=N) and R[j] do Inc (j);
if j=N+1 then Result:=true else Result:=false;
end; {Result}
ΠΡΠΎΠΌΠ΅ ΠΏΠ΅ΡΠ΅ΡΠΈΡΠ»Π΅Π½Π½ΡΡ «ΠΊΠΈΡΠΏΠΈΡΠΈΠΊΠΎΠ²», Π½Π°ΠΌ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΠΌΠ΅ΡΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ, ΠΌΠΎΠΆΠ½ΠΎ Π»ΠΈ ΡΡΠΎΠ»Π±Π΅Ρ Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ k Π²ΠΊΠ»ΡΡΠ°ΡΡ Π² ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΏΡΠΎΡΠΌΠΎΡΡΠ΅ΡΡ ΡΡΠΎΠ»Π±Π΅Ρ Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ k ΠΌΠ°ΡΡΠΈΡΡ A* ΠΈ ΠΏΡΠΎΠ²Π΅ΡΠΈΡΡ, Π½Π΅Ρ Π»ΠΈ ΡΠΎΠ²ΠΏΠ°Π΄Π΅Π½ΠΈΠΉ Π΅Π΄ΠΈΠ½ΠΈΡΠ½ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΡΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ true ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΌΠ°ΡΡΠΈΠ²Π° R.
function Cross (k:integer):boolean; {ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΡΡΠΎΠ»Π±ΡΠ° Ρ ΡΠ°ΡΡΠΈΡΠ½ΡΠΌ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ΠΌ, ΡΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌ ΡΠ°Π½Π΅Π΅}
var j: integer;
begin
j:=1;
while (j<=N) and Not (R[j] and (A*[j, k]=1)) do Inc (j);
if j=N+1 then Cross:=true else Cross:=false;
end; {Cross}
ΠΠ°ΠΊΠ»ΡΡΠΈΡΠ΅Π»ΡΠ½Π°Ρ Π»ΠΎΠ³ΠΈΠΊΠ° ΠΏΠΎΠΈΡΠΊΠ° (Find) ΠΈΠΌΠ΅Π΅Ρ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² Π½ΠΎΠΌΠ΅Ρ Π±Π»ΠΎΠΊΠ° (ΡΡΡΠΎΠΊΠΈ ΠΌΠ°ΡΡΠΈΡΡ Bl) — ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ bloc ΠΈ Π½ΠΎΠΌΠ΅Ρ ΠΏΠΎΠ·ΠΈΡΠΈΠΈ Π² ΡΡΡΠΎΠΊΠ΅. ΠΠ΅ΡΠ²ΡΠΉ Π²ΡΠ·ΠΎΠ² — Find (1,1).
procedure Find (bloc, jnd: integer);
{ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΠ΅ Π³Π»ΠΎΠ±Π°Π»ΡΠ½ΡΠ΅}
begin
if Result then begin if P
Sbetter:=S;
end;
end
else if Bl [bloc, jnd]=0 then exit
else if Cross (Bl[bloc, jnd]) then begin
Include (Bl[bloc, jnd]);
Find (bloc+1,1);
Exclude (Bl[bloc, jnd]);
end
else if R[bloc] then Find (bloc+1,1);
Find (bloc, jnd+1);
end; {Find}
ΠΠ°ΠΌ ΠΎΡΡΠ°Π»ΠΎΡΡ Π΄Π°ΡΡ ΠΎΠ±ΡΡΡ Π»ΠΎΠ³ΠΈΠΊΡ, Π½ΠΎ ΠΏΠΎΡΠ»Π΅ Π²ΡΠΏΠΎΠ»Π½Π΅Π½Π½ΠΎΠΉ ΡΠ°Π±ΠΎΡΡ ΠΎΠ½Π° Π½Π΅ Π²ΡΠ·ΡΠ²Π°Π΅Ρ Π·Π°ΡΡΡΠ΄Π½Π΅Π½ΠΈΠΉ.
program R_min;
const MaxN=…;
type… var…
procedure Init; {Π²Π²ΠΎΠ΄ ΠΈ ΠΈΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·Π°ΡΠΈΡ Π΄Π°Π½Π½ΡΡ }
begin
…
end;
procedure Print; {Π²ΡΠ²ΠΎΠ΄ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ°}
begin
…
end;
{ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ ΠΈ ΡΡΠ½ΠΊΡΠΈΠΈ, ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½Π½ΡΠ΅ ΡΠ°Π½Π΅Π΅}
{ΠΎΡΠ½ΠΎΠ²Π½Π°Ρ Π»ΠΎΠ³ΠΈΠΊΠ°}
begin
Init;
Blocs;
Find (1,1);
Print;
end.
ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
ΠΠΎΠ½ΡΡΠΈΠ΅, ΠΏΡΠΎΡΠΈΠ²ΠΎΠΏΠΎΠ»ΠΎΠΆΠ½ΠΎΠ΅ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌΡ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠΌΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Ρ, Π΅ΡΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΠΎΠ»Π½ΡΠΉ ΠΏΠΎΠ΄Π³ΡΠ°Ρ (ΠΊΠ»ΠΈΠΊΠ°). Π ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π΅ Π½Π΅Ρ ΡΠΌΠ΅ΠΆΠ½ΡΡ Π²Π΅ΡΡΠΈΠ½, Π² ΠΊΠ»ΠΈΠΊΠ΅ Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΠΎΠΏΠ°ΡΠ½ΠΎ ΡΠΌΠ΅ΠΆΠ½Ρ. ΠΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π³ΡΠ°ΡΠ° G ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ ΠΊΠ»ΠΈΠΊΠ΅ Π³ΡΠ°ΡΠ° G', Π³Π΄Π΅ G' - Π΄ΠΎΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π³ΡΠ°ΡΠ° G.
ΠΠ΄Π΅Π»ΡΡΠΎΠ½-ΠΠ΅Π»ΡΡΠΊΠΈΠΉ Π. Π., ΠΠΈΠ½ΠΈΡ Π. Π., ΠΠ°ΡΠ·Π°Π½ΠΎΠ² Π. Π. ΠΠΎΡΠΎΠΊΠΎΠ²ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ. — Π.: ΠΠ°ΡΠΊΠ°, 1975.
ΠΠ΅ΡΠΆ Π. Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ² ΠΈ Π΅Π΅ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅. — Π.: ΠΠ, 1962.
ΠΠΌΠ΅Π»ΠΈΡΠ΅Π² Π.Π., ΠΠ΅Π»ΡΠ½ΠΈΠΊΠΎΠ² Π. Π., Π‘Π°ΡΠ²Π°Π½ΠΎΠ² Π. Π., Π’ΡΡΠΊΠ΅Π²ΠΈΡ Π . Π. ΠΠ΅ΠΊΡΠΈΠΈ ΠΏΠΎ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ². — Π.: ΠΠ°ΡΠΊΠ°, 1990.
ΠΡΠΊΠΎΠ² Π. Π. Π’Π΅ΠΎΡΠΈΡ ΠΊΠΎΠ½Π΅ΡΠ½ΡΡ Π³ΡΠ°ΡΠΎΠ². — ΠΠΎΠ²ΠΎΡΠΈΠ±ΠΈΡΡΠΊ: ΠΠ°ΡΠΊΠ°; Π‘ΠΈΠ±. ΠΎΡΠ΄-Π½ΠΈΠ΅, 1969.
ΠΠ΅Π½ΡΠ΅Π½ Π., ΠΠ°ΡΠ½Π΅Ρ Π. ΠΠΎΡΠΎΠΊΠΎΠ²ΠΎΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅.-Π.:Π Π°Π΄ΠΈΠΎ ΠΈ ΡΠ²ΡΠ·Ρ, 1984.
ΠΠ°ΡΡΡΠ½ΠΎΠ² Π.Π., Π‘Π°Π±Π΅Π»ΡΡΠ΅Π»ΡΠ΄ Π. Π. Π‘Π±ΠΎΡΠ½ΠΈΠΊ Π·Π°Π΄Π°Π½ΠΈΠΉ ΠΏΠΎ ΠΏΡΠ°ΠΊΡΠΈΠΊΡΠΌΡ Π½Π° ΠΠΠ. — Π.: ΠΠ°ΡΠΊΠ°, 1986.
ΠΡΠΈΡΡΠΎΡΠΈΠ΄Π΅Ρ Π. Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ². ΠΠ»Π³ΠΎΡΠΈΡΠΌΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΠΎΠ΄Ρ ΠΎΠ΄. — Π.: ΠΠΈΡ, 1978.
ΠΠΎΡΠΌΠ°Π½ Π.
ΠΠ²Π΅Π΄Π΅Π½ΠΈΠ΅
Π² ΠΏΡΠΈΠΊΠ»Π°Π΄Π½ΡΡ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠΈΠΊΡ. — Π.: ΠΠ°ΡΠΊΠ°, 1975.
ΠΠΈΠΏΡΠΊΠΈΠΉ Π. ΠΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠΈΠΊΠ° Π΄Π»Ρ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΡΠΎΠ². — Π.: ΠΠΈΡ, 1988.
ΠΠ°ΠΉΠ½ΠΈΠΊΠ° Π. ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ ΠΎΠΏΡΠΈΠΌΠΈΠ·Π°ΡΠΈΠΈ Π½Π° ΡΠ΅ΡΡΡ ΠΈ Π³ΡΠ°ΡΠ°Ρ .-Π.:ΠΠΈΡ, 1981.
ΠΠ΅ΡΠ΅ΠΏΡΡΠ΅Π½ΠΊΠΎ Π.Π., ΠΠΎΠΏΠΊΠΎΠ² Π. Π., ΠΠ°ΠΉΠ½Π°Π³Π°ΡΠ΅Π² Π‘. Π. ΠΈ Π΄Ρ. ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ ΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ Π½Π° Π³ΡΠ°ΡΠ°Ρ ΠΈ ΡΠ΅ΡΡΡ . — ΠΠΎΠ²ΠΎΡΠΈΠ±ΠΈΡΡΠΊ: ΠΠ°ΡΠΊΠ°; Π‘ΠΈΠ±. ΠΎΡΠ΄-Π½ΠΈΠ΅, 1990.
ΠΠΊΡΠ»ΠΎΠ² Π‘. Π. ΠΠΎΠ½ΡΠΏΠ΅ΠΊΡΡ Π·Π°Π½ΡΡΠΈΠΉ ΠΏΠΎ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΊΠ΅ (Π°Π»Π³ΠΎΡΠΈΡΠΌΡ Π½Π° Π³ΡΠ°ΡΠ°Ρ ). Π£ΡΠ΅Π±Π½ΠΎΠ΅ ΠΏΠΎΡΠΎΠ±ΠΈΠ΅ Π΄Π»Ρ ΡΡΡΠ΄Π΅Π½ΡΠΎΠ² ΠΈ ΡΡΠΈΡΠ΅Π»Π΅ΠΉ ΡΠΊΠΎΠ». — ΠΠΈΡΠΎΠ², 1996.
ΠΠ°ΠΏΠ°Π΄ΠΈΠΌΠΈΡΡΠΈΡ Π₯., Π‘ΡΠ°ΠΉΠ³Π»ΠΈΡ Π. ΠΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠ½Π°Ρ ΠΎΠΏΡΠΈΠΌΠΈΠ·Π°ΡΠΈΡ: ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ ΠΈ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ.-Π.:ΠΠΈΡ, 1985.
Π‘Π²Π°ΠΌΠΈ Π., Π’Ρ ΡΠ»Π°ΡΠΈΡΠ°ΠΌΠ°Π½ Π. ΠΡΠ°ΡΡ, ΡΠ΅ΡΠΈ ΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ. — Π.: ΠΠΈΡ, 1984.
Π€ΠΈΠ»ΠΈΠΏΡ Π., ΠΠ°ΡΡΠΈΠ°-ΠΠΈΠ°Ρ Π. ΠΠ΅ΡΠΎΠ΄Ρ Π°Π½Π°Π»ΠΈΠ·Π° ΡΠ΅ΡΠ΅ΠΉ. — Π.: ΠΠΈΡ, 1984.
Π€ΠΎΡΠ΄ Π.Π ., Π€Π°Π»ΠΊΠ΅ΡΡΠΎΠ½ Π. Π . ΠΠΎΡΠΎΠΊΠΈ Π² ΡΠ΅ΡΡΡ . — Π.: ΠΠΈΡ, 1963.
Π€ΡΡΠ½ΠΊ Π., Π€ΡΠΈΡ Π. Π‘Π΅ΡΠΈ, ΡΠ²ΡΠ·Ρ ΠΈ ΠΏΠΎΡΠΎΠΊΠΈ. — Π.: Π‘Π²ΡΠ·Ρ, 1978.
Π₯Π°ΡΠ°ΡΠΈ Π€. Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ². — Π.: ΠΠΈΡ, 1973.