🀀 Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹: всС, Ρ‡Ρ‚ΠΎ Π½ΡƒΠΆΠ½ΠΎ Π·Π½Π°Ρ‚ΡŒ для собСсСдования

Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ эффСктивно Ρ€Π΅ΡˆΠ°Ρ‚ΡŒ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹ΠΉ спСктр ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΎΠ½Π½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡. Однако ΠΈΡ… ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ Ρ‚Ρ‰Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ Π°Π½Π°Π»ΠΈΠ·Π° Π·Π°Π΄Π°Ρ‡ΠΈ ΠΈ структуры ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Π΅ΠΌΡ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΆΠ°Π΄Π½Ρ‹ΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ Π½Π΅ всСгда Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΠ΅Ρ‚ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅. Π’ этой ΡΡ‚Π°Ρ‚ΡŒΠ΅ ΠΌΡ‹ рассмотрим основныС ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΡ‹ Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΆΠ°Π΄Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², ΠΈΡ… прСимущСства ΠΈ нСдостатки, Π° Ρ‚Π°ΠΊΠΆΠ΅ Ρ€Π°Π·Π±Π΅Ρ€Π΅ΠΌ нСсколько практичСских ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠ² ΠΈΡ… примСнСния.

Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ β€” это класс Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС Π΄Π΅Π»Π°ΡŽΡ‚ локально ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Π²Ρ‹Π±ΠΎΡ€, полагая, Ρ‡Ρ‚ΠΎ это ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Ρ‚ ΠΊ глобально ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΌΡƒ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ Π² ΠΊΠΎΠ½Ρ†Π΅. ΠžΡΠ½ΠΎΠ²Π½Ρ‹Π΅ характСристики ΠΆΠ°Π΄Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²:

  • Π›ΠΎΠΊΠ°Π»ΡŒΠ½Π°Ρ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ β€” Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π΄Π΅Π»Π°Π΅Ρ‚ Π²Ρ‹Π±ΠΎΡ€, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ каТСтся Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠΈΠΌ, максимально Π²Ρ‹Π³ΠΎΠ΄Π½Ρ‹ΠΌ Π² Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚ (ΠΈ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ ΠΎΡˆΠΈΠ±ΠΎΡ‡Π½Ρ‹ΠΌ Π² рСтроспСктивС).
  • ΠΠ΅ΠΎΠ±Ρ€Π°Ρ‚ΠΈΠΌΠΎΡΡ‚ΡŒ β€” Π²Ρ‹Π±ΠΎΡ€, сдСланный Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС, Π½Π΅ измСняСтся. Алгоритм Π½Π΅ возвращаСтся Π½Π°Π·Π°Π΄, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΈΠ·ΠΌΠ΅Π½ΠΈΡ‚ΡŒ своС ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π΅Π΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅.
  • ΠŸΠΎΡΡ‚Π΅ΠΏΠ΅Π½Π½ΠΎΠ΅ построСниС Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ β€” Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ строит Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ шаг Π·Π° шагом, добавляя ΠΊ ΡƒΠΆΠ΅ построСнному частичному Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ Π½ΠΎΠ²Ρ‹Π΅ элСмСнты.

НазваниС Β«ΠΆΠ°Π΄Π½Ρ‹Π΅Β» происходит ΠΎΡ‚ Π°Π½Π°Π»ΠΎΠ³ΠΈΠΈ с Ρ‡Π΅Π»ΠΎΠ²Π΅ΠΊΠΎΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ, ΡΡ‚Ρ€Π΅ΠΌΡΡΡŒ ΠΊ максимальной Π²Ρ‹Π³ΠΎΠ΄Π΅, Ρ…Π²Π°Ρ‚Π°Π΅Ρ‚ всС самоС Ρ†Π΅Π½Π½ΠΎΠ΅, Ρ‡Ρ‚ΠΎ Π²ΠΈΠ΄ΠΈΡ‚ Π² Π΄Π°Π½Π½Ρ‹ΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚, Π½Π΅ Π·Π°Π΄ΡƒΠΌΡ‹Π²Π°ΡΡΡŒ ΠΎ долгосрочных послСдствиях. Π–Π°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Ρ‚ΠΎΡ‡Π½ΠΎ Ρ‚Π°ΠΊ ΠΆΠ΅ всСгда Π²Ρ‹Π±ΠΈΡ€Π°Π΅Ρ‚ Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠΈΠΉ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ ΠΈΠ· доступных, Π½Π΅ учитывая влияниС этого Π²Ρ‹Π±ΠΎΡ€Π° Π½Π° Π±ΡƒΠ΄ΡƒΡ‰ΠΈΠ΅ шаги. Π’ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ ΠΈΡ‚ΠΎΠ³ΠΎΠ²ΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ Π΄Π°Π»Π΅ΠΊΠΎ Π½Π΅ всСгда оказываСтся ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ с использованиСм ΠΆΠ°Π΄Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ‚ ΡΠ»ΡƒΠΆΠΈΡ‚ΡŒ классичСская Π·Π°Π΄Π°Ρ‡Π° ΠΎ Ρ€ΡŽΠΊΠ·Π°ΠΊΠ΅. ΠŸΡ€Π΅Π΄ΡΡ‚Π°Π²ΡŒΡ‚Π΅, Ρ‡Ρ‚ΠΎ Π²Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ ΡΠΎΠ±Ρ€Π°Ρ‚ΡŒ Ρ€ΡŽΠΊΠ·Π°ΠΊ с максимальной Ρ†Π΅Π½Π½ΠΎΡΡ‚ΡŒΡŽ Π²Π΅Ρ‰Π΅ΠΉ, Π½ΠΎ ΠΎΠ½ ΠΈΠΌΠ΅Π΅Ρ‚ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½Π½ΡƒΡŽ Π²ΠΌΠ΅ΡΡ‚ΠΈΠΌΠΎΡΡ‚ΡŒ (ΠΏΠΎ ΠΎΠ±ΡŠΠ΅ΠΌΡƒ ΠΈΠ»ΠΈ ΠΏΠΎ вСсу). Π–Π°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π² Π΄Π°Π½Π½ΠΎΠΌ случаС Π±ΡƒΠ΄Π΅Ρ‚ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС Π²Ρ‹Π±ΠΈΡ€Π°Ρ‚ΡŒ самый Ρ†Π΅Π½Π½Ρ‹ΠΉ ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ помСщаСтся Π² Ρ€ΡŽΠΊΠ·Π°ΠΊ, ΠΏΠΎΠΊΠ° ΠΎΠ½ Π½Π΅ заполнится. Алгоритм дСйствуСт Ρ‚Π°ΠΊ:

  • РассчитываСт ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ вСса (ΠΈΠ»ΠΈ объСма) для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚Π°.
  • Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΡƒΠ΅Ρ‚ ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚Ρ‹ ΠΏΠΎ ΡƒΠ±Ρ‹Π²Π°Π½ΠΈΡŽ этой стоимости.
  • ДобавляСт ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚Ρ‹ Π² Ρ€ΡŽΠΊΠ·Π°ΠΊ, начиная с ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚Π° с наибольшСй ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒΡŽ Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ вСса/объСма, ΠΏΠΎΠΊΠ° позволяСт ΠΎΡΡ‚Π°Π²ΡˆΠΈΠΉΡΡ вСс Ρ€ΡŽΠΊΠ·Π°ΠΊΠ°.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ Π½Π΅ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ β€” извСстная Π·Π°Π΄Π°Ρ‡Π° ΠΎ Π²Ρ‹Π±ΠΎΡ€Π΅ ΠΌΠΎΠ½Π΅Ρ‚: здСсь ΠΆΠ°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ всСгда Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΡ€ΠΎΠΈΠ³Ρ€Ρ‹Π²Π°Ρ‚ΡŒ Π»ΡŽΠ±ΠΎΠΌΡƒ Π΄Ρ€ΡƒΠ³ΠΎΠΌΡƒ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Ρƒ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ способСн ΠΏΡ€ΠΎΡΡ‡ΠΈΡ‚Ρ‹Π²Π°Ρ‚ΡŒ послСдствия своих дСйствий Π½Π° нСсколько шагов Π²ΠΏΠ΅Ρ€Π΅Π΄.

