Π Π°Π±ΠΎΡΠ° Ρ ΠΌΠ°ΡΡΠΈΠ²Π°ΠΌΠΈ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΡΠ½Π΄Π°ΠΌΠ΅Π½ΡΠ°Π»ΡΠ½ΠΎΠΉ ΡΠ°ΡΡΡΡ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠΈ Π² ΠΏΠ»Π°ΡΡΠΎΡΠΌΠ΅ 1Π‘:ΠΡΠ΅Π΄ΠΏΡΠΈΡΡΠΈΠ΅. Π Π°Π·ΡΠ°Π±ΠΎΡΡΠΈΠΊΠΈ ΠΏΠΎΡΡΠΎΡΠ½Π½ΠΎ ΡΡΠ°Π»ΠΊΠΈΠ²Π°ΡΡΡΡ Ρ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎΡΡΡΡ Π½Π΅ ΠΏΡΠΎΡΡΠΎ ΠΏΠ΅ΡΠ΅Π±ΡΠ°ΡΡ Π΄Π°Π½Π½ΡΠ΅, Π½ΠΎ ΠΈ ΡΠΎΡΠ½ΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ ΠΏΠΎΠ·ΠΈΡΠΈΡ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΠΎΠ³ΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ. ΠΠΎΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅ ΡΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ ΠΏΠΎΠ»ΡΡΠΈΡΡ ΠΈΠ½Π΄Π΅ΠΊΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, ΠΊΡΠΈΡΠΈΡΠ΅ΡΠΊΠΈ Π²Π°ΠΆΠ½ΠΎ Π΄Π»Ρ ΠΎΠΏΡΠΈΠΌΠΈΠ·Π°ΡΠΈΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΈ ΠΊΠΎΡΡΠ΅ΠΊΡΠ½ΠΎΠ³ΠΎ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ ΠΈΠ»ΠΈ Π·Π°ΠΌΠ΅Π½Ρ Π΄Π°Π½Π½ΡΡ Π² ΡΡΡΡΠΊΡΡΡΠ΅.
Π ΠΎΡΠ»ΠΈΡΠΈΠ΅ ΠΎΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΠ·ΡΠΊΠΎΠ², Π³Π΄Π΅ ΠΈΠ½Π΄Π΅ΠΊΡΠ°ΡΠΈΡ ΠΌΠΎΠΆΠ΅Ρ Π½Π°ΡΠΈΠ½Π°ΡΡΡΡ Ρ Π΅Π΄ΠΈΠ½ΠΈΡΡ, Π² 1Π‘ ΠΌΠ°ΡΡΠΈΠ²Ρ ΡΡΡΠΎΠ³ΠΎ ΠΈΠ½Π΄Π΅ΠΊΡΠΈΡΡΡΡΡΡ Ρ Π½ΡΠ»Ρ. ΠΡΠΎ Π±Π°Π·ΠΎΠ²ΠΎΠ΅ ΠΏΡΠ°Π²ΠΈΠ»ΠΎ, Π½Π°ΡΡΡΠ΅Π½ΠΈΠ΅ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΠΎΡΠΈΠ±ΠΊΠ°ΠΌ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΠΈΠ»ΠΈ Π½Π΅ΠΊΠΎΡΡΠ΅ΠΊΡΠ½ΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ. Π Π΄Π°Π½Π½ΠΎΠΉ ΡΡΠ°ΡΡΠ΅ ΠΌΡ Π΄Π΅ΡΠ°Π»ΡΠ½ΠΎ ΡΠ°Π·Π±Π΅ΡΠ΅ΠΌ Π²ΡΡΡΠΎΠ΅Π½Π½ΡΠ΅ ΠΌΠ΅Ρ Π°Π½ΠΈΠ·ΠΌΡ ΠΏΠΎΠΈΡΠΊΠ° ΠΈ ΡΡΡΠ½ΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΠΏΠΎΠ·ΠΈΡΠΈΠΈ.
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠ΅ ΡΡΠ΅Π½Π°ΡΠΈΠΈ: ΠΎΡ ΠΏΠΎΠΈΡΠΊΠ° ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ Π²Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ Π΄ΠΎ ΡΠ°Π±ΠΎΡΡ Ρ Π½Π΅ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΠΌΠΈ ΡΠΏΠΈΡΠΊΠ°ΠΌΠΈ. ΠΡ ΡΠ°ΠΊΠΆΠ΅ ΠΎΠ±ΡΡΠ΄ΠΈΠΌ Π½ΡΠ°Π½ΡΡ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ ΠΈ ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎΡΡΠΈ ΡΠ°Π±ΠΎΡΡ Ρ ΡΠΈΠΏΠ°ΠΌΠΈ Π΄Π°Π½Π½ΡΡ , ΠΊΠΎΡΠΎΡΡΠ΅ Π²Π»ΠΈΡΡΡ Π½Π° ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ ΠΏΠΎΠΈΡΠΊΠ°.
ΠΠ°Π·ΠΎΠ²ΡΠ΅ ΠΏΡΠΈΠ½ΡΠΈΠΏΡ ΠΈΠ½Π΄Π΅ΠΊΡΠ°ΡΠΈΠΈ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ² Π² 1Π‘
ΠΠ°ΡΡΠΈΠ² Π² ΠΊΠΎΠ½ΡΠΈΠ³ΡΡΠ°ΡΠΈΡΡ
1Π‘ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅Ρ ΡΠΎΠ±ΠΎΠΉ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΡ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ. ΠΠ°ΠΆΠ΄ΠΎΠΌΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΏΡΠΈΡΠ²Π°ΠΈΠ²Π°Π΅ΡΡΡ ΡΠΈΡΠ»ΠΎΠ²ΠΎΠΉ ΠΈΠ΄Π΅Π½ΡΠΈΡΠΈΠΊΠ°ΡΠΎΡ, Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΠΉ ΠΈΠ½Π΄Π΅ΠΊΡΠΎΠΌ. ΠΡΠΌΠ΅ΡΠ°ΡΠΈΡ Π²ΡΠ΅Π³Π΄Π° Π½Π°ΡΠΈΠ½Π°Π΅ΡΡΡ Ρ Π½ΡΠ»Ρ, ΡΡΠΎ ΠΎΠ·Π½Π°ΡΠ°Π΅Ρ: ΠΏΠ΅ΡΠ²ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΈΠΌΠ΅Π΅Ρ ΠΈΠ½Π΄Π΅ΠΊΡ 0, Π²ΡΠΎΡΠΎΠΉ β 1, Π° ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΠΉ β ΠΠ°ΡΡΠΈΠ².ΠΠΡΠ°Π½ΠΈΡΠ°().
ΠΡΠΈ ΠΈΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΌΠ°ΡΡΠΈΠ²Π° Π΅Π³ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΠ½ΠΎΡΡΡ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΡΠΈΠΊΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΉ ΠΈΠ»ΠΈ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠΉ. ΠΡΠ»ΠΈ Π²Ρ ΠΏΠΎΠΏΡΡΠ°Π΅ΡΠ΅ΡΡ ΠΎΠ±ΡΠ°ΡΠΈΡΡΡΡ ΠΊ ΠΈΠ½Π΄Π΅ΠΊΡΡ, ΠΏΡΠ΅Π²ΡΡΠ°ΡΡΠ΅ΠΌΡ Π²Π΅ΡΡ Π½ΡΡ Π³ΡΠ°Π½ΠΈΡΡ, ΡΠΈΡΡΠ΅ΠΌΠ° Π²ΡΠ±ΡΠΎΡΠΈΡ ΠΈΡΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅.
ΠΠ»Ρ ΠΏΡΠΎΠ²Π΅ΡΠΊΠΈ ΡΡΡΠ΅ΡΡΠ²ΠΎΠ²Π°Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° ΠΏΠΎ ΠΈΠ½Π΄Π΅ΠΊΡΡ ΡΠ°ΡΡΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡ ΠΌΠ΅ΡΠΎΠ΄ ΠΡΡΡΠΎΠΉ() ΠΈΠ»ΠΈ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ Ρ ΠΠ΅ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΎ, ΠΎΠ΄Π½Π°ΠΊΠΎ ΡΠ°ΠΌ ΡΠ°ΠΊΡ Π½Π°Π»ΠΈΡΠΈΡ ΠΈΠ½Π΄Π΅ΠΊΡΠ° ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ Π³ΡΠ°Π½ΠΈΡΠ°ΠΌΠΈ ΠΌΠ°ΡΡΠΈΠ²Π°. ΠΠ½Π°Π½ΠΈΠ΅ ΡΡΠΈΡ
Π³ΡΠ°Π½ΠΈΡ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎ ΠΈΡΠ΅ΡΠΈΡΠΎΠ²Π°ΡΡΡΡ ΠΏΠΎ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΈ.
β οΈ ΠΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠΠΎΠΏΡΡΠΊΠ° ΠΏΠΎΠ»ΡΡΠΈΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΏΠΎ Π½Π΅ΡΡΡΠ΅ΡΡΠ²ΡΡΡΠ΅ΠΌΡ ΠΈΠ½Π΄Π΅ΠΊΡΡ (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ,
ΠΠ°ΡΡΠΈΠ²[-1]ΠΈΠ»ΠΈΠΠ°ΡΡΠΈΠ²[Π Π°Π·ΠΌΠ΅Ρ]) ΠΏΡΠΈΠ²Π΅Π΄Π΅Ρ ΠΊ ΠΎΡΠΈΠ±ΠΊΠ΅ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ "ΠΠ½Π΄Π΅ΠΊΡ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ Π²Π½Π΅ Π³ΡΠ°Π½ΠΈΡ ΠΌΠ°ΡΡΠΈΠ²Π°".
ΠΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ΅ΡΠΎΠ΄Π° ΠΠΎΠΈΡΠΊ Π΄Π»Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΠΏΠΎΠ·ΠΈΡΠΈΠΈ
Π‘Π°ΠΌΡΠΉ ΡΠ°ΡΠΏΡΠΎΡΡΡΠ°Π½Π΅Π½Π½ΡΠΉ ΠΈ ΡΠ΄ΠΎΠ±Π½ΡΠΉ ΡΠΏΠΎΡΠΎΠ± ΡΠ·Π½Π°ΡΡ ΠΈΠ½Π΄Π΅ΠΊΡ β ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π²ΡΡΡΠΎΠ΅Π½Π½ΡΠΉ ΠΌΠ΅ΡΠΎΠ΄ ΠΠΎΠΈΡΠΊ. ΠΡΠΎΡ ΠΌΠ΅ΡΠΎΠ΄ ΡΠΊΠ°Π½ΠΈΡΡΠ΅Ρ ΠΌΠ°ΡΡΠΈΠ² Ρ Π½Π°ΡΠ°Π»Π° ΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ ΠΈΠ½Π΄Π΅ΠΊΡ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ Π½Π°ΠΉΠ΄Π΅Π½Π½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΠΎΠ»Π½ΠΎΡΡΡΡ ΡΠ°Π²Π΅Π½ ΠΈΡΠΊΠΎΠΌΠΎΠΌΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡ. ΠΡΠ»ΠΈ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½, ΠΌΠ΅ΡΠΎΠ΄ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ -1.
Π‘ΠΈΠ½ΡΠ°ΠΊΡΠΈΡ ΠΌΠ΅ΡΠΎΠ΄Π° ΠΏΡΠ΅Π΄Π΅Π»ΡΠ½ΠΎ ΠΏΡΠΎΡΡ: ΠΠ½Π΄Π΅ΠΊΡ = ΠΠ°ΡΡΠΈΠ².ΠΠΎΠΈΡΠΊ(ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅). ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ Π΄Π»Ρ Π½Π΅Π±ΠΎΠ»ΡΡΠΈΡ
ΠΈ ΡΡΠ΅Π΄Π½ΠΈΡ
ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ². ΠΠ΄Π½Π°ΠΊΠΎ ΡΡΠΎΠΈΡ ΡΡΠΈΡΡΠ²Π°ΡΡ, ΡΡΠΎ ΠΏΠΎΠΈΡΠΊ ΠΎΡΡΡΠ΅ΡΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ, Π° Π½Π΅ ΠΏΠΎ ΡΡΡΠ»ΠΊΠ΅ Π½Π° ΠΎΠ±ΡΠ΅ΠΊΡ, Π΅ΡΠ»ΠΈ ΡΡΠΎ Π½Π΅ ΠΏΡΠΈΠΌΠΈΡΠΈΠ²Π½ΡΠΉ ΡΠΈΠΏ.
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΏΡΠΈΠΌΠ΅Ρ ΠΊΠΎΠ΄Π°, Π΄Π΅ΠΌΠΎΠ½ΡΡΡΠΈΡΡΡΡΠΈΠΉ ΡΠ°Π±ΠΎΡΡ ΠΌΠ΅ΡΠΎΠ΄Π°:
ΠΠ°ΡΡΠΈΠ² = ΠΠΎΠ²ΡΠΉ ΠΠ°ΡΡΠΈΠ²;
ΠΠ°ΡΡΠΈΠ².ΠΠΎΠ±Π°Π²ΠΈΡΡ("Π―Π±Π»ΠΎΠΊΠΎ");
ΠΠ°ΡΡΠΈΠ².ΠΠΎΠ±Π°Π²ΠΈΡΡ("ΠΡΡΡΠ°");
ΠΠ°ΡΡΠΈΠ².ΠΠΎΠ±Π°Π²ΠΈΡΡ("Π‘Π»ΠΈΠ²Π°");
ΠΠ½Π΄Π΅ΠΊΡΠΡΡΡΠΈ = ΠΠ°ΡΡΠΈΠ².ΠΠΎΠΈΡΠΊ("ΠΡΡΡΠ°"); // ΠΠ΅ΡΠ½Π΅Ρ 1
ΠΠ½Π΄Π΅ΠΊΡΠΠΈΡΠ½ΠΈ = ΠΠ°ΡΡΠΈΠ².ΠΠΎΠΈΡΠΊ("ΠΠΈΡΠ½Ρ"); // ΠΠ΅ΡΠ½Π΅Ρ -1
ΠΠ°ΠΆΠ½ΠΎ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ ΠΌΠ΅ΡΠΎΠ΄ ΠΠΎΠΈΡΠΊ ΡΡΠ²ΡΡΠ²ΠΈΡΠ΅Π»Π΅Π½ ΠΊ ΡΠΈΠΏΡ Π΄Π°Π½Π½ΡΡ
. Π§ΠΈΡΠ»ΠΎ 1 ΠΈ ΡΡΡΠΎΠΊΠ° "1" Π±ΡΠ΄ΡΡ ΡΡΠΈΡΠ°ΡΡΡΡ ΡΠ°Π·Π½ΡΠΌΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌΠΈ, ΠΈ ΠΏΠΎΠΈΡΠΊ Π½Π΅ Π΄Π°ΡΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ° ΠΏΡΠΈ Π½Π΅ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠΈ ΡΠΈΠΏΠΎΠ².
ΠΠ΅ΡΠΎΠ΄ ΠΠΎΠΈΡΠΊ ΠΎΡΡΠ°Π½Π°Π²Π»ΠΈΠ²Π°Π΅ΡΡΡ Π½Π° ΠΏΠ΅ΡΠ²ΠΎΠΌ ΡΠΎΠ²ΠΏΠ°Π΄Π΅Π½ΠΈΠΈ. ΠΡΠ»ΠΈ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Π΅ΡΡΡ Π΄ΡΠ±Π»ΠΈΠΊΠ°ΡΡ, Π²Ρ ΠΏΠΎΠ»ΡΡΠΈΡΠ΅ ΠΈΠ½Π΄Π΅ΠΊΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΠΈΠ· Π½ΠΈΡ .
ΠΠΎΠΈΡΠΊ Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ ΠΌΠ΅ΡΠΎΠ΄Π° ΠΠ°ΠΉΡΠΈ
ΠΠ»ΡΡΠ΅ΡΠ½Π°ΡΠΈΠ²ΠΎΠΉ ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΠΎΠΈΡΠΊ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΌΠ΅ΡΠΎΠ΄ ΠΠ°ΠΉΡΠΈ. Π₯ΠΎΡΡ ΠΈΡ
ΡΡΠ½ΠΊΡΠΈΠΎΠ½Π°Π» Π²ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΌ ΡΡ
ΠΎΠΆ, ΠΠ°ΠΉΡΠΈ ΠΏΡΠ΅Π΄ΠΎΡΡΠ°Π²Π»ΡΠ΅Ρ Π±ΠΎΠ»Π΅Π΅ Π³ΠΈΠ±ΠΊΠΈΠ΅ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠΈ Π΄Π»Ρ ΡΠ°Π±ΠΎΡΡ Ρ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΡΠΌΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ ΠΈ ΡΠ°ΡΡΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ Π² ΠΊΠΎΠ½ΡΠ΅ΠΊΡΡΠ΅ ΡΠΈΠ»ΡΡΡΠ°ΡΠΈΠΈ ΠΈΠ»ΠΈ ΡΠ»ΠΎΠΆΠ½ΠΎΠ³ΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡ.
ΠΠ΅ΡΠΎΠ΄ ΠΠ°ΠΉΡΠΈ ΡΠ°ΠΊΠΆΠ΅ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ ΠΈΠ½Π΄Π΅ΠΊΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° ΠΈΠ»ΠΈ -1, Π΅ΡΠ»ΠΈ ΠΏΠΎΠΈΡΠΊ Π±Π΅Π·ΡΡΠΏΠ΅ΡΠ΅Π½. ΠΡΠ½ΠΎΠ²Π½ΠΎΠ΅ ΠΎΡΠ»ΠΈΡΠΈΠ΅ ΠΌΠΎΠΆΠ΅Ρ Π·Π°ΠΊΠ»ΡΡΠ°ΡΡΡΡ Π² ΠΌΠ΅Ρ
Π°Π½ΠΈΠ·ΠΌΠ΅ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ², ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎ Π΅ΡΠ»ΠΈ ΠΌΠ°ΡΡΠΈΠ² ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΡΠ»ΠΎΠΆΠ½ΡΠ΅ ΡΡΡΡΠΊΡΡΡΡ ΠΈΠ»ΠΈ ΡΡΡΠ»ΠΊΠΈ Π½Π° ΠΎΠ±ΡΠ΅ΠΊΡΡ Π±Π°Π·Ρ Π΄Π°Π½Π½ΡΡ
.
- π ΠΠ΅ΡΠΎΠ΄
ΠΠ°ΠΉΡΠΈΠΈΠ΄Π΅Π°Π»ΡΠ½ΠΎ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΠΈΡ Π΄Π»Ρ ΠΏΠΎΠΈΡΠΊΠ° ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΡΡ ΡΠΊΠ·Π΅ΠΌΠΏΠ»ΡΡΠΎΠ² ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ². - β‘ ΠΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΡ
ΠΠ°ΠΉΡΠΈΡΠΎΠΏΠΎΡΡΠ°Π²ΠΈΠΌΠ° ΡΠΠΎΠΈΡΠΊΠ½Π° Π»ΠΈΠ½Π΅ΠΉΠ½ΡΡ ΠΌΠ°ΡΡΠΈΠ²Π°Ρ . - π ΠΡΠΈ ΡΠ°Π±ΠΎΡΠ΅ Ρ Π±ΠΎΠ»ΡΡΠΈΠΌΠΈ ΠΎΠ±ΡΠ΅ΠΌΠ°ΠΌΠΈ Π΄Π°Π½Π½ΡΡ ΠΎΠ±Π° ΠΌΠ΅ΡΠΎΠ΄Π° ΡΡΠ΅Π±ΡΡΡ ΠΏΠΎΠ»Π½ΠΎΠ³ΠΎ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠ°.
ΠΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ ΡΡΠΈΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΠΈΠ·Π±Π΅ΠΆΠ°ΡΡ Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΡ Π³ΡΠΎΠΌΠΎΠ·Π΄ΠΊΠΈΡ ΡΠΈΠΊΠ»ΠΎΠ² Π΄Π»Ρ ΠΏΡΠΎΡΡΡΡ Π·Π°Π΄Π°Ρ. ΠΠ΄Π½Π°ΠΊΠΎ, Π΅ΡΠ»ΠΈ ΡΡΠ΅Π±ΡΠ΅ΡΡΡ Π½Π°ΠΉΡΠΈ Π²ΡΠ΅ Π²Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, ΠΏΡΠΈΠ΄Π΅ΡΡΡ ΠΊΠΎΠΌΠ±ΠΈΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΡΡΠΈ ΠΌΠ΅ΡΠΎΠ΄Ρ Ρ ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠΌ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠΎΠΌ, ΡΠ΄Π²ΠΈΠ³Π°Ρ Π½Π°ΡΠ°Π»ΡΠ½ΡΡ ΠΏΠΎΠ·ΠΈΡΠΈΡ ΠΏΠΎΠΈΡΠΊΠ°.
Π ΡΡΠ½ΠΎΠΉ ΠΏΠ΅ΡΠ΅Π±ΠΎΡ ΡΠ΅ΡΠ΅Π· ΡΠΈΠΊΠ» ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ
Π ΡΠΈΡΡΠ°ΡΠΈΡΡ
, ΠΊΠΎΠ³Π΄Π° ΡΡΠ°Π½Π΄Π°ΡΡΠ½ΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΏΠΎΠΈΡΠΊΠ° Π½Π΅ ΠΏΠΎΠ΄Ρ
ΠΎΠ΄ΡΡ (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΡΡΠ΅Π±ΡΠ΅ΡΡΡ Π½Π°ΠΉΡΠΈ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΏΠΎ ΡΠ°ΡΡΠΈΡΠ½ΠΎΠΌΡ ΡΠΎΠ²ΠΏΠ°Π΄Π΅Π½ΠΈΡ ΠΈΠ»ΠΈ ΡΠ»ΠΎΠΆΠ½ΠΎΠΌΡ ΡΡΠ»ΠΎΠ²ΠΈΡ), ΡΠ°Π·ΡΠ°Π±ΠΎΡΡΠΈΠΊΠΈ ΠΏΡΠΈΠ±Π΅Π³Π°ΡΡ ΠΊ ΡΡΡΠ½ΠΎΠΌΡ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΡ. Π¦ΠΈΠΊΠ» ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ examining ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΠ²Π°.
Π§ΡΠΎΠ±Ρ ΠΏΠΎΠ»ΡΡΠΈΡΡ ΠΈΠ½Π΄Π΅ΠΊΡ ΠΏΡΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ ΡΡΠΎΠ³ΠΎ ΡΠΈΠΊΠ»Π°, Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΠ±ΡΡΠ²ΠΈΡΡ ΠΎΡΠ΄Π΅Π»ΡΠ½ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ-ΡΡΠ΅ΡΡΠΈΠΊ ΠΏΠ΅ΡΠ΅Π΄ Π½Π°ΡΠ°Π»ΠΎΠΌ ΡΠΈΠΊΠ»Π° ΠΈ ΡΠ²Π΅Π»ΠΈΡΠΈΠ²Π°ΡΡ Π΅Ρ Π½Π° Π΅Π΄ΠΈΠ½ΠΈΡΡ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ. ΠΡΠΎ ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΠ°ΡΡΠ΅ΡΠ½ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ, ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠΈΠ²Π°ΡΡΠΈΠΉ ΠΏΠΎΠ»Π½ΡΠΉ ΠΊΠΎΠ½ΡΡΠΎΠ»Ρ Π½Π°Π΄ ΠΏΡΠΎΡΠ΅ΡΡΠΎΠΌ.
ΠΠ½Π΄Π΅ΠΊΡ = 0;
ΠΠ°ΠΉΠ΄Π΅Π½Π½ΡΠΉΠΠ½Π΄Π΅ΠΊΡ = -1;
ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΠ»Π΅ΠΌΠ΅Π½Ρ ΠΠ· ΠΠ°ΡΡΠΈΠ² Π¦ΠΈΠΊΠ»
ΠΡΠ»ΠΈ ΠΠ»Π΅ΠΌΠ΅Π½Ρ.Π¦Π΅Π½Π° > 1000 Π’ΠΎΠ³Π΄Π°
ΠΠ°ΠΉΠ΄Π΅Π½Π½ΡΠΉΠΠ½Π΄Π΅ΠΊΡ = ΠΠ½Π΄Π΅ΠΊΡ;
ΠΡΠ΅ΡΠ²Π°ΡΡ;
ΠΠΎΠ½Π΅ΡΠΡΠ»ΠΈ;
ΠΠ½Π΄Π΅ΠΊΡ = ΠΠ½Π΄Π΅ΠΊΡ + 1;
ΠΠΎΠ½Π΅ΡΠ¦ΠΈΠΊΠ»Π°;
Π’Π°ΠΊΠΎΠΉ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ Π΄Π°Π΅Ρ Π³ΠΈΠ±ΠΊΠΎΡΡΡ: Π²Ρ ΠΌΠΎΠΆΠ΅ΡΠ΅ ΠΈΡΠΊΠ°ΡΡ Π½Π΅ ΡΠΎΡΠ½ΠΎΠ΅ ΡΠΎΠ²ΠΏΠ°Π΄Π΅Π½ΠΈΠ΅, Π° ΡΠ»Π΅ΠΌΠ΅Π½Ρ, ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΡΡΡΠΈΠΉ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΌ ΠΊΡΠΈΡΠ΅ΡΠΈΡΠΌ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΠΉ ΠΏΠΎΠ΄ΡΡΡΠΎΠΊΡ ΠΈΠ»ΠΈ ΠΈΠΌΠ΅ΡΡΠΈΠΉ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ΅ ΡΠ²ΠΎΠΉΡΡΠ²ΠΎ ΠΎΠ±ΡΠ΅ΠΊΡΠ°.
β οΈ ΠΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠΡΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ ΡΡΡΠ½ΠΎΠ³ΠΎ ΡΠΈΠΊΠ»Π° Π½Π΅ Π·Π°Π±ΡΠ²Π°ΠΉΡΠ΅ ΠΈΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·ΠΈΡΠΎΠ²Π°ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΠΈΠ½Π΄Π΅ΠΊΡΠ° Π½ΡΠ»Π΅ΠΌ. ΠΡΠΈΠ±ΠΊΠ° ΠΈΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΏΡΠΈΠ²Π΅Π΄Π΅Ρ ΠΊ ΡΠΌΠ΅ΡΠ΅Π½ΠΈΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ° Π½Π° Π΅Π΄ΠΈΠ½ΠΈΡΡ.
Π¦ΠΈΠΊΠ» ΠΠΎ ΠΠ½Π΄Π΅ΠΊΡΡ Π΄Π»Ρ ΡΠΎΡΠ½ΠΎΠ³ΠΎ ΠΊΠΎΠ½ΡΡΠΎΠ»Ρ
ΠΡΠ΅ ΠΎΠ΄ΠΈΠ½ ΠΌΠΎΡΠ½ΡΠΉ ΠΈΠ½ΡΡΡΡΠΌΠ΅Π½Ρ β ΡΠΈΠΊΠ» ΠΠΎ ΠΠ½Π΄Π΅ΠΊΡΡ. ΠΠ½ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΠΈΡΠ΅ΡΠΈΡΠΎΠ²Π°ΡΡΡΡ ΠΏΠΎ ΠΌΠ°ΡΡΠΈΠ²Ρ, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ Π½Π΅ΠΏΠΎΡΡΠ΅Π΄ΡΡΠ²Π΅Π½Π½ΠΎ ΡΠΈΡΠ»ΠΎΠ²ΡΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΈΠ½Π΄Π΅ΠΊΡΠΎΠ². ΠΡΠΎ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Π΅ΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΠΉ ΡΠΏΠΎΡΠΎΠ± ΡΠ°Π±ΠΎΡΡ Ρ ΠΈΠ½Π΄Π΅ΠΊΡΠ°ΡΠΈΠ΅ΠΉ, ΡΠ°ΠΊ ΠΊΠ°ΠΊ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ ΡΠΈΠΊΠ»Π° ΡΡΠ°Π·Ρ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ Π½ΡΠΆΠ½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅.
Π‘ΠΈΠ½ΡΠ°ΠΊΡΠΈΡ ΡΠΈΠΊΠ»Π° Π²ΡΠ³Π»ΡΠ΄ΠΈΡ ΡΠ°ΠΊ: ΠΠ»Ρ ΠΠ½Π΄Π΅ΠΊΡ = 0 ΠΠΎ ΠΠ°ΡΡΠΈΠ².ΠΠΡΠ°Π½ΠΈΡΠ°() Π¦ΠΈΠΊΠ». ΠΠ½ΡΡΡΠΈ ΡΠ°ΠΊΠΎΠ³ΠΎ ΡΠΈΠΊΠ»Π° ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ ΠΠ½Π΄Π΅ΠΊΡ Π°Π²ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈ ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΎΡ 0 Π΄ΠΎ ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅Π³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°. ΠΡΠΎ ΠΈΡΠΊΠ»ΡΡΠ°Π΅Ρ Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎΡΡΡ Π² ΡΡΡΠ½ΡΡ
ΡΡΠ΅ΡΡΠΈΠΊΠ°Ρ
.
ΠΠ°Π½Π½ΡΠΉ ΠΌΠ΅ΡΠΎΠ΄ ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎ ΠΏΠΎΠ»Π΅Π·Π΅Π½, ΠΊΠΎΠ³Π΄Π° Π½ΡΠΆΠ½ΠΎ Π½Π΅ ΡΠΎΠ»ΡΠΊΠΎ Π½Π°ΠΉΡΠΈ ΡΠ»Π΅ΠΌΠ΅Π½Ρ, Π½ΠΎ ΠΈ.modifyΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΠ² Π² ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΠΏΠΎΠΈΡΠΊΠ° (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΡΠ΄Π°Π»ΠΈΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ). ΠΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΡ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΈ Π²ΠΎ Π²ΡΠ΅ΠΌΡ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠ° ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ°ΡΡΠΎ ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΠΎΡΠΈΠ±ΠΊΠ°ΠΌ, ΡΠΎΠ³Π΄Π° ΠΊΠ°ΠΊ ΡΠΈΠΊΠ» ΠΏΠΎ ΠΈΠ½Π΄Π΅ΠΊΡΡ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎ ΡΠΏΡΠ°Π²Π»ΡΡΡ ΠΏΠΎΠ·ΠΈΡΠΈΡΠΌΠΈ.
| ΠΠ΅ΡΠΎΠ΄ | ΠΠΎΠ·Π²ΡΠ°ΡΠ°Π΅ΠΌΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ | Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡ | ΠΠΈΠ±ΠΊΠΎΡΡΡ ΡΡΠ»ΠΎΠ²ΠΈΡ |
|---|---|---|---|
| ΠΠΎΠΈΡΠΊ | ΠΠ½Π΄Π΅ΠΊΡ ΠΈΠ»ΠΈ -1 | O(N) | Π’ΠΎΡΠ½ΠΎΠ΅ ΡΠΎΠ²ΠΏΠ°Π΄Π΅Π½ΠΈΠ΅ |
| ΠΠ°ΠΉΡΠΈ | ΠΠ½Π΄Π΅ΠΊΡ ΠΈΠ»ΠΈ -1 | O(N) | Π’ΠΎΡΠ½ΠΎΠ΅ ΡΠΎΠ²ΠΏΠ°Π΄Π΅Π½ΠΈΠ΅ |
| Π¦ΠΈΠΊΠ» ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ | Π’ΡΠ΅Π±ΡΠ΅ΡΡΡ ΡΡΠ΅ΡΡΠΈΠΊ | O(N) | ΠΡΠ±ΠΎΠ΅ ΡΡΠ»ΠΎΠ²ΠΈΠ΅ |
| Π¦ΠΈΠΊΠ» ΠΠΎ ΠΠ½Π΄Π΅ΠΊΡΡ | ΠΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ ΡΠΈΠΊΠ»Π° | O(N) | ΠΡΠ±ΠΎΠ΅ ΡΡΠ»ΠΎΠ²ΠΈΠ΅ |
Π¦ΠΈΠΊΠ» ΠΠΎ ΠΠ½Π΄Π΅ΠΊΡΡ ΡΠ²Π»ΡΠ΅ΡΡΡ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΡΠΌ Π²Π°ΡΠΈΠ°Π½ΡΠΎΠΌ Π΄Π»Ρ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΈΠ· ΠΌΠ°ΡΡΠΈΠ²Π° Π²ΠΎ Π²ΡΠ΅ΠΌΡ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ.
ΠΡΠΎΠ±Π΅Π½Π½ΠΎΡΡΠΈ ΡΠ°Π±ΠΎΡΡ Ρ Π°ΡΡΠΎΡΠΈΠ°ΡΠΈΠ²Π½ΡΠΌΠΈ ΠΌΠ°ΡΡΠΈΠ²Π°ΠΌΠΈ
Π§Π°ΡΡΠΎ Π½Π°ΡΠΈΠ½Π°ΡΡΠΈΠ΅ ΡΠ°Π·ΡΠ°Π±ΠΎΡΡΠΈΠΊΠΈ ΠΏΡΡΠ°ΡΡ ΠΎΠ±ΡΡΠ½ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Ρ ΠΈ Π°ΡΡΠΎΡΠΈΠ°ΡΠΈΠ²Π½ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Ρ (ΡΡΡΡΠΊΡΡΡΡ ΠΈΠ»ΠΈ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΡ). Π Π°ΡΡΠΎΡΠΈΠ°ΡΠΈΠ²Π½ΡΡ ΠΌΠ°ΡΡΠΈΠ²Π°Ρ ΠΏΠΎΠ½ΡΡΠΈΠ΅ "ΠΈΠ½Π΄Π΅ΠΊΡ" Π·Π°ΠΌΠ΅Π½ΡΠ΅ΡΡΡ Π½Π° "ΠΊΠ»ΡΡ". ΠΠ»ΡΡΠΎΠΌ ΠΌΠΎΠΆΠ΅Ρ Π²ΡΡΡΡΠΏΠ°ΡΡ Π½Π΅ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΈΡΠ»ΠΎ, Π½ΠΎ ΠΈ ΡΡΡΠΎΠΊΠ°, Π΄Π°ΡΠ° ΠΈΠ»ΠΈ Π»ΡΠ±ΠΎΠΉ Π΄ΡΡΠ³ΠΎΠΉ ΡΠΈΠΏ.
ΠΡΠ»ΠΈ Π²Π°ΡΠ° Π·Π°Π΄Π°ΡΠ° β Π½Π°ΠΉΡΠΈ ΠΏΠΎΠ·ΠΈΡΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π² ΡΡΡΡΠΊΡΡΡΠ΅ ΠΏΠΎ Π΅Π³ΠΎ ΠΊΠ»ΡΡΡ, ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΠΎΠΈΡΠΊ Π½Π΅ ΡΡΠ°Π±ΠΎΡΠ°ΡΡ, ΡΠ°ΠΊ ΠΊΠ°ΠΊ ΠΎΠ½ΠΈ ΠΏΡΠ΅Π΄Π½Π°Π·Π½Π°ΡΠ΅Π½Ρ Π΄Π»Ρ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΡ
ΡΠΏΠΈΡΠΊΠΎΠ². ΠΠ»Ρ ΡΡΡΡΠΊΡΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ ΠΌΠ΅ΡΠΎΠ΄ ΠΠΎΠ»ΡΡΠΈΡΡ ΠΈΠ»ΠΈ ΠΏΡΠΎΠ²Π΅ΡΠΊΠ° ΡΠ΅ΡΠ΅Π· Π‘Π²ΠΎΠΉΡΡΠ²ΠΎ.
ΠΠ΄Π½Π°ΠΊΠΎ, Π΅ΡΠ»ΠΈ Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎ ΠΈΠΌΠ΅Π½Π½ΠΎ ΡΠΈΡΠ»ΠΎΠ²ΠΎΠ΅ ΡΠΌΠ΅ΡΠ΅Π½ΠΈΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π² ΡΡΡΡΠΊΡΡΡΠ΅ (ΡΡΠΎ ΡΡΠ΅Π±ΡΠ΅ΡΡΡ ΡΠ΅Π΄ΠΊΠΎ), ΠΏΡΠΈΠ΄Π΅ΡΡΡ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°ΡΡ ΠΊΠ»ΡΡΠΈ Π² ΠΌΠ°ΡΡΠΈΠ² ΡΠ΅ΡΠ΅Π· ΠΌΠ΅ΡΠΎΠ΄ ΠΠ»ΡΡΠΈ() ΠΈ ΡΠΆΠ΅ Π² ΡΡΠΎΠΌ ΠΌΠ°ΡΡΠΈΠ²Π΅ ΠΈΡΠΊΠ°ΡΡ ΠΈΠ½Π΄Π΅ΠΊΡ Π½ΡΠΆΠ½ΠΎΠ³ΠΎ ΠΊΠ»ΡΡΠ°. ΠΡΠΎ Π΄Π²ΡΡ
ΡΡΠ°ΠΏΠ½ΡΠΉ ΠΏΡΠΎΡΠ΅ΡΡ, ΠΊΠΎΡΠΎΡΡΠΉ ΡΠ»Π΅Π΄ΡΠ΅Ρ ΡΡΠΈΡΡΠ²Π°ΡΡ ΠΏΡΠΈ ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ Π°ΡΡ
ΠΈΡΠ΅ΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ
.
ΠΠ°ΠΊ ΠΏΠΎΠ»ΡΡΠΈΡΡ ΠΈΠ½Π΄Π΅ΠΊΡ ΠΊΠ»ΡΡΠ° Π² Π‘ΡΡΡΠΊΡΡΡΠ΅?
Π‘Π½Π°ΡΠ°Π»Π° ΠΏΠΎΠ»ΡΡΠΈΡΠ΅ ΠΌΠ°ΡΡΠΈΠ² ΠΊΠ»ΡΡΠ΅ΠΉ: ΠΠ»ΡΡΠΈ = Π‘ΡΡΡΠΊΡΡΡΠ°.ΠΠ»ΡΡΠΈ(). ΠΠ°ΡΠ΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠΉΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄ ΠΠΎΠΈΡΠΊ Π½Π° ΡΡΠΎΠΌ ΠΌΠ°ΡΡΠΈΠ²Π΅: ΠΠ½Π΄Π΅ΠΊΡ = ΠΠ»ΡΡΠΈ.ΠΠΎΠΈΡΠΊ(ΠΡΠΆΠ½ΡΠΉΠΠ»ΡΡ).
Π§Π°ΡΡΡΠ΅ ΠΎΡΠΈΠ±ΠΊΠΈ ΠΈ ΠΎΠΏΡΠΈΠΌΠΈΠ·Π°ΡΠΈΡ ΠΏΠΎΠΈΡΠΊΠ°
ΠΠ΄Π½ΠΎΠΉ ΠΈΠ· ΡΠ°ΠΌΡΡ
ΡΠ°ΡΠΏΡΠΎΡΡΡΠ°Π½Π΅Π½Π½ΡΡ
ΠΎΡΠΈΠ±ΠΎΠΊ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΈΠ³Π½ΠΎΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅ΠΌΠΎΠ³ΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ -1. ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΡΡ ΡΠ°ΡΡΠΎ ΡΡΠ°Π·Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡ Π½Π°ΠΉΠ΄Π΅Π½Π½ΡΠΉ ΠΈΠ½Π΄Π΅ΠΊΡ Π΄Π»Ρ Π΄ΠΎΡΡΡΠΏΠ° ΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, Π½Π΅ ΠΏΡΠΎΠ²Π΅ΡΠΈΠ² ΡΡΠΏΠ΅ΡΠ½ΠΎΡΡΡ ΠΏΠΎΠΈΡΠΊΠ°. ΠΡΠΎ Π³Π°ΡΠ°Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎ ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΠΏΠ°Π΄Π΅Π½ΠΈΡ ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ.
ΠΡΠ΅Π³Π΄Π° ΠΏΡΠΎΠ²Π΅ΡΡΠΉΡΠ΅ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ ΠΏΠ΅ΡΠ΅Π΄ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ:
ΠΠ½Π΄Π΅ΠΊΡ = ΠΠ°ΡΡΠΈΠ².ΠΠΎΠΈΡΠΊ(ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅);
ΠΡΠ»ΠΈ ΠΠ½Π΄Π΅ΠΊΡ <> -1 Π’ΠΎΠ³Π΄Π°
ΠΠ»Π΅ΠΌΠ΅Π½Ρ = ΠΠ°ΡΡΠΈΠ²[ΠΠ½Π΄Π΅ΠΊΡ];
// ΠΠ°Π»ΡΠ½Π΅ΠΉΡΠ°Ρ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠ°
ΠΠΎΠ½Π΅ΡΠΡΠ»ΠΈ;
Π’Π°ΠΊΠΆΠ΅ ΡΡΠΎΠΈΡ ΡΠΏΠΎΠΌΡΠ½ΡΡΡ ΠΎ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ. ΠΠΈΠ½Π΅ΠΉΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ (O(N)) ΡΡΠ°Π½ΠΎΠ²ΠΈΡΡΡ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΡΠΌ Π½Π° ΠΎΡΠ΅Π½Ρ Π±ΠΎΠ»ΡΡΠΈΡ ΠΌΠ°ΡΡΠΈΠ²Π°Ρ (Π΄Π΅ΡΡΡΠΊΠΈ ΡΡΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ²). ΠΡΠ»ΠΈ ΠΏΠΎΠΈΡΠΊ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΡΠ°ΡΡΠΎ, ΠΈΠΌΠ΅Π΅Ρ ΡΠΌΡΡΠ» ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΠ² ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π±ΠΈΠ½Π°ΡΠ½ΡΠΉ ΠΏΠΎΠΈΡΠΊ, Π»ΠΈΠ±ΠΎ ΠΏΠ΅ΡΠ΅ΡΠΌΠΎΡΡΠ΅ΡΡ ΡΡΡΡΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ , ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ Π‘ΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅ Π΄Π»Ρ ΠΌΠ³Π½ΠΎΠ²Π΅Π½Π½ΠΎΠ³ΠΎ Π΄ΠΎΡΡΡΠΏΠ° ΠΏΠΎ ΠΊΠ»ΡΡΡ.
β οΈ ΠΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠΠ½ΡΠ΅ΡΡΠ΅ΠΉΡ ΠΈ ΠΌΠ΅ΡΠΎΠ΄Ρ ΡΠ°Π±ΠΎΡΡ Ρ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΡΠΌΠΈ ΠΌΠΎΠ³ΡΡ Π½Π΅Π·Π½Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΠΎΡΠ»ΠΈΡΠ°ΡΡΡΡ Π² ΡΠ°Π·Π½ΡΡ Π²Π΅ΡΡΠΈΡΡ ΠΏΠ»Π°ΡΡΠΎΡΠΌΡ 1Π‘. ΠΡΠ΅Π³Π΄Π° ΡΠ²Π΅ΡΡΠΉΡΠ΅ΡΡ Ρ ΡΠΈΠ½ΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈΠΌ ΠΏΠΎΠΌΠΎΡΠ½ΠΈΠΊΠΎΠΌ Π²Π°ΡΠ΅ΠΉ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΠΎΠΉ Π²Π΅ΡΡΠΈΠΈ ΠΊΠΎΠ½ΡΠΈΠ³ΡΡΠ°ΡΠΈΠΈ.
βοΈ ΠΠΎΠ½ΡΡΠΎΠ»Ρ ΠΏΠ΅ΡΠ΅Π΄ ΠΏΠΎΠΈΡΠΊΠΎΠΌ ΠΈΠ½Π΄Π΅ΠΊΡΠ°
ΠΠΎΠΏΡΠΎΡΡ ΠΈ ΠΎΡΠ²Π΅ΡΡ (FAQ)
Π§ΡΠΎ Π²Π΅ΡΠ½Π΅Ρ ΠΌΠ΅ΡΠΎΠ΄ ΠΠΎΠΈΡΠΊ, Π΅ΡΠ»ΠΈ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π²ΡΡΡΠ΅ΡΠ°Π΅ΡΡΡ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΡΠ°Π·?
ΠΠ΅ΡΠΎΠ΄ ΠΠΎΠΈΡΠΊ Π²ΡΠ΅Π³Π΄Π° Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ ΠΈΠ½Π΄Π΅ΠΊΡ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ Π½Π°ΠΉΠ΄Π΅Π½Π½ΠΎΠ³ΠΎ Π²Ρ
ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, Π½Π°ΡΠΈΠ½Π°Ρ ΡΠΊΠ°Π½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Ρ Π½Π°ΡΠ°Π»Π° ΠΌΠ°ΡΡΠΈΠ²Π° (ΠΈΠ½Π΄Π΅ΠΊΡ 0). ΠΠΎΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ Π΄ΡΠ±Π»ΠΈΠΊΠ°ΡΡ ΠΈΠ³Π½ΠΎΡΠΈΡΡΡΡΡΡ.
ΠΠΎΠΆΠ½ΠΎ Π»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΠ΅ ΠΈΠ½Π΄Π΅ΠΊΡΡ Π΄Π»Ρ Π΄ΠΎΡΡΡΠΏΠ° ΠΊ ΠΊΠΎΠ½ΡΡ ΠΌΠ°ΡΡΠΈΠ²Π°, ΠΊΠ°ΠΊ Π² Python?
ΠΠ΅Ρ, Π² ΡΠ·ΡΠΊΠ΅ 1Π‘ ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½Π°Ρ ΠΈΠ½Π΄Π΅ΠΊΡΠ°ΡΠΈΡ Π½Π΅ ΠΏΠΎΠ΄Π΄Π΅ΡΠΆΠΈΠ²Π°Π΅ΡΡΡ. ΠΠ»Ρ Π΄ΠΎΡΡΡΠΏΠ° ΠΊ ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅ΠΌΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΌΠ΅ΡΠΎΠ΄ ΠΠ°ΡΡΠΈΠ².ΠΠΡΠ°Π½ΠΈΡΠ°() ΠΈΠ»ΠΈ Π²ΡΡΠΈΡΠ»ΡΡΡ ΠΈΠ½Π΄Π΅ΠΊΡ ΠΊΠ°ΠΊ ΠΠ°ΡΡΠΈΠ².ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ() - 1.
ΠΠ°ΠΊ Π½Π°ΠΉΡΠΈ ΠΈΠ½Π΄Π΅ΠΊΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, Π΅ΡΠ»ΠΈ ΠΈΠ·Π²Π΅ΡΡΠ½ΠΎ ΡΠΎΠ»ΡΠΊΠΎ ΡΠ°ΡΡΡ Π΅Π³ΠΎ ΡΡΡΠΎΠΊΠΎΠ²ΠΎΠ³ΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ?
ΠΡΡΡΠΎΠ΅Π½Π½ΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΠΎΠΈΡΠΊ ΠΈ ΠΠ°ΠΉΡΠΈ ΠΈΡΡΡ ΠΏΠΎΠ»Π½ΠΎΠ΅ ΡΠΎΠ²ΠΏΠ°Π΄Π΅Π½ΠΈΠ΅. ΠΠ»Ρ ΠΏΠΎΠΈΡΠΊΠ° ΠΏΠΎ ΡΠ°ΡΡΠΈ ΡΡΡΠΎΠΊΠΈ Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΠΈΠΊΠ» (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ) ΠΈ ΡΡΠ½ΠΊΡΠΈΡ Π‘ΡΡΠΠ°ΠΉΡΠΈ Π²Π½ΡΡΡΠΈ ΡΡΠ»ΠΎΠ²ΠΈΡ ΡΠΈΠΊΠ»Π° Π΄Π»Ρ ΠΏΡΠΎΠ²Π΅ΡΠΊΠΈ Π²Ρ
ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΠΏΠΎΠ΄ΡΡΡΠΎΠΊΠΈ.
Π ΡΠ΅ΠΌ ΡΠ°Π·Π½ΠΈΡΠ° ΠΌΠ΅ΠΆΠ΄Ρ ΠΈΠ½Π΄Π΅ΠΊΡΠΎΠΌ ΠΌΠ°ΡΡΠΈΠ²Π° ΠΈ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ ΡΡΡΠΎΠΊΠΈ Π² Π’Π°Π±Π»ΠΈΡΠ½ΠΎΠΌ ΠΠΎΠΊΡΠΌΠ΅Π½ΡΠ΅?
ΠΠ½Π΄Π΅ΠΊΡ ΠΌΠ°ΡΡΠΈΠ²Π° Π½Π°ΡΠΈΠ½Π°Π΅ΡΡΡ Ρ 0, Π° Π½ΠΎΠΌΠ΅Ρ ΡΡΡΠΎΠΊΠΈ Π² ΡΠ°Π±Π»ΠΈΡΠ½ΠΎΠΌ Π΄ΠΎΠΊΡΠΌΠ΅Π½ΡΠ΅ 1Π‘ ΠΎΠ±ΡΡΠ½ΠΎ Π½Π°ΡΠΈΠ½Π°Π΅ΡΡΡ Ρ 1. ΠΡΠΎ Π²Π°ΠΆΠ½ΠΎΠ΅ ΡΠ°Π·Π»ΠΈΡΠΈΠ΅, ΠΎ ΠΊΠΎΡΠΎΡΠΎΠΌ Π½ΡΠΆΠ½ΠΎ ΠΏΠΎΠΌΠ½ΠΈΡΡ ΠΏΡΠΈ ΠΏΠ΅ΡΠ΅Π½ΠΎΡΠ΅ Π΄Π°Π½Π½ΡΡ ΠΈΠ· ΠΌΠ°ΡΡΠΈΠ²Π° Π² ΡΠ°Π±Π»ΠΈΡΡ ΠΈ ΠΎΠ±ΡΠ°ΡΠ½ΠΎ, ΡΡΠΎΠ±Ρ Π½Π΅ ΡΠΌΠ΅ΡΡΠΈΡΡ Π΄Π°Π½Π½ΡΠ΅ Π½Π° ΠΎΠ΄Π½Ρ ΡΡΡΠΎΠΊΡ.