Π Π°Π±ΠΎΡΠ° Ρ ΠΌΠ°ΡΡΠΈΠ²Π°ΠΌΠΈ Π² 1Π‘:ΠΡΠ΅Π΄ΠΏΡΠΈΡΡΠΈΠ΅ β ΠΎΠ΄Π½Π° ΠΈΠ· ΡΠ°ΠΌΡΡ
Π²ΠΎΡΡΡΠ΅Π±ΠΎΠ²Π°Π½Π½ΡΡ
Π·Π°Π΄Π°Ρ ΠΏΡΠΈ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠ΅ Π±ΠΈΠ·Π½Π΅Ρ-Π»ΠΎΠ³ΠΈΠΊΠΈ. Π§Π°ΡΡΠΎ ΡΡΠ΅Π±ΡΠ΅ΡΡΡ Π½Π΅ ΠΏΡΠΎΡΡΠΎ Π΄ΠΎΠ±Π°Π²ΠΈΡΡ ΠΈΠ»ΠΈ ΡΠ΄Π°Π»ΠΈΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ, Π° ΠΏΠΎΠΌΠ΅Π½ΡΡΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ Π΄Π²Π° ΠΈΠ»ΠΈ Π±ΠΎΠ»Π΅Π΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ β Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΏΡΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ΅, ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠ΅ ΠΊΠΎΠ»ΠΎΠ½ΠΎΠΊ Π² ΠΎΡΡΠ΅ΡΠ°Ρ
ΠΈΠ»ΠΈ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠΌ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΈ ΠΏΠΎΡΡΠ΄ΠΊΠ° ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ Π΄Π°Π½Π½ΡΡ
. ΠΠ° ΠΏΠ΅ΡΠ²ΡΠΉ Π²Π·Π³Π»ΡΠ΄ Π·Π°Π΄Π°ΡΠ° ΠΊΠ°ΠΆΠ΅ΡΡΡ ΡΡΠΈΠ²ΠΈΠ°Π»ΡΠ½ΠΎΠΉ, Π½ΠΎ Π² 1Π‘ Π΅ΡΡΡ Π½ΡΠ°Π½ΡΡ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠ³ΡΡ ΠΏΡΠΈΠ²Π΅ΡΡΠΈ ΠΊ ΠΎΡΠΈΠ±ΠΊΠ°ΠΌ ΠΏΡΠΈ ΡΠ°Π±ΠΎΡΠ΅ Ρ ΠΠ°ΡΡΠΈΠ²ΠΎΠΌ, Π‘ΠΏΠΈΡΠΊΠΎΠΌΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ ΠΈΠ»ΠΈ Π΄Π°ΠΆΠ΅ Π’Π°Π±Π»ΠΈΡΠ΅ΠΉΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ.
Π ΡΡΠΎΠΉ ΡΡΠ°ΡΡΠ΅ ΠΌΡ ΡΠ°Π·Π±Π΅ΡΠ΅ΠΌ 5 ΠΏΡΠΎΠ²Π΅ΡΠ΅Π½Π½ΡΡ
ΡΠΏΠΎΡΠΎΠ±ΠΎΠ² ΠΎΠ±ΠΌΠ΅Π½Π° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ β ΠΎΡ ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ swap Ρ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π΄ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ Π²ΡΡΡΠΎΠ΅Π½Π½ΡΡ
ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΠΏΠ»Π°ΡΡΠΎΡΠΌΡ ΠΈ ΠΎΠΏΡΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°Π½Π½ΡΡ
Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Π΄Π»Ρ Π±ΠΎΠ»ΡΡΠΈΡ
Π½Π°Π±ΠΎΡΠΎΠ² Π΄Π°Π½Π½ΡΡ
. ΠΡΠΎΠ±ΠΎΠ΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ ΡΠ΄Π΅Π»ΠΈΠΌ ΡΠΈΠΏΠΈΡΠ½ΡΠΌ ΠΎΡΠΈΠ±ΠΊΠ°ΠΌ ΠΏΡΠΈ ΡΠ°Π±ΠΎΡΠ΅ Ρ ΠΈΠ½Π΄Π΅ΠΊΡΠ°ΠΌΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ Π²Π΅Π΄ΡΡ ΠΊ ΠΏΠΎΡΠ΅ΡΠ΅ Π΄Π°Π½Π½ΡΡ
ΠΈΠ»ΠΈ ΠΈΡΠΊΠ»ΡΡΠ΅Π½ΠΈΡΠΌ Π²ΠΎ Π²ΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ. ΠΡ ΡΠ°ΠΊΠΆΠ΅ ΡΠ·Π½Π°Π΅ΡΠ΅, ΠΊΠ°ΠΊ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎ ΠΎΡΠ³Π°Π½ΠΈΠ·ΠΎΠ²ΡΠ²Π°ΡΡ ΠΎΠ±ΠΌΠ΅Π½ Π² ΡΠΈΠΊΠ»Π°Ρ
ΠΈ ΠΏΠΎΡΠ΅ΠΌΡ ΠΈΠ½ΠΎΠ³Π΄Π° ΠΏΡΠΎΡΠ΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π‘ΡΡΡΠΊΡΡΡΡ Π²ΠΌΠ΅ΡΡΠΎ ΠΌΠ°ΡΡΠΈΠ²Π°.
1. ΠΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΎΠ±ΠΌΠ΅Π½ Ρ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ (swap)
Π‘Π°ΠΌΡΠΉ ΡΠ½ΠΈΠ²Π΅ΡΡΠ°Π»ΡΠ½ΡΠΉ ΠΈ ΠΏΠΎΠ½ΡΡΠ½ΡΠΉ ΠΌΠ΅ΡΠΎΠ΄ β ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ. ΠΠ½ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π²ΠΎ Π²ΡΠ΅Ρ Π²Π΅ΡΡΠΈΡΡ 1Π‘:ΠΡΠ΅Π΄ΠΏΡΠΈΡΡΠΈΠ΅ 8.x ΠΈ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΠΈΡ Π΄Π»Ρ Π»ΡΠ±ΡΡ ΡΠΈΠΏΠΎΠ² Π΄Π°Π½Π½ΡΡ : ΡΠΈΡΠ΅Π», ΡΡΡΠΎΠΊ, ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΈΠ»ΠΈ Π΄Π°ΠΆΠ΅ Π΄ΡΡΠ³ΠΈΡ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ². ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· ΡΡΠ΅Ρ ΡΠ°Π³ΠΎΠ²:
- Π‘ΠΎΡ ΡΠ°Π½ΠΈΡΡ ΠΏΠ΅ΡΠ²ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π²ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ.
- ΠΡΠΈΡΠ²ΠΎΠΈΡΡ ΠΏΠ΅ΡΠ²ΠΎΠΌΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Π²ΡΠΎΡΠΎΠ³ΠΎ.
- ΠΡΠΈΡΠ²ΠΎΠΈΡΡ Π²ΡΠΎΡΠΎΠΌΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΡΠΎΡ ΡΠ°Π½Π΅Π½Π½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΈΠ· Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ.
ΠΡΠΈΠΌΠ΅Ρ ΠΊΠΎΠ΄Π° Π΄Π»Ρ ΠΌΠ°ΡΡΠΈΠ²Π° Ρ ΡΠΈΡΠ»ΠΎΠ²ΡΠΌΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌΠΈ:
ΠΠ°ΡΡΠΈΠ² = ΠΠΎΠ²ΡΠΉ ΠΠ°ΡΡΠΈΠ²();
ΠΠ°ΡΡΠΈΠ².ΠΠΎΠ±Π°Π²ΠΈΡΡ(10);
ΠΠ°ΡΡΠΈΠ².ΠΠΎΠ±Π°Π²ΠΈΡΡ(20);
// ΠΠ±ΠΌΠ΅Π½ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Ρ ΠΈΠ½Π΄Π΅ΠΊΡΠ°ΠΌΠΈ 0 ΠΈ 1
ΠΡΠ΅ΠΌΠ΅Π½Π½Π°ΡΠΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ = ΠΠ°ΡΡΠΈΠ²[0];
ΠΠ°ΡΡΠΈΠ²[0] = ΠΠ°ΡΡΠΈΠ²[1];
ΠΠ°ΡΡΠΈΠ²[1] = ΠΡΠ΅ΠΌΠ΅Π½Π½Π°ΡΠΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ;
βοΈ ΠΡΠΎΠ²Π΅ΡΠΊΠ° ΠΏΠ΅ΡΠ΅Π΄ ΠΎΠ±ΠΌΠ΅Π½ΠΎΠΌ
β οΈ ΠΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠΡΠ»ΠΈ Π²Ρ ΡΠ°Π±ΠΎΡΠ°Π΅ΡΠ΅ Ρ Π‘ΠΏΠΈΡΠΊΠΎΠΌΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ, ΠΏΠΎΠΌΠ½ΠΈΡΠ΅, ΡΡΠΎ ΠΈΠ½Π΄Π΅ΠΊΡΠ°ΡΠΈΡ Π½Π°ΡΠΈΠ½Π°Π΅ΡΡΡ Ρ 0, Π½ΠΎ ΠΌΠ΅ΡΠΎΠ΄ ΠΠΎΠ»ΡΡΠΈΡΡ() ΠΌΠΎΠΆΠ΅Ρ Π²Π΅ΡΠ½ΡΡΡ ΠΠ΅ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΎ ΠΏΡΠΈ Π½Π΅Π²Π΅ΡΠ½ΠΎΠΌ ΠΈΠ½Π΄Π΅ΠΊΡΠ΅. ΠΡΠ΅Π³Π΄Π° ΠΏΡΠΎΠ²Π΅ΡΡΠΉΡΠ΅ Π³ΡΠ°Π½ΠΈΡΡ:
ΠΡΠ»ΠΈ ΠΠ½Π΄Π΅ΠΊΡ1 >= 0 Π ΠΠ½Π΄Π΅ΠΊΡ1 < ΠΠ°ΡΡΠΈΠ².ΠΠΡΠ°Π½ΠΈΡΠ°() Π ΠΠ½Π΄Π΅ΠΊΡ2 >= 0 Π ΠΠ½Π΄Π΅ΠΊΡ2 < ΠΠ°ΡΡΠΈΠ².ΠΠΡΠ°Π½ΠΈΡΠ°() Π’ΠΎΠ³Π΄Π°
// ΠΡΠΏΠΎΠ»Π½ΡΠ΅ΠΌ ΠΎΠ±ΠΌΠ΅Π½
ΠΠΎΠ½Π΅ΡΠΡΠ»ΠΈ;
2. ΠΠ±ΠΌΠ΅Π½ Π±Π΅Π· Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ (Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΈ ΠΏΠΎΠ±ΠΈΡΠΎΠ²ΡΠΉ)
Π Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΠ»ΡΡΠ°ΡΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠ±ΠΎΠΉΡΠΈΡΡ Π±Π΅Π· ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΠΈΠ»ΠΈ ΠΏΠΎΠ±ΠΈΡΠΎΠ²ΡΠΉ XOR. ΠΡΠΎΡ ΠΌΠ΅ΡΠΎΠ΄ ΡΠΊΠΎΠ½ΠΎΠΌΠΈΡ ΠΏΠ°ΠΌΡΡΡ, Π½ΠΎ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΠΈΡ ΡΠΎΠ»ΡΠΊΠΎ Π΄Π»Ρ ΡΠΈΡΠ΅Π» ΠΈ ΡΡΠ΅Π±ΡΠ΅Ρ ΠΎΡΡΠΎΡΠΎΠΆΠ½ΠΎΡΡΠΈ:
- π’ Π‘Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅/Π²ΡΡΠΈΡΠ°Π½ΠΈΠ΅:
a = a + b; b = a - b; a = a - b; - π Π£ΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅/Π΄Π΅Π»Π΅Π½ΠΈΠ΅:
a = a * b; b = a / b; a = a / b;(ΠΎΠΏΠ°ΡΠ½ΠΎ ΠΏΡΠΈ Π΄Π΅Π»Π΅Π½ΠΈΠΈ Π½Π° Π½ΠΎΠ»Ρ!) - β ΠΠΎΠ±ΠΈΡΠΎΠ²ΡΠΉ XOR:
a = a Xor b; b = a Xor b; a = a Xor b;(ΡΠΎΠ»ΡΠΊΠΎ Π΄Π»Ρ ΡΠ΅Π»ΡΡ ΡΠΈΡΠ΅Π»)
ΠΡΠΈΠΌΠ΅Ρ Ρ ΠΏΠΎΠ±ΠΈΡΠΎΠ²ΡΠΌ XOR:
Π§ΠΈΡΠ»ΠΎ1 = 5; // 0101 Π² Π΄Π²ΠΎΠΈΡΠ½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΠ΅
Π§ΠΈΡΠ»ΠΎ2 = 3; // 0011 Π² Π΄Π²ΠΎΠΈΡΠ½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΠ΅
Π§ΠΈΡΠ»ΠΎ1 = Π§ΠΈΡΠ»ΠΎ1 Xor Π§ΠΈΡΠ»ΠΎ2; // 0110 (6)
Π§ΠΈΡΠ»ΠΎ2 = Π§ΠΈΡΠ»ΠΎ1 Xor Π§ΠΈΡΠ»ΠΎ2; // 0101 (5)
Π§ΠΈΡΠ»ΠΎ1 = Π§ΠΈΡΠ»ΠΎ1 Xor Π§ΠΈΡΠ»ΠΎ2; // 0011 (3)
ΠΠ»Ρ ΠΎΠ±ΠΌΠ΅Π½Π° ΡΡΡΠΎΠΊ ΠΈΠ»ΠΈ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² Π»ΡΡΡΠ΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΌΠ΅ΡΠΎΠ΄ Ρ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ β Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ Π·Π΄Π΅ΡΡ Π½Π΅ ΠΏΡΠΈΠΌΠ΅Π½ΠΈΠΌΡ ΠΈ ΠΏΡΠΈΠ²Π΅Π΄ΡΡ ΠΊ ΠΎΡΠΈΠ±ΠΊΠ°ΠΌ.
β οΈ ΠΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠΡΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΡ
ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² Π΅ΡΡΡ ΡΠΈΡΠΊ ΠΏΠ΅ΡΠ΅ΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ
, Π΅ΡΠ»ΠΈ ΡΠΈΡΠ»Π° ΡΠ»ΠΈΡΠΊΠΎΠΌ Π±ΠΎΠ»ΡΡΠΈΠ΅. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΎΠ±ΠΌΠ΅Π½ 2147483647 (ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Π΄Π»Ρ 32-Π±ΠΈΡΠ½ΠΎΠ³ΠΎ ΡΠ΅Π»ΠΎΠ³ΠΎ) ΠΈ 1 ΠΏΡΠΈΠ²Π΅Π΄Π΅Ρ ΠΊ ΠΎΡΠΈΠ±ΠΊΠ΅.
3. ΠΠ±ΠΌΠ΅Π½ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π² Π’Π°Π±Π»ΠΈΡΠ΅ΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ
Π’Π°Π±Π»ΠΈΡΠ°ΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ Π² 1Π‘ β ΡΡΠΎ Π½Π΅ ΠΏΡΠΎΡΡΠΎ ΠΌΠ°ΡΡΠΈΠ², Π° ΠΏΠΎΠ»Π½ΠΎΡΠ΅Π½Π½Π°Ρ ΡΡΡΡΠΊΡΡΡΠ° Ρ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠ°ΠΌΠΈ ΠΈ ΡΡΡΠΎΠΊΠ°ΠΌΠΈ. ΠΠ»Ρ ΠΎΠ±ΠΌΠ΅Π½Π° ΡΡΡΠΎΠΊ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ Π½ΡΠΆΠ½ΠΎ ΡΡΠΈΡΡΠ²Π°ΡΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ Π½ΡΠ°Π½ΡΠΎΠ²:
- ΠΠΎΠ»ΡΡΠΈΡΡ ΡΡΡΠ»ΠΊΠΈ Π½Π° ΡΡΡΠΎΠΊΠΈ ΠΏΠΎ ΠΈΠ½Π΄Π΅ΠΊΡΠ°ΠΌ.
- ΠΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΌΠ΅ΡΠΎΠ΄
ΠΠ΅ΡΠ΅ΠΌΠ΅ΡΡΠΈΡΡ()ΠΈΠ»ΠΈ ΠΎΠ±ΠΌΠ΅Π½ΡΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΊΠΎΠ»ΠΎΠ½ΠΎΠΊ Π²ΡΡΡΠ½ΡΡ.
ΠΡΠΈΠΌΠ΅Ρ ΠΎΠ±ΠΌΠ΅Π½Π° Π΄Π²ΡΡ ΡΡΡΠΎΠΊ:
Π’Π°Π±Π»ΠΈΡΠ° = ΠΠΎΠ²ΡΠΉ Π’Π°Π±Π»ΠΈΡΠ°ΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ();
Π’Π°Π±Π»ΠΈΡΠ°.ΠΠΎΠ»ΠΎΠ½ΠΊΠΈ.ΠΠΎΠ±Π°Π²ΠΈΡΡ("ΠΠ°ΠΈΠΌΠ΅Π½ΠΎΠ²Π°Π½ΠΈΠ΅");
Π’Π°Π±Π»ΠΈΡΠ°.ΠΠΎΠ»ΠΎΠ½ΠΊΠΈ.ΠΠΎΠ±Π°Π²ΠΈΡΡ("ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ");
Π’Π°Π±Π»ΠΈΡΠ°.ΠΠΎΠ±Π°Π²ΠΈΡΡ();
Π’Π°Π±Π»ΠΈΡΠ°[0].ΠΠ°ΠΈΠΌΠ΅Π½ΠΎΠ²Π°Π½ΠΈΠ΅ = "Π’ΠΎΠ²Π°Ρ1";
Π’Π°Π±Π»ΠΈΡΠ°[0].ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ = 10;
Π’Π°Π±Π»ΠΈΡΠ°.ΠΠΎΠ±Π°Π²ΠΈΡΡ();
Π’Π°Π±Π»ΠΈΡΠ°[1].ΠΠ°ΠΈΠΌΠ΅Π½ΠΎΠ²Π°Π½ΠΈΠ΅ = "Π’ΠΎΠ²Π°Ρ2";
Π’Π°Π±Π»ΠΈΡΠ°[1].ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ = 20;
// ΠΠ±ΠΌΠ΅Π½ ΡΡΡΠΎΠΊ Ρ ΠΈΠ½Π΄Π΅ΠΊΡΠ°ΠΌΠΈ 0 ΠΈ 1
Π‘ΡΡΠΎΠΊΠ°1 = Π’Π°Π±Π»ΠΈΡΠ°[0];
Π‘ΡΡΠΎΠΊΠ°2 = Π’Π°Π±Π»ΠΈΡΠ°[1];
Π’Π°Π±Π»ΠΈΡΠ°[0].ΠΠ°ΠΈΠΌΠ΅Π½ΠΎΠ²Π°Π½ΠΈΠ΅ = Π‘ΡΡΠΎΠΊΠ°2.ΠΠ°ΠΈΠΌΠ΅Π½ΠΎΠ²Π°Π½ΠΈΠ΅;
Π’Π°Π±Π»ΠΈΡΠ°[0].ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ = Π‘ΡΡΠΎΠΊΠ°2.ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ;
Π’Π°Π±Π»ΠΈΡΠ°[1].ΠΠ°ΠΈΠΌΠ΅Π½ΠΎΠ²Π°Π½ΠΈΠ΅ = Π‘ΡΡΠΎΠΊΠ°1.ΠΠ°ΠΈΠΌΠ΅Π½ΠΎΠ²Π°Π½ΠΈΠ΅;
Π’Π°Π±Π»ΠΈΡΠ°[1].ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ = Π‘ΡΡΠΎΠΊΠ°1.ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ;
| ΠΠ΅ΡΠΎΠ΄ | ΠΡΠΈΠΌΠ΅Π½ΠΈΠΌΠΎΡΡΡ | ΠΠ»ΡΡΡ | ΠΠΈΠ½ΡΡΡ |
|---|---|---|---|
| ΠΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ swap | ΠΡΠ±ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Ρ ΠΈ ΡΠΈΠΏΡ Π΄Π°Π½Π½ΡΡ | ΠΡΠΎΡΡΠΎΡΠ°, Π½Π°Π΄Π΅ΠΆΠ½ΠΎΡΡΡ | Π’ΡΠ΅Π±ΡΠ΅Ρ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ |
| ΠΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΎΠ±ΠΌΠ΅Π½ | Π’ΠΎΠ»ΡΠΊΠΎ ΡΠΈΡΠ»Π° | ΠΠΊΠΎΠ½ΠΎΠΌΠΈΡ ΠΏΠ°ΠΌΡΡΡ | Π ΠΈΡΠΊ ΠΏΠ΅ΡΠ΅ΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ, Π½Π΅ΡΠΈΡΠ°Π΅ΠΌΡΠΉ ΠΊΠΎΠ΄ |
| ΠΠ±ΠΌΠ΅Π½ ΡΡΡΠΎΠΊ Π² Π’Π°Π±Π»ΠΈΡΠ΅ΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ | Π’Π°Π±Π»ΠΈΡΠ°ΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ |
Π‘ΠΎΡ ΡΠ°Π½ΡΠ΅Ρ ΡΡΡΡΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ | Π’ΡΠ΅Π±ΡΠ΅Ρ ΠΎΠ±ΠΌΠ΅Π½Π° ΠΏΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠ΅ |
4. ΠΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ Π²ΡΡΡΠΎΠ΅Π½Π½ΡΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΠΏΠ»Π°ΡΡΠΎΡΠΌΡ 1Π‘
ΠΠ°ΡΠΈΠ½Π°Ρ Ρ Π²Π΅ΡΡΠΈΠΈ 8.3.10, Π² 1Π‘:ΠΡΠ΅Π΄ΠΏΡΠΈΡΡΠΈΠ΅ ΠΏΠΎΡΠ²ΠΈΠ»ΠΈΡΡ ΡΠ΄ΠΎΠ±Π½ΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ Π΄Π»Ρ ΡΠ°Π±ΠΎΡΡ Ρ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΡΠΌΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠΆΠ½ΠΎ Π°Π΄Π°ΠΏΡΠΈΡΠΎΠ²Π°ΡΡ Π΄Π»Ρ ΠΎΠ±ΠΌΠ΅Π½Π° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ²:
- π
ΠΡΡΠ°Π²ΠΈΡΡ()+Π£Π΄Π°Π»ΠΈΡΡ(): ΠΡΡΠ°Π²ΠΈΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΏΠ΅ΡΠ΅Π΄ Π²ΡΠΎΡΡΠΌ, Π·Π°ΡΠ΅ΠΌ ΡΠ΄Π°Π»ΠΈΡΡ ΠΎΡΠΈΠ³ΠΈΠ½Π°Π»ΡΠ½ΡΠΉ. - π
ΠΠΎΠΌΠ΅Π½ΡΡΡΠΠ΅ΡΡΠ°ΠΌΠΈ(): Π Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΠΊΠΎΠ½ΡΠ΅ΠΊΡΡΠ°Ρ (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π²ΠΠ΅ΡΠ΅Π²ΠΎΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ) Π΅ΡΡΡ ΡΠΏΠ΅ΡΠΈΠ°Π»ΠΈΠ·ΠΈΡΠΎΠ²Π°Π½Π½ΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ. - π
Π‘ΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ()Ρ ΠΊΠ°ΡΡΠΎΠΌΠ½ΡΠΌ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ΠΌ: ΠΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π΄Π»Ρ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΏΠΎ Π·Π°Π΄Π°Π½Π½ΠΎΠΌΡ ΠΏΡΠ°Π²ΠΈΠ»Ρ.
ΠΡΠΈΠΌΠ΅Ρ Ρ ΠΡΡΠ°Π²ΠΈΡΡ() ΠΈ Π£Π΄Π°Π»ΠΈΡΡ():
ΠΠ°ΡΡΠΈΠ² = ΠΠΎΠ²ΡΠΉ ΠΠ°ΡΡΠΈΠ²();
ΠΠ°ΡΡΠΈΠ².ΠΠΎΠ±Π°Π²ΠΈΡΡ("Π");
ΠΠ°ΡΡΠΈΠ².ΠΠΎΠ±Π°Π²ΠΈΡΡ("Π");
ΠΠ°ΡΡΠΈΠ².ΠΠΎΠ±Π°Π²ΠΈΡΡ("Π");
// ΠΠ±ΠΌΠ΅Π½ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² 0 ΠΈ 2
ΠΠ»Π΅ΠΌΠ΅Π½Ρ0 = ΠΠ°ΡΡΠΈΠ²[0];
ΠΠ°ΡΡΠΈΠ².ΠΡΡΠ°Π²ΠΈΡΡ(2, ΠΠ»Π΅ΠΌΠ΅Π½Ρ0); // ΠΡΡΠ°Π²Π»ΡΠ΅ΠΌ ΠΏΠ΅ΡΠ΅Π΄ ΠΈΠ½Π΄Π΅ΠΊΡΠΎΠΌ 2
ΠΠ°ΡΡΠΈΠ².Π£Π΄Π°Π»ΠΈΡΡ(0); // Π£Π΄Π°Π»ΡΠ΅ΠΌ ΠΎΡΠΈΠ³ΠΈΠ½Π°Π»ΡΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ 0
ΠΠ°ΡΡΠΈΠ²[1] = ΠΠ°ΡΡΠΈΠ²[2]; // ΠΠΎΠΏΠΈΡΡΠ΅ΠΌ ΡΠ»Π΅ΠΌΠ΅Π½Ρ 2 Π½Π° ΠΌΠ΅ΡΡΠΎ 1
ΠΠ°ΡΡΠΈΠ².Π£Π΄Π°Π»ΠΈΡΡ(2); // Π£Π΄Π°Π»ΡΠ΅ΠΌ Π΄ΡΠ±Π»ΠΈΠΊΠ°Ρ
ΠΠΎΡΠ΅ΠΌΡ Π½Π΅ ΡΡΠΎΠΈΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π‘ΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ() Π΄Π»Ρ ΠΎΠ±ΠΌΠ΅Π½Π°?
ΠΠ΅ΡΠΎΠ΄ Π‘ΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ() ΠΈΠΌΠ΅Π΅Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ O(n log n), ΡΠΎΠ³Π΄Π° ΠΊΠ°ΠΊ ΠΏΡΡΠΌΠΎΠΉ ΠΎΠ±ΠΌΠ΅Π½ β O(1). ΠΠ»Ρ Π΄Π²ΡΡ
ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π½Π΅ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½Π° ΠΈ ΠΌΠΎΠΆΠ΅Ρ ΠΏΡΠΈΠ²Π΅ΡΡΠΈ ΠΊ Π½Π΅ΠΎΠΆΠΈΠ΄Π°Π½Π½ΡΠΌ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ°ΠΌ, Π΅ΡΠ»ΠΈ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Π΅ΡΡΡ Π΄ΡΠ±Π»ΠΈΠΊΠ°ΡΡ.
β οΈ ΠΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠΡΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ ΠΡΡΠ°Π²ΠΈΡΡ()/Π£Π΄Π°Π»ΠΈΡΡ() ΡΠ»Π΅Π΄ΠΈΡΠ΅ Π·Π° ΡΠΌΠ΅ΡΠ΅Π½ΠΈΠ΅ΠΌ ΠΈΠ½Π΄Π΅ΠΊΡΠΎΠ² ΠΏΠΎΡΠ»Π΅ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΏΠΎΡΠ»Π΅ Π²ΡΡΠ°Π²ΠΊΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π½Π° ΠΏΠΎΠ·ΠΈΡΠΈΡ 2, ΡΠ»Π΅ΠΌΠ΅Π½Ρ, ΠΊΠΎΡΠΎΡΡΠΉ Π±ΡΠ» Π½Π° ΡΡΠΎΠΉ ΠΏΠΎΠ·ΠΈΡΠΈΠΈ, ΡΠ΄Π²ΠΈΠ½Π΅ΡΡΡ Π½Π° 3.
5. ΠΠΏΡΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΠΎΠ±ΠΌΠ΅Π½ Π΄Π»Ρ Π±ΠΎΠ»ΡΡΠΈΡ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ²
ΠΡΠ»ΠΈ Π²Π°ΠΌ Π½ΡΠΆΠ½ΠΎ ΠΏΠΎΠΌΠ΅Π½ΡΡΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Ρ ΡΡΡΡΡΠ°ΠΌΠΈ ΠΈΠ»ΠΈ ΠΌΠΈΠ»Π»ΠΈΠΎΠ½Π°ΠΌΠΈ Π·Π°ΠΏΠΈΡΠ΅ΠΉ, ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΌΠΎΠ³ΡΡ ΡΠ°Π±ΠΎΡΠ°ΡΡ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ. Π ΡΠ°ΠΊΠΈΡ ΡΠ»ΡΡΠ°ΡΡ ΡΡΠΎΠΈΡ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅ΡΡ:
- π ΠΠ»ΠΎΡΠ½ΡΠΉ ΠΎΠ±ΠΌΠ΅Π½: Π Π°Π·Π±ΠΈΡΡ ΠΌΠ°ΡΡΠΈΠ² Π½Π° Π±Π»ΠΎΠΊΠΈ ΠΈ ΠΎΠ±ΠΌΠ΅Π½ΠΈΠ²Π°ΡΡ ΠΈΡ ΠΏΠ°ΡΠ°Π»Π»Π΅Π»ΡΠ½ΠΎ (Π΄Π»Ρ ΠΌΠ½ΠΎΠ³ΠΎΠΏΠΎΡΠΎΡΠ½ΡΡ Π·Π°Π΄Π°Ρ).
- π ΠΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ Π±ΡΡΠ΅ΡΠ°: Π‘ΠΎΠ·Π΄Π°ΡΡ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ.
- π ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π€ΠΈΡΠ΅ΡΠ°-ΠΠ΅ΡΡΠ°: ΠΠ»Ρ ΡΠ»ΡΡΠ°ΠΉΠ½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ (shuffle) ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ².
ΠΡΠΈΠΌΠ΅Ρ ΠΎΠΏΡΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ ΠΎΠ±ΠΌΠ΅Π½Π° Π΄Π»Ρ Π±ΠΎΠ»ΡΡΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π°:
ΠΡΠΎΡΠ΅Π΄ΡΡΠ° ΠΠΏΡΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉΠΠ±ΠΌΠ΅Π½(ΠΠ°ΡΡΠΈΠ², ΠΠ½Π΄Π΅ΠΊΡ1, ΠΠ½Π΄Π΅ΠΊΡ2)
ΠΡΠ»ΠΈ ΠΠ½Π΄Π΅ΠΊΡ1 = ΠΠ½Π΄Π΅ΠΊΡ2 Π’ΠΎΠ³Π΄Π°
ΠΠΎΠ·Π²ΡΠ°Ρ;
ΠΠΎΠ½Π΅ΡΠΡΠ»ΠΈ;
// ΠΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌ ΡΡΡΡΠΊΡΡΡΡ Π΄Π»Ρ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠ³ΠΎ Ρ
ΡΠ°Π½Π΅Π½ΠΈΡ
ΠΡΡΠ΅Ρ = ΠΠΎΠ²ΡΠΉ Π‘ΡΡΡΠΊΡΡΡΠ°("ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅1, ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅2");
ΠΡΡΠ΅Ρ.ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅1 = ΠΠ°ΡΡΠΈΠ²[ΠΠ½Π΄Π΅ΠΊΡ1];
ΠΡΡΠ΅Ρ.ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅2 = ΠΠ°ΡΡΠΈΠ²[ΠΠ½Π΄Π΅ΠΊΡ2];
ΠΠ°ΡΡΠΈΠ²[ΠΠ½Π΄Π΅ΠΊΡ1] = ΠΡΡΠ΅Ρ.ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅2;
ΠΠ°ΡΡΠΈΠ²[ΠΠ½Π΄Π΅ΠΊΡ2] = ΠΡΡΠ΅Ρ.ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅1;
ΠΠΎΠ½Π΅ΡΠΡΠΎΡΠ΅Π΄ΡΡΡ
ΠΠ»Ρ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ² ΡΠ°Π·ΠΌΠ΅ΡΠΎΠΌ Π±ΠΎΠ»Π΅Π΅ 10 000 ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ swap ΠΌΠΎΠΆΠ΅Ρ ΡΠ°Π±ΠΎΡΠ°ΡΡ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅ ΠΈΠ·-Π·Π° ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎΡΡΠ΅ΠΉ ΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ ΠΏΠ°ΠΌΡΡΡΡ Π² 1Π‘. Π ΡΠ°ΠΊΠΈΡ ΡΠ»ΡΡΠ°ΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠΉΡΠ΅ Π±ΡΡΠ΅ΡΠΈΠ·Π°ΡΠΈΡ ΠΈΠ»ΠΈ Π±Π»ΠΎΡΠ½ΡΡ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΡ.
β οΈ ΠΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅: Π 1Π‘:ΠΡΠ΅Π΄ΠΏΡΠΈΡΡΠΈΠ΅ Π½Π΅Ρ Π½Π°ΡΡΠΎΡΡΠ΅ΠΉ ΠΌΠ½ΠΎΠ³ΠΎΠΏΠΎΡΠΎΡΠ½ΠΎΡΡΠΈ, ΠΏΠΎΡΡΠΎΠΌΡ "ΠΏΠ°ΡΠ°Π»Π»Π΅Π»ΡΠ½ΡΠΉ" ΠΎΠ±ΠΌΠ΅Π½ Π±Π»ΠΎΠΊΠΎΠ² ΡΠ΅Π°Π»ΠΈΠ·ΡΠ΅ΡΡΡ ΡΠ΅ΡΠ΅Π· ΡΠ°Π·Π±ΠΈΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ Π½Π° Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΡΡΠ°Π½Π·Π°ΠΊΡΠΈΠΉ ΠΈΠ»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ Π€ΠΎΠ½ΠΎΠ²ΡΡ
ΠΠ°Π΄Π°Ρ (Π΄ΠΎΡΡΡΠΏΠ½ΠΎ Ρ Π²Π΅ΡΡΠΈΠΈ 8.3.14).
6. Π§Π°ΡΡΡΠ΅ ΠΎΡΠΈΠ±ΠΊΠΈ ΠΈ ΠΊΠ°ΠΊ ΠΈΡ ΠΈΠ·Π±Π΅ΠΆΠ°ΡΡ
ΠΠ°ΠΆΠ΅ ΠΎΠΏΡΡΠ½ΡΠ΅ ΡΠ°Π·ΡΠ°Π±ΠΎΡΡΠΈΠΊΠΈ 1Π‘ ΠΈΠ½ΠΎΠ³Π΄Π° ΡΡΠ°Π»ΠΊΠΈΠ²Π°ΡΡΡΡ Ρ ΠΏΡΠΎΠ±Π»Π΅ΠΌΠ°ΠΌΠΈ ΠΏΡΠΈ ΠΎΠ±ΠΌΠ΅Π½Π΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΌΠ°ΡΡΠΈΠ²Π°. ΠΠΎΡ ΡΠ°ΠΌΡΠ΅ ΡΠ°ΡΠΏΡΠΎΡΡΡΠ°Π½Π΅Π½Π½ΡΠ΅ ΠΎΡΠΈΠ±ΠΊΠΈ ΠΈ ΡΠΏΠΎΡΠΎΠ±Ρ ΠΈΡ ΠΏΡΠ΅Π΄ΠΎΡΠ²ΡΠ°ΡΠ΅Π½ΠΈΡ:
- π’ ΠΡΡ
ΠΎΠ΄ Π·Π° Π³ΡΠ°Π½ΠΈΡΡ ΠΌΠ°ΡΡΠΈΠ²Π°: ΠΡΠΎΠ²Π΅ΡΡΠΉΡΠ΅ ΠΈΠ½Π΄Π΅ΠΊΡΡ Ρ ΠΏΠΎΠΌΠΎΡΡΡ
ΠΠΡΠ°Π½ΠΈΡΠ°()ΠΈΠ»ΠΈΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ(). - π ΠΠ±ΠΌΠ΅Π½ Ρ ΡΠ°ΠΌΠΈΠΌ ΡΠΎΠ±ΠΎΠΉ: ΠΡΠ΅Π³Π΄Π° Π΄ΠΎΠ±Π°Π²Π»ΡΠΉΡΠ΅ ΠΏΡΠΎΠ²Π΅ΡΠΊΡ
ΠΡΠ»ΠΈ ΠΠ½Π΄Π΅ΠΊΡ1 <> ΠΠ½Π΄Π΅ΠΊΡ2 Π’ΠΎΠ³Π΄Π°. - ποΈ ΠΠΎΡΠ΅ΡΡ Π΄Π°Π½Π½ΡΡ ΠΏΡΠΈ Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΎΠΌ ΠΎΠ±ΠΌΠ΅Π½Π΅: ΠΡΠΏΠΎΠ»ΡΠ·ΡΠΉΡΠ΅ ΡΠΎΠ»ΡΠΊΠΎ Π΄Π»Ρ ΡΠΈΡΠ΅Π» ΠΈ ΠΈΠ·Π±Π΅Π³Π°ΠΉΡΠ΅ ΠΏΠ΅ΡΠ΅ΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ.
- π ΠΠ΅ΡΠΎΠ²ΠΌΠ΅ΡΡΠΈΠΌΡΠ΅ ΡΠΈΠΏΡ: ΠΡΠΈ ΠΎΠ±ΠΌΠ΅Π½Π΅ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΡΠ±Π΅Π΄ΠΈΡΠ΅ΡΡ, ΡΡΠΎ ΠΎΠ½ΠΈ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠΈΠΏΠ° (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π½Π΅ ΠΏΡΡΠ°ΠΉΡΠ΅ΡΡ ΠΏΠΎΠΌΠ΅Π½ΡΡΡ
Π‘ΠΏΡΠ°Π²ΠΎΡΠ½ΠΈΠΊΠ‘ΡΡΠ»ΠΊΠ°ΠΈΠΠΎΠΊΡΠΌΠ΅Π½ΡΠ‘ΡΡΠ»ΠΊΠ°).
ΠΡΠΈΠΌΠ΅Ρ Π·Π°ΡΠΈΡΡ ΠΎΡ Π²ΡΡ ΠΎΠ΄Π° Π·Π° Π³ΡΠ°Π½ΠΈΡΡ:
ΠΡΠΎΡΠ΅Π΄ΡΡΠ° ΠΠ΅Π·ΠΎΠΏΠ°ΡΠ½ΡΠΉΠΠ±ΠΌΠ΅Π½(ΠΠ°ΡΡΠΈΠ², ΠΠ½Π΄Π΅ΠΊΡ1, ΠΠ½Π΄Π΅ΠΊΡ2)
ΠΡΠ»ΠΈ ΠΠ½Π΄Π΅ΠΊΡ1 < 0 ΠΠΠ ΠΠ½Π΄Π΅ΠΊΡ2 < 0 ΠΠΠ
ΠΠ½Π΄Π΅ΠΊΡ1 >= ΠΠ°ΡΡΠΈΠ².ΠΠΡΠ°Π½ΠΈΡΠ°() ΠΠΠ
ΠΠ½Π΄Π΅ΠΊΡ2 >= ΠΠ°ΡΡΠΈΠ².ΠΠΡΠ°Π½ΠΈΡΠ°() Π’ΠΎΠ³Π΄Π°
ΠΠΎΠ·Π²ΡΠ°Ρ;
ΠΠΎΠ½Π΅ΡΠΡΠ»ΠΈ;
ΠΡΠ»ΠΈ ΠΠ½Π΄Π΅ΠΊΡ1 = ΠΠ½Π΄Π΅ΠΊΡ2 Π’ΠΎΠ³Π΄Π°
ΠΠΎΠ·Π²ΡΠ°Ρ;
ΠΠΎΠ½Π΅ΡΠΡΠ»ΠΈ;
// ΠΠ±ΠΌΠ΅Π½
ΠΡΠ΅ΠΌΠ΅Π½Π½Π°ΡΠΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ = ΠΠ°ΡΡΠΈΠ²[ΠΠ½Π΄Π΅ΠΊΡ1];
ΠΠ°ΡΡΠΈΠ²[ΠΠ½Π΄Π΅ΠΊΡ1] = ΠΠ°ΡΡΠΈΠ²[ΠΠ½Π΄Π΅ΠΊΡ2];
ΠΠ°ΡΡΠΈΠ²[ΠΠ½Π΄Π΅ΠΊΡ2] = ΠΡΠ΅ΠΌΠ΅Π½Π½Π°ΡΠΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ;
ΠΠΎΠ½Π΅ΡΠΡΠΎΡΠ΅Π΄ΡΡΡ
β οΈ ΠΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅: Π ΡΠΏΡΠ°Π²Π»ΡΠ΅ΠΌΡΡ
ΡΠΎΡΠΌΠ°Ρ
ΠΏΡΠΈ ΠΎΠ±ΠΌΠ΅Π½Π΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π’Π°Π±Π»ΠΈΡΡΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ, ΠΏΡΠΈΠ²ΡΠ·Π°Π½Π½ΠΎΠΉ ΠΊ ΡΠΎΡΠΌΠ΅, ΠΌΠΎΠΆΠ΅Ρ ΠΏΠΎΡΡΠ΅Π±ΠΎΠ²Π°ΡΡΡΡ Π²ΡΠ·Π²Π°ΡΡ ΠΠ±Π½ΠΎΠ²ΠΈΡΡ() Π΄Π»Ρ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΡ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΉ Π² ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡΠ΅.
FAQ: ΠΡΠ²Π΅ΡΡ Π½Π° ΡΠ°ΡΡΡΠ΅ Π²ΠΎΠΏΡΠΎΡΡ
ΠΠΎΠΆΠ½ΠΎ Π»ΠΈ ΠΏΠΎΠΌΠ΅Π½ΡΡΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠΈ Π² Π’Π°Π±Π»ΠΈΡΠ΅ΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ?
ΠΠ°, Π½ΠΎ ΡΡΠΎ ΡΡΠ΅Π±ΡΠ΅Ρ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ Π½ΠΎΠ²ΡΡ ΠΊΠΎΠ»ΠΎΠ½ΠΎΠΊ ΠΈ ΠΊΠΎΠΏΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π΄Π°Π½Π½ΡΡ . ΠΡΡΠΌΠΎΠ³ΠΎ ΠΌΠ΅ΡΠΎΠ΄Π° ΠΎΠ±ΠΌΠ΅Π½Π° ΠΊΠΎΠ»ΠΎΠ½ΠΎΠΊ Π² 1Π‘ Π½Π΅Ρ. ΠΡΠΈΠΌΠ΅Ρ:
Π’Π°Π±Π»ΠΈΡΠ°.ΠΠΎΠ»ΠΎΠ½ΠΊΠΈ.ΠΡΡΠ°Π²ΠΈΡΡ(1, "ΠΡΠ΅ΠΌΠ΅Π½Π½Π°ΡΠΠΎΠ»ΠΎΠ½ΠΊΠ°");
Π’Π°Π±Π»ΠΈΡΠ°.ΠΠΎΠ»ΠΎΠ½ΠΊΠΈ[1].ΠΠΌΡ = "Π‘ΡΠ°ΡΠΎΠ΅ΠΠΌΡΠΠΎΠ»ΠΎΠ½ΠΊΠΈ2";
Π’Π°Π±Π»ΠΈΡΠ°.ΠΠΎΠ»ΠΎΠ½ΠΊΠΈ[2].ΠΠΌΡ = "Π‘ΡΠ°ΡΠΎΠ΅ΠΠΌΡΠΠΎΠ»ΠΎΠ½ΠΊΠΈ1";
ΠΠΎΡΠ»Π΅ ΡΡΠΎΠ³ΠΎ Π½ΡΠΆΠ½ΠΎ ΡΠΊΠΎΠΏΠΈΡΠΎΠ²Π°ΡΡ Π΄Π°Π½Π½ΡΠ΅ ΠΈΠ· ΠΎΡΠΈΠ³ΠΈΠ½Π°Π»ΡΠ½ΡΡ ΠΊΠΎΠ»ΠΎΠ½ΠΎΠΊ Π²ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΡΠ΅ ΠΈ ΡΠ΄Π°Π»ΠΈΡΡ ΡΡΠ°ΡΡΠ΅.
ΠΠ°ΠΊ ΠΎΠ±ΠΌΠ΅Π½ΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π² Π‘ΠΏΠΈΡΠΊΠ΅ΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ?
ΠΠ½Π°Π»ΠΎΠ³ΠΈΡΠ½ΠΎ ΠΌΠ°ΡΡΠΈΠ²Ρ, Π½ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠΉΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΠΎΠ»ΡΡΠΈΡΡ() ΠΈ Π£ΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ():
Π‘ΠΏΠΈΡΠΎΠΊ = ΠΠΎΠ²ΡΠΉ Π‘ΠΏΠΈΡΠΎΠΊΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ();
Π‘ΠΏΠΈΡΠΎΠΊ.ΠΠΎΠ±Π°Π²ΠΈΡΡ("ΠΠ»Π΅ΠΌΠ΅Π½Ρ1");
Π‘ΠΏΠΈΡΠΎΠΊ.ΠΠΎΠ±Π°Π²ΠΈΡΡ("ΠΠ»Π΅ΠΌΠ΅Π½Ρ2");
ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅1 = Π‘ΠΏΠΈΡΠΎΠΊ.ΠΠΎΠ»ΡΡΠΈΡΡ(0);
ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅2 = Π‘ΠΏΠΈΡΠΎΠΊ.ΠΠΎΠ»ΡΡΠΈΡΡ(1);
Π‘ΠΏΠΈΡΠΎΠΊ.Π£ΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ(0, ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅2);
Π‘ΠΏΠΈΡΠΎΠΊ.Π£ΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ(1, ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅1);
ΠΠΎΡΠ΅ΠΌΡ ΠΏΠΎΡΠ»Π΅ ΠΎΠ±ΠΌΠ΅Π½Π° Π² Π’Π°Π±Π»ΠΈΡΠ΅ΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ Π½Π΅ ΠΎΠ±Π½ΠΎΠ²Π»ΡΠ΅ΡΡΡ ΡΠΎΡΠΌΠ°?
Π ΡΠΏΡΠ°Π²Π»ΡΠ΅ΠΌΡΡ
ΡΠΎΡΠΌΠ°Ρ
ΠΏΠΎΡΠ»Π΅ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΡ Π΄Π°Π½Π½ΡΡ
Π² Π’Π°Π±Π»ΠΈΡΠ΅ΠΠ½Π°ΡΠ΅Π½ΠΈΠΉ Π½ΡΠΆΠ½ΠΎ ΡΠ²Π½ΠΎ Π²ΡΠ·Π²Π°ΡΡ ΠΠ±Π½ΠΎΠ²ΠΈΡΡ() Π΄Π»Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° ΡΠΎΡΠΌΡ:
ΠΠ»Π΅ΠΌΠ΅Π½ΡΡΠ€ΠΎΡΠΌΡ.Π’Π°Π±Π»ΠΈΡΠ°.ΠΠ±Π½ΠΎΠ²ΠΈΡΡ();
ΠΡΠ»ΠΈ ΡΠ°Π±Π»ΠΈΡΠ° ΠΏΡΠΈΠ²ΡΠ·Π°Π½Π° ΠΊ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠΌΡ ΡΠΏΠΈΡΠΊΡ, ΠΌΠΎΠΆΠ΅Ρ ΠΏΠΎΡΡΠ΅Π±ΠΎΠ²Π°ΡΡΡΡ ΠΠ΅ΡΠ΅ΡΠΈΡΠ°ΡΡ().
ΠΠ°ΠΊ ΠΏΠΎΠΌΠ΅Π½ΡΡΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ ΡΡΡΠΎΠΊΠΈ Π² ΡΠ°Π±Π»ΠΈΡΠ΅ Π΄ΠΎΠΊΡΠΌΠ΅Π½ΡΠ° (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π² ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ)?
ΠΠ»Ρ ΡΠ°Π±Π»ΠΈΡΠ½ΡΡ
ΡΠ°ΡΡΠ΅ΠΉ Π΄ΠΎΠΊΡΠΌΠ΅Π½ΡΠΎΠ² ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠΉΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄ ΠΠ΅ΡΠ΅ΠΌΠ΅ΡΡΠΈΡΡ():
ΠΠΎΠΊ.Π’ΠΎΠ²Π°ΡΡ.ΠΠ΅ΡΠ΅ΠΌΠ΅ΡΡΠΈΡΡ(ΠΠ½Π΄Π΅ΠΊΡ1, ΠΠ½Π΄Π΅ΠΊΡ2);
ΠΡΠ»ΠΈ Π½ΡΠΆΠ½ΠΎ ΠΎΠ±ΠΌΠ΅Π½ΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ Π² ΡΡΡΠΎΠΊΠ°Ρ (Π±Π΅Π· ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ΅Π½ΠΈΡ), ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠΉΡΠ΅ ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ swap Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ΅ΠΊΠ²ΠΈΠ·ΠΈΡΠ° ΡΡΡΠΎΠΊΠΈ.
ΠΠΎΠΆΠ½ΠΎ Π»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΎΠ±ΠΌΠ΅Π½ Π΄Π»Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΌΠ°ΡΡΠΈΠ²Π°?
Π’Π΅Ρ
Π½ΠΈΡΠ΅ΡΠΊΠΈ Π΄Π°, Π½ΠΎ ΡΡΠΎ ΠΊΡΠ°ΠΉΠ½Π΅ Π½Π΅ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ. ΠΠ»Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠΉΡΠ΅ Π²ΡΡΡΠΎΠ΅Π½Π½ΡΠΉ ΠΌΠ΅ΡΠΎΠ΄ Π‘ΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ() ΠΈΠ»ΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ Π²ΡΠΎΠ΄Π΅ ΠΏΡΠ·ΡΡΡΠΊΠΎΠ²ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ (Π΄Π»Ρ ΡΡΠ΅Π±Π½ΡΡ
ΡΠ΅Π»Π΅ΠΉ) ΠΈΠ»ΠΈ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ (Π΄Π»Ρ ΡΠ΅Π°Π»ΡΠ½ΡΡ
Π·Π°Π΄Π°Ρ). ΠΡΠΈΠΌΠ΅Ρ ΠΏΡΠ·ΡΡΡΠΊΠΎΠ²ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ:
ΠΠ»Ρ i = 0 ΠΠΎ ΠΠ°ΡΡΠΈΠ².ΠΠΡΠ°Π½ΠΈΡΠ°() - 1 Π¦ΠΈΠΊΠ»
ΠΠ»Ρ j = 0 ΠΠΎ ΠΠ°ΡΡΠΈΠ².ΠΠΡΠ°Π½ΠΈΡΠ°() - i - 2 Π¦ΠΈΠΊΠ»
ΠΡΠ»ΠΈ ΠΠ°ΡΡΠΈΠ²[j] > ΠΠ°ΡΡΠΈΠ²[j + 1] Π’ΠΎΠ³Π΄Π°
// ΠΠ±ΠΌΠ΅Π½ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ²
ΠΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ = ΠΠ°ΡΡΠΈΠ²[j];
ΠΠ°ΡΡΠΈΠ²[j] = ΠΠ°ΡΡΠΈΠ²[j + 1];
ΠΠ°ΡΡΠΈΠ²[j + 1] = ΠΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ;
ΠΠΎΠ½Π΅ΡΠΡΠ»ΠΈ;
ΠΠΎΠ½Π΅ΡΠ¦ΠΈΠΊΠ»Π°;
ΠΠΎΠ½Π΅ΡΠ¦ΠΈΠΊΠ»Π°;