ΠŸΡ€Π΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ, имССтся ряд ΠΌΠΎΠ½Π΅Ρ‚ [3, 9, 1, 2], Π²Ρ‹Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… Π² линию. Π”Π²Π° ΠΈΠ³Ρ€ΠΎΠΊΠ° ΠΏΠΎ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ Π±Π΅Ρ€ΡƒΡ‚ ΠΎΠ΄Π½Ρƒ ΠΌΠΎΠ½Π΅Ρ‚Ρƒ с любого ΠΊΠΎΠ½Ρ†Π° ряда. Π—Π°Π΄Π°Ρ‡Π° ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΈΠ³Ρ€ΠΎΠΊΠ° β€” ΠΌΠ°ΠΊΡΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ свою сумму. Π˜Π³Ρ€ΠΎΠΊΠΈ видят всС ΠΌΠΎΠ½Π΅Ρ‚Ρ‹ ΠΈ Π·Π½Π°ΡŽΡ‚, сколько стоит каТдая ΠΌΠΎΠ½Π΅Ρ‚Π°.

Π–Π°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΏΡ€Π΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС ΠΈΠ³Ρ€ΠΎΠΊ Π²Ρ‹Π±ΠΈΡ€Π°Π΅Ρ‚ Ρ‚Ρƒ ΠΌΠΎΠ½Π΅Ρ‚Ρƒ, которая ΠΈΠΌΠ΅Π΅Ρ‚ Π½Π°ΠΈΠ±ΠΎΠ»ΡŒΡˆΡƒΡŽ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ ΠΈΠ· доступных с ΠΎΠ±ΠΎΠΈΡ… ΠΊΠΎΠ½Ρ†ΠΎΠ². Π­Ρ‚ΠΎ локально ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΈΠ³Ρ€ΠΎΠΊ Π²Ρ‹Π±ΠΈΡ€Π°Π΅Ρ‚ максимально Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡƒΡŽ ΠΌΠΎΠ½Π΅Ρ‚Ρƒ Π² Π΄Π°Π½Π½Ρ‹ΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚, Π½Π΅ Π·Π°Π΄ΡƒΠΌΡ‹Π²Π°ΡΡΡŒ ΠΎ Π±ΡƒΠ΄ΡƒΡ‰Π΅ΠΌ:

  • ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ ΠΈΠ³Ρ€ΠΎΠΊ (И1) Π²ΠΈΠ΄ΠΈΡ‚ ΠΌΠΎΠ½Π΅Ρ‚Ρ‹ 3 ΠΈ 2 ΠΈ Π²Ρ‹Π±ΠΈΡ€Π°Π΅Ρ‚ 3 (Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΎΠ½Π° большС 2).
  • Π’Ρ‚ΠΎΡ€ΠΎΠΉ ΠΈΠ³Ρ€ΠΎΠΊ (И2) Π²ΠΈΠ΄ΠΈΡ‚ ΠΌΠΎΠ½Π΅Ρ‚Ρ‹ 9 ΠΈ 2 ΠΈ Π²Ρ‹Π±ΠΈΡ€Π°Π΅Ρ‚ 9.
  • ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ ΠΈΠ³Ρ€ΠΎΠΊ (И1) Π²ΠΈΠ΄ΠΈΡ‚ ΠΌΠΎΠ½Π΅Ρ‚Ρ‹ 1 ΠΈ 2 ΠΈ Π²Ρ‹Π±ΠΈΡ€Π°Π΅Ρ‚ 2.
  • Π’Ρ‚ΠΎΡ€ΠΎΠΉ ΠΈΠ³Ρ€ΠΎΠΊ (И2) Π±Π΅Ρ€Π΅Ρ‚ ΠΎΡΡ‚Π°Π²ΡˆΡƒΡŽΡΡ ΠΌΠΎΠ½Π΅Ρ‚Ρƒ 1.

Π‘ΡƒΠΌΠΌΠ° для И1: 3 + 2 = 5

Π‘ΡƒΠΌΠΌΠ° для И2: 9 + 1 = 10

Π’ ΠΈΡ‚ΠΎΠ³Π΅ И1 Π½Π°Π±Ρ€Π°Π» 5, Π° И2 β€” 10. Π–Π°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΏΡ€ΠΎΠΈΠ³Ρ€Π°Π», И1 Π½Π΅ смог ΠΌΠ°ΠΊΡΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ свою сумму. ΠžΡ‡Π΅Π²ΠΈΠ΄Π½ΠΎ, для Π²Ρ‹ΠΈΠ³Ρ€Ρ‹ΡˆΠ° Π½ΡƒΠΆΠ½ΠΎ ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Ρ‚ΡŒ Π²ΠΎ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π±ΡƒΠ΄ΡƒΡ‰ΠΈΠ΅ Ρ…ΠΎΠ΄Ρ‹ ΠΈ ΠΈΡ… послСдствия, ΠΈ ΠΎΡ†Π΅Π½ΠΈΠ²Π°Ρ‚ΡŒ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ Ρ…ΠΎΠ΄Ρ‹ ΠΏΡ€ΠΎΡ‚ΠΈΠ²Π½ΠΈΠΊΠ°, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π΅Π³ΠΎ Π²Ρ‹Π³ΠΎΠ΄Ρƒ β€” ΠΊΠ°ΠΊ это Π΄Π΅Π»Π°Π΅Ρ‚, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ минимакс.

ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ ΠΈΠ³Ρ€ΠΎΠΊ (И1) Ρ€Π°Π·ΠΌΡ‹ΡˆΠ»ΡΠ΅Ρ‚:

  • Если ΠΎΠ½ Π²ΠΎΠ·ΡŒΠΌΠ΅Ρ‚ 3, Ρ‚ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΉ ΠΈΠ³Ρ€ΠΎΠΊ (И2) ΠΈΠΌΠ΅Π΅Ρ‚ Π²Ρ‹Π±ΠΎΡ€ ΠΌΠ΅ΠΆΠ΄Ρƒ 9 ΠΈ 2.
  • Если И2 Π²Ρ‹Π±Π΅Ρ€Π΅Ρ‚ 9, Ρ‚ΠΎ И1 останСтся с [1, 2].

И1 Π²ΠΎΠ·ΡŒΠΌΠ΅Ρ‚ 2, И2 Π²ΠΎΠ·ΡŒΠΌΠ΅Ρ‚ 1.

Π‘ΡƒΠΌΠΌΠ° для И1: 3 + 2 = 5, сумма для И2: 9 + 1 = 10.

  • Если И2 Π²Ρ‹Π±Π΅Ρ€Π΅Ρ‚ 2, Ρ‚ΠΎ И1 останСтся с [9, 1].

И1 Π²ΠΎΠ·ΡŒΠΌΠ΅Ρ‚ 9, И2 Π²ΠΎΠ·ΡŒΠΌΠ΅Ρ‚ 1.

