ΠΠΎΠΌΠΏΡΠ΅ΡΡΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ ΠΈ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½ΠΈΠ΅ Π΄Π΅ΡΠ΅Π²Π° ΠΏΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΠΈΡΡΠ΅ΡΠ°
ΠΠ°Π½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΠΏΠΎΡΡΡΠΎΠΈΡΡ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ Ρ Π°ΡΡΠΌΠ΅Π½ΡΠΊΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ ΡΠ°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΡΡΠΎ Π±Ρ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°ΡΡ ΡΡΠΌΠ°ΡΠ½ΡΡ Π΄Π»ΠΈΠ½Ρ Π²Π½Π΅ΡΠ½Π΅Π³ΠΎ ΠΏΡΡΠΈ ΠΈ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΎΡ ΠΊΠΎΡΠ½Ρ Π΄Π΅ΡΠ΅Π²Π° Π΄ΠΎ Π»ΠΈΡΡΠ°. Π§ΠΈΡΠ»ΠΎ ΠΎΠ±ΠΌΠ΅Π½ΠΎΠ² ΡΠ·Π»ΠΎΠ² Π² ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΠΌΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΠΈ ΡΠ²ΠΎΠ΄ΠΈΡΡΡ ΠΊ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΡ. ΠΠΈΠ½ΠΈΠΌΠΈΠ·Π°ΡΠΈΡ Π²ΡΡΠΎΡΡ Π΄Π΅ΡΠ΅Π²Π° h= max{ lj} ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ ΠΏΡΠ΅Π΄ΠΎΡΠ²ΡΠ°ΡΠΈΡΡ ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ Π΄Π»ΠΈΠ½Π½ΡΡ ΠΊΠΎΠ΄ΠΎΠ²ΡΡ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΠΉ ΠΏΡΠΈ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠ³ΠΎ ΡΠΈΠΌΠ²ΠΎΠ»Π° Π² ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠΈ. ΠΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠΎΠΌΠΏΡΠ΅ΡΡΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ ΠΈ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½ΠΈΠ΅ Π΄Π΅ΡΠ΅Π²Π° ΠΏΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΠΈΡΡΠ΅ΡΠ° (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΠΈΠ½ΠΈΡΡΠ΅ΡΡΡΠ²ΠΎ ΠΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΡ ΠΈ ΠΠ°ΡΠΊΠΈ Π£ΠΊΡΠ°ΠΈΠ½Ρ ΠΠΠ―Π‘ΠΠΠ’ΠΠΠ¬ΠΠΠ― ΠΠΠΠΠ‘ΠΠ ΠΊ ΠΊΡΡΡΠΎΠ²ΠΎΠΌΡ ΠΏΡΠΎΠ΅ΠΊΡΡ Π½Π° ΡΠ΅ΠΌΡ:
«ΠΠΎΠΌΠΏΡΠ΅ΡΡΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ ΠΈ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½ΠΈΠ΅ Π΄Π΅ΡΠ΅Π²Π° ΠΏΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΠΈΡΡΠ΅ΡΠ°»
ΠΏΠΎ ΠΊΡΡΡΡ «ΠΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΈ Π·Π°ΡΠΈΡΠ° ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ. «
ΠΠ½Π½ΠΎΡΠ°ΡΠΈΡ
ΠΠΎΡΡΠ½ΠΈΡΠ΅Π»ΡΠ½Π°Ρ Π·Π°ΠΏΠΈΡΠΊΠ° ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΠΎΠΏΠΈΡΠ°Π½ΠΈΠ΅ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠ°Π½Π½ΠΎΠΉ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΠΈ ΡΡΠΊΠΎΠ²ΠΎΠ΄ΡΡΠ²ΠΎ ΠΏΠΎ Π΅Π΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ. Π’Π°ΠΊΠΆΠ΅ Π² Π½Π΅ΠΉ ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡΡΡ ΠΎΠΏΠΈΡΠ°Π½ΠΈΠ΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΡΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΠΊΠΎΠΌΠΏΡΠ΅ΡΡΠΈΠΈ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ.
ΠΠ½Π½ΠΎΡΠ°ΡΠΈΡ 2
ΠΠ²Π΅Π΄Π΅Π½ΠΈΠ΅
4
1. ΠΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠ° Π·Π°Π΄Π°ΡΠΈ 5
2. ΠΡΠ½ΠΎΠ²Π½ΡΠ΅ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½ΠΈΡ 6
3. ΠΠ±Π·ΠΎΡ ΠΈ Ρ Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΡΡΠΈΠΊΠ° ΡΡΡΠ΅ΡΡΠ²ΡΡΡΠΈΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΡΠΆΠ°ΡΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ, ΠΎΡΠ½ΠΎΠ²Π°Π½Π½ΡΠ΅ Π½Π° ΠΏΡΠΎΡΠ΅Π΄ΡΡΠ΅ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Ρ Π°ΡΡΠΌΠ΅Π½Π° 7
3.1. ΠΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Ρ Π°ΡΡΠΌΠ΅Π½Π° 7
3.2. ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ fgk 8
3.3. ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π²ΠΈΡΡΠ΅ΡΠ° 9
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½Π°Ρ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ 13
Π ΡΠΊΠΎΠ²ΠΎΠ΄ΡΡΠ²ΠΎ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ 13
ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
15
ΠΠΈΠ±Π»ΠΈΠΎΠ³ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΡΠΏΠΈΡΠΎΠΊ 16
ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ 17
Π Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ Π±ΠΎΠ»ΡΡΠΎΠ΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ ΡΠ΄Π΅Π»ΡΠ΅ΡΡΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ, Π½Π΅Π΄Π°ΡΠΎΠΌ Π½Π°Ρ Π²Π΅ΠΊ Π½Π°Π·ΡΠ²Π°ΡΡ «ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΎΠ½Π½ΡΠΌ». ΠΠΎ Π²ΡΠ΅ΠΌΡ ΡΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ Π»ΡΠ΄ΠΈ ΠΏΠΎΠ·Π½Π°ΡΡ ΡΠ΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΠΈ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°ΡΠΈ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ, Π²ΡΡΠ°Π΅Ρ Π²ΠΎΠΏΡΠΎΡ ΠΎ Π΅Π΅ ΠΊΠΎΠΌΠΏΡΠ΅ΡΡΠΈΠΈ.
ΠΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΡ ΡΡΡΠ΅ΡΡΠ²ΡΡΡΠΈΡ ΠΊΠΎΠΌΠΏΡΡΡΠ΅ΡΠ½ΡΡ ΡΠ΅ΡΠ΅ΠΉ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π·Π°ΠΌΠ΅ΡΠ½ΠΎ ΡΠ²Π΅Π»ΠΈΡΠ΅Π½Π° Π·Π° ΡΡΠ΅Ρ ΠΏΠΎΠ²ΡΡΠ΅Π½ΠΈΡ ΡΠΊΠΎΡΠΎΡΡΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°ΡΠΈ Π΄Π°Π½Π½ΡΡ ΠΏΠΎ ΠΊΠ°Π½Π°Π»Π°ΠΌ ΡΠ²ΡΠ·ΠΈ, ΠΊΠΎΡΠΎΡΠΎΠ΅ ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠΈΠ²Π°Π΅ΡΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΡΠΆΠ°ΡΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ (ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΠ΅ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅). ΠΠ»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΡΠΎΠΉ ΠΏΡΠΎΠ±Π»Π΅ΠΌΡ Π±ΡΠ»ΠΎ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠ°Π½ΠΎ Π±ΠΎΠ»ΡΡΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ°Π·Π½ΠΎΠΎΠ±ΡΠ°Π·Π½ΡΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠ³ΡΡ Π±ΡΡΡ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Ρ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΠΎ. ΠΠ°Π½Π½Π°Ρ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠ° ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅Ρ ΡΠΎΠ±ΠΎΠΉ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΡΠΉ ΠΌΠΎΠ΄ΡΠ»Ρ, ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠΈΠ²Π°ΡΡΠΈΠΉ ΠΊΠΎΠΌΡΠ΅ΡΡΠΈΡ ΠΈ Π΄Π΅ΠΊΠΎΠΌΠΏΡΠ΅ΡΡΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ.
1. ΠΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠ° Π·Π°Π΄Π°ΡΠΈ
ΠΠ΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠ°ΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π΄Π»Ρ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΈ Π΄Π΅ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π½Π΅ΠΏΡΠ΅ΡΡΠ²Π½ΠΎ ΠΏΠΎΡΡΡΠΏΠ°ΡΡΠ΅ΠΉ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ. ΠΠ»Ρ ΠΊΠΎΠΌΠΏΡΠ΅ΡΡΠΈΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΠΈΡΡΠ΅ΡΠ°. Π Π°Π·ΡΠ°Π±ΠΎΡΠ°ΡΡ ΡΠ΄ΠΎΠ±Π½ΡΠΉ ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡ ΠΎΠ±ΡΠ΅Π½ΠΈΡ Ρ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Π΅ΠΌ.
2. ΠΡΠ½ΠΎΠ²Π½ΡΠ΅ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½ΠΈΡ
m-ΡΠ°Π·ΠΌΠ΅Ρ Π°Π»ΡΠ°Π²ΠΈΡΠ° ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠ° ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠΉ;
zj — j-ΠΉ ΡΠΈΠΌΠ²ΠΎΠ» Π°Π»ΡΠ°Π²ΠΈΡΠ°;
M (k) =z (1), z (2), …, z (k) — ΠΏΠ΅ΡΠ²ΡΠ΅ ΠΊ ΡΠΈΠΌΠ²ΠΎΠ»ΠΎΠ² Π² ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠΈ;
k — ΡΠΈΡΠ»ΠΎ ΡΠΈΠΌΠ²ΠΎΠ»ΠΎΠ² Π² ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠΈ, ΠΎΠ±ΡΠ°Π±ΠΎΡΠ°Π½Π½ΡΡ Π΄ΠΎ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ ΠΌΠΎΠΌΠ΅Π½ΡΠ° Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ
K-ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ ΡΠΈΠΌΠ²ΠΎΠ»ΠΎΠ², ΠΎΠ±ΡΠ°Π±ΠΎΡΠ°Π½Π½ΡΡ Π½Π° ΡΠ΅ΠΊΡΡΠΈΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ;
Wj-Π²Π΅Ρ ΡΠΈΠΌΠ²ΠΎΠ»ΠΎΠ² zj, ΠΏΠΎΡΡΡΠΏΠΈΠ²ΡΠΈΡ Π½Π° ΠΌΠΎΠΌΠ΅Π½Ρ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΡ.
lj — ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΎΡ ΠΊΠΎΡΠ½Ρ Π΄Π΅ΡΠ΅Π²Π° Π΄ΠΎ zj — Π³ΠΎ Π»ΠΈΡΡΠ°.
3. ΠΠ±Π·ΠΎΡ ΠΈ Ρ Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΡΡΠΈΠΊΠ° ΡΡΡΠ΅ΡΡΠ²ΡΡΡΠΈΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΡΠΆΠ°ΡΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ, ΠΎΡΠ½ΠΎΠ²Π°Π½Π½ΡΠ΅ Π½Π° ΠΏΡΠΎΡΠ΅Π΄ΡΡΠ΅ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Ρ Π°ΡΡΠΌΠ΅Π½Π°
ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΠΈΡΡΠ΅ΡΠ° ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅Ρ ΡΠΎΠ±ΠΎΠΉ ΡΡΠΎΠ²Π΅ΡΡΠ΅Π½ΡΡΠ²ΠΎΠ²Π°Π½ΠΈΠ΅ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π₯Π°ΡΡΠΌΠ΅Π½Π°.
ΠΠ»Π°ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΌΠ΅ΡΠΎΠ΄ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π₯Π°ΡΡΠΌΠ΅Π½Π° ΠΏΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠ³Π°Π΅Ρ Π΄ΠΎ Π½Π°ΡΠ°Π»Π° ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΡ Π·Π½Π°Π½ΠΈΠ΅ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠ΅ΠΉ ΠΏΠΎΡΠ²Π»Π΅Π½ΠΈΡ ΡΠΈΠΌΠ²ΠΎΠ»ΠΎΠ² Π½Π° Π²ΡΡ ΠΎΠ΄Π΅ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠ° ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ. Π‘ΠΈΠΌΠ²ΠΎΠ»Ρ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠΈΠ²Π°ΡΡΡΡ ΠΏΠΎ ΡΠ±ΡΠ²Π°Π½ΠΈΡ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠ΅ΠΉ ΠΈΡ Π²ΠΎΠ·Π½ΠΈΠΊΠ½ΠΎΠ²Π΅Π½ΠΈΡ. ΠΠ° ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡΠ΅ΠΉ ΠΈ ΠΏΡΠΈΠ΅ΠΌΠ½ΠΎΠΉ ΡΡΠΎΡΠΎΠ½Π°Ρ Π΄ΠΎΠ»ΠΆΠ½Ρ Π±ΡΡΡ ΠΈΠ·Π²Π΅ΡΡΠ½Ρ ΠΊΠΎΠ΄ΠΎΠ²ΡΠ΅ Π΄Π΅ΡΠ΅Π²ΡΡ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΡ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ Π΄Π»Ρ Π΅Π³ΠΎ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΡΡΠ΅Π±ΡΠ΅ΡΡΡ Π΄Π²Π° ΠΏΡΠΎΡ ΠΎΠ΄Π° ΠΊΠΎΠ΄ΠΈΡΡΠ΅ΠΌΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π°. ΠΡΠΈ 1-ΠΌ ΠΏΡΠΎΡΠΌΠΎΡΡΠ΅ Π²ΡΡΠΈΡΠ»ΡΡΡΡΡ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠΈ ΠΏΠΎΡΠ²Π»Π΅Π½ΠΈΡ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π·Π½Π°ΠΊΠ° Π² ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠΈ ΠΈ ΡΠΎΡΡΠ°Π²Π»ΡΠ΅ΡΡΡ ΡΠ°Π±Π»ΠΈΡΠ° ΠΊΠΎΠ΄Π° Π₯Π°ΡΡΠΌΠ΅Π½Π°. ΠΠ° ΡΠ»Π΅Π΄ΡΠ΅ΡΠ΅ΠΌ ΡΡΠ°ΠΏΠ΅ ΠΎΡΡΡΠ΅ΡΡΠ²Π»ΡΠ΅ΡΡΡ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Π½Π° ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠΈ ΡΡΠ°ΡΠΈΡΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΡΡΡΠΊΡΡΡΡ Π΄Π΅ΡΠ΅Π²Π° Π₯Π°ΡΡΠΌΠ΅Π½Π° ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°ΡΠ° ΡΠΈΠΌΠ²ΠΎΠ»ΠΎΠ² Π² ΡΠΆΠ°ΡΠΎΠΌ Π²ΠΈΠ΄Π΅. ΠΡΠΉΠ³ΡΡΡ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΠΉ Π·Π° ΡΡΠ΅Ρ ΡΠΆΠ°ΡΠΈΡ Π΄Π°Π½Π½ΡΡ ΠΌΠΎΠΆΠ΅Ρ Π·Π°ΠΌΠ΅ΡΠ½ΠΎ ΡΠ½ΠΈΠΆΠ°ΡΡΡΡ, ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎ ΠΏΡΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°ΡΠΈ ΠΊΠΎΡΠΎΡΠΊΠΈΡ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠΉ, Π² ΡΠ²ΡΠ·ΠΈ Ρ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎΡΡΡΡ ΠΏΠ΅ΡΠ΅Π΄Π°Π²Π°ΡΡ Π΄Π΅ΠΊΠΎΠ΄Π΅ΡΡ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΡΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΡ ΠΎ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΌ Π΄Π΅ΡΠ΅Π²Π΅. ΠΡΠ΅ ΠΎΠ΄ΠΈΠ½ Π½Π΅Π΄ΠΎΡΡΠ°ΡΠΎΠΊ ΡΡΠΎ Π½Π°Π»ΠΈΡΠΈΠ΅ Π·Π°Π΄Π΅ΡΠΆΠΊΠΈ ΠΎΡ ΠΌΠΎΠΌΠ΅Π½ΡΠ° ΠΏΠΎΡΡΡΠΏΠ»Π΅Π½ΠΈΡ Π΄Π°Π½Π½ΡΡ ΠΎΡ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠ° Π΄ΠΎ Π²ΡΠ΄Π°ΡΠΈ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΡ ΠΊΠΎΠ΄ΠΎΠ²ΡΡ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΠΉ, ΡΡΠΎ ΠΎΠ³ΡΠ°Π½ΠΈΡΠΈΠ²Π°Π΅Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ Π½Π΅ΡΠ°Π²Π½ΠΎΠΌΠ΅ΡΠ½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π² ΡΠΈΡΡΠ΅ΠΌΠ°Ρ ΡΠ΅Π°Π»ΡΠ½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ.
3.1. ΠΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Ρ Π°ΡΡΠΌΠ΅Π½Π°
Π Π½Π°ΡΠ°Π»Π΅ 70-Ρ Π³ΠΎΠ΄ΠΎΠ² Π±ΡΠ»ΠΈ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠ°Π½Ρ ΠΎΠ΄Π½ΠΎΠΏΡΠΎΡ ΠΎΠ΄Π½ΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΡΠΆΠ°ΡΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ. Π‘ΡΡΡ ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠΎΠΌ, ΡΡΠΎ ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡΠΈΠΊ ΡΡΡΠΎΠΈΡ Π΄Π΅ΡΠ΅Π²ΠΎ Π₯Π°ΡΡΠΌΠ΅Π½Π° Π² ΡΠ΅ΠΌΠΏΠ΅ ΠΏΠΎΡΡΡΠΏΠ»Π΅Π½ΠΈΡ Π΄Π°Π½Π½ΡΡ ΠΎΡ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠ°. Π ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡ «ΠΎΠ±ΡΡΠ΅Π½ΠΈΠ΅» ΠΊΠΎΠ΄Π΅ΡΠ° Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ ΡΡΠ°ΡΠΈΡΡΠΈΡΠ΅ΡΠΊΠΈΡ Ρ Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΡΡΠΈΠΊ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠ° ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠΉ Π² Ρ ΠΎΠ΄Π΅ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π²ΡΡΠΈΡΠ»ΡΡΡΡΡ ΠΎΡΠ΅Π½ΠΊΠΈ ΠΈΡΡ ΠΎΠ΄Π½ΡΡ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠ΅ΠΉ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΡ ΠΈ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡΡ ΠΌΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΡ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Π₯Π°ΡΡΠΌΠ΅Π½Π°. Π’. ΠΊ. ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡ Π½Π΅ΠΏΡΠ΅ΡΡΠ²Π½ΠΎΠ΅ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π΄Π΅ΡΠ΅Π²Π°, ΡΡΠΎΡ ΠΏΡΠΎΡΠ΅ΡΡ ΠΏΠΎΠ»ΡΡΠΈΠ» Π½Π°Π·Π²Π°Π½ΠΈΠ΅ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π₯Π°ΡΡΠΌΠ΅Π½Π°. ΠΠ΅ΠΊΠΎΠ΄Π΅Ρ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π½Π΅ΠΏΡΠ΅ΡΡΠ²Π½ΠΎ «ΡΡΠΈΡΡΡΡ» Π½Π°ΡΡΠ΄Ρ Ρ ΠΊΠΎΠ΄Π΅ΡΠΎΠΌ ΠΎΡΡΡΠ΅ΡΡΠ²Π»ΡΡ ΡΠΈΠ½Ρ ΡΠΎΠ½Π½ΠΎΠ΅ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π΄Π΅ΡΠ΅Π²Π°. ΠΠ»Ρ ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠ΅Π½ΠΈΡ ΡΠΈΠ½Ρ ΡΠΎΠ½Π½ΠΎΡΡΠΈ ΠΏΡΠΎΡΠ΅ΡΡΠΎΠ² ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΈ Π΄Π΅ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΊΠΎΠ΄Π΅Ρ Π²ΡΠ΄Π°Π΅Ρ ΡΠΈΠΌΠ²ΠΎΠ» Π² Π½Π΅ΡΠΆΠ°ΡΠΎΠΌ Π²ΠΈΠ΄Π΅, Π΅ΡΠ»ΠΈ ΠΎΠ½ Π²ΠΏΠ΅ΡΠ²ΡΠ΅ ΠΏΠΎΡΠ²ΠΈΠ»ΡΡ Π½Π° Π²ΡΡ ΠΎΠ΄Π΅ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠ°, ΠΈ ΠΎΡΠΌΠ΅ΡΠ°Π΅Ρ Π΅Π³ΠΎ Π½Π° ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΌ Π΄Π΅ΡΠ΅Π²Π΅. ΠΡΠΈ ΠΏΠΎΠ²ΡΠΎΡΠ½ΠΎΠΌ ΠΏΠΎΡΠ²Π»Π΅Π½ΠΈΠΈ ΡΠΈΠΌΠ²ΠΎΠ»Π° Π½Π° Π²Ρ ΠΎΠ΄Π΅ Π΄Π΅ΠΊΠΎΠ΄Π΅ΡΠ° ΠΎΠ½ ΠΏΠ΅ΡΠ΅Π΄Π°Π΅ΡΡΡ Π½Π΅ΡΠ°Π²Π½ΠΎΠΌΠ΅ΡΠ½ΠΎΠΉ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΉ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΠ΅ΠΉ, ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΠΌΠΎΠΉ ΠΏΠΎΠ·ΠΈΡΠΈΠ΅ΠΉ ΡΠΈΠΌΠ²ΠΎΠ»Π° Π½Π° ΡΠ΅ΠΊΡΡΠ΅ΠΌ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΌ Π΄Π΅ΡΠ΅Π²Π΅.
ΠΠ° ΠΎΠ΄Π½ΠΎΠΌ ΡΡΠΎΠ²Π½Π΅ Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΌΠ΅Π½ΡΡΠ΅ 2-Ρ ΡΠ·Π»ΠΎΠ², ΠΏΠ°ΡΠ° ΡΠ·Π»ΠΎΠ² ΡΠ²Π»ΡΠ΅ΡΡΡ Π΄ΠΎΡΠ΅ΡΠ½Π΅ΠΉ, Ρ.ΠΊ. ΠΈΠΌΠ΅Π΅Ρ ΠΎΠ±ΡΠΈΠΉ ΡΠΎΠ΄ΠΈΡΠ΅Π»ΡΡΠΊΠΈΠΉ ΡΠ·Π΅Π», Π²Π΅Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΡΠ°Π²Π΅Π½ ΡΡΠΌΠΌΠ΅ Π²Π΅ΡΠΎΠ² Π΄ΠΎΡΠ΅ΡΠ½ΠΈΡ ΡΠ·Π»ΠΎΠ².
Π₯Π°ΡΡΠΌΠ΅Π½ΡΠΊΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΠΎΠ±Π»Π°Π΄Π°ΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌΠΈ ΡΠ²ΠΎΠΉΡΡΠ²Π°ΠΌΠΈ:
ΠΠΈΡΡΡΡ ΠΈΠΌΠ΅ΡΡ Π½Π΅ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΠΉ Π²Π΅Ρ W>0, ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠΎΠ΄ΠΈΡΠ΅Π»ΡΡΠΊΠΈΠΉ ΡΠ·Π΅Π» ΠΈΠΌΠ΅Π΅Ρ Π΄ΠΎΡΠ΅ΡΠ½ΠΈΠ΅ ΡΠ·Π»Ρ, Π° Π΅Π³ΠΎ Π²Π΅Ρ ΡΠ°Π²Π΅Π½ ΡΡΠΌΠΌΠ΅ Π΄ΠΎΡΠ΅ΡΠ½ΠΈΡ Π²Π΅ΡΠΎΠ².
ΠΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΡΠΎΠ²Π½Π΅ Π΄Π΅ΡΠ΅Π²Π°, ΠΊΡΠΎΠΌΠ΅ ΠΊΠΎΡΠ½Π΅Π²ΠΎΠ³ΠΎ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±ΡΡΡ Π½Π΅ ΠΌΠ΅Π½Π΅Π΅ ΠΎΠ΄Π½ΠΎΠΉ ΠΏΠ°ΡΡ ΡΠ·Π»ΠΎΠ², ΠΈΠΌΠ΅ΡΡΠΈΡ ΠΎΠ±ΡΠΈΠΉ ΡΠΎΠ΄ΠΈΡΠ΅Π»ΡΡΠΊΠΈΠΉ ΡΠ·Π΅Π».
ΠΡΠ΅ ΡΠ·Π»Ρ Π½ΡΠΌΠ΅ΡΡΡΡΡΡ Π² Π²ΠΎΠ·ΡΠ°ΡΡΠ°ΡΡΠ΅ΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅, ΡΠ·Π»Ρ Ρ Π½ΠΎΠΌΠ΅ΡΠ°ΠΌΠΈ (2j-1) ΠΈ 2j ΡΠ²Π»ΡΡΡΡΡ ΡΠ·Π»Π°ΠΌΠΈ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΡΠΎΠ²Π½Ρ Π΄Π»Ρ 1<=j<=m-1, ΠΈΡ ΠΎΠ±ΡΠΈΠΉ ΡΠΎΠ΄ΠΈΡΠ΅Π»ΡΡΠΊΠΈΠΉ ΡΠ·Π΅Π» ΠΈΠΌΠ΅Π΅Ρ Π±ΠΎΠ»Π΅Π΅ Π²ΡΡΠΎΠΊΠΈΠΉ ΡΡΠΎΠ²Π΅Π½Ρ.
3.2. ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ fgk
Π‘ΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠΎΡΡΠΎΠΈΡ Π² ΠΏΡΠΎΡΠ΅Π΄ΡΡΠ΅ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ Π»ΠΈΡΡΡΠ΅Π² ΠΈ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ Π±ΠΈΠ½Π°ΡΠ½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ Π²Π΅ΡΠΎΠΌ ΠΏΡΡΠΈ Wjlj.
ΠΠ° 1-ΠΌ ΡΡΠ°ΠΏΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ Π₯Π°ΡΡΠΌΠ΅Π½Π° ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΡΠ΅ΡΡΡ Π² ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½ΡΠ½ΠΎΠ΅ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΌΡ, ΠΊΠΎΡΠΎΡΠΎΠ΅ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΎ Π² Ρ Π°ΡΡΠΌΠ΅Π½ΠΎΠ²ΡΠΊΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ Π΄Π»Ρ M (k+1).
1-ΠΉ ΡΡΠ°ΠΏ Π½Π°ΡΠΈΠ½Π°Π΅ΡΡΡ ΠΏΠΎΡΠ»Π΅ ΠΏΠΎΠ»ΡΡΠ΅Π½ΠΈΡ ΠΎΡ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠ° ΡΠΈΠΌΠ²ΠΎΠ»Π° z (k+1), ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΠΎΠ»ΡΡΠ°Π΅Ρ ΡΡΠ°ΡΡΡ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ ΡΠ·Π»Π°. ΠΠ°ΡΠ΅ΠΌ ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡ ΠΎΠ±ΠΌΠ΅Π½ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ ΡΠ·Π»Π° (Π²ΠΊΠ»ΡΡΠ°Ρ ΠΏΠΎΠ΄Π΄Π΅ΡΠ΅Π²ΠΎ) Ρ ΡΠ·Π»ΠΎΠΌ ΠΈΠΌΠ΅ΡΡΠΈΠΌ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΉ ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²ΡΠΉ Π½ΠΎΠΌΠ΅Ρ Ρ ΡΠ°ΠΊΠΈΠΌ ΠΆΠ΅ Π²Π΅ΡΠΎΠΌ. Π ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ Π½ΠΎΠ²ΠΎΠ³ΠΎ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ ΡΠ·Π»Π° ΠΈΠ½ΠΈΡΠΈΠ»ΠΈΠ·ΠΈΡΡΠ΅ΡΡΡ ΡΠΎΠ΄ΠΈΡΠ΅Π»ΡΡΠΊΠΈΠΉ ΡΠ·Π΅Π» ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅Π³ΠΎ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ ΡΠ·Π»Π°. ΠΠ±ΠΌΠ΅Π½ Π² ΡΠ»ΡΡΠ°Π΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎΡΡΠΈ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΠ°ΡΠ½ΠΎ ΠΏΠΎΠ²ΡΠΎΡΡΠ΅ΡΡΡ ΠΏΠΎΠΊΠ° Π½Π΅ Π±ΡΠ΄Π΅Ρ Π΄ΠΎΡΡΠΈΠ³Π½ΡΡ ΠΊΠΎΡΠ΅Π½Ρ Π΄Π΅ΡΠ΅Π²Π°. ΠΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΎΠΊ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠ³ΡΡ ΠΏΠΎΠ½Π°Π΄ΠΎΠ±ΠΈΡΡΡΡ ΡΠ°Π²Π½Π° Π²ΡΡΠΎΡΠ΅ Π΄Π΅ΡΠ΅Π²Π°. ΠΠ° 2-ΠΌ ΡΡΠ°ΠΏΠ΅ ΠΈΠ½ΠΊΡΠ΅ΠΌΠ΅Π½ΡΠΈΡΡΠ΅ΡΡΡ Π»ΠΈΡΡ Π΄Π΅ΡΠ΅Π²Π° ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΉ ΠΎΠ±ΡΠ°Π±Π°ΡΡΠ²Π°Π΅ΠΌΠΎΠΌΡ ΡΠΈΠΌΠ²ΠΎΠ»Ρ ΠΈ ΠΏΠΎΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΡΠ΅ ΡΠ·Π»Ρ, ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½ΡΠ΅ Π½Π° ΠΏΡΡΠΈ Π΄Π²ΠΈΠΆΠ΅Π½ΠΈΡ ΠΎΡ Π»ΠΈΡΡΠ° ΠΊ ΠΊΠΎΡΠ½Ρ Π΄Π΅ΡΠ΅Π²Π°.
3.3. ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π²ΠΈΡΡΠ΅ΡΠ°
ΠΠ°Π½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΠΏΠΎΡΡΡΠΎΠΈΡΡ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ Ρ Π°ΡΡΠΌΠ΅Π½ΡΠΊΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ ΡΠ°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΡΡΠΎ Π±Ρ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°ΡΡ ΡΡΠΌΠ°ΡΠ½ΡΡ Π΄Π»ΠΈΠ½Ρ Π²Π½Π΅ΡΠ½Π΅Π³ΠΎ ΠΏΡΡΠΈ ΠΈ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΎΡ ΠΊΠΎΡΠ½Ρ Π΄Π΅ΡΠ΅Π²Π° Π΄ΠΎ Π»ΠΈΡΡΠ°. Π§ΠΈΡΠ»ΠΎ ΠΎΠ±ΠΌΠ΅Π½ΠΎΠ² ΡΠ·Π»ΠΎΠ² Π² ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΠΌΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΠΈ ΡΠ²ΠΎΠ΄ΠΈΡΡΡ ΠΊ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΡ. ΠΠΈΠ½ΠΈΠΌΠΈΠ·Π°ΡΠΈΡ Π²ΡΡΠΎΡΡ Π΄Π΅ΡΠ΅Π²Π° h= max{ lj} ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ ΠΏΡΠ΅Π΄ΠΎΡΠ²ΡΠ°ΡΠΈΡΡ ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ Π΄Π»ΠΈΠ½Π½ΡΡ ΠΊΠΎΠ΄ΠΎΠ²ΡΡ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΠΉ ΠΏΡΠΈ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠ³ΠΎ ΡΠΈΠΌΠ²ΠΎΠ»Π° Π² ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠΈ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠΈΡΡΠ΅ΡΠ° ΠΎΠ±Π»Π°Π΄Π°Π΅Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌΠΈ ΠΏΡΠ΅ΠΈΠΌΡΡΠ΅ΡΡΠ²Π°ΠΌΠΈ ΠΏΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡ Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠΌ FGK:
ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΎΠ±ΠΌΠ΅Π½ΠΎΠ² ΡΠ·Π»Π°ΠΌΠΈ, ΠΏΡΠΈ ΠΊΠΎΡΠΎΡΠΎΠΌ ΡΠ΅ΠΊΡΡΠΈΠΉ ΡΠ·Π΅Π» ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°Π΅ΡΡΡ Π² Π²Π΅ΡΡ ΠΏΠΎ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΌΡ Π΄Π΅ΡΠ΅Π²Ρ Π² ΠΏΡΠΎΡΠ΅ΡΡΠ΅ Π΅Π³ΠΎ ΠΌΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΠΈ ΠΎΠ³ΡΠ°Π½ΠΈΡΠΈΠ²Π°Π΅ΡΡΡ Π΅Π΄Π΅Π½ΠΈΡΠ΅ΠΉ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠΈΡΡΠ΅ΡΠ° ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡΡΠ΅Ρ Π΄Π»ΠΈΠ½Ρ Π²Π½Π΅ΡΠ½Π΅Π³ΠΎ ΠΏΡΡΠΈ Π΄Π΅ΡΠ΅Π²Π° lj ΠΈ Π³Π°ΡΠ°Π½ΡΠΈΡΡΠ΅Ρ Π΄Π΅ΡΠ΅Π²ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ Π²ΡΡΠΎΡΡ h= max{ lj} ΠΏΡΠΈ ΡΡΠ»ΠΎΠ²ΠΈΠΈ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°ΡΠΈΠΈ ΡΡΠΌΠΌΠ°ΡΠ½ΠΎΠΉ Π΄Π»ΠΈΠ½Ρ Π²Π½Π΅ΡΠ½Π΅Π³ΠΎ ΠΏΡΡΠΈ Π΄Π΅ΡΠ΅Π²Π°.
ΠΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΠΈΡΡΠ΅ΡΠ° ΠΎΡΡΡΠ΅ΡΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ°ΠΊ Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠ°Ρ Π½Π΅ΡΠ²Π½Π°Ρ Π½ΡΠΌΠ΅ΡΠ°ΡΠΈΡ (implicit numbering) ΡΠ·Π»ΠΎΠ² ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π°. ΠΡΠΈ Π½Π΅ΡΠ²Π½ΠΎΠΉ Π½ΡΠΌΠ΅ΡΠ°ΡΠΈΠΈ ΡΠ·Π»Ρ Ρ Π°ΡΡΠΌΠ΅Π½ΡΠΊΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Π½ΡΠΌΠ΅ΡΡΡΡΡΡ Π² ΠΏΠΎΡΡΠ΄ΠΊΠ΅ ΡΠ²Π΅Π»Π΅ΡΠ΅Π½ΠΈΡ ΠΏΠΎ ΡΡΠΎΠ²Π½ΡΠΌ ΡΠ»Π΅Π²Π° Π½Π°ΠΏΡΠ°Π²ΠΎ ΠΈ ΡΠ½ΠΈΠ·Ρ Π²Π²Π΅ΡΡ . ΠΠ°ΠΆΠ½Π΅ΠΉΡΠΈΠΌ ΡΡΠ»ΠΎΠ²ΠΈΠ΅ΠΌ Π½Π΅ΡΠ²Π½ΠΎΠΉ Π½ΡΠΌΠ΅ΡΠ°ΡΠΈΠΈ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠΎΠ±Π»ΡΠ΄Π΅Π½ΠΈΠ΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎΠ³ΠΎ ΡΡΠ»ΠΎΠ²ΠΈΡ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ Π΄Π΅ΡΠ΅Π²Π°:
ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π²Π΅ΡΠ° W Π²ΡΠ΅ Π»ΠΈΡΡΡΡ Π΄Π΅ΡΠ΅Π²Π° Ρ Π²Π΅ΡΠΎΠΌ W Π΄ΠΎΠ»ΠΆΠ½Ρ ΠΏΡΠ΅Π΄ΡΠ΅ΡΡΠ²ΠΎΠ²Π°ΡΡ Π²ΡΠ΅ΠΌ Π²Π½ΡΡΡΠ΅Π½Π½ΠΈΠΌ ΡΠ·Π»Π°ΠΌ Π²Π΅ΡΠ° W.
Π‘ΡΡΡΠΊΡΡΡΠ½Π°Ρ ΡΡ Π΅ΠΌΠ° Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΠΈΡΡΠ΅ΡΠ° ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Π° Π½Π° ΡΠΈΡΡΠ½ΠΊΠ΅ 1.
ΠΠ° ΡΠΈΡΡΠ½ΠΊΠ΅ 2 ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Π° ΡΡΡΡΠΊΡΡΡΠ½Π°Ρ ΡΡ Π΅ΠΌΠ° ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ ΡΠΊΠΎΠ»ΡΠΆΠ΅Π½ΠΈΡ ΠΈ ΠΏΡΠΈΡΠ°ΡΠ΅Π½ΠΈΡ.
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½Π°Ρ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ
ΠΠ»Ρ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π±ΡΠ» Π²ΡΠ±ΡΠ°Π½ ΡΠ·ΡΠΊ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π²ΡΡΠΎΠΊΠΎΠ³ΠΎ ΡΡΠΎΠ²Π½Ρ Delphi 5.0 (Object Pascal).
ΠΠ½ Π²Π΅ΡΡΠΌΠ° ΠΏΠΎΠ»Π½ΠΎ Π²ΡΡΠ°ΠΆΠ°Π΅Ρ ΠΈΠ΄Π΅ΠΈ ΡΡΡΡΠΊΡΡΡΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ. ΠΡΠΎ ΠΏΡΠΎΡΠ²Π»ΡΠ΅ΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎ Delphi ΠΌΠΎΠΆΠ΅Ρ ΡΡΠΏΠ΅ΡΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ Π΄Π»Ρ Π·Π°ΠΏΠΈΡΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌ Π½Π° ΡΠ°Π·Π½ΡΡ ΡΡΠΎΠ²Π½ΡΡ Π΅Π΅ Π΄Π΅ΡΠ°Π»ΠΈΠ·Π°ΡΠΈΠΈ, Π½Π΅ ΠΏΡΠΈΠ±Π΅Π³Π°Ρ ΠΊ ΠΏΠΎΠΌΠΎΡΠΈ Π±Π»ΠΎΠΊ-ΡΡ Π΅ΠΌ ΠΈΠ»ΠΈ ΡΠΏΠ΅ΡΠΈΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠ·ΡΠΊΠ° ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌ. Π‘ΡΠ΅Π΄ΡΡΠ²Π° ΡΠ·ΡΠΊΠ° Delphi ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡ ΠΎΡΡΡΠ΅ΡΡΠ²Π»ΡΡΡ Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΡΠΉ ΠΊΠΎΠ½ΡΡΠΎΠ»Ρ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΡΡΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ Π΄Π°Π½Π½ΡΡ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ ΡΠΈΠΏΠΎΠ² ΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΊΠ°ΠΊ Π½Π° ΡΡΠ°ΠΏΠ΅ ΡΡΠ°Π½ΡΠ»ΡΡΠΈΠΈ ΡΠ°ΠΊ ΠΈ Π½Π° ΡΡΠ°ΠΏ Π΅Π΅ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ.
Delphi ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ Π±Π΅Π· ΠΎΡΠΎΠ±ΡΡ ΡΡΡΠ΄Π½ΠΎΡΡΠ΅ΠΉ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ ΡΠ΄ΠΎΠ±Π½ΡΠΉ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»ΡΡΠΊΠΈΠΉ ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡ, Π½Π΅ ΠΏΡΠ΅Π±ΠΈΠ³Π°Ρ ΠΊ Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΡ Π½ΠΈΠ·ΠΊΠΎΡΡΠΎΠ²Π½Π΅Π²ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π°.
Π ΠΏΡΠΎΠ΅ΠΊΡΠ΅ ΠΏΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠ³Π°Π΅ΡΡΡ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Π½Π΅ΠΏΡΠ΅ΡΡΠ²Π½ΠΎ ΠΏΠΎΡΡΡΠΏΠ°ΡΡΠ΅ΠΉ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ, ΠΏΠΎΡΡΠΎΠΌΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ Π²Π²ΠΎΠ΄ΠΈΡΡ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅ Ρ ΠΊΠ»Π°Π²ΠΈΠ°ΡΡΡΡ, ΠΊΠΎΡΠΎΡΠΎΠ΅ ΠΊΠΎΠ΄ΠΈΡΡΠ΅ΡΡΡ ΠΈ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ°Π΅Ρ ΡΡΡΡΠΊΡΡΡΡ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Ρ Π°ΡΡΠΌΠ΅Π½Π°.
ΠΠ΅ΠΊΠΎΠ΄ΠΈΡΠΎΠ²ΠΊΡ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡ ΠΏΠΎ ΡΠΈΠΌΠ²ΠΎΠ»ΡΠ½ΠΎ ΠΈ ΠΏΠΎ Π±ΠΈΡΠ°ΠΌ.
Π ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ΅ Π΅ΡΡΡ ΡΠ°ΠΊ ΠΆΠ΅ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡ ΡΡΠΈΡΠ°ΡΡ Π΄Π°Π½Π½ΡΠ΅ Π΄Π»Ρ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΈΠ· ΡΡΠΉΠ»Π°.
Π ΡΠΊΠΎΠ²ΠΎΠ΄ΡΡΠ²ΠΎ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΠΏΠΎΠ΄ ΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠ΅ΠΌ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΎΠ½Π½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ Windows 9. x.
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΈΠΌΠ΅Π΅Ρ ΡΠ΄ΠΎΠ±Π½ΡΠΉ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»ΡΡΠΊΠΈΠΉ ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡ.
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΈΠΌΠ΅Π΅Ρ Π΄Π²Π΅ ΠΎΡΠ½ΠΎΠ²Π½ΡΠ΅ ΠΎΠ±Π»Π°ΡΡΠΈ: ΠΊΠΎΠ΄ΠΈΡΠΎΠ²ΠΊΠ° ΠΈ Π΄Π΅ΠΊΠΎΠ΄ΠΈΡΠΎΠ²ΠΊΠ°. Π‘ΠΏΡΠ°Π²Π° ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΎ ΠΏΠΎΠ»Π΅ Π΄Π»Ρ Π²Π²ΠΎΠ΄Π° ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΡ. Π ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΠΏΠΎΡΡΡΠΏΠ»Π΅Π½ΠΈΡ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΡ Π² ΠΎΠΊΠ½Π΅ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²ΠΊΠ° ΡΡΡΠΎΠΈΡΡΡ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ. Π ΠΏΠΎΠ»Π΅ Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ°ΡΡΡΡ ΠΏΠΎΡΡΡΠΏΠ°ΡΡΠΈΠ΅ Π΄Π°Π½Π½ΡΠ΅. Π ΠΏΠΎΠ»Π΅ ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ΅ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ°Π΅ΡΡΡ Π·Π°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅.
ΠΠ΅ΠΊΠΎΠ΄ΠΈΡΠΎΠ²ΠΊΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡ ΠΊΠ°ΠΊ ΠΏΠΎ ΡΠΈΠΌΠ²ΠΎΠ»Π°ΠΌ, ΡΠ°ΠΊ ΠΈ ΠΏΠΎ Π±ΠΈΡΠ°ΠΌ. ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠ΅ ΠΊΠ½ΠΎΠΏΠΊΠΈ: Π‘ΠΈΠΌΠ²ΠΎΠ» ΠΈ ΠΠΈΡ.
Π Π΅Π·ΡΠ»ΡΡΠ°Ρ Π΄Π΅ΠΊΠΎΠ΄ΠΈΡΠΎΠ²ΠΊΠΈ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ°Π΅ΡΡΡ Π² ΠΏΠΎΠ»Π΅ ΠΠ΅ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅. Π ΠΏΡΠΎΡΠ΅ΡΡΠ΅ Π΄Π΅ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΡΡΡΠΎΠΈΡΡΡ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ.
ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
Π Ρ ΠΎΠ΄Π΅ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΠΊΡΡΡΠΎΠ²ΠΎΠΉ ΡΠ°Π±ΠΎΡΡ Π±ΡΠ»ΠΈ Π·Π°ΠΊΡΠ΅ΠΏΠ»Π΅Π½Ρ Π·Π½Π°Π½ΠΈΡ, ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΠ΅ Π² Ρ ΠΎΠ΄Π΅ ΠΈΠ·ΡΡΠ΅Π½ΠΈΡ Π΄ΠΈΡΡΠΈΠΏΠ»ΠΈΠ½Ρ «ΠΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΈ Π·Π°ΡΠΈΡΠ° ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ». Π Π°Π±ΠΎΡΠ° Π²ΡΠΏΠΎΠ»Π½Π΅Π½Π° Π² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠΈ Ρ ΠΏΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ Π½Π° ΠΊΡΡΡΠΎΠ²ΠΎΠ΅ ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅.
ΠΠ»Ρ ΠΏΡΠΎΠ²Π΅ΡΠΊΠΈ ΡΠ°Π±ΠΎΡΠΎΡΠΏΠΎΡΠΎΠ±Π½ΠΎΡΡΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΠΈ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΡΡΠΈ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ Π²Ρ ΠΎΠ΄Π½ΡΡ Π΄Π°Π½Π½ΡΡ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠ°Π½ ΡΠ΅ΡΡΠΎΠ²ΡΠΉ ΠΏΡΠΈΠΌΠ΅Ρ. Π’Π΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΠΏΠΎΠ΄ΡΠ²Π΅ΡΠ΄ΠΈΠ»ΠΎ, ΡΡΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎ Π²ΡΠΏΠΎΠ»Π½ΠΈΠ»Π° ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΡ Π΄Π°Π½Π½ΡΡ ΠΈ Π²ΡΠ΄Π°Π΅Ρ Π²Π΅ΡΠ½ΡΠ΅ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ.
ΠΠΈΠ±Π»ΠΈΠΎΠ³ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΡΠΏΠΈΡΠΎΠΊ
ΠΠΎΠ½ΡΠΏΠ΅ΠΊΡ Π»Π΅ΠΊΡΠΈΠΉ ΠΏΠΎ ΠΊΡΡΡΡ «ΠΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΈ Π·Π°ΡΠΈΡΠ° ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ»
Π¦ΡΠΌΠ±Π°Π» Π.Π. «Π’Π΅ΠΎΡΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ ΠΈ ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅. «- ΠΠΈΠ΅Π²: «ΠΠΈΡΠ° ΡΠΊΠΎΠ»Π°», 1982 — 303Ρ.
Π.Π‘. Π§Π΅ΡΠ½Π΅Π³Π° «Π‘ΠΆΠ°ΡΠΈΠ΅ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ Π² ΠΊΠΎΠΌΠΏΡΡΡΠ΅ΡΠ½ΡΡ ΡΠ΅ΡΡΡ » — Π‘Π΅Π²ΠΠ’Π£, Π‘Π΅Π²Π°ΡΡΠΎΠΏΠΎΠ»Ρ 1997.
ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ
ΠΠ ΠΠΠΠΠΠΠΠ A
Π’Π΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΠΡΡ ΠΎΠ΄Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: Hello world!
Π’Π°Π±Π»ΠΈΡΠ° 1. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 1
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 1 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: H | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: | |
* 3
H
Π’Π°Π±Π»ΠΈΡΠ° 2. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 2
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 2 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: He | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: 1 101 000 1 100 101 | |
H 5
3 4
* e
Π’Π°Π±Π»ΠΈΡΠ° 3. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 3
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 3 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: Hel | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: 1 101 000 1 100 101 1 001 101 100 | |
5 6
* l H e
1 2 3 4
Π’Π°Π±Π»ΠΈΡΠ° 4. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 4
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 4 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: Hell | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: 1 101 000 1 100 101 1 001 101 100 01 | |
l
5 6
e
3 4
* H
Π’Π°Π±Π»ΠΈΡΠ° 5. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 5
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 5 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: Hello | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: 1 101 000 1 100 101 1 001 101 100 01 110 1 101 111 | |
7 8
e h l
3 4 5 6
* o
Π’Π°Π±Π»ΠΈΡΠ° 6. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 6
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 6 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: Hello_ | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: 1 101 000 1 100 101 1 001 101 100 01 110 1 101 111 100 100 000 | |
9 10
e l
5 6 7 8
* - h o
1 2 3 4
Π’Π°Π±Π»ΠΈΡΠ° 7. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 7
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 7 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: Hello_ w | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: 1 101 000 1 100 101 1 001 101 100 01 110 1 101 111 100 100 000 1 001 110 111 | |
11 12
l
7 8 9 10
* w e — h o
1 2 3 4 5 6
Π’Π°Π±Π»ΠΈΡΠ° 8. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 8
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 8 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: Hello_ wo | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: 1 101 000 1 100 101 1 001 101 100 01 110 1 101 111 100 100 000 1 001 110 111 111 | |
11 12
o l
7 8 9 10
e h
3 4 5 6
* w
Π’Π°Π±Π»ΠΈΡΠ° 9. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 9
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 9 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: Hello_ wor | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: 1 101 000 1 100 101 1 001 101 100 01 110 1 101 111 100 100 000 1 001 110 111 111 1110 1 110 010 | |
o 13 14
9 10 11 12
h w e — l
3 4 5 6 7 8
* r
1 2
Π’Π°Π±Π»ΠΈΡΠ° 10. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 10
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 10 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: Hello_ worl | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: 1 101 000 1 100 101 1 001 101 100 01 110 1 101 111 100 100 000 1 001 110 111 111 1110 1 110 010 111 | |
13 l 14
9 10 11 12
h w e — o
3 4 5 6 / 7 8
* r
1 2
Π’Π°Π±Π»ΠΈΡΠ° 11. ΠΡΠ΅ΡΠ°ΡΠΈΡ№ 11
ΠΡΠ΅ΡΠ°ΡΠΈΡ № 11 | |
Π‘ΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: Hello_ world | |
ΠΠ°ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π½Π½ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅: 1 101 000 1 100 101 1 001 101 100 01 110 1 101 111 100 100 000 1 001 110 111 111 1110 1 110 010 111 1100 1 100 100 | |
15 16
l
11 12 13 14
h w e o
5 6 7 8 9 10
* d — r
1 2 3 4
ΠΠ ΠΠΠΠΠΠΠΠ Π Π’Π΅ΠΊΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ
unit Form;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, ExtCtrls, Core;
type
TForm1 = class (TForm)
InChar: TEdit;
Panel1: TPaintBox;
Panel2: TPaintBox;
Label1: TLabel;
Label2: TLabel;
CodeTableMemo: TMemo;
MessageMemo: TMemo;
Label3: TLabel;
Label4: TLabel;
CodedMsg: TMemo;
Button1: TButton;
DecodedMsg: TMemo;
Button2: TButton;
Label5: TLabel;
procedure InCharKeyPress (Sender: TObject; var Key: Char);
procedure Button1Click (Sender: TObject);
procedure FormResize (Sender: TObject);
procedure FormPaint (Sender: TObject);
procedure Button2Click (Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
Tree, DecodeTree: PTree;
codetable: array [char] of string;
decodetable: array [char] of string;
procedure MakeCodeTable (Top: PTree);
implementation
{$R *. DFM}
procedure DrawTree (D: TPaintBox; P: Ptree; w, h: integer);
var
C: TCanvas;
procedure Draw (T: PTree; x, y, level, ofs: integer);
begin
if (T<>nil) then
begin
if (T. Left<>nil) then
begin
c. MoveTo (x, y);
c. LineTo (x-(ofs div 2), y+30);
end;
if (T. Right<>nil) then
begin
c. MoveTo (x, y);
c. LineTo (x+(ofs div 2), y+30);
end;
C. Ellipse (x-12,y-12,x+12,y+12);
if t. isleaf then if t. symbol=#0 then C. TextOut (x-4,y-25,'*') else C. TextOut (x-4,y-25,t. Symbol);
C. TextOut (x-6,y-7, inttostr (T. wiegth));
C. TextOut (x-6,y+12, inttostr (T. number));
Draw (T. Left, x-(ofs div 2), y+30,level+1,ofs div 2);
Draw (T. Right, x+(ofs div 2), y+30,level+1,ofs div 2);
end;
end;
begin
C: =D. Canvas;
C. Brush. Color: =clBtnFace;
C. FillRect (D. ClientRect);
Draw (P, w div 2,30,1,w div 2);
end;
procedure MakeDeCodeTable (Top: PTree);
procedure CT (P: PTree; code: string);
begin
if P<>nil then
begin
if (P. Wiegth>=0) and (P. IsLeaf) then
begin
decodetable [P. Symbol]: =code;
end;
if not P. IsLeaf then
begin
CT (P. Left, code+'0');
CT (P. Right, code+'1');
end;
end;
end;
begin
CT (Top,'');
end;
var
DCounter: integer;
DString: String;
DByte: byte;
DB: Boolean;
procedure AddCharToDMess (C: Char);
var
S: String;
begin
With Form1. DecodedMsg do
begin
S: =Text;
Clear;
Text: =S+C;
end;
end;
procedure Decode (BIT: Char);
var
i, j: integer;
c: char;
begin
if DB then
begin
if DCounter=0 then
DCounter: =7 else
dec (DCounter);
DByte: =((DByte shl 1) or (byte (bit) and 1));
if DCounter=0 then
begin
AddSymbol (DecodeTree, chr (DByte));
CheckWiegth (DecodeTree);
Enumerate (DecodeTree);
Huffman (DecodeTree);
Vitter (DecodeTree);
DrawTree (Form1. Panel2, DecodeTree, Form1. Panel2. ClientWidth, 500);
MakeDeCodeTable (DecodeTree);
AddCharToDMess (chr (DByte));
DString: ='';
DB: =false;
end;
end else
if DecodeTree=nil then
begin
DB: =true;
Decode (BIT);
end else
begin
DString: =DString + Bit;
for c: =#0 to #255 do
begin
if DecodeTable [c] =DString then
begin
if c=#0 then
begin
DB: =true;
DCounter: =0;
end else
begin
AddSymbol (DecodeTree, c);
CheckWiegth (DecodeTree);
Enumerate (DecodeTree);
Huffman (DecodeTree);
Vitter (DecodeTree);
DrawTree (Form1. Panel2, DecodeTree, Form1. Panel2. ClientWidth, 500);
MakeDeCodeTable (DecodeTree);
DString: ='';
AddCharToDMess (c);
DB: =false;
break;
end;
end;
end;
end;
end;
procedure MakeCodeTable (Top: PTree);
procedure CT (P: PTree; code: string);
begin
if P<>nil then
begin
if (P. Wiegth>=0) and (P. IsLeaf) then
begin
codetable [P. Symbol]: =code;
end;
if not P. IsLeaf then
begin
CT (P. Left, code+'0');
CT (P. Right, code+'1');
end;
end;
end;
begin
CT (Top,'');
end;
procedure ShowCT;
var
C: Char;
begin
Form1. CodeTableMemo. Clear;
For c: =#0 to #255 do
begin
if CodeTable [c] <>'' then
begin
Form1. CodeTableMemo. Lines. Append (c+' - '+CodeTable [c]);
end;
end;
end;
procedure AddCharToMess (C: Char);
var
S: String;
begin
With Form1. MessageMemo do
begin
S: =Text;
Clear;
Text: =S+C;
end;
end;
procedure AddCoded (c: char);
var
s: string;
begin
S: =Form1. CodedMsg. Lines. Text;
Form1. CodedMsg. Clear;
Form1. CodedMsg. Lines. Text: =S+' '+CodeTable [c];
end;
procedure AddASC (c: char);
var
i: integer;
s: string;
b: byte;
begin
s: ='';
b: =byte (c);
for i: =1 to 8 do
begin
s: =chr ((b and 1) +$ 30) +s;
b: =(b shr 1);
end;
S: =Form1. CodedMsg. Lines. Text+' '+s;
Form1. CodedMsg. Clear;
Form1. CodedMsg. Lines. Text: =S;
end;
procedure TForm1. InCharKeyPress (Sender: TObject; var Key: Char);
var
B: Boolean;
begin
B: =AddSymbol (Tree, Key);
CheckWiegth (Tree);
Enumerate (Tree);
Huffman (Tree);
DrawTree (Panel1,Tree, Panel1. ClientWidth, 500);
Application. MessageBox ('stop','stop', MB_OK);
Vitter (Tree);
DrawTree (Panel1,Tree, Panel1. ClientWidth, 500);
if B then
begin
AddCoded (#0);
AddASC (key);
end else
begin
AddCoded (key);
end;
MakeCodeTable (Tree);
AddCharToMess (Key);
ShowCT;
InChar. Clear;
end;
procedure TForm1. Button1Click (Sender: TObject);
var
s: string;
c: char;
begin
s: =CodedMsg. Text;
if (s<>'') then
begin
while s =' ' do Delete (s, 1,1);
while ((s<>'') and (s <>' ')) do
begin
Decode (s [1]);
Delete (s, 1,1);
end;
CodedMsg. Clear;
CodedMsg. Text: =s;
end;
end;
procedure TForm1. FormResize (Sender: TObject);
begin
Panel1. Top: =20;
Panel1. Height: =(ClientHeight div 2) — 20;
Label2. Top: =(ClientHeight div 2);
Panel2. top: =(ClientHeight div 2) +20;
Panel2. Height: =(ClientHeight div 2) — 20;
end;
procedure TForm1. FormPaint (Sender: TObject);
begin
DrawTree (Panel1,Tree, Panel1. ClientWidth, 500);
DrawTree (Panel2,DecodeTree, Panel2. ClientWidth, 500);
end;
procedure TForm1. Button2Click (Sender: TObject);
var
s: string;
c: char;
begin
s: =CodedMsg. Text;
if (s<>'') then
begin
while s =' ' do Delete (s, 1,1);
if ((s<>'') and (s <>' ')) then
begin
Decode (s [1]);
Delete (s, 1,1);
end;
CodedMsg. Clear;
CodedMsg. Text: =s;
end;
end;
end.
unit Core;
{$B-}
interface
uses Graphics;
type
PTree = ^TTree;
TTree = record
Left, Right, Up: PTree;
Symbol: char;
Wiegth: integer;
Number: integer;
IsLeaf: boolean;
end;
function NewNode (l, r, u: PTree; s: char; c, n: integer; i: boolean): PTree;
procedure DeleteTree (var P: PTree);
function AddNewSymbolToTree (var Top: PTree; c: char): boolean;
function AddSymbolToTree (var Top: PTree; c: char): boolean;
function AddSymbol (var Top: PTree; c: char): boolean;
function MaxLevel (Top: PTree): integer;
procedure NodesOnLevel (Top: PTree; var qol: integer; l, level: integer);
function GetNodeFromLevel (P: Ptree; level, number: integer; var l, n: integer): PTree;
procedure Enumerate (P: PTree);
function CheckWiegth (P: PTree): integer;
function GetNodeByNumber (P: PTree; number: integer): PTree;
function GetLeafByWiegthMax (P: PTree; wiegth: integer): PTree;
procedure Vitter (P: PTree);
procedure Huffman (P: PTree);
implementation
Uses Math, SysUtils;
{$B-}
function CheckWiegth (P: PTree): integer;
begin
Result: =0;
if P<>nil then
begin
if not P. Isleaf then
begin
Result: =CheckWiegth (P. left) +CheckWiegth (P. right);
P. Wiegth: =Result;
end else Result: =P. Wiegth;
end else
Result: =0;
end;
procedure Huffman (P: PTree);
var
i, j, k: integer;
t, tt: PTree;
tmp: TTree;
begin
k: =1;
t: =GetNodeByNumber (P, k);
while t<>nil do
begin
tt: =GetNodeByNumber (P, k+1);
if tt<>nil then
begin
if tt. Wiegth
begin
move (tt^, tmp, sizeof (tmp));
move (t^, tt^, sizeof (tmp));
move (tmp, t^, sizeof (tmp));
CheckWiegth (P);
Enumerate (P);
k: =1;
end;
end;
inc (k);
T: =GetNodeByNumber (P, k);
end;
end;
procedure Vitter (P: PTree);
var
i, j, k, l: integer;
t, tt, ttt: PTree;
tmp: TTree;
begin
k: =1;
t: =GetNodeByNumber (P, 1);
while t<>nil do
begin
if not T. IsLeaf then
begin
tt: =GetLeafByWiegthMax (P, t. wiegth);
if (tt<>nil) then
begin
if (tt. Number>T. Number) then
begin
move (tt^, tmp, sizeof (tmp));
move (t^, tt^, sizeof (tmp));
move (tmp, t^, sizeof (tmp));
CheckWiegth (P);
Enumerate (P);
k: =1;
end;
end;
end;
inc (k);
T: =GetNodeByNumber (P, k);
end;
end;
function GetLeafByWiegthMax (P: PTree; wiegth: integer): PTree;
var
i: integer;
Node: PTree;
begin
Result: =nil;
i: =1;
Node: =GetNodeByNumber (P, i);
while Node<>nil do
begin
if Node. Wiegth > wiegth then exit; // ???
if Node. IsLeaf and (Node. Wiegth=wiegth) then
begin
Result: =Node;
end;
inc (i);
Node: =GetNodeByNumber (P, i);
end;
end;
function GetNodeByNumber (P: PTree; number: integer): PTree;
begin
if (P<>nil) then
begin
if P. Number=number then result: =P else
begin
Result: =GetNodeByNumber (P. Left, number);
if Result=nil then Result: =GetNodeByNumber (P. Right, number);
end;
end else Result: =nil;
end;
procedure Enumerate (P: PTree);
var
i, j, k, l, n, o, s: integer;
T: PTree;
begin
n: =0;
k: =MaxLevel (P);
for i: =k downto 1 do
begin
o: =1;
s: =1;
l: =1;
T: =GetNodeFromLevel (P, i, l, o, s);
while T<>nil do
begin
inc (n);
T. Number: =n;
inc (l);
o: =1;
s: =1;
T: =GetNodeFromLevel (P, i, l, o, s);
end;
end;
end;
function GetNodeFromLevel (P: PTREE; level, number: integer; var l, n: integer): PTree;
var
T: PTRee;
begin
result: =nil;
if (P<>nil) then
begin
if (l
begin
inc (l);
T: =GetNodeFromLevel (P. Left, level, number, l, n);
dec (l);
if (T=nil) then
begin
inc (l);
Result: =GetNodeFromLevel (P. Right, level, number, l, n);
dec (l);
end
else Result: =T;
end else
begin
if (l=level) then
begin
if (n=number) then result: =P else
begin
result: =nil;
end;
inc (n);
end else result: =nil;
end;
end else
result: =nil;
end;
procedure NodesOnLevel (Top: PTree; var qol: integer; l, level: integer);
begin
if Top<>nil then
begin
if level=l then
begin
inc (qol);
end else
begin
NodesOnLevel (top. Left, qol, l+1,Level);
NodesOnLevel (top. Right, qol, l+1,Level);
end;
end;
end;
function MaxLevel (Top: PTree): integer;
begin
if (Top=nil) then
begin
Result: =0;
end else
begin
Result: =Max (MaxLevel (Top. Left), MaxLevel (Top. Right)) +1;
end;
end;
function AddSymbol (var Top: PTree; c: char): boolean;
begin
if (not AddSymbolToTree (Top, c)) then
if (not AddNewSymbolToTree (Top, c)) then
result: =false // Error
else
result: =true // Added
else
result: =false; // Updated
end;
function AddSymbolToTree (var Top: PTree; c: char): boolean;
begin
if Top=nil then Result: =False else
begin
if Top. IsLeaf then
begin
if Top. Symbol=c then
begin
inc (Top. Wiegth);
result: =true;
end else
begin
result: =false;
end;
end else
begin
if AddSymbolToTree (Top. left, c) or AddSymbolToTree (Top. right, c) then
begin
inc (Top. Wiegth);
result: =true;
end else
result: =false;
end;
end;
end;
function AddNewSymbolToTree (var Top: PTree; c: char): boolean;
begin
if Top=nil then
begin
Top: =NewNode (nil, nil, nil,#0,1,0,false);
Top. left: =NewNode (nil, nil, Top,#0,0,0,true);
Top. Right: =NewNode (nil, nil, Top, c,1,0,true);
result: =true;
end else
begin
if (Top. Wiegth=0) and (top. Symbol=#0) then
begin
Top. Left: =NewNode (nil, nil, Top,#0,0,0,true);
Top. Right: =NewNode (nil, nil, Top, c,1,0,true);
Top. IsLeaf: =false;
Top. Wiegth: =1;
Result: =true;
end else
begin
if (Top. Left<>nil) and AddNewSymbolToTree (Top. Left, c) then
begin
result: =true;
exit;
end;
if (Top. Right<>nil) and AddNewSymbolToTree (Top. Right, c) then
begin
result: =true;
exit;
end;
result: =false;
end;
end;
end;
procedure DeleteTree (var P: PTree);
begin
if P=nil then exit;
DeleteTree (P. Left);
DeleteTree (P. Right);
Dispose (P);
P: =nil;
end;
function NewNode (l, r, u: ptree; s: char; c, n: integer; i: boolean): PTree;
var
P: PTree;
begin
new (P);
P. Left: =l;
P. Right: =r;
P. Up: =u;
P. Symbol: =s;
P. Wiegth: =c;
P. Number: =n;
P. IsLeaf: =i;
result: =P;
end;
end.