ΠΠ°Π½Π½ΡΠΉ ΡΠ΅ΠΏΠΎΠ·ΠΈΡΠΎΡΠΈΠΉ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΠΊΡΠ°ΡΠΊΠΎΠ΅ ΠΈΠ·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΡ (Π. ΠΡ Π°ΡΠ³Π°Π²Π°, "ΠΡΠΎΠΊΠ°Π΅ΠΌ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ"). Π‘ΠΎΠ΄Π΅ΡΠΆΠΈΠΌΠΎΠ΅ ΡΠ΅ΠΏΠΎΠ·ΠΈΡΠΎΡΠΈΡ Π½Π΅ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ Π»ΠΈΡΠ½Π΅ΠΉ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ (Π½Π° ΠΌΠΎΠΉ Π²Π·Π³Π»ΡΠ΄), ΡΡΠΎ Π·Π½Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΠΏΠΎΠΌΠΎΠ³Π°Π΅Ρ Π² ΡΡΠ²ΠΎΠ΅Π½ΠΈΠΈ ΠΌΠ°ΡΠ΅ΡΠΈΠ°Π»Π°. ΠΠΎΠΌΠΈΠΌΠΎ ΠΊΡΠ°ΡΠΊΠΎΠ³ΠΎ ΠΈΠ·Π»ΠΎΠΆΠ΅Π½ΠΈΡ, ΡΠ΅ΠΏΠΎΠ·ΠΈΡΠΎΡΠΈΠΉ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ Π°Π½ΠΈΠΌΠΈΡΠΎΠ²Π°Π½Π½ΡΠ΅ ΠΈΠ·ΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΡ (GIF), ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΡΠΉ ΠΊΠΎΠ΄ Π½Π° Java/Kotlin. ΠΠ°Π΄Π΅ΡΡΡ, ΡΡΠΎ ΠΌΠ°ΡΠ΅ΡΠΈΠ°Π», ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Π½ΡΠΉ Π² ΡΠ΅ΠΏΠΎΠ·ΠΈΡΠΎΡΠΈΠΈ, Π±ΡΠ΄Π΅Ρ ΠΠ°ΠΌ ΠΏΠΎΠ»Π΅Π·Π΅Π½!
# | ΠΠ°Π³ΠΎΠ»ΠΎΠ²ΠΎΠΊ | ΠΡΠΈΠΌΠ΅ΡΡ |
---|---|---|
1 | ΠΠ½Π°ΠΊΠΎΠΌΡΡΠ²ΠΎ Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°ΠΌΠΈ | Java, Kotlin |
2 | Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ | Java, Kotlin |
3 | Π Π΅ΠΊΡΡΡΠΈΡ | Java, Kotlin |
4 | ΠΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° | Java, Kotlin |
5 | Π₯Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ | Java, Kotlin |
6 | ΠΠΎΠΈΡΠΊ Π² ΡΠΈΡΠΈΠ½Ρ | Java, Kotlin |
7 | ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ | Java, Kotlin |
8 | ΠΠ°Π΄Π½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ | Java, Kotlin |
9 | ΠΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ | Java, Kotlin |
- ΠΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ
- Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ
- Π Π΅ΠΊΡΡΡΠΈΡ
- ΠΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°
- "Π Π°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉ"
- ΠΠ°ΡΠ° ΡΠ»ΠΎΠ² ΠΎ ΡΡΠ½ΠΊΡΠΈΠΎΠ½Π°Π»ΡΠ½ΠΎΠΌ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ
- Π£ΠΏΡΠ°ΠΆΠ½Π΅Π½ΠΈΡ
- Quick Sort (ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π½Π° Java)
- ΠΠ± "Π-Π±ΠΎΠ»ΡΡΠΎΠΌ"
- Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ ΠΈ Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°
- Π¨ΠΏΠ°ΡΠ³Π°Π»ΠΊΠ°
- Π₯Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ
- ΠΠΎΠΈΡΠΊ Π² ΡΠΈΡΠΈΠ½Ρ
- ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ
- ΠΠ°Π΄Π½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ
- ΠΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅
ΠΠ»Π³ΠΎΡΠΈΡΠΌΠΎΠΌ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π½Π°Π±ΠΎΡ ΠΈΠ½ΡΡΡΡΠΊΡΠΈΠΉ Π΄Π»Ρ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ. Π ΠΏΡΠΈΠ½ΡΠΈΠΏΠ΅, Π»ΡΠ±ΠΎΠΉ ΡΡΠ°Π³ΠΌΠ΅Π½Ρ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π° ΠΌΠΎΠΆΠ½ΠΎ Π½Π°Π·Π²Π°ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠΌ.
ΠΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ - Π°Π»Π³ΠΎΡΠΈΡΠΌ; Π½Π° Π²Ρ ΠΎΠ΄Π΅ ΠΎΠ½ ΠΏΠΎΠ»ΡΡΠ°Π΅Ρ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΡΠΏΠΈΡΠΎΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ². ΠΡΠ»ΠΈ ΡΠ»Π΅ΠΌΠ΅Π½Ρ, ΠΊΠΎΡΠΎΡΡΠΉ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π½Π°ΠΉΡΠΈ, ΠΏΡΠΈΡΡΡΡΡΠ²ΡΠ΅Ρ Π² ΡΠΏΠΈΡΠΊΠ΅, ΡΠΎ Π±ΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ ΡΡ ΠΏΠΎΠ·ΠΈΡΠΈΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ ΠΎΠ½ Π±ΡΠ» Π½Π°ΠΉΠ΄Π΅Π½. Π ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π±ΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ null.
ΠΡΠΈ Π±ΠΈΠ½Π°ΡΠ½ΠΎΠΌ ΠΏΠΎΠΈΡΠΊΠ΅ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ°Π· ΠΈΡΠΊΠ»ΡΡΠ°Π΅ΡΡΡ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Π° ΡΠΈΡΠ΅Π».
ΠΠ»Ρ ΡΠΏΠΈΡΠΊΠ° ΠΈΠ· n ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π±ΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π·Π° log2(n) ΡΠ°Π³ΠΎΠ², ΡΠΎΠ³Π΄Π° ΠΊΠ°ΠΊ ΠΏΡΠΎΡΡΠΎΠΉ ΠΏΠΎΠΈΡΠΊ Π±ΡΠ΄Π΅Ρ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ Π·Π° n ΡΠ°Π³ΠΎΠ².
ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ. ΠΠ»Ρ ΡΠΏΠΈΡΠΊΠ° ΠΈΠ· 8 ΡΠΈΡΠ΅Π» Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ 3 ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ, ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ 2^3 = 8. ΠΠ»Ρ ΡΠΏΠΈΡΠΊΠ° ΠΈΠ· 1024 ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΏΠΎΡΡΠ΅Π±ΡΠ΅ΡΡΡ 10 ΠΈΡΠ΅ΡΠ°ΡΠΈΠΉ, ΡΠ°ΠΊ ΠΊΠ°ΠΊ 2^10 = 1024.
ΠΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΠΎΠ»ΡΠΊΠΎ Π² ΡΠΎΠΌ ΡΠ»ΡΡΠ°Π΅, Π΅ΡΠ»ΠΈ ΡΠΏΠΈΡΠΎΠΊ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½.
Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π½Π° Java: Binary Search
ΠΠΈΠ½Π΅ΠΉΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ - Π²ΡΠ΅ΠΌΡ, ΠΊΠΎΠ³Π΄Π° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΏΠΎΠΏΡΡΠΎΠΊ ΡΠΎΠ²ΠΏΠ°Π΄Π°Π΅Ρ Ρ ΡΠ°Π·ΠΌΠ΅ΡΠΎΠΌ ΡΠΏΠΈΡΠΊΠ°.
ΠΡΠ°ΠΊ, ΠΏΡΠΎΡΡΠΎΠΉ ΠΏΠΎΠΈΡΠΊ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ O(n), Π° Π±ΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ - Π·Π° Π²ΡΠ΅ΠΌΡ O(log n).
ΠΠΈΠΆΠ΅ ΠΏΠ΅ΡΠ΅ΡΠΈΡΠ»Π΅Π½Ρ ΠΏΡΡΡ ΡΠ°Π·Π½ΠΎΠ²ΠΈΠ΄Π½ΠΎΡΡΠ΅ΠΉ "Π-Π±ΠΎΠ»ΡΡΠΎΠ³ΠΎ", ΠΊΠΎΡΠΎΡΡΠ΅ Π±ΡΠ΄ΡΡ Π²ΡΡΡΠ΅ΡΠ°ΡΡΡΡ ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎ ΡΠ°ΡΡΠΎ, Π² ΠΏΠΎΡΡΠ΄ΠΊΠ΅ ΡΠ±ΡΠ²Π°Π½ΠΈΡ ΡΠΊΠΎΡΠΎΡΡΠΈ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ.
ΠΡΠΈΠΌΠ΅ΡΡ "O-Π±ΠΎΠ»ΡΡΠΎΠ³ΠΎ"
- O(log n), ΠΈΠ»ΠΈ Π»ΠΎΠ³Π°ΡΠΈΡΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ Π²ΡΠ΅ΠΌΡ. ΠΡΠΈΠΌΠ΅Ρ: Π±ΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ.
- O(n), ΠΈΠ»ΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ. ΠΡΠΈΠΌΠ΅Ρ: ΠΏΡΠΎΡΡΠΎΠΉ ΠΏΠΎΠΈΡΠΊ.
- O(n * log n). ΠΡΠΈΠΌΠ΅Ρ: ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ (Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°).
- O(n^2). ΠΡΠΈΠΌΠ΅Ρ: ΠΌΠ΅Π΄Π»Π΅Π½Π½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ (ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ).
- O(n!). ΠΡΠΈΠΌΠ΅Ρ: ΠΎΡΠ΅Π½Ρ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ (Π·Π°Π΄Π°ΡΠ° ΠΎ ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΠ΅ΡΠ΅).
- Π‘ΠΊΠΎΡΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Π½Π΅ ΠΈΠ·ΠΌΠ΅ΡΡΠ΅ΡΡΡ Π² ΡΠ΅ΠΊΡΠ½Π΄Π°Ρ .
- ΠΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΎΠΏΠΈΡΡΠ²Π°Π΅ΡΡΡ ΡΠΎΡΡΠΎΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ.
- ΠΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Π²ΡΡΠ°ΠΆΠ°Π΅ΡΡΡ ΠΊΠ°ΠΊ "Π-Π±ΠΎΠ»ΡΡΠΎΠ΅".
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ (Π°Π½Π³Π». selection sort) - ΠΏΡΠΎΡΡΠΎΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΠΊΠΎΡΠΎΡΡΠΉ ΠΈΠΌΠ΅Π΅Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ O(n^2).
ΠΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ i-ΠΎΠΌ ΡΠ°Π³Π΅ Π½Π°Ρ ΠΎΠ΄ΠΈΠΌ i-ΡΠΉ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΈ ΠΌΠ΅Π½ΡΠ΅ΠΌ Π΅Π³ΠΎ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ Ρ i-ΡΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠΌ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ Π±ΡΠ΄Π΅Ρ ΠΏΠΎΠ»ΡΡΠ΅Π½ ΠΌΠ°ΡΡΠΈΠ², ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΠΏΠΎ Π²ΠΎΠ·ΡΠ°ΡΡΠ°Π½ΠΈΡ.
ΠΡΠ²Π΅Ρ Π½Π° Π΄Π°Π½Π½ΡΠΉ Π²ΠΎΠΏΡΠΎΡ ΡΠ²ΡΠ·Π°Π½ Ρ ΡΠΎΠ»ΡΡ ΠΊΠΎΠ½ΡΡΠ°Π½Ρ Π² "Π-Π±ΠΎΠ»ΡΡΠΎΠΌ". ΠΠ°, Π² Π΄Π΅ΠΉΡΡΠ²ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ Π½Π΅ Π½ΡΠΆΠ½ΠΎ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ°Π· ΠΏΡΠΎΠ²Π΅ΡΡΡΡ ΡΠΏΠΈΡΠΎΠΊ ΠΈΠ· n ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ². Π‘Π½Π°ΡΠ°Π»Π° ΠΏΡΠΎΠ²Π΅ΡΡΡΡΡΡ n ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΠΏΠΎΡΠΎΠΌ n - 1, n - 2 ... 2, 1. Π ΡΡΠ΅Π΄Π½Π΅ΠΌ ΠΏΡΠΎΠ²Π΅ΡΡΠ΅ΡΡΡ ΡΠΏΠΈΡΠΎΠΊ ΠΈΠ· 1/2 * n ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ². ΠΠ³ΠΎ Π²ΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΠΎΡΡΠ°Π²ΠΈΡ O(n * 1/2 * n). ΠΠ΄Π½Π°ΠΊΠΎ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΡ (ΡΠ°ΠΊΠΈΠ΅ ΠΊΠ°ΠΊ 1/2) Π² "O-Π±ΠΎΠ»ΡΡΠΎΠΌ" ΠΈΠ³Π½ΠΎΡΠΈΡΡΡΡΡΡ, ΠΏΠΎΡΡΠΎΠΌΡ ΠΌΡ ΠΏΡΠΎΡΡΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌ O(n * n), ΠΈΠ»ΠΈ O(n^2).
Π Π΅ΠΊΡΡΡΠΈΡ - ΠΌΠ΅ΡΠΎΠ΄ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΡΠΉ Π²ΠΎ ΠΌΠ½ΠΎΠ³ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°Ρ .
Π Π΅ΠΊΡΡΡΠΈΡ Π²ΡΠ·ΡΠ²Π°Π΅Ρ Ρ Π»ΡΠ΄Π΅ΠΉ ΠΏΡΠΎΡΠΈΠ²ΠΎΡΠ΅ΡΠΈΠ²ΡΠ΅ ΡΡΠ²ΡΡΠ²Π°. ΠΠ½ΠΈ Π»ΠΈΠ±ΠΎ ΠΎΠ±ΠΎΠΆΠ°ΡΡ Π΅Ρ, Π»ΠΈΠ±ΠΎ Π½Π΅Π½Π°Π²ΠΈΠ΄ΡΡ, Π»ΠΈΠ±ΠΎ Π½Π΅Π½Π°Π²ΠΈΠ΄ΡΡ, ΠΏΠΎΠΊΠ° Π½Π΅ ΠΏΠΎΠ»ΡΠ±ΡΡ ΡΠ΅ΡΠ΅Π· ΠΏΠ°ΡΡ-ΡΡΠΎΠΉΠΊΡ Π»Π΅Ρ. ΠΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΡΠ΅ΠΊΡΡΡΠΈΠΈ Π½Π΅ ΡΡΠΊΠΎΡΡΠ΅Ρ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ: Π±ΠΎΠ»Π΅Π΅ ΡΠΎΠ³ΠΎ, ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Ρ ΡΠΈΠΊΠ»Π°ΠΌΠΈ ΠΈΠ½ΠΎΠ³Π΄Π° ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π±ΡΡΡΡΠ΅Π΅.
ΠΠΈ ΠΠΎΠ»Π΄ΡΡΠ»Π» (Ρ ΡΠ°ΠΉΡΠ° Stack Overflow) ΡΠΊΠ°Π·Π°Π»:
Π¦ΠΈΠΊΠ»Ρ ΠΌΠΎΠ³ΡΡ ΡΡΠΊΠΎΡΠΈΡΡ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ. Π Π΅ΠΊΡΡΡΠΈΡ ΠΌΠΎΠΆΠ΅Ρ ΡΡΠΊΠΎΡΠΈΡΡ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΡΠ°. ΠΡΠ±ΠΈΡΠ°ΠΉΡΠ΅, ΡΡΠΎ Π²Π°ΠΆΠ½Π΅Π΅ Π² Π²Π°ΡΠ΅ΠΉ ΡΠΈΡΡΠ°ΡΠΈΠΈ!
ΠΠ°ΠΆΠ΄Π°Ρ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½Π°Ρ ΡΡΠ½ΠΊΡΠΈΡ ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· Π΄Π²ΡΡ ΡΠ°ΡΡΠ΅ΠΉ: Π±Π°Π·ΠΎΠ²ΠΎΠ³ΠΎ ΡΠ»ΡΡΠ°Ρ ΠΈ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎΠ³ΠΎ ΡΠ»ΡΡΠ°Ρ. Π ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΡΠ½ΠΊΡΠΈΡ Π²ΡΠ·ΡΠ²Π°Π΅Ρ ΡΠ°ΠΌΠ° ΡΠ΅Π±Ρ. Π Π±Π°Π·ΠΎΠ²ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΡΠ½ΠΊΡΠΈΡ ΡΠ΅Π±Ρ Π½Π΅ Π²ΡΠ·ΡΠ²Π°Π΅Ρ, ΡΡΠΎΠ±Ρ ΠΏΡΠ΅Π΄ΠΎΡΠ²ΡΠ°ΡΠΈΡΡ Π·Π°ΡΠΈΠΊΠ»ΠΈΠ²Π°Π½ΠΈΠ΅.
β¦ Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΡΠ»Π΅Π΄ΡΡΡΡΡ Π·Π°Π΄Π°ΡΡ. ΠΠ°ΠΏΠΈΡΠ°ΡΡ ΡΡΠ½ΠΊΡΠΈΡ Π΄Π»Ρ Π²ΡΠ²ΠΎΠ΄Π° ΠΎΠ±ΡΠ°ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΡΠ΅ΡΠ°.
ΠΠΎΡΠΌΠΎΡΡΠ΅ΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ
ΠΡΠ΅ ΡΡΠΎ Π²ΡΠ΅ΠΌΡ, ΡΠ°Π±ΠΎΡΠ°Ρ Ρ ΡΠ΅ΠΊΡΡΡΠΈΠ΅ΠΉ, ΠΌΡ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π»ΠΈΡΡ ΡΡΠ΅ΠΊΠΎΠΌ Π²ΡΠ·ΠΎΠ²ΠΎΠ².
ΠΠΎΠ½ΡΠ΅ΠΏΡΠΈΡ ΡΡΠ΅ΠΊΠ° Π²ΡΠ·ΠΎΠ²ΠΎΠ² ΠΈΠ³ΡΠ°Π΅Ρ Π²Π°ΠΆΠ½ΡΡ ΡΠΎΠ»Ρ Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ Π²ΠΎΠΎΠ±ΡΠ΅; ΠΊΡΠΎΠΌΠ΅ ΡΠΎΠ³ΠΎ, Π΅Π΅ Π²Π°ΠΆΠ½ΠΎ ΠΏΠΎΠ½ΠΈΠΌΠ°ΡΡ ΠΏΡΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ ΡΠ΅ΠΊΡΡΡΠΈΠΈ.
Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ ΡΡΠ΅ΠΊΠ° Π²ΡΠ·ΠΎΠ²ΠΎΠ²
Π Π΅ΠΊΡΡΡΠΈΠ²Π½ΡΠ΅ ΡΡΠ½ΠΊΡΠΈΠΈ ΡΠΎΠΆΠ΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡ ΡΡΠ΅ΠΊ Π²ΡΠ·ΠΎΠ²ΠΎΠ²! ΠΠΎΡΠΌΠΎΡΡΠΈΠΌ, ΠΊΠ°ΠΊ ΡΡΠΎ Π΄Π΅Π»Π°Π΅ΡΡΡ, Π½Π° ΠΏΡΠΈΠΌΠ΅ΡΠ΅ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ ΡΠ°ΠΊΡΠΎΡΠΈΠ°Π»Π°.
ΠΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ ΡΠ°ΠΊΡΠΎΡΠΈΠ°Π»Π°
Π‘ΡΠ΅ΠΊ ΡΠ΄ΠΎΠ±Π΅Π½, Π½ΠΎ Ρ Π½Π΅Π³ΠΎ Π΅ΡΡΡ ΡΠ²ΠΎΡ ΡΠ΅Π½Π°: ΡΠΎΡ ΡΠ°Π½Π΅Π½ΠΈΠ΅ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΠΎΠΉ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ ΠΌΠΎΠΆΠ΅Ρ ΠΏΡΠΈΠ²Π΅ΡΡΠΈ ΠΊ Π·Π½Π°ΡΠΈΡΠ΅Π»ΡΠ½ΡΠΌ Π·Π°ΡΡΠ°ΡΠ°ΠΌ ΠΏΠ°ΠΌΡΡΠΈ. ΠΠ°ΠΆΠ΄ΡΠΉ Π²ΡΠ·ΠΎΠ² ΡΡΠ½ΠΊΡΠΈΠΈ Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ Π½Π΅ ΠΌΠ½ΠΎΠ³ΠΎ ΠΏΠ°ΠΌΡΡΠΈ, Π½ΠΎ Π΅ΡΠ»ΠΈ ΡΡΠ΅ΠΊ ΡΡΠ°Π½Π΅Ρ ΡΠ»ΠΈΡΠΊΠΎΠΌ Π²ΡΡΠΎΠΊΠΈΠΌ, ΡΡΠΎ Π±ΡΠ΄Π΅Ρ ΠΎΠ·Π½Π°ΡΠ°ΡΡ, ΡΡΠΎ Π²Π°Ρ ΠΊΠΎΠΌΠΏΡΡΡΠ΅Ρ ΡΠΎΡ ΡΠ°Π½ΡΠ΅Ρ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΡ ΠΏΠΎ ΠΎΡΠ΅Π½Ρ ΠΌΠ½ΠΎΠ³ΠΈΠΌ Π²ΡΠ·ΠΎΠ²Π°ΠΌ. ΠΠ° ΡΡΠΎΠΉ ΡΡΠ°Π΄ΠΈΠΈ Π΅ΡΡΡ Π΄Π²Π° Π²Π°ΡΠΈΠ°Π½ΡΠ°:
- ΠΠ΅ΡΠ΅ΠΏΠΈΡΠ°ΡΡ ΠΊΠΎΠ΄ Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ ΡΠΈΠΊΠ»Π°.
- ΠΠΎΠΏΡΠΎΠ±ΠΎΠ²Π°ΡΡ Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ ΡΠ°ΠΊ Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠΎΠΉ Ρ Π²ΠΎΡΡΠΎΠ²ΠΎΠΉ ΡΠ΅ΠΊΡΡΡΠΈΠ΅ΠΉ.
- ΠΠΎΠ³Π΄Π° ΡΡΠ½ΠΊΡΠΈΡ Π²ΡΠ·ΡΠ²Π°Π΅Ρ ΡΠ°ΠΌΡ ΡΠ΅Π±Ρ, ΡΡΠΎ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠ΅ΠΊΡΡΡΠΈΠ΅ΠΉ.
- Π ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎΠΉ ΡΡΠ½ΠΊΡΠΈΠΈ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±ΡΡΡ Π΄Π²Π° ΡΠ»ΡΡΠ°Ρ: Π±Π°Π·ΠΎΠ²ΡΠΉ ΠΈ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΡΠΉ.
- Π‘ΡΠ΅ΠΊ ΠΏΠΎΠ΄Π΄Π΅ΡΠΆΠΈΠ²Π°Π΅Ρ Π΄Π²Π΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ: Π·Π°Π½Π΅ΡΠ΅Π½ΠΈΠ΅ ΠΈ ΠΈΠ·Π²Π»Π΅ΡΠ΅Π½ΠΈΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ².
- ΠΡΠ΅ Π²ΡΠ·ΠΎΠ²Ρ ΡΡΠ½ΠΊΡΠΈΠΉ ΡΠΎΡ ΡΠ°Π½ΡΡΡΡΡ Π² ΡΡΠ΅ΠΊΠ΅ Π²ΡΠ·ΠΎΠ²ΠΎΠ².
- ΠΡΠ»ΠΈ ΡΡΠ΅ΠΊ Π²ΡΠ·ΠΎΠ²ΠΎΠ² ΡΡΠ°Π½Π΅Ρ Π±ΠΎΠ»ΡΡΠΈΠΌ, ΠΎΠ½ Π·Π°ΠΉΠΌΠ΅Ρ ΡΠ»ΠΈΡΠΊΠΎΠΌ ΠΌΠ½ΠΎΠ³ΠΎ ΠΏΠ°ΠΌΡΡΠΈ.
ΠΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° - ΡΠ»Π΅Π³Π°Π½ΡΠ½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΡΠ°ΡΡΠΎ ΠΏΡΠΈΠΌΠ΅Π½ΡΠ΅ΠΌΡΠΉ Π½Π° ΠΏΡΠ°ΠΊΡΠΈΠΊΠ΅. ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅Ρ ΡΡΡΠ°ΡΠ΅Π³ΠΈΡ "ΡΠ°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉ".
ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π½Π°ΠΌΠ½ΠΎΠ³ΠΎ Π±ΡΡΡΡΠ΅Π΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π²ΡΠ±ΠΎΡΠΎΠΌ. ΠΠ½ ΡΠ²Π»ΡΠ΅ΡΡΡ Ρ ΠΎΡΠΎΡΠΈΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠΎΠΌ ΡΠ»Π΅Π³Π°Π½ΡΠ½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π°.
ΠΡΠ°ΠΊ, ΠΏΡΠ΅Π΄ΡΡΠ°Π²ΡΡΠ΅, ΡΡΠΎ Π²Ρ ΡΠ΅ΡΠΌΠ΅Ρ, Π²Π»Π°Π΄Π΅ΡΡΠΈΠΉ Π·Π΅ΠΌΠ΅Π»ΡΠ½ΡΠΌ ΡΡΠ°ΡΡΠΊΠΎΠΌ. ΠΠ΅ΠΌΠ΅Π»ΡΠ½ΡΠΉ ΡΡΠ°ΡΡΠΎΠΊ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ Π½Π° ΡΠΈΡΡΠ½ΠΊΠ΅ Π½ΠΈΠΆΠ΅.
ΠΡ Ρ ΠΎΡΠΈΡΠ΅ ΡΠ°Π²Π½ΠΎΠΌΠ΅ΡΠ½ΠΎ ΡΠ°Π·Π΄Π΅Π»ΠΈΡΡ Π·Π΅ΠΌΠ»Ρ Π½Π° ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΡΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΠ΅ ΡΡΠ°ΡΡΠΊΠΈ. Π£ΡΠ°ΡΡΠΊΠΈ Π΄ΠΎΠ»ΠΆΠ½Ρ Π±ΡΡΡ Π½Π°ΡΡΠΎΠ»ΡΠΊΠΎ Π±ΠΎΠ»ΡΡΠΈΠΌΠΈ, Π½Π°ΡΠΊΠΎΠ»ΡΠΊΠΎ ΡΡΠΎ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ.
ΠΠ°ΠΊ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΉ ΡΠ°Π·ΠΌΠ΅Ρ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ° Π΄Π»Ρ ΡΡΠ°ΡΡΠΊΠ°? ΠΠΎΡΠΏΠΎΠ»ΡΠ·ΡΠΉΡΠ΅ΡΡ ΡΡΡΠ°ΡΠ΅Π³ΠΈΠ΅ΠΉ "ΡΠ°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉ"! ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ Π½Π° Π±Π°Π·Π΅ ΡΡΠΎΠΉ ΡΡΡΠ°ΡΠ΅Π³ΠΈΠΈ ΡΠ²Π»ΡΡΡΡΡ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΡΠΌΠΈ.
Π Π΅ΡΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ "ΡΠ°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉ" ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· Π΄Π²ΡΡ ΡΠ°Π³ΠΎΠ²:
- Π‘Π½Π°ΡΠ°Π»Π° ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ Π±Π°Π·ΠΎΠ²ΡΠΉ ΡΠ»ΡΡΠ°ΠΉ. ΠΡΠΎ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±ΡΡΡ ΠΏΡΠΎΡΡΠ΅ΠΉΡΠΈΠΉ ΡΠ»ΡΡΠ°ΠΉ ΠΈΠ· Π²ΡΠ΅Ρ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΡ .
- ΠΠ°Π΄Π°ΡΠ° Π΄Π΅Π»ΠΈΡΡΡ ΠΈΠ»ΠΈ ΡΠΎΠΊΡΠ°ΡΠ°Π΅ΡΡΡ Π΄ΠΎ ΡΠ΅Ρ ΠΏΠΎΡ, ΠΏΠΎΠΊΠ° Π½Π΅ Π±ΡΠ΄Π΅Ρ ΡΠ²Π΅Π΄Π΅Π½Π° ΠΊ Π±Π°Π·ΠΎΠ²ΠΎΠΌΡ ΡΠ»ΡΡΠ°Ρ.
ΠΠ»Ρ Π½Π°ΡΠ°Π»Π° ΡΠ°Π·ΠΌΠ΅ΡΠΈΠΌ ΡΠ°ΠΌΡΠ΅ Π±ΠΎΠ»ΡΡΠΈΠ΅ ΡΡΠ°ΡΡΠΊΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ.
ΠΡΠ°ΠΊ, Π² ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΌ Π½Π°Π΄Π΅Π»Π΅ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΡΠΈΡΡ Π΄Π²Π° ΡΡΠ°ΡΡΠΊΠ° 640 Ρ 640, ΠΈ Π΅ΡΠ΅ ΠΎΡΡΠ°Π½Π΅ΡΡΡ ΠΌΠ΅ΡΡΠΎ. Π’ΡΡ-ΡΠΎ ΠΈ Π½Π°ΡΡΡΠΏΠ°Π΅Ρ ΠΌΠΎΠΌΠ΅Π½Ρ ΠΈΡΡΠΈΠ½Ρ. ΠΠ΅ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΉ ΠΎΡΡΠ°ΡΠΎΠΊ - ΡΡΠΎ ΡΠΎΠΆΠ΅ Π½Π°Π΄Π΅Π» Π·Π΅ΠΌΠ»ΠΈ, ΠΊΠΎΡΠΎΡΡΠΉ Π½ΡΠΆΠ½ΠΎ ΡΠ°Π·Π΄Π΅Π»ΠΈΡΡ. Π’ΠΎ Π΅ΡΡΡ ΠΊ Π½Π΅ΠΌΡ (Π½Π΅ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠΌΡ ΠΎΡΡΠ°ΡΠΊΡ) Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΡΠΈΠΌΠ΅Π½ΠΈΡΡ ΡΠΎΡ ΠΆΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌ.
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΌΡ ΡΠΎΠ»ΡΠΊΠΎ ΡΡΠΎ ΡΠΎΠΊΡΠ°ΡΠΈΠ»ΠΈ Π·Π°Π΄Π°ΡΡ Ρ ΡΠ°Π·ΠΌΠ΅ΡΠ° 1680 Ρ 640 Π΄ΠΎ 640 Ρ 400! ΠΠ²ΠΈΠ³Π°Π΅ΠΌΡΡ Π΄Π°Π»ΡΡΠ΅!
Π’Π΅ΠΏΠ΅ΡΡ Π½Π°ΠΌ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΠ°Π·Π΄Π΅Π»ΠΈΡΡ ΡΠ΅Π³ΠΌΠ΅Π½Ρ 640 Ρ 400. Π Π°Π·ΠΌΠ΅ΡΡ ΡΠ°ΠΌΠΎΠ³ΠΎ Π±ΠΎΠ»ΡΡΠΎΠ³ΠΎ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ°, ΠΊΠΎΡΠΎΡΡΠΉ ΠΌΠΎΠΆΠ½ΠΎ ΡΠΎΠ·Π΄Π°ΡΡ, ΡΠΎΡΡΠ°Π²Π»ΡΡΡ 400 Ρ 400 ΠΌ (ΡΠΌ. ΡΠΈΡΡΠ½ΠΎΠΊ Π½ΠΈΠΆΠ΅).
ΠΠΎΡΠ»Π΅ ΡΠ°Π·Π΄Π΅Π»Π΅Π½ΠΈΡ ΠΎΡΡΠ°Π΅ΡΡΡ ΠΌΠ΅Π½ΡΡΠΈΠΉ ΡΠ΅Π³ΠΌΠ΅Π½Ρ Ρ ΡΠ°Π·ΠΌΠ΅ΡΠ°ΠΌΠΈ 400 Ρ 240 ΠΌ. Π Π°Π·Π΄Π΅Π»ΠΈΠΌ ΡΡΠΎΡ ΡΠ΅Π³ΠΌΠ΅Π½Ρ (ΡΠΌ. ΡΠΈΡΡΠ½ΠΎΠΊ Π½ΠΈΠΆΠ΅).
ΠΡΡΠ΅ΠΊΠ°Ρ ΠΏΠΎΠ΄Π΅Π»Π΅Π½Π½ΡΡ ΡΠ°ΡΡΡ, ΠΌΡ ΠΏΡΠΈΡ ΠΎΠ΄ΠΈΠΌ ΠΊ Π΅ΡΠ΅ ΠΌΠ΅Π½ΡΡΠ΅ΠΌΡ ΡΠ°Π·ΠΌΠ΅ΡΡ ΡΠ΅Π³ΠΌΠ΅Π½ΡΠ°, 240 Ρ 160 ΠΌ.
ΠΠΎΡΠ»Π΅ ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠ³ΠΎ ΠΎΡΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΏΠΎΠ»ΡΡΠ°Π΅ΡΡΡ Π΅ΡΠ΅ ΠΌΠ΅Π½ΡΡΠΈΠΉ ΡΠ΅Π³ΠΌΠ΅Π½Ρ (ΡΠΌ. ΡΠΈΡΡΠ½ΠΎΠΊ Π½ΠΈΠΆΠ΅).
Π£ΡΠ°, ΠΌΡ ΠΏΡΠΈΡΠ»ΠΈ ΠΊ Π±Π°Π·ΠΎΠ²ΠΎΠΌΡ ΡΠ»ΡΡΠ°Ρ: 160 ΠΊΡΠ°ΡΠ½ΠΎ 80. ΠΡΠ»ΠΈ ΡΠ°Π·Π±ΠΈΡΡ ΡΡΠΎΡ ΡΠ΅Π³ΠΌΠ΅Π½Ρ Π½Π° ΠΊΠ²Π°Π΄ΡΠ°ΡΡ, Π½ΠΈΡΠ΅Π³ΠΎ Π»ΠΈΡΠ½Π΅Π³ΠΎ Π½Π΅ ΠΎΡΡΠ°Π½Π΅ΡΡΡ!
ΠΡΠ°ΠΊ, Π΄Π»Ρ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π½Π°Π΄Π΅Π»Π° Π·Π΅ΠΌΠ»ΠΈ ΡΠ°ΠΌΡΠΉ Π±ΠΎΠ»ΡΡΠΎΠΉ ΡΠ°Π·ΠΌΠ΅Ρ ΡΡΠ°ΡΡΠΊΠ° Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π΅Π½ 80 Ρ 80 ΠΌ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ²ΠΊΠ»ΠΈΠ΄Π°
"ΠΡΠ»ΠΈ Π²Ρ Π½Π°ΠΉΠ΄Π΅ΡΠ΅ ΡΠ°ΠΌΡΠΉ Π±ΠΎΠ»ΡΡΠΎΠΉ ΡΡΠ°ΡΡΠΎΠΊ, ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡΠΈΠΉ Π΄Π»Ρ ΡΡΠΎΠ³ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΠ°, ΡΡΠΎ Π±ΡΠ΄Π΅Ρ ΡΠ°ΠΌΡΠΉ Π±ΠΎΠ»ΡΡΠΎΠΉ ΡΡΠ°ΡΡΠΎΠΊ, ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡΠΈΠΉ Π΄Π»Ρ Π²ΡΠ΅ΠΉ ΡΠ΅ΡΠΌΡ."ΠΡΠ»ΠΈ ΠΠ°Ρ ΠΈΠ½ΡΠ΅ΡΠ΅ΡΡΠ΅Ρ Π΄ΠΎΠΊΠ°Π·Π°ΡΠ΅Π»ΡΡΡΠ²ΠΎ, ΠΏΠΎΠΈΡΠΈΡΠ΅ "Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΠ²ΠΊΠ»ΠΈΠ΄Π°".
ΠΠ°ΠΊ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΡΡΠ°ΡΠ΅Π³ΠΈΡ "ΡΠ°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉ":
- ΠΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΠ΅ ΠΏΡΠΎΡΡΠ΅ΠΉΡΠΈΠΉ ΡΠ»ΡΡΠ°ΠΉ ΠΊΠ°ΠΊ Π±Π°Π·ΠΎΠ²ΡΠΉ.
- ΠΡΠΈΠ΄ΡΠΌΠ°ΠΉΡΠ΅, ΠΊΠ°ΠΊ ΡΠ²Π΅ΡΡΠΈ Π·Π°Π΄Π°ΡΡ ΠΊ Π±Π°Π·ΠΎΠ²ΠΎΠΌΡ ΡΠ»ΡΡΠ°Ρ.
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΌΡ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π»ΠΈ ΡΡΡΡ ΡΡΡΠ°ΡΠ΅Π³ΠΈΠΈ "ΡΠ°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉ".
Π ΡΠ·ΡΠΊΠ°Ρ ΡΡΠ½ΠΊΡΠΈΠΎΠ½Π°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ, ΡΠ°ΠΊΠΈΡ ΠΊΠ°ΠΊ Haskell, ΡΠΈΠΊΠ»ΠΎΠ² Π½Π΅Ρ, ΠΏΠΎΡΡΠΎΠΌΡ Π΄Π»Ρ Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΡ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΏΡΠΈΡ ΠΎΠ΄ΠΈΡΡΡ ΠΏΡΠΈΠΌΠ΅Π½ΡΡΡ ΡΠ΅ΠΊΡΡΡΠΈΡ. ΠΡΠ»ΠΈ Π²Ρ Ρ ΠΎΡΠΎΡΠΎ ΠΏΠΎΠ½ΠΈΠΌΠ°Π΅ΡΠ΅ ΡΠ΅ΠΊΡΡΡΠΈΡ, Π²Π°ΠΌ Π±ΡΠ΄Π΅Ρ ΠΏΡΠΎΡΠ΅ ΠΈΠ·ΡΡΠ°ΡΡ ΡΡΠ½ΠΊΡΠΈΠΎΠ½Π°Π»ΡΠ½ΡΠ΅ ΡΠ·ΡΠΊΠΈ.
Π‘ΠΎΠ²Π΅Ρ
ΠΠΎΠ³Π΄Π° Π²Ρ ΠΏΠΈΡΠ΅ΡΠ΅ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΡΡ ΡΡΠ½ΠΊΡΠΈΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ Π·Π°Π΄Π΅ΠΉΡΡΠ²ΠΎΠ²Π°Π½ ΠΌΠ°ΡΡΠΈΠ², Π±Π°Π·ΠΎΠ²ΡΠΌ ΡΠ»ΡΡΠ°Π΅ΠΌ ΡΠ°ΡΡΠΎ ΠΎΠΊΠ°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΡΡΡΠΎΠΉ ΠΌΠ°ΡΡΠΈΠ² ΠΈΠ»ΠΈ ΠΌΠ°ΡΡΠΈΠ² ΠΈΠ· ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°. ΠΡΠ»ΠΈ Π²Ρ Π½Π΅ Π·Π½Π°Π΅ΡΠ΅, Ρ ΡΠ΅Π³ΠΎ Π½Π°ΡΠ°ΡΡ, - Π½Π°ΡΠ½ΠΈΡΠ΅ Ρ ΡΡΠΎΠ³ΠΎ.
- ΠΠΌΠ΅Π΅ΡΡΡ ΠΌΠ°ΡΡΠΈΠ² ΡΠΈΡΠ΅Π». ΠΡΠΆΠ½ΠΎ ΠΏΡΠΎΡΡΠΌΠΌΠΈΡΠΎΠ²Π°ΡΡ Π²ΡΠ΅ ΡΠΈΡΠ»Π° ΠΈ Π²Π΅ΡΠ½ΡΡΡ ΡΡΠΌΠΌΡ. Π Π΅ΡΠΈΡΡ Π·Π°Π΄Π°ΡΡ, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ ΡΠ΅ΠΊΡΡΡΠΈΡ.
- ΠΠ°ΠΏΠΈΡΠ°ΡΡ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΡΡ ΡΡΠ½ΠΊΡΠΈΡ Π΄Π»Ρ ΠΏΠΎΠ΄ΡΡΠ΅ΡΠ° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π² ΡΠΏΠΈΡΠΊΠ΅.
- ΠΠ°ΠΉΠ΄ΠΈΡΠ΅ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅Π΅ ΡΠΈΡΠ»ΠΎ Π² ΡΠΏΠΈΡΠΊΠ΅.
ΠΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΎΡΠ½ΠΎΡΠΈΡΡΡ ΠΊ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°ΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. ΠΠ½Π° ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π½Π°ΠΌΠ½ΠΎΠ³ΠΎ Π±ΡΡΡΡΠ΅Π΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π²ΡΠ±ΠΎΡΠΎΠΌ ΠΈ ΡΠ°ΡΡΠΎ ΠΏΡΠΈΠΌΠ΅Π½ΡΠ΅ΡΡΡ Π² ΡΠ΅Π°Π»ΡΠ½ΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ°Ρ . Quick sort ΠΎΡΠ½ΠΎΠ²Π°Π½Π° Π½Π° ΡΡΡΠ°ΡΠ΅Π³ΠΈΠΈ "ΡΠ°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉ".
ΠΠΎΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΡΡ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΎΠΉ Π΄Π»Ρ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½ΠΈΡ ΠΌΠ°ΡΡΠΈΠ²Π°.
ΠΡΠ°ΠΊ, ΡΡΠΎ Π±ΡΠ΄Π΅Ρ ΡΠ²Π»ΡΡΡΡΡ Π±Π°Π·ΠΎΠ²ΡΠΌ ΡΠ»ΡΡΠ°Π΅ΠΌ?
ΠΡΡΡΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Ρ ΠΈ ΠΌΠ°ΡΡΠΈΠ²Ρ, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΠ΅ Π²ΡΠ΅Π³ΠΎ ΠΎΠ΄ΠΈΠ½ ΡΠ»Π΅ΠΌΠ΅Π½Ρ, ΡΡΠ°Π½ΡΡ Π±Π°Π·ΠΎΠ²ΡΠΌ ΡΠ»ΡΡΠ°Π΅ΠΌ. Π’Π°ΠΊΠΈΠ΅ ΠΌΠ°ΡΡΠΈΠ²Ρ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠΎΡΡΠΎ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°ΡΡ Π² ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΌ Π²ΠΈΠ΄Π΅ - ΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ Π½ΠΈΡΠ΅Π³ΠΎ Π½Π΅ Π½ΡΠΆΠ½ΠΎ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΠ°ΠΊ: ΡΠ½Π°ΡΠ°Π»Π° Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ, ΠΊΠΎΡΠΎΡΡΠΉ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΎΠΏΠΎΡΠ½ΡΠΌ.
ΠΠ°ΡΠ΅ΠΌ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, ΠΌΠ΅Π½ΡΡΠΈΠ΅ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ, ΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, Π±ΠΎΠ»ΡΡΠΈΠ΅ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ. ΠΡΠΎΡ ΠΏΡΠΎΡΠ΅ΡΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠ°Π·Π΄Π΅Π»Π΅Π½ΠΈΠ΅ΠΌ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ½ΠΈΠΊΠ°Π»Π΅Π½ ΡΠ΅ΠΌ, ΡΡΠΎ Π΅Π³ΠΎ ΡΠΊΠΎΡΠΎΡΡΡ Π·Π°Π²ΠΈΡΠΈΡ ΠΎΡ Π²ΡΠ±ΠΎΡΠ° ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°.
Π Ρ ΡΠ΄ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π·Π° Π²ΡΠ΅ΠΌΡ O(n^2). ΠΠΈΡΡΡΡ Π½Π΅ Π»ΡΡΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π²ΡΠ±ΠΎΡΠΎΠΌ! ΠΠΎ ΡΡΠΎ Ρ ΡΠ΄ΡΠΈΠΉ ΡΠ»ΡΡΠ°ΠΉ, Π° Π² ΡΡΠ΅Π΄Π½Π΅ΠΌ Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ O(n log n).
ΠΠΎΠΏΡΠΎΡΡ, ΠΊΠΎΡΠΎΡΡΠ΅ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡΡ:
- ΡΡΠΎ Π² Π΄Π°Π½Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΏΠΎΠ½ΠΈΠΌΠ°Π΅ΡΡΡ ΠΏΠΎΠ΄ "Ρ ΡΠ΄ΡΠΈΠΌ" ΠΈ "ΡΡΠ΅Π΄Π½ΠΈΠΌ" ΡΠ»ΡΡΠ°Π΅ΠΌ?
- Π΅ΡΠ»ΠΈ Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π² ΡΡΠ΅Π΄Π½Π΅ΠΌ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ O(n log n), Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ O(n log n) Π²ΡΠ΅Π³Π΄Π°, ΡΠΎ ΠΏΠΎΡΠ΅ΠΌΡ Π±Ρ Π½Π΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ? Π Π°Π·Π²Π΅ ΠΎΠ½Π° Π½Π΅ Π±ΡΡΡΡΠ΅Π΅?
ΠΠΎΠΏΡΠΎΠ±ΡΠ΅ΠΌ Π²ΡΡΡΠ½ΠΈΡΡ, ΠΊΠ°ΠΊΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π±ΡΡΡΡΠ΅Π΅: ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ ΠΈΠ»ΠΈ Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°.
ΠΠΎΠΏΡΡΡΠΈΠΌ, Ρ Π½Π°Ρ ΠΈΠΌΠ΅Π΅ΡΡΡ ΠΏΡΠΎΡΡΠ°Ρ ΡΡΠ½ΠΊΡΠΈΡ Π΄Π»Ρ Π²ΡΠ²ΠΎΠ΄Π° ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π² ΡΠΏΠΈΡΠΊΠ΅:
def print_items(list):
for item in list:
print item
ΠΡΠ° ΡΡΠ½ΠΊΡΠΈΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ ΠΏΠ΅ΡΠ΅Π±ΠΈΡΠ°Π΅Ρ Π²ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΡΠΏΠΈΡΠΊΠ° ΠΈ Π²ΡΠ²ΠΎΠ΄ΠΈΡ ΠΈΡ . Π’Π°ΠΊ ΠΊΠ°ΠΊ ΡΡΠ½ΠΊΡΠΈΡ ΠΏΠ΅ΡΠ΅Π±ΠΈΡΠ°Π΅Ρ Π²Π΅ΡΡ ΡΠΏΠΈΡΠΎΠΊ, ΠΎΠ½Π° Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ O(n).
ΠΠ·ΠΌΠ΅Π½ΠΈΠΌ Π½Π°ΡΡ ΡΡΠ½ΠΊΡΠΈΡ (print_items), Π΄ΠΎΠ±Π°Π²ΠΈΠ² ΡΠ΅ΠΊΡΠ½Π΄Π½ΡΡ ΠΏΠ°ΡΠ·Ρ ΠΏΠ΅ΡΠ΅Π΄ Π²ΡΠ²ΠΎΠ΄ΠΎΠΌ Π·Π½Π°ΡΠ΅Π½ΠΈΡ:
from time import sleep
def print_items2(list):
for item in list:
sleep(1)
print item
Π Π°Π±ΠΎΡΠ° ΡΡΠ½ΠΊΡΠΈΠΉ ΠΏΡΠΎΠ΄Π΅ΠΌΠΎΠ½ΡΡΡΠΈΡΠΎΠ²Π°Π½Π° Π½ΠΈΠΆΠ΅:
# ΠΠΌΠ΅Π΅ΡΡΡ ΡΠΏΠΈΡΠΎΠΊ ΠΈΠ· ΠΏΡΡΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ²: 2|4|6|8|10
print_items: 246810
print_items2: 2 <ΠΏΠ°ΡΠ·Π°> 4 <ΠΏΠ°ΡΠ·Π°> 6 <ΠΏΠ°ΡΠ·Π°> 8 <ΠΏΠ°ΡΠ·Π°> 10 <ΠΏΠ°ΡΠ·Π°>
ΠΠ±Π΅ ΡΡΠ½ΠΊΡΠΈΠΈ ΠΏΡΠΎΡ ΠΎΠ΄ΡΡ ΠΏΠΎ ΡΠΏΠΈΡΠΊΡ ΠΎΠ΄ΠΈΠ½ ΡΠ°Π·, ΠΈ ΠΎΠ±Π΅ Π²ΡΠΏΠΎΠ»Π½ΡΡΡΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ O(n).
ΠΠΎΠΏΡΠΎΡ. ΠΠ°ΠΊΠ°Ρ ΠΈΠ· Π½ΠΈΡ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π±ΡΡΡΡΠ΅Π΅?
ΠΡΠ²Π΅Ρ. print_items ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π½Π°ΠΌΠ½ΠΎΠ³ΠΎ Π±ΡΡΡΡΠ΅Π΅, ΠΏΠΎΡΠΎΠΌΡ ΡΡΠΎ ΠΎΠ½Π° ΠΠ Π΄Π΅Π»Π°Π΅Ρ ΠΏΠ°ΡΠ·Ρ ΠΏΠ΅ΡΠ΅Π΄ Π²ΡΠ²ΠΎΠ΄ΠΎΠΌ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°.
Π‘Π»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, Π΄Π°ΠΆΠ΅ ΠΏΡΠΈ ΡΠΎΠΌ, ΡΡΠΎ ΠΎΠ±Π΅ ΡΡΠ½ΠΊΡΠΈΠΈ ΠΈΠΌΠ΅ΡΡ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΡΡ ΡΠΊΠΎΡΠΎΡΡΡ "Π-Π±ΠΎΠ»ΡΡΠΎΠ΅", ΡΠ΅Π°Π»ΡΠ½ΠΎ print_items ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π±ΡΡΡΡΠ΅Π΅.
Π‘ΡΠΎΠΈΡ ΠΏΠΎΠ½ΠΈΠΌΠ°ΡΡ, ΠΊΠΎΠ³Π΄Π° ΠΌΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌ "Π-Π±ΠΎΠ»ΡΡΠΎΠ΅" (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, O(n)), Π² Π΄Π΅ΠΉΡΡΠ²ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ ΡΡΠΎ ΠΎΠ·Π½Π°ΡΠ°Π΅Ρ ΡΠ»Π΅Π΄ΡΡΡΠ΅Π΅: c * n
.
ΠΠ΄Π΅ΡΡ
c
- Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΡΠΈΠΊΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΠΊ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ Π΄Π»Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°. ΠΠ½ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠΎΠΉ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π²ΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΠΌΠΎΠΆΠ΅Ρ ΡΠΎΡΡΠ°Π²Π»ΡΡΡ 10 ΠΌΠΈΠ»Π»ΠΈΡΠ΅ΠΊΡΠ½Π΄ * n Π΄Π»Ρ print_items ΠΏΡΠΎΡΠΈΠ² 1 ΡΠ΅ΠΊΡΠ½Π΄Ρ * n Π΄Π»Ρ print_items2.
ΠΠ±ΡΡΠ½ΠΎ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠ° ΠΈΠ³Π½ΠΎΡΠΈΡΡΠ΅ΡΡΡ, ΠΏΠΎΡΠΎΠΌΡ ΡΡΠΎ Π΅ΡΠ»ΠΈ Π΄Π²Π° Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΈΠΌΠ΅ΡΡ ΡΠ°Π·Π½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ "Π-Π±ΠΎΠ»ΡΡΠΎΠ΅", ΠΎΠ½Π° ΡΠΎΠ»ΠΈ Π½Π΅ ΠΈΠ³ΡΠ°Π΅Ρ.
ΠΠ»Ρ ΠΏΡΠΈΠΌΠ΅ΡΠ° Π²ΠΎΠ·ΡΠΌΠ΅ΠΌ Π±ΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΈ ΠΏΡΠΎΡΡΠΎΠΉ ΠΏΠΎΠΈΡΠΊ. ΠΠΎΠΏΡΡΡΠΈΠΌ, ΡΡΠΎ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΡ ΠΏΡΠΈΡΡΡΡΡΠ²ΡΡΡ Π² ΠΎΠ±ΠΎΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°Ρ .
10 ΠΌΡ * n 1 Ρ * log n
__________ ___________
// ΠΡΠΎΡΡΠΎΠΉ ΠΏΠΎΠΈΡΠΊ // ΠΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ
ΠΠ°ΡΠ° ΡΠ΅Π°ΠΊΡΠΈΡ Π±ΡΠ΄Π΅Ρ ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΉ: "ΠΠ³ΠΎ! Π£ ΠΏΡΠΎΡΡΠΎΠ³ΠΎ ΠΏΠΎΠΈΡΠΊΠ° ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠ° ΡΠ°Π²Π½Π° 10 ΠΌΠΈΠ»Π»ΠΈΡΠ΅ΠΊΡΠ½Π΄Π°ΠΌ, Π° Ρ Π±ΠΈΠ½Π°ΡΠ½ΠΎΠ³ΠΎ ΠΏΠΎΠΈΡΠΊΠ° - 1 ΡΠ΅ΠΊΡΠ½Π΄Π°. ΠΡΠΎΡΡΠΎΠΉ ΠΏΠΎΠΈΡΠΊ Π½Π°ΠΌΠ½ΠΎΠ³ΠΎ Π±ΡΡΡΡΠ΅Π΅!"
ΠΠΎ, Π΄Π°Π²Π°ΠΉΡΠ΅ ΠΏΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ, ΡΡΠΎ ΠΏΠΎΠΈΡΠΊ Π²Π΅Π΄Π΅ΡΡΡ ΠΏΠΎ ΡΠΏΠΈΡΠΊΡ ΠΈΠ· 4 ΠΌΠΈΠ»Π»ΠΈΠ°ΡΠ΄ΠΎΠ² ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΡΠΎΠ³Π΄Π° Π²ΡΠ΅ΠΌΡ Π±ΡΠ΄Π΅Ρ ΡΠ°ΠΊΠΈΠΌ:
ΠΡΠΎΡΡΠΎΠΉ ΠΏΠΎΠΈΡΠΊ | 10 ΠΌΡ * 4 ΠΌΠΈΠ»Π»ΠΈΠ°ΡΠ΄Π° = 463 Π΄Π½Ρ (c * n, Π³Π΄Π΅ Ρ = 10 ΠΌΡ).
ΠΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ | 1 Ρ * 32 = 32 ΡΠ΅ΠΊΡΠ½Π΄Ρ (Ρ * log n, Π³Π΄Π΅ Ρ = 1 Ρ).
ΠΠ°ΠΊ ΠΌΠΎΠΆΠ΅ΠΌ Π·Π°ΠΌΠ΅ΡΠΈΡΡ, Π±ΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ Π²ΡΠ΅ ΡΠ°Π²Π½ΠΎ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π½Π°ΠΌΠ½ΠΎΠ³ΠΎ Π±ΡΡΡΡΠ΅Π΅. ΠΠΎΠ½ΡΡΠ°Π½ΡΠ° Π½ΠΈ Π½Π° ΡΡΠΎ Π½Π΅ ΠΏΠΎΠ²Π»ΠΈΡΠ»Π°.
ΠΠ΄Π½Π°ΠΊΠΎ Π² Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΠ»ΡΡΠ°ΡΡ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠ° ΠΌΠΎΠΆΠ΅Ρ ΠΈΠΌΠ΅ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅. ΠΠ΄ΠΈΠ½ ΠΈΠ· ΠΏΡΠΈΠΌΠ΅ΡΠΎΠ² ΡΠ°ΠΊΠΎΠ³ΠΎ ΡΠΎΠ΄Π° - Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ. Π£ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠ° ΠΌΠ΅Π½ΡΡΠ΅, ΡΠ΅ΠΌ Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ, ΠΏΠΎΡΡΠΎΠΌΡ, Π½Π΅ΡΠΌΠΎΡΡΡ Π½Π° ΡΠΎ ΡΡΠΎ ΠΎΠ±Π° Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Ρ Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΠ·ΡΡΡΡΡ Π²ΡΠ΅ΠΌΠ΅Π½Π΅ΠΌ O(n log n), Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π±ΡΡΡΡΠ΅Π΅.
- Π‘ΡΡΠ°ΡΠ΅Π³ΠΈΡ Β«ΡΠ°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉΒ» ΠΎΡΠ½ΠΎΠ²Π°Π½Π° Π½Π° ΡΠ°Π·Π±ΠΈΠ΅Π½ΠΈΠΈ Π·Π°Π΄Π°ΡΠΈ Π½Π° ΡΠΌΠ΅Π½ΡΡΠ°ΡΡΠΈΠ΅ΡΡ ΡΡΠ°Π³ΠΌΠ΅Π½ΡΡ. ΠΡΠ»ΠΈ Π²Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΠ΅ Π΄Π°Π½Π½ΡΡ ΡΡΡΠ°ΡΠ΅Π³ΠΈΡ ΡΠΎ ΡΠΏΠΈΡΠΊΠΎΠΌ, ΡΠΎ Π±Π°Π·ΠΎΠ²ΡΠΌ ΡΠ»ΡΡΠ°Π΅ΠΌ, ΡΠΊΠΎΡΠ΅Π΅ Π²ΡΠ΅Π³ΠΎ, Π±ΡΠ΄Π΅Ρ ΡΠ²Π»ΡΡΡΡΡ ΠΏΡΡΡΠΎΠΉ ΠΌΠ°ΡΡΠΈΠ² ΠΈΠ»ΠΈ ΠΌΠ°ΡΡΠΈΠ² ΠΈΠ· ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°.
- ΠΡΠ»ΠΈ Π²Ρ ΡΠ΅Π°Π»ΠΈΠ·ΡΠ΅ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΡΠΎ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ ΡΠ»Π΅Π΄ΡΠ΅Ρ Π²ΡΠ±ΡΠ°ΡΡ ΡΠ»ΡΡΠ°ΠΉΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ. Π‘ΡΠ΅Π΄Π½Π΅Π΅ Π²ΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠΎΡΡΠ°Π²Π»ΡΠ΅Ρ Π(n log n)!
- ΠΠΎΠ½ΡΡΠ°Π½ΡΡ Π² Β«Π-Π±ΠΎΠ»ΡΡΠΎΠΌΒ» ΠΈΠ½ΠΎΠ³Π΄Π° ΠΌΠΎΠ³ΡΡ ΠΈΠΌΠ΅ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅. ΠΠΌΠ΅Π½Π½ΠΎ ΠΏΠΎ ΡΡΠΎΠΉ ΠΏΡΠΈΡΠΈΠ½Π΅ Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π±ΡΡΡΡΠ΅Π΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ.
ΠΡΠ΅Π΄ΡΡΠ°Π²ΡΡΠ΅, ΡΡΠΎ Π²Ρ ΡΠ²Π»ΡΠ΅ΡΠ΅ΡΡ ΠΏΡΠΎΠ΄Π°Π²ΡΠΎΠΌ Π² ΠΌΠ°Π»Π΅Π½ΡΠΊΠΎΠΌ ΠΌΠ°Π³Π°Π·ΠΈΠ½ΡΠΈΠΊΠ΅. ΠΠΎΠ³Π΄Π° ΠΊΠ»ΠΈΠ΅Π½Ρ ΠΏΠΎΠΊΡΠΏΠ°Π΅Ρ ΡΠΎΠ²Π°ΡΡ, Π²Ρ ΠΏΡΠΎΠ²Π΅ΡΡΠ΅ΡΠ΅ ΠΈΡ ΡΠ΅Π½Ρ ΠΏΠΎ ΠΊΠ½ΠΈΠ³Π΅. ΠΡΠ»ΠΈ Π·Π°ΠΏΠΈΡΠΈ Π² ΠΊΠ½ΠΈΠ³Π΅ Π½Π΅ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Ρ ΠΏΠΎ Π°Π»ΡΠ°Π²ΠΈΡΡ, ΡΠΎ ΠΏΠΎΠΈΡΠΊ ΡΠ»ΠΎΠ²Π° Β«Π°ΠΏΠ΅Π»ΡΡΠΈΠ½ΡΒ» Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅ Π·Π°ΠΉΠΌΠ΅Ρ ΡΠ»ΠΈΡΠΊΠΎΠΌ ΠΌΠ½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ. ΠΠΎΠ½Π΅ΡΠ½ΠΎ, Π΅ΡΠ»ΠΈ ΠΆΠ΅ ΠΊΠ½ΠΈΠ³Π° ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π° ΠΏΠΎ Π°Π»ΡΠ°Π²ΠΈΡΡ, Π²Ρ ΠΌΠΎΠΆΠ΅ΡΠ΅ Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ Π±ΠΈΠ½Π°ΡΠ½ΡΠΌ ΠΏΠΎΠΈΡΠΊΠΎΠΌ, Π²ΡΠ΅ΠΌΡ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΡΠΎΡΡΠ°Π²Π»ΡΠ΅Ρ Π²ΡΠ΅Π³ΠΎ O(log n).
ΠΠΎ ΠΏΠΎΠΈΡΠΊ Π΄Π°Π½Π½ΡΡ Π² ΠΊΠ½ΠΈΠ³Π΅ - Π³ΠΎΠ»ΠΎΠ²Π½Π°Ρ Π±ΠΎΠ»Ρ, Π΄Π°ΠΆΠ΅ Π΅ΡΠ»ΠΈ Π΅Π΅ ΡΠΎΠ΄Π΅ΡΠΆΠΈΠΌΠΎΠ΅ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½ΠΎ. ΠΠΎΠΊΠ° Π²Ρ Π»ΠΈΡΡΠ°Π΅ΡΠ΅ ΡΡΡΠ°Π½ΠΈΡΡ, ΠΊΠ»ΠΈΠ΅Π½Ρ ΠΏΠΎΡΠΈΡ ΠΎΠ½ΡΠΊΡ Π½Π°ΡΠΈΠ½Π°Π΅Ρ Π²ΡΡ ΠΎΠ΄ΠΈΡΡ ΠΈΠ· ΡΠ΅Π±Ρ. ΠΠΎΡΠ°Π·Π΄ΠΎ ΡΠ΄ΠΎΠ±Π½Π΅Π΅ Π±ΡΠ»ΠΎ Π±Ρ Π·Π°Π²Π΅ΡΡΠΈ ΠΏΠΎΠΌΠΎΡΠ½ΠΈΡΡ, ΠΊΠΎΡΠΎΡΠ°Ρ ΠΏΠΎΠΌΠ½ΠΈΡ Π²ΡΠ΅ Π½Π°Π·Π²Π°Π½ΠΈΡ ΡΠΎΠ²Π°ΡΠΎΠ² ΠΈ ΡΠ΅Π½Ρ. Π’ΠΎΠ³Π΄Π° Π½ΠΈΡΠ΅Π³ΠΎ ΠΈΡΠΊΠ°ΡΡ Π²ΠΎΠΎΠ±ΡΠ΅ Π½Π΅ ΠΏΡΠΈΠ΄Π΅ΡΡΡ: Π²Ρ ΡΠΏΡΠ°ΡΠΈΠ²Π°Π΅ΡΠ΅ ΠΏΠΎΠΌΠΎΡΠ½ΠΈΡΡ, Π° ΠΎΠ½Π° ΠΌΠ³Π½ΠΎΠ²Π΅Π½Π½ΠΎ ΠΎΡΠ²Π΅ΡΠ°Π΅Ρ.
Π Π΄Π°Π½Π½ΠΎΠΉ ΡΠΈΡΡΠ°ΡΠΈΠΈ ΠΎΡΠ»ΠΈΡΠ½ΠΎ ΠΏΠΎΠ΄ΠΎΠΉΠ΄Π΅Ρ ΡΡΡΡΠΊΡΡΡΠ° Π΄Π°Π½Π½ΡΡ , ΠΊΠΎΡΠΎΡΠ°Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΠ°.
Π₯Π΅Ρ-ΡΡΠ½ΠΊΡΠΈΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅Ρ ΡΠΎΠ±ΠΎΠΉ ΡΡΠ½ΠΊΡΠΈΡ, ΠΊΠΎΡΠΎΡΠ°Ρ ΠΏΠΎΠ»ΡΡΠ°Π΅Ρ ΡΡΡΠΎΠΊΡ ΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ ΡΠΈΡΠ»ΠΎ. ΠΠΎΠ΄ "ΡΡΡΠΎΠΊΠΎΠΉ" Π² Π΄Π°Π½Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΏΠΎΠ½ΠΈΠΌΠ°ΡΡ Π»ΡΠ±ΡΠ΅ Π΄Π°Π½Π½ΡΠ΅.
Π Π½Π°ΡΡΠ½ΠΎΠΉ ΡΠ΅ΡΠΌΠΈΠ½ΠΎΠ»ΠΎΠ³ΠΈΠΈ Π³ΠΎΠ²ΠΎΡΡΡ, ΡΡΠΎ Ρ Π΅Ρ-ΡΡΠ½ΠΊΡΠΈΡ Β«ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ°Π΅Ρ ΡΡΡΠΎΠΊΠΈ Π½Π° ΡΠΈΡΠ»Π°". ΠΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ΄ΡΠΌΠ°ΡΡ, ΡΡΠΎ Π½Π°ΠΉΡΠΈ Π·Π°ΠΊΠΎΠ½ΠΎΠΌΠ΅ΡΠ½ΠΎΡΡΠΈ ΠΏΠΎΠ»ΡΡΠ΅Π½ΠΈΡ ΡΠΈΡΠ΅Π» Π΄Π»Ρ ΠΏΠΎΠ΄Π°Π²Π°Π΅ΠΌΡΡ Π½Π° Π²Ρ ΠΎΠ΄ ΡΡΡΠΎΠΊ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ. ΠΠ΄Π½Π°ΠΊΠΎ Ρ Π΅Ρ-ΡΡΠ½ΠΊΡΠΈΡ Π΄ΠΎΠ»ΠΆΠ½Π° ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΎΠ²Π°ΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΌ ΡΡΠ΅Π±ΠΎΠ²Π°Π½ΠΈΡΠΌ:
- ΠΠ½Π° Π΄ΠΎΠ»ΠΆΠ½Π° Π±ΡΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΠΉ. ΠΠΎΠΏΡΡΡΠΈΠΌ, Π²Ρ ΠΏΠ΅ΡΠ΅Π΄Π°Π»ΠΈ Π΅ΠΉ ΡΡΡΠΎΠΊΡ "Π°ΠΏΠ΅Π»ΡΡΠΈΠ½Ρ" ΠΈ ΠΏΠΎΠ»ΡΡΠΈΠ»ΠΈ 4. ΠΡΠΎ Π·Π½Π°ΡΠΈΡ, ΡΡΠΎ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ°Π· Π² Π±ΡΠ΄ΡΡΠ΅ΠΌ, ΠΏΠ΅ΡΠ΅Π΄Π°Π²Π°Ρ Π΅ΠΉ ΡΡΡΠΎΠΊΡ Β«Π°ΠΏΠ΅Π»ΡΡΠΈΠ½ΡΒ», Π²Ρ Π±ΡΠ΄Π΅ΡΠ΅ ΠΏΠΎΠ»ΡΡΠ°ΡΡ 4. ΠΠ΅Π· ΡΡΠΎΠ³ΠΎ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΠ° Π±Π΅ΡΠΏΠΎΠ»Π΅Π·Π½Π°.
- Π Π°Π·Π½ΡΠΌ ΡΠ»ΠΎΠ²Π°ΠΌ Π΄ΠΎΠ»ΠΆΠ½Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΎΠ²Π°ΡΡ ΡΠ°Π·Π½ΡΠ΅ ΡΠΈΡΠ»Π°. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Ρ Π΅Ρ-ΡΡΠ½ΠΊΡΠΈΡ, ΠΊΠΎΡΠΎΡΠ°Ρ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ 1 Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΠΎΠ³ΠΎ ΡΠ»ΠΎΠ²Π°, Π½ΠΈΠΊΡΠ΄Π° Π½Π΅ Π³ΠΎΠ΄ΠΈΡΡΡ. Π ΠΈΠ΄Π΅Π°Π»Π΅ ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ Π²Ρ ΠΎΠ΄Π½ΠΎΠ΅ ΡΠ»ΠΎΠ²ΠΎ Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ°ΡΡΡΡ Π½Π° ΡΠ²ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ.
ΠΡΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ ΠΈΡΠΊΠ»ΡΡΠΈΡΠ΅Π»ΡΠ½ΠΎ Π±ΡΡΡΡΠΎ ΡΠ°Π±ΠΎΡΠ°ΡΡ! ΠΠ±ΡΠ°ΡΠ΅Π½ΠΈΠ΅ ΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΌΠ°ΡΡΠΈΠ²Π° ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡ ΠΌΠ³Π½ΠΎΠ²Π΅Π½Π½ΠΎ, Π° Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡ ΠΌΠ°ΡΡΠΈΠ²Ρ Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ Π΄Π°Π½Π½ΡΡ , ΠΏΠΎΡΡΠΎΠΌΡ ΠΏΡΠΈ ΠΎΠ±ΡΠ°ΡΠ΅Π½ΠΈΠΈ ΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌ ΠΎΠ½ΠΈ Π½Π΅ ΡΡΡΡΠΏΠ°ΡΡ ΠΌΠ°ΡΡΠΈΠ²Π°ΠΌ.
Π Π»ΡΠ±ΠΎΠΌ ΠΏΡΠΈΠ»ΠΈΡΠ½ΠΎΠΌ ΡΠ·ΡΠΊΠ΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡ. Π₯Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ ΡΠ°ΠΊΠΆΠ΅ ΠΈΠ·Π²Π΅ΡΡΠ½Ρ ΠΏΠΎΠ΄ Π΄ΡΡΠ³ΠΈΠΌΠΈ Π½Π°Π·Π²Π°Π½ΠΈΡΠΌΠΈ: Β«Π°ΡΡΠΎΡΠΈΠ°ΡΠΈΠ²Π½ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²ΡΒ» , Β«ΡΠ»ΠΎΠ²Π°ΡΠΈΒ», Β«ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΡΒ», Β«Ρ Π΅Ρ-ΠΊΠ°ΡΡΡΒ» ΠΈΠ»ΠΈ ΠΏΡΠΎΡΡΠΎ Β«Ρ Π΅ΡΠΈΒ».
ΠΠ°Π΄Π°ΡΠ°. ΠΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ, Π²Ρ ΡΡΠΊΠΎΠ²ΠΎΠ΄ΠΈΡΠ΅ ΠΈΠ·Π±ΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΠΌ ΡΡΠ°ΡΡΠΊΠΎΠΌ. ΠΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎ, ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΈΠ·Π±ΠΈΡΠ°ΡΠ΅Π»Ρ ΠΌΠΎΠΆΠ΅Ρ ΠΏΡΠΎΠ³ΠΎΠ»ΠΎΡΠΎΠ²Π°ΡΡ Π²ΡΠ΅Π³ΠΎ ΠΎΠ΄ΠΈΠ½ ΡΠ°Π·. ΠΠ°ΠΊ ΠΏΡΠΎΠ²Π΅ΡΠΈΡΡ, ΡΡΠΎ ΠΎΠ½ Π³ΠΎΠ»ΠΎΡΠΎΠ²Π°Π» ΡΠ°Π½Π΅Π΅? ΠΠΎΠ³Π΄Π° ΡΠ΅Π»ΠΎΠ²Π΅ΠΊ ΠΏΡΠΈΡ ΠΎΠ΄ΠΈΡ Π³ΠΎΠ»ΠΎΡΠΎΠ²Π°ΡΡ, Π²Ρ ΡΠ·Π½Π°Π΅ΡΠ΅ Π΅Π³ΠΎ ΠΏΠΎΠ»Π½ΠΎΠ΅ ΠΈΠΌΡ, Π° Π·Π°ΡΠ΅ΠΌ ΠΏΡΠΎΠ²Π΅ΡΡΠ΅ΡΠ΅ ΠΏΠΎ ΡΠΏΠΈΡΠΊΡ ΡΠΆΠ΅ ΠΏΡΠΎΠ³ΠΎΠ»ΠΎΡΠΎΠ²Π°Π²ΡΠΈΡ ΠΈΠ·Π±ΠΈΡΠ°ΡΠ΅Π»Π΅ΠΉ. ΠΡΠ»ΠΈ ΠΈΠΌΡ Π²Ρ ΠΎΠ΄ΠΈΡ Π² ΡΠΏΠΈΡΠΎΠΊ, Π·Π½Π°ΡΠΈΡ, ΡΡΠΎΡ ΡΠ΅Π»ΠΎΠ²Π΅ΠΊ ΡΠΆΠ΅ ΠΏΡΠΎΠ³ΠΎΠ»ΠΎΡΠΎΠ²Π°Π» - Π³ΠΎΠ½ΠΈΡΠ΅ Π½Π°Π³Π»Π΅ΡΠ°! Π ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π²Ρ Π΄ΠΎΠ±Π°Π²Π»ΡΠ΅ΡΠ΅ ΠΈΠΌΡ Π² ΡΠΏΠΈΡΠΎΠΊ ΠΈ ΡΠ°Π·ΡΠ΅ΡΠ°Π΅ΡΠ΅ Π΅ΠΌΡ ΠΏΡΠΎΠ³ΠΎΠ»ΠΎΡΠΎΠ²Π°ΡΡ.
ΠΠΎ... ΠΠ°ΠΊ Π±ΡΡΡ, ΠΊΠΎΠ³Π΄Π° ΡΠΏΠΈΡΠΎΠΊ ΠΏΡΠΎΠ³ΠΎΠ»ΠΎΡΠΎΠ²Π°Π²ΡΠΈΡ
ΡΡΠ°Π½Π΅Ρ ΠΎΠ³ΡΠΎΠΌΠ½ΡΠΌ?
ΠΠ΅ΡΠΆΠ΅Π»ΠΈ Π½ΡΠΆΠ½ΠΎ Π±ΡΠ΄Π΅Ρ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ°Π·, ΠΊΠΎΠ³Π΄Π° ΠΊΡΠΎ-ΡΠΎ ΠΏΡΠΈΡ
ΠΎΠ΄ΠΈΡ Π³ΠΎΠ»ΠΎΡΠΎΠ²Π°ΡΡ,
ΠΏΡΠΎΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡ Π³ΠΈΠ³Π°Π½ΡΡΠΊΠΈΠΉ ΡΠΏΠΈΡΠΎΠΊ ΠΈ ΠΏΡΠΎΠ²Π΅ΡΡΡΡ, Π³ΠΎΠ»ΠΎΡΠΎΠ²Π°Π» ΠΎΠ½ ΠΈΠ»ΠΈ Π½Π΅Ρ?
Π‘ΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅: Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ Ρ Π΅ΡΠ΅ΠΌ!
Π Π΅ΡΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ Π½Π° Java:
Π Π΅ΡΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ Π½Π° Kotlin:
ΠΠΎΠΆΠ΅Ρ ΡΠ»ΡΡΠΈΡΡΡΡ ΡΠ°ΠΊ, ΡΡΠΎ Ρ Π΄Π²ΡΡ ΡΠ°Π·Π½ΡΡ ΠΊΠ»ΡΡΠ΅ΠΉ ΠΎΠΊΠ°ΠΆΠ΅ΡΡΡ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΡΠΉ Ρ ΡΡ. ΠΠ»ΠΈ Ρ ΡΡ Π±ΡΠ΄Π΅Ρ ΡΠ°Π·Π½ΡΠΌ, Π½ΠΎ ΠΏΠΎ ΡΠΎΡΠΌΡΠ»Π΅ ΠΏΠΎΠ·ΠΈΡΠΈΡ Π΄Π»Ρ ΠΎΠ±ΠΎΠΈΡ Ρ ΡΡΠ΅ΠΉ Π±ΡΠ΄Π΅Ρ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎΠΉ. Π’ΠΎΠ³Π΄Π° Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΎΠ±ΠΎΠΈΡ ΠΊΠ»ΡΡΠ΅ΠΉ ΠΎΠΊΠ°ΠΆΡΡΡΡ Π·Π°ΠΏΠΈΡΠ°Π½Ρ Π² ΠΎΠ΄Π½Ρ Β«ΠΊΠΎΡΠ·ΠΈΠ½ΠΊΡΒ». ΠΡΠΎ ΠΈ Π΅ΡΡΡ ΠΊΠΎΠ»Π»ΠΈΠ·ΠΈΡ. ΠΠΌΠ΅Π½Π½ΠΎ ΠΈΠ·-Π·Π° ΠΊΠΎΠ»Π»ΠΈΠ·ΠΈΠΉ Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ ΡΠ²ΡΠ·Π°Π½Π½ΡΠΉ ΡΠΏΠΈΡΠΎΠΊ: Π΅ΡΠ»ΠΈ Π±Ρ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ ΠΏΡΠΎΡΡΠΎ Ρ ΡΠ°Π½ΠΈΠ»ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡ, Π»ΡΠ±Π°Ρ ΠΊΠΎΠ»Π»ΠΈΠ·ΠΈΡ ΠΏΠ΅ΡΠ΅Π·Π°ΠΏΠΈΡΠ°Π»Π° Π±Ρ ΡΠ΅ΠΊΡΡΠ΅Π΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅, Π° ΡΡΠΎ ΠΎΠΏΠ°ΡΠ½ΠΎ. Π ΠΏΡΠΈ ΡΠ΅ΠΊΡΡΠ΅ΠΉ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ, Π΄Π°ΠΆΠ΅ Π΅ΡΠ»ΠΈ ΡΠ»ΡΡΠΈΡΡΡ ΠΊΠΎΠ»Π»ΠΈΠ·ΠΈΡ, Π½ΠΎΠ²ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΏΡΠΎΡΡΠΎ Π·Π°ΠΏΠΈΡΠ΅ΡΡΡ Π² Π½Π°ΡΠ°Π»ΠΎ ΡΠΎΠΉ ΠΆΠ΅ Β«ΠΊΠΎΡΠ·ΠΈΠ½ΠΊΠΈΒ», Π½Π΅ ΠΈΠ·ΠΌΠ΅Π½ΠΈΠ² ΡΡΠ°ΡΠΎΠ΅.
ΠΡΠ°ΠΊ, ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°ΡΡ Π΄Π²Π° Π²ΡΠ²ΠΎΠ΄Π°:
- Π²ΡΠ±ΠΎΡ Ρ Π΅Ρ-ΡΡΠ½ΠΊΡΠΈΠΈ Π΄Π΅ΠΉΡΡΠ²ΠΈΡΠ΅Π»ΡΠ½ΠΎ Π²Π°ΠΆΠ΅Π½. Π₯Π΅Ρ-ΡΡΠ½ΠΊΡΠΈΡ, ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ°ΡΡΠ°Ρ Π²ΡΠ΅ ΠΊΠ»ΡΡΠΈ Π½Π° ΠΎΠ΄ΠΈΠ½ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΠ²Π°, Π½ΠΈΠΊΡΠ΄Π° Π½Π΅ Π³ΠΎΠ΄ΠΈΡΡΡ. Π ΠΈΠ΄Π΅Π°Π»Π΅ Ρ Π΅Ρ-ΡΡΠ½ΠΊΡΠΈΡ Π΄ΠΎΠ»ΠΆΠ½Π° ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ ΠΊΠ»ΡΡΠΈ ΡΠ°Π²Π½ΠΎΠΌΠ΅ΡΠ½ΠΎ ΠΏΠΎ Π²ΡΠ΅ΠΌΡ Ρ Π΅ΡΡ;
- Π΅ΡΠ»ΠΈ ΡΠ²ΡΠ·Π°Π½Π½ΡΠ΅ ΡΠΏΠΈΡΠΊΠΈ ΡΡΠ°Π½ΠΎΠ²ΡΡΡΡ ΡΠ»ΠΈΡΠΊΠΎΠΌ Π΄Π»ΠΈΠ½Π½ΡΠΌΠΈ, ΡΠ°Π±ΠΎΡΠ° Ρ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΠ΅ΠΉ ΡΠΈΠ»ΡΠ½ΠΎ Π·Π°ΠΌΠ΅Π΄Π»ΡΠ΅ΡΡΡ. ΠΠΎ ΠΎΠ½ΠΈ Π½Π΅ ΡΡΠ°Π½ΡΡ ΡΠ»ΠΈΡΠΊΠΎΠΌ Π΄Π»ΠΈΠ½Π½ΡΠΌΠΈ ΠΏΡΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ Ρ ΠΎΡΠΎΡΠ΅ΠΉ Ρ Π΅Ρ-ΡΡΠ½ΠΊΡΠΈΠΈ!
ΠΠΎΡΡΡΠΈΡΠΈΠ΅Π½Ρ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ Π²ΡΡΠΈΡΠ»ΡΠ΅ΡΡΡ ΠΏΠΎ ΠΏΡΠΎΡΡΠΎΠΉ ΡΠΎΡΠΌΡΠ»Π΅: ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π² Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΠ΅ / ΠΎΠ±ΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ². ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π² ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΉ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΠ΅ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½Ρ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΠ°Π²Π΅Π½ 3/4.
Π‘ ΠΌΠ΅Π½ΡΡΠΈΠΌ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΠΎΠΌ Π·Π°Π³ΡΡΠ·ΠΊΠΈ ΡΠΈΡΠ»ΠΎ ΠΊΠΎΠ»Π»ΠΈΠ·ΠΈΠΉ ΡΠΌΠ΅Π½ΡΡΠ°Π΅ΡΡΡ, ΠΈ Π²Π°ΡΠ° ΡΠ°Π±Π»ΠΈΡΠ° Π½Π°ΡΠΈΠ½Π°Π΅Ρ ΡΠ°Π±ΠΎΡΠ°ΡΡ Π±ΠΎΠ»Π΅Π΅ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ. Π₯ΠΎΡΠΎΡΠ΅Π΅ ΠΏΡΠΈΠ±Π»ΠΈΠΆΠ΅Π½Π½ΠΎΠ΅ ΠΏΡΠ°Π²ΠΈΠ»ΠΎ: ΠΈΠ·ΠΌΠ΅Π½ΡΠΉΡΠ΅ ΡΠ°Π·ΠΌΠ΅Ρ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ, ΠΊΠΎΠ³Π΄Π° ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½Ρ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΠΏΡΠ΅Π²ΡΡΠ°Π΅Ρ 0,7. ΠΠΎ Π²Π΅Π΄Ρ Π½Π° ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΡΠ°Π·ΠΌΠ΅ΡΠΎΠ² ΡΡ ΠΎΠ΄ΠΈΡ ΠΌΠ½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ, ΡΠΊΠ°ΠΆΠ΅ΡΠ΅ Π²Ρ, ΠΈ Π±ΡΠ΄Π΅ΡΠ΅ Π°Π±ΡΠΎΠ»ΡΡΠ½ΠΎ ΠΏΡΠ°Π²Ρ! ΠΠ°, ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΡΠ°Π·ΠΌΠ΅ΡΠΎΠ² ΡΡΠ΅Π±ΡΠ΅Ρ Π·Π½Π°ΡΠΈΡΠ΅Π»ΡΠ½ΡΡ Π·Π°ΡΡΠ°Ρ ΡΠ΅ΡΡΡΡΠΎΠ², ΠΏΠΎΡΡΠΎΠΌΡ ΠΎΠ½ΠΎ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡΡ ΡΠ»ΠΈΡΠΊΠΎΠΌ ΡΠ°ΡΡΠΎ. Π ΡΡΠ΅Π΄Π½Π΅ΠΌ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ ΡΠ°Π±ΠΎΡΠ°ΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ 0(1) Π΄Π°ΠΆΠ΅ Ρ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ΠΌ ΡΠ°Π·ΠΌΠ΅ΡΠΎΠ².
Π₯Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ ΡΡΠ΅Π·Π²ΡΡΠ°ΠΉΠ½ΠΎ ΠΏΠΎΠ»Π΅Π·Π½Ρ, ΠΏΠΎΡΠΎΠΌΡ ΡΡΠΎ ΠΎΠ½ΠΈ ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠΈΠ²Π°ΡΡ Π²ΡΡΠΎΠΊΡΡ ΡΠΊΠΎΡΠΎΡΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ ΠΈ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡ ΠΏΠΎ-ΡΠ°Π·Π½ΠΎΠΌΡ ΠΌΠΎΠ΄Π΅Π»ΠΈΡΠΎΠ²Π°ΡΡ Π΄Π°Π½Π½ΡΠ΅.
- Π₯Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΠ° ΡΠΎΠ·Π΄Π°Π΅ΡΡΡ ΠΎΠ±ΡΠ΅Π΄ΠΈΠ½Π΅Π½ΠΈΠ΅ΠΌ Ρ Π΅Ρ-ΡΡΠ½ΠΊΡΠΈΠΈ Ρ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠΌ.
- ΠΠΎΠ»Π»ΠΈΠ·ΠΈΠΈ Π½Π΅ΠΆΠ΅Π»Π°ΡΠ΅Π»ΡΠ½Ρ. Π₯Π΅Ρ-ΡΡΠ½ΠΊΡΠΈΡ Π΄ΠΎΠ»ΠΆΠ½Π° ΡΠ²Π΅ΡΡΠΈ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΊΠΎΠ»Π»ΠΈΠ·ΠΈΠΉ ΠΊ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΡ.
- Π₯Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠΈΠ²Π°ΡΡ ΠΎΡΠ΅Π½Ρ Π±ΡΡΡΡΠΎΠ΅ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΏΠΎΠΈΡΠΊΠ°, Π²ΡΡΠ°Π²ΠΊΠΈ ΠΈ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ.
- Π₯Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ Ρ ΠΎΡΠΎΡΠΎ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡ Π΄Π»Ρ ΠΌΠΎΠ΄Π΅Π»ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠΉ ΠΌΠ΅ΠΆΠ΄Ρ ΠΎΠ±ΡΠ΅ΠΊΡΠ°ΠΌΠΈ.
- ΠΠ°ΠΊ ΡΠΎΠ»ΡΠΊΠΎ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½Ρ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΠΏΡΠ΅Π²ΡΡΠ°Π΅Ρ 0,7, ΠΏΠΎΡΠ° ΠΈΠ·ΠΌΠ΅Π½ΡΡΡ ΡΠ°Π·ΠΌΠ΅Ρ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ.
- Π₯Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ Π΄Π»Ρ ΠΊΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π΄Π°Π½Π½ΡΡ (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π½Π° Π²Π΅Π±-ΡΠ΅ΡΠ²Π΅ΡΠ°Ρ ).
- Π₯Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ Ρ ΠΎΡΠΎΡΠΎ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡ Π΄Π»Ρ ΠΎΠ±Π½Π°ΡΡΠΆΠ΅Π½ΠΈΡ Π΄ΡΠ±Π»ΠΈΠΊΠ°ΡΠΎΠ².
ΠΠΎΠΈΡΠΊ Π² ΡΠΈΡΠΈΠ½Ρ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ Π½Π°ΠΉΡΠΈ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π΅ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ Π΄Π²ΡΠΌΡ ΠΎΠ±ΡΠ΅ΠΊΡΠ°ΠΌΠΈ. ΠΠ΄Π½Π°ΠΊΠΎ ΡΠ°ΠΌ ΡΠ΅ΡΠΌΠΈΠ½ Β«ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π΅ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅Β» ΠΌΠΎΠΆΠ΅Ρ ΠΈΠΌΠ΅ΡΡ ΠΌΠ½ΠΎΠ³ΠΎ ΡΠ°Π·Π½ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ! ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΠΏΠΎΠΈΡΠΊΠ° Π² ΡΠΈΡΠΈΠ½Ρ ΠΌΠΎΠΆΠ½ΠΎ:
- Π½Π°ΠΏΠΈΡΠ°ΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π΄Π»Ρ ΠΈΠ³ΡΡ Π² ΡΠ°ΡΠΊΠΈ, ΠΊΠΎΡΠΎΡΠ°Ρ Π²ΡΡΠΈΡΠ»ΡΠ΅Ρ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΏΡΡΡ ΠΊ ΠΏΠΎΠ±Π΅Π΄Π΅;
- ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ ΠΏΡΠΎΠ²Π΅ΡΠΊΡ ΠΏΡΠ°Π²ΠΎΠΏΠΈΡΠ°Π½ΠΈΡ (ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΉ, ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΡΡΡΠΈΡ ΠΎΡΠΈΠ±ΠΎΡΠ½ΠΎ Π½Π°ΠΏΠΈΡΠ°Π½Π½ΠΎΠ΅ ΡΠ»ΠΎΠ²ΠΎ Π² ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΠ΅, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ ΠΠΠΠΠ ΠΠ€Π -> ΠΠΠΠΠ ΠΠ’Π - ΠΎΠ΄Π½ΠΎ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅);
- Π½Π°ΠΉΡΠΈ Π±Π»ΠΈΠΆΠ°ΠΉΡΠ΅Π³ΠΎ ΠΊ Π²Π°ΠΌ Π²ΡΠ°ΡΠ°.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠΈΡΠΊΠ° Π² ΡΠΈΡΠΈΠ½Ρ (Π°Π½Π³Π». breadth-first search, BFS) ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ Π½Π°ΠΉΡΠΈ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠ΅ ΠΏΡΡΠΈ ΠΈΠ· ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π½Π΅Π²Π·Π²Π΅ΡΠ΅Π½Π½ΠΎΠ³ΠΎ (ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ ΠΈΠ»ΠΈ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ) Π³ΡΠ°ΡΠ° Π΄ΠΎ Π²ΡΠ΅Ρ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ Π²Π΅ΡΡΠΈΠ½. ΠΠΎΠ΄ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΌ ΠΏΡΡΠ΅ΠΌ ΠΏΠΎΠ΄ΡΠ°Π·ΡΠΌΠ΅Π²Π°Π΅ΡΡΡ ΠΏΡΡΡ, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΠΉ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π΅ ΡΠΈΡΠ»ΠΎ ΡΠ΅Π±Π΅Ρ.
ΠΠ°Π΄Π°Π½ΠΈΠ΅. Π Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ Π³ΡΠ°Ρ (Π½Π° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΠΎΠΌ ΡΡΠΎΠ²Π½Π΅), ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ Π½Π° ΡΠΈΡΡΠ½ΠΊΠ΅ Π½ΠΈΠΆΠ΅.
ΠΡΠ°Ρ ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΡ ΡΠ·Π»ΠΎΠ². Π ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ·Π΅Π» ΡΠΎΠ΅Π΄ΠΈΠ½ΡΠ΅ΡΡΡ Ρ ΡΠΎΡΠ΅Π΄Π½ΠΈΠΌΠΈ ΡΠ·Π»Π°ΠΌΠΈ. ΠΠΎΠ·Π½ΠΈΠΊΠ°Π΅Ρ Π²ΠΎΠΏΡΠΎΡ: ΠΊΠ°ΠΊΡΡ ΡΡΡΡΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ, ΡΡΠΎΠ±Ρ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ Π΄Π°Π½Π½ΡΠ΅ ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΡ?
ΠΡΠ΄Π΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΡ!
ΠΠΎΠ΄ Π½Π° ΡΠ·ΡΠΊΠ΅ Java Π²ΡΠ³Π»ΡΠ΄ΠΈΡ ΡΠ°ΠΊ:
private static Map<String, List<String>> graph = new HashMap<>();
graph.put("you", Arrays.asList("alice", "bob", "claire"));
graph.put("bob", Arrays.asList("anuj", "peggy"));
graph.put("alice", Arrays.asList("peggy"));
graph.put("claire", Arrays.asList("thom", "jonny"));
// Π£ ΠΠ½ΡΠ΄ΠΆΠ°, ΠΠ΅Π³Π³ΠΈ, Π’ΠΎΠΌΠ° ΠΈ ΠΠΆΠΎΠ½Π½ΠΈ ΡΠΎΡΠ΅Π΄Π΅ΠΉ Π½Π΅Ρ.
graph.put("anuj", Collections.emptyList());
graph.put("peggy", Collections.emptyList());
graph.put("thom", Collections.emptyList());
graph.put("jonny", Collections.emptyList());
Π Ρ Π΅Ρ-ΡΠ°Π±Π»ΠΈΡΠ°Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π½Π΅ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Ρ, ΠΏΠΎΡΡΠΎΠΌΡ Π΄ΠΎΠ±Π°Π²Π»ΡΡΡ ΠΏΠ°ΡΡ "ΠΊΠ»ΡΡ-Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅" ΠΌΠΎΠΆΠ½ΠΎ Π² Π»ΡΠ±ΠΎΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅.
ΠΠ½ΡΠ΄ΠΆ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠΎΡΠ΅Π΄ΠΎΠΌ ΠΠΎΠ±Π°, Π½ΠΎ ΠΠΎΠ± Π½Π΅ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠΎΡΠ΅Π΄ΠΎΠΌ ΠΠ½ΡΠ΄ΠΆΠ°. Π’Π°ΠΊΠΎΠΉ Π³ΡΠ°Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΡΠΌ - ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΡ Π΄Π΅ΠΉΡΡΠ²ΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ Π² ΠΎΠ΄Π½Ρ ΡΡΠΎΡΠΎΠ½Ρ.
Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π½Π° Java Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ Π² BreadthFirstSearch.java
ΠΡΠ»ΠΈ ΠΏΠΎΠΈΡΠΊ ΠΏΡΠΎΠ΄Π°Π²ΡΠ° ΠΌΠ°Π½Π³ΠΎ Π±ΡΠ» Π²ΡΠΏΠΎΠ»Π½Π΅Π½ ΠΏΠΎ Π²ΡΠ΅ΠΉ ΡΠ΅ΡΠΈ, Π·Π½Π°ΡΠΈΡ, Π²Ρ ΠΏΡΠΎΡΠ»ΠΈ ΠΏΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ ΡΠ΅Π±ΡΡ (Π½Π°ΠΏΠΎΠΌΠ½Ρ: ΡΠ΅Π±ΡΠΎΠΌ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΎΠ΅Π΄ΠΈΠ½ΠΈΡΠ΅Π»ΡΠ½Π°Ρ Π»ΠΈΠ½ΠΈΡ ΠΈΠ»ΠΈ Π»ΠΈΠ½ΠΈΡ ΡΠΎ ΡΡΡΠ΅Π»ΠΊΠΎΠΉ, Π²Π΅Π΄ΡΡΠ°Ρ ΠΎΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠ΅Π»ΠΎΠ²Π΅ΠΊΠ° ΠΊ Π΄ΡΡΠ³ΠΎΠΌΡ). Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π²ΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΠΎΡΡΠ°Π²Π»ΡΠ΅Ρ ΠΊΠ°ΠΊ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ Π(ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ).
Π’Π°ΠΊΠΆΠ΅ Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ΅ Π΄ΠΎΠ»ΠΆΠ½Π° Ρ ΡΠ°Π½ΠΈΡΡΡΡ ΠΎΡΠ΅ΡΠ΅Π΄Ρ ΠΏΠΎΠΈΡΠΊΠ°. ΠΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠ΅Π»ΠΎΠ²Π΅ΠΊΠ° Π² ΠΎΡΠ΅ΡΠ΅Π΄Ρ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π·Π° ΠΏΠΎΡΡΠΎΡΠ½Π½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ: Π(1). ΠΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ΅Π»ΠΎΠ²Π΅ΠΊΠ° ΠΏΠΎΡΡΠ΅Π±ΡΠ΅Ρ ΡΡΠΌΠΌΠ°ΡΠ½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ Π(ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π»ΡΠ΄Π΅ΠΉ). ΠΠΎΠΈΡΠΊ Π² ΡΠΈΡΠΈΠ½Ρ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ Π(ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π»ΡΠ΄Π΅ΠΉ + ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ), ΡΡΠΎ ΠΎΠ±ΡΡΠ½ΠΎ Π·Π°ΠΏΠΈΡΡΠ²Π°Π΅ΡΡΡ Π² ΡΠΎΡΠΌΠ΅ O(V+E) (V - ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½, Π - ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ).
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ Π΄Π»Ρ ΠΏΠΎΠΈΡΠΊΠ° ΠΏΡΡΠΈ ΠΎΡ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠΉ ΡΠΎΡΠΊΠΈ ΠΊ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠΉ Π·Π° ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π΅ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· ΡΠ΅ΡΡΡΠ΅Ρ ΡΠ°Π³ΠΎΠ²:
- ΠΠ°ΠΉΡΠΈ ΡΠ·Π΅Π» Ρ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΉ ΡΡΠΎΠΈΠΌΠΎΡΡΡΡ (ΡΠΎ Π΅ΡΡΡ ΡΠ·Π΅Π», Π΄ΠΎ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ Π΄ΠΎΠ±ΡΠ°ΡΡΡΡ Π·Π° ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ).
- ΠΠ±Π½ΠΎΠ²ΠΈΡΡ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ ΡΠΎΡΠ΅Π΄Π΅ΠΉ ΡΡΠΎΠ³ΠΎ ΡΠ·Π»Π°.
- ΠΠΎΠ²ΡΠΎΡΡΡΡ, ΠΏΠΎΠΊΠ° ΡΡΠΎ Π½Π΅ Π±ΡΠ΄Π΅Ρ ΡΠ΄Π΅Π»Π°Π½ΠΎ Π΄Π»Ρ Π²ΡΠ΅Ρ ΡΠ·Π»ΠΎΠ² Π³ΡΠ°ΡΠ°.
- ΠΡΡΠΈΡΠ»ΠΈΡΡ ΠΈΡΠΎΠ³ΠΎΠ²ΡΠΉ ΠΏΡΡΡ.
ΠΠΎΠ³Π΄Π° Π²Ρ ΡΠ°Π±ΠΎΡΠ°Π΅ΡΠ΅ Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ, Ρ ΠΊΠ°ΠΆΠ΄ΡΠΌ ΡΠ΅Π±ΡΠΎΠΌ Π³ΡΠ°ΡΠ° ΡΠ²ΡΠ·ΡΠ²Π°Π΅ΡΡΡ ΡΠΈΡΠ»ΠΎ, Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠΎΠ΅ Π²Π΅ΡΠΎΠΌ. ΠΡΠ°Ρ Ρ Π²Π΅ΡΠ°ΠΌΠΈ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π²Π·Π²Π΅ΡΠ΅Π½Π½ΡΠΌ Π³ΡΠ°ΡΠΎΠΌ. ΠΡΠ°Ρ Π±Π΅Π· Π²Π΅ΡΠΎΠ² Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π½Π΅Π²Π·Π²Π΅ΡΠ΅Π½Π½ΡΠΌ Π³ΡΠ°ΡΠΎΠΌ.
Π Π½Π΅Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΠΎΠΌ Π³ΡΠ°ΡΠ΅ ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ Π½ΠΎΠ²ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ Π΄ΠΎΠ±Π°Π²Π»ΡΠ΅Ρ Π΅ΡΠ΅ ΠΎΠ΄ΠΈΠ½ ΡΠΈΠΊΠ». ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΠΎΠ»ΡΠΊΠΎ Ρ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΡΠΌΠΈ Π°ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠΌΠΈ Π³ΡΠ°ΡΠ°ΠΌΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ Π½Π΅ΡΠ΅Π΄ΠΊΠΎ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°ΡΡΡΡ ΡΠΎΠΊΡΠ°ΡΠ΅Π½ΠΈΠ΅ΠΌ DAG (Directed Acyclic Graph).
Π₯ΠΎΡΠ΅ΡΡΡ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ ΠΏΡΠΈ Π½Π°Π»ΠΈΡΠΈΠΈ ΡΠ΅Π±Π΅Ρ, ΠΈΠΌΠ΅ΡΡΠΈΡ ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΠΉ Π²Π΅Ρ. Π’Π°ΠΊΠΈΠ΅ ΡΠ΅Π±ΡΠ° Π½Π°ΡΡΡΠ°ΡΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°.
ΠΠΎΡΠΌΠΎΡΡΠΈΠΌ, ΠΊΠ°ΠΊ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ ΡΠ΅Π°Π»ΠΈΠ·ΡΠ΅ΡΡΡ Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΠΎΠΌ ΠΊΠΎΠ΄Π΅. ΠΠΈΠΆΠ΅ ΠΈΠ·ΠΎΠ±ΡΠ°ΠΆΠ΅Π½ Π³ΡΠ°Ρ, ΠΊΠΎΡΠΎΡΡΠΉ Π±ΡΠ΄Π΅Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ Π² ΡΡΠΎΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠ΅.
Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π½Π° ΡΠ·ΡΠΊΠ΅ Java ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Π° Π² DijkstraAlgorithm.java
ΠΠ°ΠΊΠΎΠ² Π²Π΅Ρ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΏΡΡΠΈ ΠΎΡ Π½Π°ΡΠ°Π»Π° Π΄ΠΎ ΠΊΠΎΠ½ΡΠ° Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΈΠ· ΡΠ»Π΅Π΄ΡΡΡΠΈΡ Π³ΡΠ°ΡΠΎΠ²?
ΠΡΠ²Π΅ΡΡ
Π - 8; Π - 60; Π‘ - ΠΊΠ°Π²Π΅ΡΠ·Π½ΡΠΉ Π²ΠΎΠΏΡΠΎΡ (ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΏΡΡΡ Π½Π΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΠΈΠ·-Π·Π° Π½Π°Π»ΠΈΡΠΈΡ ΡΠΈΠΊΠ»Π° Ρ ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΠΌ Π²Π΅ΡΠΎΠΌ).ΠΠΎΠΏΡΡΡΠΈΠΌ, ΠΈΠΌΠ΅Π΅ΡΡΡ ΡΡΠ΅Π±Π½ΡΠΉ ΠΊΠ»Π°ΡΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ Π½ΡΠΆΠ½ΠΎ ΠΏΡΠΎΠ²Π΅ΡΡΠΈ ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ½ΠΎ Π±ΠΎΠ»ΡΡΠ΅ ΡΡΠΎΠΊΠΎΠ². ΠΡ ΠΏΠΎΠ»ΡΡΠ°Π΅ΡΠ΅ ΡΠΏΠΈΡΠΎΠΊ ΡΡΠΎΠΊΠΎΠ² (ΡΠΌ. ΡΠΈΡΡΠ½ΠΎΠΊ Π½ΠΈΠΆΠ΅).
ΠΡΠΎΠ²Π΅ΡΡΠΈ Π² ΠΊΠ»Π°ΡΡΠ΅ Π²ΡΠ΅ ΡΡΠΎΠΊΠΈ Π½Π΅ ΠΏΠΎΠ»ΡΡΠΈΡΡΡ, ΠΏΠΎΡΠΎΠΌΡ ΡΡΠΎ Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ ΠΈΠ· Π½ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΊΡΡΠ²Π°ΡΡΡΡ ΠΏΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ.
ΠΡΠΎΠ΄Π΅ Π±Ρ ΡΠ»ΠΎΠΆΠ½Π°Ρ Π·Π°Π΄Π°ΡΠ°, Π²Π΅ΡΠ½ΠΎ? ΠΠ° ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΎΠΊΠ°Π·ΡΠ²Π°Π΅ΡΡΡ Π½Π° ΡΠ΄ΠΈΠ²Π»Π΅Π½ΠΈΠ΅ ΠΏΡΠΎΡΡΡΠΌ. ΠΠΎΡ ΠΊΠ°ΠΊ ΠΎΠ½ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ:
- ΠΡΠ±ΡΠ°ΡΡ ΡΡΠΎΠΊ, Π·Π°Π²Π΅ΡΡΠ°ΡΡΠΈΠΉΡΡ ΡΠ°Π½ΡΡΠ΅ Π²ΡΠ΅Ρ . ΠΡΠΎ ΠΏΠ΅ΡΠ²ΡΠΉ ΡΡΠΎΠΊ, ΠΊΠΎΡΠΎΡΡΠΉ Π±ΡΠ΄Π΅Ρ ΠΏΡΠΎΠ²Π΅Π΄Π΅Π½ Π² ΠΊΠ»Π°ΡΡΠ΅.
- ΠΠ°ΡΠ΅ΠΌ Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ ΡΡΠΎΠΊ, Π½Π°ΡΠΈΠ½Π°ΡΡΠΈΠΉΡΡ ΠΏΠΎΡΠ»Π΅ Π·Π°Π²Π΅ΡΡΠ΅Π½ΠΈΡ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΡΡΠΎΠΊΠ°. Π ΡΠ½ΠΎΠ²Π° ΡΠ»Π΅Π΄ΡΠ΅Ρ Π²ΡΠ±ΡΠ°ΡΡ ΡΡΠΎΠΊ, ΠΊΠΎΡΠΎΡΡΠΉ Π·Π°Π²Π΅ΡΡΠ°Π΅ΡΡΡ ΡΠ°Π½ΡΡΠ΅ Π²ΡΠ΅Ρ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ . ΠΠ½ ΡΡΠ°Π½ΠΎΠ²ΠΈΡΡΡ Π²ΡΠΎΡΡΠΌ ΡΡΠΎΠΊΠΎΠΌ Π² ΡΠ°ΡΠΏΠΈΡΠ°Π½ΠΈΠΈ.
ΠΡΠΎΠ΄ΠΎΠ»ΠΆΠ°ΠΉΡΠ΅ Π΄Π΅ΠΉΡΡΠ²ΠΎΠ²Π°ΡΡ ΠΏΠΎ ΡΠΎΠΌΡ ΠΆΠ΅ ΠΏΡΠΈΠ½ΡΠΈΠΏΡ - ΠΈ Π²Ρ ΠΏΠΎΠ»ΡΡΠΈΡΠ΅ ΠΎΡΠ²Π΅Ρ!
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΡΠΊΠΎΠ»ΡΠ½ΡΠ΅ ΡΡΠΎΠΊΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ Π±ΡΠ΄ΡΡ ΠΏΡΠΎΠ²ΠΎΠ΄ΠΈΡΡΡΡ Π² ΠΊΠ»Π°ΡΡΠ΅, ΠΎΡΠΌΠ΅ΡΠ΅Π½Ρ Π³Π°Π»ΠΎΡΠΊΠΎΠΉ.
ΠΠ°Π΄Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΡΠΎΡΡ: Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΠΎΠ½ Π²ΡΠ±ΠΈΡΠ°Π΅Ρ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ Π²Π°ΡΠΈΠ°Π½Ρ. Π Π½Π°ΡΠ΅ΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠ΅ ΠΏΡΠΈ Π²ΡΠ±ΠΎΡΠ΅ ΡΡΠΎΠΊΠ° Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ ΡΠΎΡ ΡΡΠΎΠΊ, ΠΊΠΎΡΠΎΡΡΠΉ Π·Π°Π²Π΅ΡΡΠ°Π΅ΡΡΡ ΡΠ°Π½ΡΡΠ΅ Π΄ΡΡΠ³ΠΈΡ .
Π ΡΠ΅Ρ Π½ΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠ΅ΡΠΌΠΈΠ½ΠΎΠ»ΠΎΠ³ΠΈΠΈ: Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ Π»ΠΎΠΊΠ°Π»ΡΠ½ΠΎ-ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅, Π° Π² ΠΈΡΠΎΠ³Π΅ Π²Ρ ΠΏΠΎΠ»ΡΡΠ°Π΅ΡΠ΅ Π³Π»ΠΎΠ±Π°Π»ΡΠ½ΠΎ-ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. Π₯ΠΎΡΠΈΡΠ΅ Π²Π΅ΡΡΡΠ΅, Ρ ΠΎΡΠΈΡΠ΅ Π½Π΅Ρ, Π½ΠΎ ΡΡΠΎΡ ΠΏΡΠΎΡΡΠΎΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΡΠΏΠ΅ΡΠ½ΠΎ Π½Π°Ρ ΠΎΠ΄ΠΈΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ ΡΠΎΡΡΠ°Π²Π»Π΅Π½ΠΈΡ ΡΠ°ΡΠΏΠΈΡΠ°Π½ΠΈΡ!
ΠΡ ΠΎΡΠΊΡΡΠ²Π°Π΅ΡΠ΅ ΡΠΎΠ±ΡΡΠ²Π΅Π½Π½ΡΡ Π°Π²ΡΠΎΡΡΠΊΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π½Π° ΡΠ°Π΄ΠΈΠΎ ΠΈ Ρ ΠΎΡΠΈΡΠ΅, ΡΡΠΎΠ±Ρ Π²Π°Ρ ΡΠ»ΡΡΠ°Π»ΠΈ Π²ΠΎ Π²ΡΠ΅Ρ 50 ΡΡΠ°ΡΠ°Ρ . ΠΡΠΆΠ½ΠΎ ΡΠ΅ΡΠΈΡΡ, Π½Π° ΠΊΠ°ΠΊΠΈΡ ΡΠ°Π΄ΠΈΠΎΡΡΠ°Π½ΡΠΈΡΡ Π΄ΠΎΠ»ΠΆΠ½Π° ΡΡΠ°Π½ΡΠ»ΠΈΡΠΎΠ²Π°ΡΡΡΡ Π²Π°ΡΠ° ΠΏΠ΅ΡΠ΅Π΄Π°ΡΠ°. ΠΠ°ΠΆΠ΄Π°Ρ ΡΡΠ°Π½ΡΠΈΡ ΡΡΠΎΠΈΡ Π΄Π΅Π½Π΅Π³, ΠΏΠΎΡΡΠΎΠΌΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΡΠ°Π½ΡΠΈΠΉ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΠ²Π΅ΡΡΠΈ ΠΊ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΡ. ΠΠΌΠ΅Π΅ΡΡΡ ΡΠΏΠΈΡΠΎΠΊ ΡΡΠ°Π½ΡΠΈΠΉ. ΠΠ°ΠΆΠ΄Π°Ρ ΡΡΠ°Π½ΡΠΈΡ ΠΏΠΎΠΊΡΡΠ²Π°Π΅Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΉ Π½Π°Π±ΠΎΡ ΡΡΠ°ΡΠΎΠ², ΡΡΠΈ Π½Π°Π±ΠΎΡΡ ΠΏΠ΅ΡΠ΅ΠΊΡΡΠ²Π°ΡΡΡΡ.
ΠΠ°ΠΊ Π½Π°ΠΉΡΠΈ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ Π½Π°Π±ΠΎΡ ΡΡΠ°Π½ΡΠΈΠΉ, ΠΊΠΎΡΠΎΡΡΠΉ Π±Ρ ΠΏΠΎΠΊΡΡΠ²Π°Π» Π²ΡΠ΅ 50 ΡΡΠ°ΡΠΎΠ²?
ΠΠΎΡ ΠΊΠ°ΠΊ Π²ΡΠ³Π»ΡΠ΄ΠΈΡ ΠΆΠ°Π΄Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ, ΠΊΠΎΡΠΎΡΡΠΉ Π²ΡΠ΄Π°Π΅Ρ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ, Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ Π±Π»ΠΈΠ·ΠΊΠΈΠΉ ΠΊ ΠΎΠΏΡΠΈΠΌΡΠΌΡ:
- ΠΡΠ±ΡΠ°ΡΡ ΡΡΠ°Π½ΡΠΈΡ, ΠΏΠΎΠΊΡΡΠ²Π°ΡΡΡΡ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΡΠ°ΡΠΎΠ², Π΅ΡΠ΅ Π½Π΅ Π²Ρ ΠΎΠ΄ΡΡΠΈΡ Π² ΠΏΠΎΠΊΡΡΡΠΈΠ΅. ΠΡΠ»ΠΈ ΡΡΠ°Π½ΡΠΈΡ Π±ΡΠ΄Π΅Ρ ΠΏΠΎΠΊΡΡΠ²Π°ΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ ΡΡΠ°ΡΡ, ΡΠΆΠ΅ Π²Ρ ΠΎΠ΄ΡΡΠΈΠ΅ Π² ΠΏΠΎΠΊΡΡΡΠΈΠ΅, ΡΡΠΎ Π½ΠΎΡΠΌΠ°Π»ΡΠ½ΠΎ.
- ΠΠΎΠ²ΡΠΎΡΡΡΡ, ΠΏΠΎΠΊΠ° ΠΎΡΡΠ°ΡΡΡΡ ΡΡΠ°ΡΡ, Π½Π΅ Π²Ρ ΠΎΠ΄ΡΡΠΈΠ΅ Π² ΠΏΠΎΠΊΡΡΡΠΈΠ΅.
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΡΠΉ ΠΊΠΎΠ΄ ΡΠ°ΡΠΏΠΎΠ»Π°Π³Π°Π΅ΡΡΡ Π² Π΄ΠΈΡΠ΅ΠΊΡΠΎΡΠΈΠΈ greedy_algorithms.
ΠΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ - ΠΌΠ΅ΡΠΎΠ΄ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΠ»ΠΎΠΆΠ½ΡΡ Π·Π°Π΄Π°Ρ, ΡΠ°Π·Π±ΠΈΠ²Π°Π΅ΠΌΡΡ Π½Π° ΠΏΠΎΠ΄Π·Π°Π΄Π°ΡΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ ΡΠ΅ΡΠ°ΡΡΡΡ Π² ΠΏΠ΅ΡΠ²ΡΡ ΠΎΡΠ΅ΡΠ΅Π΄Ρ.
ΠΡΠ΅Π΄ΡΡΠ°Π²ΠΈΠΌ, ΡΡΠΎ Ρ Π½Π°Ρ Π΅ΡΡΡ ΡΡΠΊΠ·Π°ΠΊ, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ½Π΅ΡΡΠΈ ΡΠΎΠ²Π°ΡΡ ΠΎΠ±ΡΠΈΠΌ Π²Π΅ΡΠΎΠΌ Π΄ΠΎ 4 ΡΡΠ½ΡΠΎΠ².
ΠΡΡΡ ΡΡΠΈ ΠΏΡΠ΅Π΄ΠΌΠ΅ΡΠ°, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ»ΠΎΠΆΠΈΡΡ Π² ΡΡΠΊΠ·Π°ΠΊ.
- ΠΠΎΡΡΠ±ΡΠΊ, ΠΊΠΎΡΠΎΡΡΠΉ Π²Π΅ΡΠΈΡ 3 ΡΡΠ½ΡΠ° ΠΈ ΡΡΠΎΠΈΡ 2000$;
- ΠΠ°Π³Π½ΠΈΡΠΎΡΠΎΠ½ β 4 ΡΡΠ½ΡΠ° ΠΌΠΎΡΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΎΠ±ΠΎΠΉΠ΄ΡΡΡΡ Π² 3000$;
- ΠΠΈΡΠ°ΡΠ° β Π²Π΅ΡΠΈΡ 1 ΡΡΠ½Ρ, Π° ΡΡΠΎΠΈΡ 1500$.
ΠΠ°ΠΊΠΈΠ΅ ΠΏΡΠ΅Π΄ΠΌΠ΅ΡΡ ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΡ Π² ΡΡΠΊΠ·Π°ΠΊ, ΡΡΠΎΠ±Ρ ΡΡΠΎΠΈΠΌΠΎΡΡΡ Π΄ΠΎΠ±ΡΡΠΈ Π±ΡΠ»Π° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ?
Π§ΡΠΎΠ±Ρ ΡΠ΅ΡΠΈΡΡ Π·Π°Π΄Π°ΡΡ, Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΡΡ ΠΏΡΠΈΡΠΌΠ°ΠΌΠΈ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ.
Π Π°Π·ΠΎΠ±ΡΡΠΌ Π·Π°Π΄Π°ΡΡ Π½Π° ΠΏΠΎΠ΄Π·Π°Π΄Π°ΡΠΈ ΠΈ Π±ΡΠ΄Π΅ΠΌ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ ΠΈΡ ΡΠ΅ΡΠ°ΡΡ. ΠΡΠΈ ΡΡΠΎΠΌ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ ΡΠ°Π³Π΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅Π³ΠΎ.
Π Π΅ΡΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ Π½Π° Java: Π·Π°Π΄Π°ΡΠ° ΠΎ ΡΡΠΊΠ·Π°ΠΊΠ΅
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ Π΅ΡΠ΅ ΠΎΠ΄ΠΈΠ½ ΠΏΡΠΈΠΌΠ΅Ρ.
ΠΠΎΠΏΡΡΡΠΈΠΌ, Π²Ρ ΠΎΡΠΊΡΡΠ»ΠΈ ΡΠ°ΠΉΡ dictionary.com. ΠΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ Π²Π²ΠΎΠ΄ΠΈΡ ΡΠ»ΠΎΠ²ΠΎ, Π° ΡΠ°ΠΉΡ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅. ΠΠΎ Π΅ΡΠ»ΠΈ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ Π²Π²Π΅Π» Π½Π΅ΡΡΡΠ΅ΡΡΠ²ΡΡΡΠ΅Π΅ ΡΠ»ΠΎΠ²ΠΎ, Π½ΡΠΆΠ½ΠΎ ΠΏΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΡΡ, ΠΊΠ°ΠΊΠΎΠ΅ ΡΠ»ΠΎΠ²ΠΎ ΠΈΠΌΠ΅Π»ΠΎΡΡ Π² Π²ΠΈΠ΄Ρ.
ΠΠ»Π΅ΠΊΡ ΠΈΡΠ΅Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ "fish", Π½ΠΎ ΠΎΠ½ ΡΠ»ΡΡΠ°ΠΉΠ½ΠΎ Π²Π²Π΅Π» "hish". Π’Π°ΠΊΠΎΠ³ΠΎ ΡΠ»ΠΎΠ²Π° Π² ΡΠ»ΠΎΠ²Π°ΡΠ΅ Π½Π΅Ρ, Π½ΠΎ Π·Π°ΡΠΎ Ρ Π²Π°Ρ Π΅ΡΡΡ ΡΠΏΠΈΡΠΎΠΊ ΠΏΠΎΡ ΠΎΠΆΠΈΡ ΡΠ»ΠΎΠ².
Π‘ΠΠΠΠ, ΠΠΠ₯ΠΠΠΠ ΠΠ "ΠISΠ":
- FISH
- VISTA
ΠΡΠ°ΠΊ, ΠΠ»Π΅ΠΊΡ Π²Π²Π΅Π» ΡΡΡΠΎΠΊΡ hish. ΠΠ°ΠΊΠΎΠ΅ ΡΠ»ΠΎΠ²ΠΎ ΠΎΠ½ Ρ ΠΎΡΠ΅Π» Π²Π²Π΅ΡΡΠΈ Π½Π° ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅: fish ΠΈΠ»ΠΈ vista?
Π Π΅ΡΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΎ Π² Π΄ΠΈΡΠ΅ΠΊΡΠΎΡΠΈΠΈ longest_common_subsequence