Π‘ΡƒΠΌΠΌΠ° для И1: 3 + 9 = 12, сумма для И2: 2 + 1 = 3.

  • Если И1 Π²ΠΎΠ·ΡŒΠΌΠ΅Ρ‚ 2, Ρ‚ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΉ ΠΈΠ³Ρ€ΠΎΠΊ (И2) ΠΈΠΌΠ΅Π΅Ρ‚ Π²Ρ‹Π±ΠΎΡ€ ΠΌΠ΅ΠΆΠ΄Ρƒ 3 ΠΈ 1.
  • Если И2 Π²Ρ‹Π±Π΅Ρ€Π΅Ρ‚ 3, Ρ‚ΠΎ И1 останСтся с [9, 1].

И1 Π²ΠΎΠ·ΡŒΠΌΠ΅Ρ‚ 9, И2 Π²ΠΎΠ·ΡŒΠΌΠ΅Ρ‚ 1.

Π‘ΡƒΠΌΠΌΠ° для И1: 2 + 9 = 11, сумма для И2: 3 + 1 = 4.

  • Если И2 Π²Ρ‹Π±Π΅Ρ€Π΅Ρ‚ 1, Ρ‚ΠΎ И1 останСтся с [3, 9].

И1 Π²ΠΎΠ·ΡŒΠΌΠ΅Ρ‚ 9, И2 Π²ΠΎΠ·ΡŒΠΌΠ΅Ρ‚ 3.

Π‘ΡƒΠΌΠΌΠ° для И1: 2 + 9 = 11, сумма для И2: 1 + 3 = 4.

Из Π°Π½Π°Π»ΠΈΠ·Π° Π²ΠΈΠ΄Π½ΠΎ, Ρ‡Ρ‚ΠΎ Π»ΡƒΡ‡ΡˆΠΈΠΉ Ρ…ΠΎΠ΄ для И1 β€” Π²Π·ΡΡ‚ΡŒ 2 Π² Π½Π°Ρ‡Π°Π»Π΅, Ρ‡Ρ‚ΠΎ даст Π΅ΠΌΡƒ прСимущСство ΠΈ Π»ΡƒΡ‡ΡˆΡƒΡŽ ΠΈΡ‚ΠΎΠ³ΠΎΠ²ΡƒΡŽ сумму.

***

ΠšΡƒΡ€Ρ «Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…Β» ΠΎΡ‚ Proglib Academy

ΠšΡƒΡ€Ρ «Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…Β» ΠΏΡ€Π΅Π΄Π½Π°Π·Π½Π°Ρ‡Π΅Π½ для Ρ‚Π΅Ρ…, ΠΊΡ‚ΠΎ Ρ…ΠΎΡ‡Π΅Ρ‚ ΡƒΠ³Π»ΡƒΠ±ΠΈΡ‚ΡŒ свои знания Π² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ, ΠΏΠΎΠ΄Π³ΠΎΡ‚ΠΎΠ²ΠΈΡ‚ΡŒΡΡ ΠΊ собСсСдованиям Π² Π²Π΅Π΄ΡƒΡ‰ΠΈΠ΅ IT-ΠΊΠΎΠΌΠΏΠ°Π½ΠΈΠΈ ΠΈ ΡƒΡ‡Π°ΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ Π² слоТных ΠΏΡ€ΠΎΠ΅ΠΊΡ‚Π°Ρ….

πŸŽ“ ΠŸΠΎΡ‡Π΅ΠΌΡƒ стоит ΠΈΠ·ΡƒΡ‡Π°Ρ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹

  • Π—Π½Π°Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Ρ€Π°ΡΡˆΠΈΡ€ΡΠ΅Ρ‚ инструмСнтарий Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠ°.
  • ΠŸΠΎΠ΄Π³ΠΎΡ‚ΠΎΠ²ΠΊΠ° ΠΊ тСхничСским собСсСдованиям Π² ΠΊΠΎΠΌΠΏΠ°Π½ΠΈΠΈ, Ρ‚Π°ΠΊΠΈΠ΅ ΠΊΠ°ΠΊ ЯндСкс, Π‘Π±Π΅Ρ€, Google, Microsoft ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠ΅.
  • ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½ΠΈΠ΅ сСртификата ΠΎ ΠΏΡ€ΠΎΡ…ΠΎΠΆΠ΄Π΅Π½ΠΈΠΈ курса ΠΎΡ‚ Proglib Academy

πŸ” Π§Ρ‚ΠΎ вас ΠΆΠ΄Π΅Ρ‚

  • 47 Π²ΠΈΠ΄Π΅ΠΎΠ»Π΅ΠΊΡ†ΠΈΠΉ ΠΈ 150 практичСских Π·Π°Π΄Π°Π½ΠΈΠΉ β€” ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ°, которая ΠΏΠΎΠΌΠΎΠΆΠ΅Ρ‚ Π²Π°ΠΌ ΠΎΡΠ²ΠΎΠΈΡ‚ΡŒ ΠΊΠ»ΡŽΡ‡Π΅Π²Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ….
  • ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Π½Π°ΠΏΡ€Π°Π²Π»Π΅Π½Π½ΠΎΡΡ‚ΡŒ β€” написаниС ΠΊΠΎΠ΄Π° ΠΈ Ρ€Π°Π·Π±ΠΎΡ€ алгоритмичСских Π·Π°Π΄Π°Ρ‡.
  • ΠŸΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΊΠ° ΠΏΡ€Π΅ΠΏΠΎΠ΄Π°Π²Π°Ρ‚Π΅Π»Π΅ΠΉ β€” ΠΊΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΈ ΠΏΠΎ заданиям Π½Π° протяТСнии всСго курса.

πŸ’‘ ПослС курса Π²Ρ‹ смоТСтС

  • Π‘ΠΎΠ·Π΄Π°Π²Π°Ρ‚ΡŒ Π½ΠΎΠ²Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ….
  • Π›Π΅Π³ΠΊΠΎ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ тСхничСскиС собСсСдования.
  • ΠŸΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Π΅ Π½Π°Π²Ρ‹ΠΊΠΈ Π² Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ΅ΠΊΡ‚Π°Ρ….
***

ΠŸΡ€Π΅ΠΈΠΌΡƒΡ‰Π΅ΡΡ‚Π²Π° ΠΈ нСдостатки ΠΆΠ°Π΄Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈΠΌΠ΅ΡŽΡ‚ свои достоинства, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΄Π΅Π»Π°ΡŽΡ‚ ΠΈΡ… ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌΠΈ для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ Ρ‚ΠΈΠΏΠ°, ΠΈ нСдостатки, ΠΎ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… всСгда Π½ΡƒΠΆΠ½ΠΎ ΠΏΠΎΠΌΠ½ΠΈΡ‚ΡŒ.

ΠŸΠ»ΡŽΡΡ‹ ΠΆΠ°Π΄Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²:

  • ΠŸΡ€ΠΎΡΡ‚ΠΎΡ‚Π° ΠΈ Π»Π΅Π³ΠΊΠΎΡΡ‚ΡŒ Π² Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ β€” ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ просты для понимания ΠΈ программирования, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΈΡ… Π»ΠΎΠ³ΠΈΠΊΠ° основана Π½Π° принятии максимально Π²Ρ‹Π³ΠΎΠ΄Π½Ρ‹Ρ… Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΉ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС.
  • Π‘ΠΊΠΎΡ€ΠΎΡΡ‚ΡŒ β€” ΠΊΠ°ΠΊ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ, ΠΈΠΌΠ΅ΡŽΡ‚ Π½ΠΈΠ·ΠΊΡƒΡŽ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½ΡƒΡŽ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ, часто Π»ΠΈΠ½Π΅ΠΉΠ½ΡƒΡŽ ΠΈΠ»ΠΈ Π»ΠΎΠ³Π°Ρ€ΠΈΡ„ΠΌΠΈΡ‡Π΅ΡΠΊΡƒΡŽ, Ρ‡Ρ‚ΠΎ Π΄Π΅Π»Π°Π΅Ρ‚ ΠΈΡ… подходящими для Π·Π°Π΄Π°Ρ‡, Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‰ΠΈΡ… быстрого Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ.
  • Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ для ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡ β€” ΠΎΡ‚Π»ΠΈΡ‡Π½ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‚ для ряда Π·Π°Π΄Π°Ρ‡, Π³Π΄Π΅ локально ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ приводят ΠΊ глобально ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ. НапримСр β€” Π·Π°Π΄Π°Ρ‡Π° ΠΎ Π²Ρ‹Π±ΠΎΡ€Π΅ мСроприятий, обычная Π·Π°Π΄Π°Ρ‡Π° ΠΎ Ρ€ΡŽΠΊΠ·Π°ΠΊΠ΅ ΠΈ построСниС ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… остовных Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π².
  • НСбольшиС трСбования ΠΊ памяти β€” ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΆΠ°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π΄Π΅Π»Π°ΡŽΡ‚ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π½Π° основС Ρ‚Π΅ΠΊΡƒΡ‰Π΅Π³ΠΎ состояния, ΠΎΠ½ΠΈ Π½Π΅ Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ хранСния большого количСства ΠΏΡ€ΠΎΠΌΠ΅ΠΆΡƒΡ‚ΠΎΡ‡Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… β€” это экономит ΠΏΠ°ΠΌΡΡ‚ΡŒ.
  • Π₯ΠΎΡ€ΠΎΡˆΠ΅Π΅ ΠΏΡ€ΠΈΠ±Π»ΠΈΠΆΠ΅Π½Π½ΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ β€” Π΄Π°ΠΆΠ΅ Ссли Π½Π΅ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΡŽΡ‚ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ, часто Π΄Π°ΡŽΡ‚ Ρ…ΠΎΡ€ΠΎΡˆΠ΅Π΅ ΠΏΡ€ΠΈΠ±Π»ΠΈΠΆΠ΅Π½ΠΈΠ΅ Π·Π° Ρ€Π°Π·ΡƒΠΌΠ½ΠΎΠ΅ врСмя.

ΠœΠΈΠ½ΡƒΡΡ‹ ΠΆΠ°Π΄Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²:

  • НС всСгда Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΡŽΡ‚ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅. Π—Π°Π΄Π°Ρ‡ΠΈ, для ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π½ΡƒΠΆΠ½ΠΎ ΠΎΡ†Π΅Π½ΠΈΠ²Π°Ρ‚ΡŒ послСдствия дСйствий (ΠΈ ΠΈΠ½ΠΎΠ³Π΄Π° Π²Ρ‹Π±ΠΈΡ€Π°Ρ‚ΡŒ Π½Π΅ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ Π»ΠΎΠΊΠ°Π»ΡŒΠ½Ρ‹Π΅ ΠΎΠΏΡ†ΠΈΠΈ для достиТСния глобального ΠΎΠΏΡ‚ΠΈΠΌΡƒΠΌΠ°), Π½Π΅ ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ Ρ€Π΅ΡˆΠ΅Π½Ρ‹ ΠΆΠ°Π΄Π½Ρ‹ΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ эффСктивно.
  • ΠžΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½Π½Π°Ρ ΠΎΠ±Π»Π°ΡΡ‚ΡŒ примСнСния ΠΈ Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡ‚ΡŒ ΠΎΡ‚ структуры Π·Π°Π΄Π°Ρ‡ΠΈ. Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ подходят Ρ‚ΠΎΠ»ΡŒΠΊΠΎ для Ρ‚Π΅Ρ… Π·Π°Π΄Π°Ρ‡, Π³Π΄Π΅ локально ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎ Π²Π΅Π΄ΡƒΡ‚ ΠΊ глобально ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ. НапримСр, ΠΆΠ°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΈΡ‚ для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΎ Ρ€Π°Π·ΠΌΠ΅Π½Π΅ ΠΌΠΎΠ½Π΅Ρ‚, Π²Ρ‹ΠΏΡƒΡ‰Π΅Π½Π½Ρ‹Ρ… Π² амСриканской номинальной систСмС (1, 5, 10, 25, 50, 100/$1) ΠΈ Π½Π΅ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΈΡ‚ для Ρ‚Π°ΠΊΠΎΠΉ ΠΆΠ΅ Π·Π°Π΄Π°Ρ‡ΠΈ, Ссли Π² Π½Π΅ΠΉ ΠΈΠ΄Π΅Ρ‚ Ρ€Π΅Ρ‡ΡŒ ΠΎ Ρ€Π°Π·ΠΌΠ΅Π½Π΅ ΠΌΠΎΠ½Π΅Ρ‚ ΠΈΠ· старой британской систСмы (1, 3, 6, 12, 24, 30). А Ссли Π² Π·Π°Π΄Π°Ρ‡Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ ΠΌΠΎΠ½Π΅Ρ‚Ρ‹, Π²Ρ‹ΠΏΡƒΡ‰Π΅Π½Π½Ρ‹Π΅ Π² систСмС (1, r, r2, r3), Ρ‚ΠΎ Π»ΡƒΡ‡ΡˆΠ΅Π³ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ, Ρ‡Π΅ΠΌ ΠΆΠ°Π΄Π½ΠΎΠ΅, просто Π½Π΅ Π½Π°ΠΉΡ‚ΠΈ.
  • ΠžΡ‚ΡΡƒΡ‚ΡΡ‚Π²ΠΈΠ΅ гибкости. Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΡΠ»Π΅Π΄ΡƒΡŽΡ‚ фиксированной стратСгии Π²Ρ‹Π±ΠΎΡ€Π°, Π½Π΅ допуская ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΉ ΠΈΠ»ΠΈ ΡƒΠ»ΡƒΡ‡ΡˆΠ΅Π½ΠΈΠΉ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΉ ΠΏΠΎ Ρ…ΠΎΠ΄Ρƒ выполнСния. Они Π½Π΅ Π°Π΄Π°ΠΏΡ‚ΠΈΡ€ΡƒΡŽΡ‚ΡΡ ΠΊ измСнСниям условий ΠΈΠ»ΠΈ появлСнию Π½ΠΎΠ²Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. По этой ΠΏΡ€ΠΈΡ‡ΠΈΠ½Π΅ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΆΠ°Π΄Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° нСльзя Ρ€Π΅ΡˆΠΈΡ‚ΡŒ Π·Π°Π΄Π°Ρ‡Ρƒ ΠΎ Ρ€ΡŽΠΊΠ·Π°ΠΊΠ΅ 0-1.
  • ΠŸΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½Π°Ρ Π½Π΅ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ Π² Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… прилоТСниях. Π­Ρ‚ΠΎ слСдствиС ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π΅Π³ΠΎ ΠΏΡƒΠ½ΠΊΡ‚Π°: Π² Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡Π°Ρ… часто Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡŽΡ‚ ситуации, Π³Π΄Π΅ ΠΆΠ°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π½Π΅ ΠΌΠΎΠ³ΡƒΡ‚ ΡƒΡ‡Π΅ΡΡ‚ΡŒ всС Π½ΡŽΠ°Π½ΡΡ‹ ΠΈ ограничСния, ΠΈ это ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ Π½Π΅ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ ΠΈΠ»ΠΈ Π΄Π°ΠΆΠ΅ Π½Π΅Π²Π΅Ρ€Π½Ρ‹ΠΌ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡΠΌ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ Π² Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… прилоТСниях ΠΆΠ°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ Π² ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ с Π΄Ρ€ΡƒΠ³ΠΈΠΌΠΈ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π°ΠΌΠΈ.

Π“Π»Π°Π²Π½Ρ‹Π΅ особСнности использования ΠΆΠ°Π΄Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈΠΌΠ΅ΡŽΡ‚ свои ΠΏΠ»ΡŽΡΡ‹ ΠΈ ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ ΠΏΠΎΠ»Π΅Π·Π½Ρ‹ Π² Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… ситуациях, Π½ΠΎ ΠΈΡ… Π²Ρ‹Π±ΠΎΡ€ ΠΈ рСализация Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ Π²Π½ΠΈΠΌΠ°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π°:

  • Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Ρ…ΠΎΡ€ΠΎΡˆΠΎ подходят для Π·Π°Π΄Π°Ρ‡ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ, Π³Π΄Π΅ Π½ΡƒΠΆΠ½ΠΎ Π²Ρ‹Π±ΠΈΡ€Π°Ρ‚ΡŒ самыС Ρ†Π΅Π½Π½Ρ‹Π΅ ΠΎΠΏΡ†ΠΈΠΈ ΠΈΠ· ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ Π½Π°Π±ΠΎΡ€Π° Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ². НапримСр, Π² Π·Π°Π΄Π°Ρ‡Π΅ ΠΎ Ρ€ΡŽΠΊΠ·Π°ΠΊΠ΅ ΠΈΠ»ΠΈ Π·Π°Π΄Π°Ρ‡Π΅ Π²Ρ‹Π±ΠΎΡ€Π° мСроприятий Π΅ΡΡ‚ΡŒ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½Ρ‹Π΅ элСмСнты, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΠΎΠΆΠ½ΠΎ Π²Ρ‹Π±Ρ€Π°Ρ‚ΡŒ для достиТСния ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π°.
  • РСкурсивноС прСдставлСниС ΠΆΠ°Π΄Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΏΡ€ΠΎΡ‰Π΅ для понимания ΠΈ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ, Π½ΠΎ для ΠΏΠΎΠ²Ρ‹ΡˆΠ΅Π½ΠΈΡ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π΅Π³ΠΎ слСдуСт Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎ.
  • Π–Π°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π½Π΅ всСгда ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΌΡƒ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ, Π½ΠΎ ΠΎΠ½ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΡ€Π΅Π΄ΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Ρ†Π΅Π½Π½Ρ‹Π΅ ΠΈΠ΄Π΅ΠΈ ΠΈ ΠΏΠΎΠΌΠΎΡ‡ΡŒ Π»ΡƒΡ‡ΡˆΠ΅ ΠΏΠΎΠ½ΡΡ‚ΡŒ структуру ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°. Π’Π°ΠΊΠΆΠ΅ ΠΆΠ°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΌΠΎΠΆΠ΅Ρ‚ ΡΠ»ΡƒΠΆΠΈΡ‚ΡŒ Π² качСствС эвристичСского ΠΌΠ΅Ρ‚ΠΎΠ΄Π°, прСдоставляя быстроС ΠΈ достаточно эффСктивноС ΠΏΡ€ΠΈΠ±Π»ΠΈΠΆΠ΅Π½Π½ΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅.
  • Π’ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… случаях Π²Ρ‹Π±ΠΎΡ€ ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎΠ³ΠΎ ΠΆΠ°Π΄Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π½Π΅ΠΎΡ‡Π΅Π²ΠΈΠ΄Π½Ρ‹ΠΌ, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Π·Π°Π΄Π°Ρ‡Ρƒ ΠΌΠΎΠΆΠ½ΠΎ Ρ€Π΅ΡˆΠΈΡ‚ΡŒ нСсколькими ΠΆΠ°Π΄Π½Ρ‹ΠΌΠΈ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π°ΠΌΠΈ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ всСгда Π½ΡƒΠΆΠ½ΠΎ ΠΏΡ€ΠΎΠ²ΠΎΠ΄ΠΈΡ‚ΡŒ Π²Π½ΠΈΠΌΠ°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ Π°Π½Π°Π»ΠΈΠ· Π·Π°Π΄Π°Ρ‡ΠΈ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠ½ΡΡ‚ΡŒ, ΠΊΠ°ΠΊΠΎΠ΅ ΠΈΠ· ΠΆΠ°Π΄Π½Ρ‹Ρ… Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΉ Π±ΡƒΠ΄Π΅Ρ‚ Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠΈΠΌ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ Π·Π°Π΄Π°Ρ‡, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ эффСктивно Ρ€Π΅ΡˆΠ°ΡŽΡ‚ΡΡ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΆΠ°Π΄Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

НСсмотря Π½Π° Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ограничСния ΠΈ нСдостатки ΠΆΠ°Π΄Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², с ΠΈΡ… ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎ Ρ€Π΅ΡˆΠ°Ρ‚ΡŒ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹Ρ… Ρ‚ΠΈΠΏΠΎΠ². Рассмотрим нСсколько ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠ².

ΠžΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅ распрСдСлСниС Π·Π°Π΄Π°Ρ‡

ΠŸΠ΅Ρ€Π΅Π΄ Π½Π°ΠΌΠΈ стоит ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ распрСдСлСния Π·Π°Π΄Π°Ρ‡ ΠΌΠ΅ΠΆΠ΄Ρƒ Ρ€Π°Π±ΠΎΡ‡ΠΈΠΌΠΈ. Условия Ρ‚Π°ΠΊΠΈΠ΅:

  • ΠšΠ°ΠΆΠ΄ΠΎΠΌΡƒ Ρ€Π°Π±ΠΎΡ‡Π΅ΠΌΡƒ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±Ρ‹Ρ‚ΡŒ Π½Π°Π·Π½Π°Ρ‡Π΅Π½ΠΎ Ρ€ΠΎΠ²Π½ΠΎ Π΄Π²Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ.
  • КаТдая Π·Π°Π΄Π°Ρ‡Π° Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ‚ фиксированноС количСство Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ.
  • Π—Π°Π΄Π°Ρ‡ΠΈ нСзависимы, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Π½Π΅Ρ‚ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΠΉ Ρ‚ΠΈΠΏΠ° Β«Π·Π°Π΄Π°Ρ‡Π° 4 Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ‚ Π½Π°Ρ‡Π°Ρ‚ΡŒΡΡ Π΄ΠΎ Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ 3Β».
  • Π›ΡŽΠ±Π°Ρ Π·Π°Π΄Π°Ρ‡Π° ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π½Π°Π·Π½Π°Ρ‡Π΅Π½Π° Π»ΡŽΠ±ΠΎΠΌΡƒ Ρ€Π°Π±ΠΎΡ‡Π΅ΠΌΡƒ.

Π’Ρ€Π΅Π±ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΊ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ ΠΎΠ΄Π½ΠΎ β€” Ρ€Π°ΡΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ задания ΠΌΠ΅ΠΆΠ΄Ρƒ исполнитСлями Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ врСмя Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½ΠΈΡ всСх Π·Π°Π΄Π°Ρ‡.

РСшСниС:

ΠŸΡ€ΠΎΡΡ‚ΠΎΠ΅ пСрСчислСниС всСх Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… ΠΏΠ°Ρ€ Π·Π°Π΄Π°Ρ‡ нСцСлСсообразно ΠΈΠ·-Π·Π° слишком большого количСства ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΉ:

(n2)(nβˆ’22)(nβˆ’42)...(42)(22)=n!/2n/2

ВмСсто этого слСдуСт ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚ΡŒ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π½Π° структуру Π·Π°Π΄Π°Ρ‡ΠΈ. Π’Π°ΠΆΠ½ΠΎ ΡƒΡ‡Π΅ΡΡ‚ΡŒ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ ΠΈ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ значСния, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΈΠΌΠ΅Π΅Ρ‚ смысл ΡΠΎΡ‡Π΅Ρ‚Π°Ρ‚ΡŒ Π·Π°Π΄Π°Ρ‡ΠΈ с большСй ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ с Π·Π°Π΄Π°Ρ‡Π°ΠΌΠΈ с мСньшСй ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ. Но это Π½Π΅ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ сводится ΠΊ суммС min ΠΈ ΠΌΠ°Ρ… Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния: Ссли Ρƒ нас Π΅ΡΡ‚ΡŒ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ 1, 8, 9 ΠΈ 10 часов, ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ выполнСния всСх Ρ€Π°Π±ΠΎΡ‚ Π±ΡƒΠ΄Π΅Ρ‚ Π½Π΅ 1 + 10, Π° 8 + 9 часов. Π’ΠΎ Π΅ΡΡ‚ΡŒ вмСсто простого суммирования наибольшСго ΠΈ наимСньшСго значСния Π½ΡƒΠΆΠ½ΠΎ:

  • ΠžΡ‚ΡΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π·Π°Π΄Π°Ρ‡.
  • Π‘ΠΎΡ‡Π΅Ρ‚Π°Ρ‚ΡŒ ΡΠ°ΠΌΡƒΡŽ ΠΊΠΎΡ€ΠΎΡ‚ΠΊΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ с самой Π΄Π»ΠΈΠ½Π½ΠΎΠΉ, Π²Ρ‚ΠΎΡ€ΡƒΡŽ ΡΠ°ΠΌΡƒΡŽ ΠΊΠΎΡ€ΠΎΡ‚ΠΊΡƒΡŽ β€” со Π²Ρ‚ΠΎΡ€ΠΎΠΉ самой Π΄Π»ΠΈΠ½Π½ΠΎΠΉ ΠΈ Ρ‚.Π΄.
  • Π’Ρ‹Π±Ρ€Π°Ρ‚ΡŒ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ элСмСнт ΠΈΠ· Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚ΠΈΡ€ΡƒΡŽΡ‰Π΅Π³ΠΎ списка.

ΠŸΡ€Π΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ, Π΅ΡΡ‚ΡŒ 6 Π·Π°Π΄Π°Ρ‡ с ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ 5, 2, 1, 6, 4 ΠΈ 4 часа. ΠžΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅ распрСдСлСниС Π±ΡƒΠ΄Π΅Ρ‚ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ:

  • ΠŸΠ΅Ρ€Π²ΠΎΠΌΡƒ Ρ€Π°Π±ΠΎΡ‡Π΅ΠΌΡƒ β€” Π·Π°Π΄Π°Ρ‡ΠΈ с ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ 1 ΠΈ 6.
  • Π’Ρ‚ΠΎΡ€ΠΎΠΌΡƒ Ρ€Π°Π±ΠΎΡ‡Π΅ΠΌΡƒ β€” Π·Π°Π΄Π°Ρ‡ΠΈ с ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ 2 ΠΈ 5.
  • Π’Ρ€Π΅Ρ‚ΡŒΠ΅ΠΌΡƒ Ρ€Π°Π±ΠΎΡ‡Π΅ΠΌΡƒ β€” Π·Π°Π΄Π°Ρ‡ΠΈ с ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ 4 ΠΈ 4.

ΠŸΡ€ΠΈ Ρ‚Π°ΠΊΠΎΠΌ распрСдСлСнии всС Π·Π°Π΄Π°Ρ‡ΠΈ Π±ΡƒΠ΄ΡƒΡ‚ Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½Ρ‹ Ρ‡Π΅Ρ€Π΅Π· max(1 + 6, 2 + 5, 4 + 4) = 8 часов:

import collections

PairedTasks = collections.namedtuple('PairedTasks', ('task_1', 'task_2'))

def optimum_task_assignment(task_durations):
    task_durations.sort()
    return [
        PairedTasks(task_durations[i], task_durations[~i])
        for i in range(len(task_durations) // 2)
    ]

tasks = [5, 2, 1, 6, 4, 4]
assignment = optimum_task_assignment(tasks)
for i, pair in enumerate(assignment):
    print(f'Π˜ΡΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒ {i + 1}: Π—Π°Π΄Π°Ρ‡Π° 1 ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ {pair.task_1} Ρ‡ ΠΈ Π—Π°Π΄Π°Ρ‡Π° 2 ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ  {pair.task_2} Ρ‡.')
print(f'ВсС Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π±ΡƒΠ΄ΡƒΡ‚ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½Ρ‹ Π·Π° {max(assignment)[0] + max(assignment)[1]} Ρ‡.')

Π’Ρ‹Π²ΠΎΠ΄:

Π˜ΡΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒ 1: Π—Π°Π΄Π°Ρ‡Π° 1 ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ 1 Ρ‡ ΠΈ Π—Π°Π΄Π°Ρ‡Π° 2 ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ  6 Ρ‡.
Π˜ΡΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒ 2: Π—Π°Π΄Π°Ρ‡Π° 1 ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ 2 Ρ‡ ΠΈ Π—Π°Π΄Π°Ρ‡Π° 2 ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ  5 Ρ‡.
Π˜ΡΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒ 3: Π—Π°Π΄Π°Ρ‡Π° 1 ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ 4 Ρ‡ ΠΈ Π—Π°Π΄Π°Ρ‡Π° 2 ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ  4 Ρ‡.
ВсС Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π±ΡƒΠ΄ΡƒΡ‚ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½Ρ‹ Π·Π° 8 Ρ‡.

Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ этого Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ β€” O(n log n), Π³Π΄Π΅ n β€” количСство Π·Π°Π΄Π°Ρ‡, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ основноС врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ‚ сортировка.

πŸ’» Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° программиста
Π‘ΠΎΠ»ΡŒΡˆΠ΅ ΠΏΠΎΠ»Π΅Π·Π½Ρ‹Ρ… ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»ΠΎΠ² Π²Ρ‹ Π½Π°ΠΉΠ΄Π΅Ρ‚Π΅ Π½Π° нашСм Ρ‚Π΅Π»Π΅Π³Ρ€Π°ΠΌ-ΠΊΠ°Π½Π°Π»Π΅ Β«Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° программиста»

РасписаниС для ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ оТидания

Π’ этой Π·Π°Π΄Π°Ρ‡Π΅ трСбуСтся ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΎΠ±Ρ‰Π΅Π΅ врСмя оТидания запросов ΠΊ Π±Π°Π·Π΅ Π΄Π°Π½Π½Ρ‹Ρ…, учитывая Π·Π°Ρ€Π°Π½Π΅Π΅ извСстноС врСмя обслуТивания ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ запроса. Запросы Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Π°Π½Ρ‹ ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΌΡƒ Π·Π° Ρ€Π°Π· ΠΈ ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½Ρ‹ Π² любом порядкС. ВрСмя оТидания запроса Π΄ΠΎ Π΅Π³ΠΎ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ называСтся Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ оТидания этого запроса.

Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π½Π°ΠΈΠ²Π½ΠΎΠ³ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ с ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ΠΎΠΌ всСх Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΉ ΠΎΠ³Ρ€ΠΎΠΌΠ½Π° β€” O(n!), Π³Π΄Π΅ n β€” число запросов. Β«Π–Π°Π΄Π½Ρ‹ΠΉΒ» ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ Π² этом случаС Π½Π°ΠΌΠ½ΠΎΠ³ΠΎ эффСктивнСС β€” ΠΎΠ½ Π²ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ Π² сСбя:

  • Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΡƒ запросов ΠΏΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ обслуТивания. ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Π»ΠΎΠ³ΠΈΡ‡Π½ΠΎ ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΠ΅ запросы ΠΏΠ΅Ρ€Π²Ρ‹ΠΌΠΈ, ΠΌΡ‹ сортируСм запросы ΠΏΠΎ ΠΈΡ… Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ обслуТивания. Π­Ρ‚ΠΎ позволяСт Π½Π°ΠΌ ΡƒΠΏΠΎΡ€ΡΠ΄ΠΎΡ‡ΠΈΡ‚ΡŒ запросы Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ запросы с мСньшим Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ обслуТивания Π±Ρ‹Π»ΠΈ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Π°Π½Ρ‹ Ρ€Π°Π½ΡŒΡˆΠ΅.
  • ΠžΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΡƒ запросов Π² порядкС возрастания Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ обслуТивания. ПослС сортировки запросов ΠΌΡ‹ ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Π΅ΠΌ ΠΈΡ… Π² порядкС возрастания Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ обслуТивания. Π­Ρ‚ΠΎ обСспСчиваСт минимальноС ΠΎΠ±Ρ‰Π΅Π΅ врСмя оТидания, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ запрос Π½Π°Ρ‡ΠΈΠ½Π°Π΅Ρ‚ ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒΡΡ сразу послС Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½ΠΈΡ ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π΅Π³ΠΎ запроса с мСньшим ΠΈΠ»ΠΈ Ρ€Π°Π²Π½Ρ‹ΠΌ Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ обслуТивания.

ΠŸΡ€Π΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ, Ρƒ нас Π΅ΡΡ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ ΠΏΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΠΈ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ обслуТивания запросов: (2, 5, 1, 3). Если ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ запросы Π² порядкС, ΡƒΠΊΠ°Π·Π°Π½Π½ΠΎΠΌ Π² спискС, Ρ‚ΠΎ ΠΎΠ±Ρ‰Π΅Π΅ врСмя оТидания Π±ΡƒΠ΄Π΅Ρ‚ Ρ€Π°Π²Π½ΠΎ 0 + (2) + (2 + 5) + (2 + 5 + 1) = 17. ΠŸΡ€ΠΈ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ запросов Π² порядкС убывания Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ обслуТивания ΠΎΠ±Ρ‰Π΅Π΅ врСмя оТидания увСличиваСтся Π΄ΠΎ 0 + (5) + (5 + 3) + (5 + 3 + 2) = 23. Но Ссли Ρ€Π°ΡΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚ΡŒ ΠΏΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΠΈ ΠΏΠΎ Π²ΠΎΠ·Ρ€Π°ΡΡ‚Π°Π½ΠΈΡŽ для примСнСния ΠΆΠ°Π΄Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ самоС ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅ врСмя ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ 0 + (1) + (1 + 2) + (1 + 2 + 3) = 10:

def minimum_total_waiting_time(service_times):
    service_times.sort()
    
    total_waiting_time = 0
    for i, service_time in enumerate(service_times):
        num_remaining_queries = len(service_times) - (i + 1)
        total_waiting_time += service_time * num_remaining_queries
    
    return total_waiting_time

service_times = [2, 5, 1, 3]
print(minimum_total_waiting_time(service_times))

Π’Ρ‹Π²ΠΎΠ΄:

10

Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ этого Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ опрСдСляСтся Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ, Π·Π°Ρ‚Ρ€Π°Ρ‡Π΅Π½Π½Ρ‹ΠΌ Π½Π° сортировку, ΠΈ составляСт O(n log n).

Π—Π°Π΄Π°Ρ‡Π° покрытия ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»ΠΎΠ²

Π­Ρ‚Π° Π·Π°Π΄Π°Ρ‡Π° Π·Π°ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠΌΠΎΡ‡ΡŒ мастСру ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ количСство посСщСний производствСнного Ρ†Π΅Ρ…Π° для ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ Ρ…ΠΎΠ΄Π° выполнСния Ρ€Π°Π±ΠΎΡ‚. КаТдая Π·Π°Π΄Π°Ρ‡Π° начинаСтся ΠΈ заканчиваСтся Π² ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ΅ врСмя. ΠœΠ°ΡΡ‚Π΅Ρ€ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΠΎΡΠ΅Ρ‚ΠΈΡ‚ΡŒ Ρ†Π΅Ρ… Π² любой ΠΌΠΎΠΌΠ΅Π½Ρ‚ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ ΠΈ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ всС Π·Π°Π΄Π°Ρ‡ΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΈΠ΄ΡƒΡ‚ Π² этот ΠΌΠΎΠΌΠ΅Π½Ρ‚. НСобходимо Π½Π°ΠΉΡ‚ΠΈ минимальноС количСство посСщСний, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ‚ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ всС Π·Π°Π΄Π°Ρ‡ΠΈ.

Для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΈΡ‚ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ ΠΆΠ°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ:

  • Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»ΠΎΠ². Π‘Π½Π°Ρ‡Π°Π»Π° Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΡ‚ΡΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ всС ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Ρ‹ ΠΏΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ окончания. Π­Ρ‚ΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ‚ ΡΠΎΡΡ€Π΅Π΄ΠΎΡ‚ΠΎΡ‡ΠΈΡ‚ΡŒΡΡ Π½Π° Π·Π°Π΄Π°Ρ‡Π°Ρ…, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π·Π°ΠΊΠ°Π½Ρ‡ΠΈΠ²Π°ΡŽΡ‚ΡΡ Ρ€Π°Π½ΡŒΡˆΠ΅.
  • Π’Ρ‹Π±ΠΎΡ€ ΠΊΡ€Π°ΠΉΠ½ΠΈΡ… Ρ‚ΠΎΡ‡Π΅ΠΊ. ПослС сортировки ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»ΠΎΠ² выбираСтся врСмя окончания ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Π° Π² отсортированном спискС. Π­Ρ‚ΠΎ врСмя становится ΠΎΠ΄Π½ΠΈΠΌ ΠΈΠ· ΠΌΠΎΠΌΠ΅Π½Ρ‚ΠΎΠ² посСщСния мастСра.
  • Поиск ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π³ΠΎ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Π°. Π”Π°Π»Π΅Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΈΡ‰Π΅Ρ‚ ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π», ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π½Π΅ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ ΡƒΠΆΠ΅ Π²Ρ‹Π±Ρ€Π°Π½Π½Ρ‹ΠΌΠΈ ΠΌΠΎΠΌΠ΅Π½Ρ‚Π°ΠΌΠΈ посСщСния. Как Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚Π°ΠΊΠΎΠΉ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π» Π½Π°ΠΉΠ΄Π΅Π½, Π΅Π³ΠΎ врСмя окончания Ρ‚Π°ΠΊΠΆΠ΅ выбираСтся Π² качСствС ΠΌΠΎΠΌΠ΅Π½Ρ‚Π° посСщСния.
  • ΠŸΠΎΠ²Ρ‚ΠΎΡ€Π΅Π½ΠΈΠ΅ процСсса. ΠžΠΏΠΈΡΠ°Π½Π½Ρ‹ΠΉ Π²Ρ‹ΡˆΠ΅ этапы ΠΏΠΎΠ²Ρ‚ΠΎΡ€ΡΡŽΡ‚ΡΡ, ΠΏΠΎΠΊΠ° Π½Π΅ Π±ΡƒΠ΄ΡƒΡ‚ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚Ρ‹ всС ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Ρ‹.

ΠŸΡ€Π΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ, Ρƒ нас Π΅ΡΡ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Ρ‹ Π·Π°Π΄Π°Ρ‡: [(1,2), (2,3), (3,4), (2,3), (4,5)]. ПослС сортировки ΠΏΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ окончания ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»ΠΎΠ² ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ: [(1,2), (2,3), (2,3), (3,4), (4,5)]. ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ Π²Ρ‹Π±Ρ€Π°Π½Π½Ρ‹ΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚ посСщСния β€” это врСмя окончания ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Π°, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ 2. Π­Ρ‚ΠΎΡ‚ ΠΌΠΎΠΌΠ΅Π½Ρ‚ ΠΏΠΎΠΊΡ€Ρ‹Π²Π°Π΅Ρ‚ ΠΏΠ΅Ρ€Π²Ρ‹Π΅ Ρ‚Ρ€ΠΈ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Π°. Π”Π°Π»Π΅Π΅ ΠΈΡ‰Π΅ΠΌ ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π», ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π½Π΅ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ 2, ΠΈ Π½Π°Ρ…ΠΎΠ΄ΠΈΠΌ Π΅Π³ΠΎ β€” это (3,4). Π’Ρ‹Π±ΠΈΡ€Π°Π΅ΠΌ врСмя Π΅Π³ΠΎ окончания, 4, Π² качСствС ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π³ΠΎ ΠΌΠΎΠΌΠ΅Π½Ρ‚Π° посСщСния. Π­Ρ‚ΠΎ ΠΏΠΎΠΊΡ€Ρ‹Π²Π°Π΅Ρ‚ ΠΎΡΡ‚Π°Π²ΡˆΠΈΠ΅ΡΡ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Ρ‹.

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, минимальноС количСство посСщСний для ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ всСх Π·Π°Π΄Π°Ρ‡ составляСт 2 (Π² ΠΌΠΎΠΌΠ΅Π½Ρ‚Ρ‹ 2 ΠΈ 4):

import collections
import operator

Interval = collections.namedtuple('Interval', ['left', 'right'])

def find_minimum_visits(intervals):
    intervals.sort(key=operator.attrgetter('right'))
    last_visit_time, num_visits = float('-inf'), 0
    for interval in intervals:
        if interval.left > last_visit_time:
            last_visit_time = interval.right
            num_visits += 1
    return num_visits


intervals = [
    Interval(1, 2),
    Interval(2, 3),
    Interval(3, 4),
    Interval(2, 3),
    Interval(4, 5)
]

print(find_minimum_visits(intervals)) 

Π’Ρ‹Π²ΠΎΠ΄:

2

Π”Ρ€ΡƒΠ³ΠΎΠΉ способ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ:

def min_points_cover_intervals(intervals):
    sorted_intervals = sorted(intervals, key=lambda x: x[1])
    points = []
    while sorted_intervals:
        point = sorted_intervals[0][1]
        points.append(point)
        sorted_intervals = [interval for interval in sorted_intervals if not(interval[0] <= point <= interval[1])]
    
    return points

intervals = [(1, 2), (2, 3), (3, 4), (2, 3), (4, 5)]
result = min_points_cover_intervals(intervals)
print(f"МинимальноС количСство посСщСний: {len(result)}, Π² ΠΌΠΎΠΌΠ΅Π½Ρ‚Ρ‹: {result}")  

Π’Ρ‹Π²ΠΎΠ΄:

МинимальноС количСство посСщСний: 2, Π² ΠΌΠΎΠΌΠ΅Π½Ρ‚Ρ‹: [2, 4]

ВрСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ этого Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ опрСдСляСтся сортировкой ΠΈ Ρ€Π°Π²Π½Π° O(n log n).

ПодвСдСм ΠΈΡ‚ΠΎΠ³ΠΈ

Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‚ собой ΠΌΠΎΡ‰Π½Ρ‹ΠΉ ΠΈ эффСктивный ΠΌΠ΅Ρ‚ΠΎΠ΄ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹Ρ… ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΎΠ½Π½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡. Π˜Ρ… Π³Π»Π°Π²Π½Ρ‹Π΅ прСимущСства β€” простота Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ ΠΈ высокая ΡΠΊΠΎΡ€ΠΎΡΡ‚ΡŒ Ρ€Π°Π±ΠΎΡ‚Ρ‹. Π₯отя ΠΆΠ°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π½Π΅ ΡƒΠ½ΠΈΠ²Π΅Ρ€ΡΠ°Π»ΡŒΠ½Ρ‹ ΠΈ Π½Π΅ всСгда приводят ΠΊ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΌΡƒ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ, ΠΎΠ½ΠΈ слуТат ΠΎΡ‚Π»ΠΈΡ‡Π½ΠΎΠΉ ΠΎΡ‚ΠΏΡ€Π°Π²Π½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠΎΠΉ для Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ Π±ΠΎΠ»Π΅Π΅ слоТных Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², Π° Π² Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… случаях ΠΌΠΎΠ³ΡƒΡ‚ ΠΏΡ€Π΅Π΄ΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ достаточно Ρ…ΠΎΡ€ΠΎΡˆΠ΅Π΅ ΠΏΡ€ΠΈΠ±Π»ΠΈΠΆΠ΅Π½Π½ΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅.

***

Π‘Ρ‚Π°Ρ‚ΡŒΠΈ ΠΏΠΎ Ρ‚Π΅ΠΌΠ΅

Π›Π£Π§Π¨Π˜Π• БВАВЬИ ПО Π’Π•ΠœΠ•

admin
18 июля 2019

ЛогичСскиС Π·Π°Π΄Π°Ρ‡ΠΈ: 15 ΡƒΠΏΡ€Π°ΠΆΠ½Π΅Π½ΠΈΠΉ для Ρ‚Ρ€Π΅Π½ΠΈΡ€ΠΎΠ²ΠΊΠΈ ΠΌΠΎΠ·Π³Π°

ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡΡ‚Π°ΠΌ Π±Π΅Π· Π»ΠΎΠ³ΠΈΠΊΠΈ Π½ΠΈΠΊΡƒΠ΄Π°. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ врСмя ΠΏΡ€ΠΎΠΊΠ°Ρ‡Π°Ρ‚ΡŒ ΠΌΠΎΠ·Π³: ΠΏΡ€ΠΎΠ²Π΅Ρ€ΡŒΡ‚Π΅ св...
admin
11 дСкабря 2018

ООП Π½Π° Python: ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΠΈ, ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΡ‹ ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ

ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π½Π° Python допускаСт Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ»ΠΎΠ³ΠΈΠΈ, Π½ΠΎ Π² Π΅Π³ΠΎ основС...
admin
20 октября 2016

27 сайтов с Π·Π°Π΄Π°Ρ‡ΠΊΠ°ΠΌΠΈ для оттачивания Π½Π°Π²Ρ‹ΠΊΠΎΠ² программирования

<strong>РСшСниС Π·Π°Π΄Π°Ρ‡ β€” Ρ…ΠΎΡ€ΠΎΡˆΠΈΠΉ способ Ρ€Π°Π·Π²ΠΈΡ‚ΡŒ Π½Π°Π²Ρ‹ΠΊΠΈ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ.</strong>