πŸ†πŸ‘οΈ Воповая Π·Π°Π΄Π°Ρ‡ΠΊΠ° Π½Π° Stack Overflow: ΠΊΠ°ΠΊ Π½Π°ΠΉΡ‚ΠΈ k ΠΏΡ€ΠΎΠΏΡƒΡ‰Π΅Π½Π½Ρ‹Ρ… чисСл Π² ΠΏΠΎΡ‚ΠΎΠΊΠ΅ Π΄Π°Π½Π½Ρ‹Ρ…

РСшаСм ΠΎΠ΄Π½Ρƒ ΠΈΠ· самых популярных Π½Π° Stack Overflow Π·Π°Π΄Π°Ρ‡ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° свСрки мноТСств, симмСтричСских Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ΠΈ уравнСния k-ΠΉ стСпСни.

πŸ†πŸ‘οΈ Воповая Π·Π°Π΄Π°Ρ‡ΠΊΠ° Π½Π° Stack Overflow: ΠΊΠ°ΠΊ Π½Π°ΠΉΡ‚ΠΈ k ΠΏΡ€ΠΎΠΏΡƒΡ‰Π΅Π½Π½Ρ‹Ρ… чисСл Π² ΠΏΠΎΡ‚ΠΎΠΊΠ΅ Π΄Π°Π½Π½Ρ‹Ρ…

ΠŸΡ€Π΅Π΄Ρ‹ΡΡ‚ΠΎΡ€ΠΈΡ этой Π·Π°Π΄Π°Ρ‡ΠΈ ΠΈΠ·Π»ΠΎΠΆΠ΅Π½Π° Π² ΠΏΠ΅Ρ€Π²ΠΎΠΉ части, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΌΡ‹ рассмотрСли нСсколько Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ для k = 1, 2 ΠΈ 3, ΠΈ выяснили, Ρ‡Ρ‚ΠΎ для ΠΎΠ±Ρ‰Π΅Π³ΠΎ случая ΠΈ для k β‰₯ 4 Π½ΡƒΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π±ΠΎΠ»Π΅Π΅ ΡƒΠ½ΠΈΠ²Π΅Ρ€ΡΠ°Π»ΡŒΠ½Ρ‹ΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄, связанный с симмСтричСскими функциями.

Π’Π°ΠΊΠΈΡ… ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΎΠ² извСстно Π΄Π²Π°, ΠΎΠ±Π° ΠΈΠ·Π»ΠΎΠΆΠ΅Π½Ρ‹ Π² ΠΏΡƒΠ±Π»ΠΈΠΊΠ°Ρ†ΠΈΠΈ Уильяма Π“Π°ΡΠ°Ρ€ΡˆΠ° (pdf), посвящСнной всСм Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹ΠΌ способам вычислСния k ΠΏΡ€ΠΎΠΏΡƒΡ‰Π΅Π½Π½Ρ‹Ρ… чисСл Π² массивах ΠΈ ΠΏΠΎΡ‚ΠΎΠΊΠ°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Π’ ΠΏΠ΅Ρ€Π²ΠΎΠΌ случаС симмСтричСскиС ΠΌΠ½ΠΎΠ³ΠΎΡ‡Π»Π΅Π½Ρ‹ выводятся ΠΈΠ· стСпСнных сумм с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ тоТдСств ΠΡŒΡŽΡ‚ΠΎΠ½Π°, Π° Π²ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΌ случаС симмСтричСскиС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ Π½Π° всСх этапах Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ. Π›ΡŽΠ±ΠΎΠΉ ΠΈΠ· этих Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΡ€Π΅Ρ‚Π΅Π½Π΄ΠΎΠ²Π°Ρ‚ΡŒ Π½Π° Π·Π²Π°Π½ΠΈΠ΅ Ρ‚ΠΎΠ³ΠΎ самого «Бвятого Грааля», ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Ρ…ΠΎΡ‚Π΅Π» Π½Π°ΠΉΡ‚ΠΈ Π°Π²Ρ‚ΠΎΡ€ Ρ‚Π΅ΠΌΡ‹ Π½Π° Stack Overflow, Π½ΠΎ здСсь ΠΌΡ‹ Π±ΡƒΠ΄Π΅ΠΌ Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Ρ‚ΡŒ Π²Ρ‚ΠΎΡ€ΠΎΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄, ΠΊΠ°ΠΊ самый ΠΎΡ€ΠΈΠ³ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹ΠΉ.

«Бвятой Π“Ρ€Π°Π°Π»ΡŒΒ»: aΠ»Π³ΠΎΡ€ΠΈΡ‚ΠΌ свСрки мноТСств

Π“Π°ΡΠ°Ρ€Ρˆ ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ Π΄Π΅Ρ‚Π°Π»ΡŒΠ½ΠΎΠ΅ матСматичСскоС Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ для ΠΎΠ±Ρ‰Π΅Π³ΠΎ случая, основанноС Π½Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ΅ Мински-Π’Ρ€Π°Ρ…Ρ‚Π΅Π½Π±Π΅Ρ€Π³Π°-ЗиппСля. УсловиС Π·Π°Π΄Π°Ρ‡ΠΈ, ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΈ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ дСйствий выглядят Ρ‚Π°ΠΊ:

  • ΠŸΠΎΡ‚ΠΎΠΊ Π΄Π°Π½Π½Ρ‹Ρ… (ΠΈΠ»ΠΈ массив) прСдставляСт собой мноТСство {1, 2...n}, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ всС числа ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½Ρ‹, ΠΈ ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ располоТСны Π² любом порядкС. ΠŸΡ€ΠΈ ΠΏΠ΅Ρ€Π΅Π΄Π°Ρ‡Π΅ мноТСства k чисСл Π±Ρ‹Π»ΠΈ ΠΏΡ€ΠΎΠΏΡƒΡ‰Π΅Π½Ρ‹. ΠžΠ±ΠΎΠ·Π½Π°Ρ‡ΠΈΠΌ ΠΈΡ… y1, y2, ..., yk. НСобходимо Π½Π°ΠΉΡ‚ΠΈ эти числа, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ Π½Π΅ Π±ΠΎΠ»Π΅Π΅ O(k log n) Π±ΠΈΡ‚ΠΎΠ² памяти.
  • Π§Ρ‚ΠΎΠ±Ρ‹ ΡΠΎΠ±Π»ΡŽΡΡ‚ΠΈ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΠ΅ ΠΏΠΎ использованию памяти (ΠΈ Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠΎΡ‚ΠΎΡ‡Π½ΡƒΡŽ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΡƒ), ΠΌΡ‹ вычисляСм симмСтричСскиС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ числа x1, x2, ..., xn-k ΠΏΠΎ ΠΌΠ΅Ρ€Π΅ поступлСния чисСл. По ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΡŽ, s0 всСгда Ρ€Π°Π²Π½Π° 0, s1 прСдставляСт собой сумму чисСл, s2 – сумму ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠΉ всСх Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… ΠΏΠ°Ρ€ чисСл, s3 – сумму ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠΉ всСх ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΉ Ρ‚Ρ€ΠΎΠ΅ΠΊ чисСл ΠΈ Ρ‚Π°ΠΊ Π΄Π°Π»Π΅Π΅. Π’ ΠΈΡ‚ΠΎΠ³Π΅ ΠΌΡ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ Π½Π°Π±ΠΎΡ€ симмСтричСских Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π² Π½ΠΎΡ‚Π°Ρ†ΠΈΠΈ Π“Π°ΡΠ°Ρ€ΡˆΠ° ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ΡΡ s1n-k, s2n-k, s3n-k ΠΈ Ρ‚Π°ΠΊ Π΄Π°Π»Π΅Π΅ (L – Π΄Π»ΠΈΠ½Π° фактичСски ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½ΠΎΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ чисСл, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ n – k).
πŸ†πŸ‘οΈ Воповая Π·Π°Π΄Π°Ρ‡ΠΊΠ° Π½Π° Stack Overflow: ΠΊΠ°ΠΊ Π½Π°ΠΉΡ‚ΠΈ k ΠΏΡ€ΠΎΠΏΡƒΡ‰Π΅Π½Π½Ρ‹Ρ… чисСл Π² ΠΏΠΎΡ‚ΠΎΠΊΠ΅ Π΄Π°Π½Π½Ρ‹Ρ…
  • Зная L ΠΈ k, ΠΌΡ‹ ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ n – Π΄Π»ΠΈΠ½Ρƒ ΠΏΠΎΠ»Π½ΠΎΠΉ числовой ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ. Π­Ρ‚ΠΎ Π΄Π°Π΅Ρ‚ Π½Π°ΠΌ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ симмСтричСскиС суммы для ΠΏΠΎΠ»Π½ΠΎΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ, с ΡƒΡ‡Π΅Ρ‚ΠΎΠΌ всСх чисСл, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΡ€ΠΎΠΏΡƒΡ‰Π΅Π½Ρ‹ Π² фактичСском ΠΏΠΎΡ‚ΠΎΠΊΠ΅ Π΄Π°Π½Π½Ρ‹Ρ…. Π­Ρ‚ΠΈ вычислСния Π΄Π΅Π»Π°ΡŽΡ‚ΡΡ нСзависимо ΠΎΡ‚ Π²Ρ…ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΏΠΎΡ‚ΠΎΠΊΠ°:
  • Π’ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ ΠΌΡ‹ ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ систСму ΡƒΡ€Π°Π²Π½Π΅Π½ΠΈΠΉ, ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΌΠΎΠΆΠ΅ΠΌ вывСсти сумму, ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ ΠΈ суммы ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠΉ всСх Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΉ ΠΏΡ€ΠΎΠΏΡƒΡ‰Π΅Π½Π½Ρ‹Ρ… чисСл, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Ρƒ нас ΡƒΠΆΠ΅ Π΅ΡΡ‚ΡŒ sin , sin-k , s0k , s0nβˆ’k :
  • Π˜Ρ‚ΠΎΠ³ΠΎΠΌ всСх этих манипуляций станСт ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ k-стСпСни. Вычислив Π΅Π³ΠΎ ΠΊΠΎΡ€Π½ΠΈ, ΠΌΡ‹ Π½Π°ΠΉΠ΄Π΅ΠΌ всС ΠΏΡ€ΠΎΠΏΡƒΡ‰Π΅Π½Π½Ρ‹Π΅ числа:
***

Как быстро ΠΎΡΠ²ΠΎΠΈΡ‚ΡŒ ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΡƒ?

Заглядывай Π½Π° наш ΠΎΠ½Π»Π°ΠΉΠ½-курс ΠΏΠΎ ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ΅ для Data Science, Π³Π΄Π΅ Ρ‚Ρ‹ познакомишься с основными модСлями машинного обучСния, Π½Π°ΡƒΡ‡ΠΈΡˆΡŒΡΡ Π²Ρ‹Π±ΠΈΡ€Π°Ρ‚ΡŒ ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ подходящиС tree-based ΠΌΠΎΠ΄Π΅Π»ΠΈ.

ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° занятий:

  • Школьная ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ°: ΠΎΡ‚ Ρ‚Π΅ΠΎΡ€ΠΈΠΈ мноТСств Π΄ΠΎ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄Π½ΠΎΠΉ ΠΈ ΠΈΠ½Ρ‚Π΅Π³Ρ€Π°Π»Π°.
  • ΠœΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΡ‡Π΅ΡΠΊΠΈΠΉ Π°Π½Π°Π»ΠΈΠ·: ΠΎΡ‚ числовых ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚Π΅ΠΉ Π΄ΠΎ Ρ‚Π΅ΠΎΡ€ΠΈΠΈ ΠΌΠ΅Ρ€Ρ‹ ΠΈ ΠΈΠ½Ρ‚Π΅Π³Ρ€Π°Π»Π° Π›Π°ΠΌΠ±Π΅Ρ€Π°.
  • ЛинСйная Π°Π»Π³Π΅Π±Ρ€Π°: ΠΎΡ‚ ΠΌΠ°Ρ‚Ρ€ΠΈΡ† Π΄ΠΎ Π±ΠΈΠ»ΠΈΠ½Π΅ΠΉΠ½Ρ‹Ρ… Ρ„ΠΎΡ€ΠΌ.
  • ΠšΠΎΠΌΠ±ΠΈΠ½Π°Ρ‚ΠΎΡ€ΠΈΠΊΠ°: ΠΏΡ€Π°Π²ΠΈΠ»Π° ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ‚ΠΎΡ€ΠΈΠΊΠΈ, мноТСства ΠΈ сочСтания.
  • ВСория вСроятностСй ΠΈ матСматичСская статистика: ΠΎΡ‚ случайных событий Π΄ΠΎ рСгрСссии.
  • МашинноС ΠΎΠ±ΡƒΡ‡Π΅Π½ΠΈΠ΅: Word2vec, Π³Ρ€Π°Π΄ΠΈΠ΅Π½Ρ‚Π½Ρ‹ΠΉ спуск, KNN ΠΈ Ρ‚. Π΄.
***

РСализация Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π½Π° Python

Ѐункция actual_sums() вычисляСт фактичСскиС симмСтричСскиС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΏΠΎ ΠΌΠ΅Ρ€Π΅ поступлСния чисСл:

def actual_sums(lst, k):
    sums = [0] * (k + 1)
    sums[0] = 1  # s0 ΠΏΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΡŽ Ρ€Π°Π²Π½Π° 1

    for num in lst:
        for j in range(k, 0, -1):
            sums[j] += num * sums[j - 1]

    return sums

Ѐункция complete_sums() Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ нСзависимо ΠΎΡ‚ Π²Ρ…ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΏΠΎΡ‚ΠΎΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ вычисляСт ΠΎΠΆΠΈΠ΄Π°Π΅ΠΌΡ‹Π΅, ΠΏΠΎΠ»Π½Ρ‹Π΅ симмСтричСскиС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ:

def complete_sums(n, k):
    sums = [0] * (k + 1)
    sums[0] = 1  # s0 ΠΏΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΡŽ Ρ€Π°Π²Π½Π° 1

    for i in range(1, n + 1):
        for j in range(k, 0, -1):
            sums[j] += i * sums[j - 1]

    return sums

ΠšΠΎΡΡ„Ρ„ΠΈΡ†ΠΈΠ΅Π½Ρ‚Ρ‹ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ°, ΠΊΠ°ΠΊ ΠΈ ΠΎΠΆΠΈΠ΄Π°Π΅ΠΌΡ‹Π΅/фактичСскиС суммы, Π²Ρ‹Ρ‡ΠΈΡΠ»ΡΡŽΡ‚ΡΡ Ρ€Π΅ΠΊΡƒΡ€Ρ€Π΅Π½Ρ‚Π½ΠΎ:

def compute_coeff(actual, complete, k):
    coeffs = [0] * (k + 1)
    coeffs[0] = 1
    coeffs[1] = complete[1] - actual[1]

    for i in range(2, k + 1):
        coeff = complete[i] - actual[i]
        for j in range(1, i):
            coeff -= actual[j] * coeffs[i - j]
        coeffs[i] = coeff

    return coeffs

К ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρƒ, для числовой ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΏΡ€ΠΎΠΏΡƒΡ‰Π΅Π½ΠΎ 12 чисСл, коэффициСнты ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° Π±ΡƒΠ΄ΡƒΡ‚ Π²Ρ‹Π³Π»ΡΠ΄Π΅Ρ‚ΡŒ Ρ‚Π°ΠΊ:

#lst = [22, 15, 4, 24, 14, 2, 17, 8, 28, 20, 5, 10, 12, 1, 19, 26]
#k = 12

[1, 179, 14336, 678200, 21069782, 451977986, 6849635572, 73706941164, 557311879377, 2877528115395, 9587151599652, 18393142628196, 15226233422400]

Π Π΅ΡˆΠ°Ρ‚ΡŒ Ρ‚Π°ΠΊΠΈΠ΅ уравнСния ΠΏΡ€ΠΎΡ‰Π΅ всСго с NumPy:

import numpy as np

def complete_sums(n, k):
    sums = [0] * (k + 1)
    sums[0] = 1  # s0 ΠΏΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΡŽ Ρ€Π°Π²Π½Π° 1

    for i in range(1, n + 1):
        for j in range(k, 0, -1):
            sums[j] += i * sums[j - 1]

    return sums

def actual_sums(lst, k):
    sums = [0] * (k + 1)
    sums[0] = 1  # s0 ΠΏΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΡŽ Ρ€Π°Π²Π½Π° 1

    for num in lst:
        for j in range(k, 0, -1):
            sums[j] += num * sums[j - 1]

    return sums

def compute_coeff(actual, complete, k):
    coeffs = [0] * (k + 1)
    coeffs[0] = 1
    coeffs[1] = complete[1] - actual[1]

    for i in range(2, k + 1):
        coeff = complete[i] - actual[i]
        for j in range(1, i):
            coeff -= actual[j] * coeffs[i - j]
        coeffs[i] = coeff

    return coeffs

lst = [22, 15, 4, 24, 14, 2, 17, 8, 28, 20, 5, 10, 12, 1, 19, 26]
k = 12
n = len(lst) + k

actual = actual_sums(lst, k)
complete = complete_sums(n, k)
coefficients = compute_coeff(actual, complete, k)
roots = np.roots(coefficients)
print("ΠŸΡ€ΠΎΠΏΡƒΡ‰Π΅Π½Π½Ρ‹Π΅ числа:")
for root in roots:
    print(f"{root* -1:.0f}")

Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚:

ΠŸΡ€ΠΎΠΏΡƒΡ‰Π΅Π½Π½Ρ‹Π΅ числа:
27
25
23
21
18
16
13
11
9
7
6
3

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

Алгоритм свСрки мноТСств позволяСт ΠΎΠ±ΠΎΠΉΡ‚ΠΈΡΡŒ Π±Π΅Π· тоТдСств ΠΡŒΡŽΡ‚ΠΎΠ½Π° ΠΈ чисСл Π‘Π΅Ρ€Π½ΡƒΠ»Π»ΠΈ, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΎΠ½ основан Π½Π° прямом вычислСнии симмСтричСских Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ. ΠžΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Π°Ρ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ достигаСтся Π·Π° счСт Ρ€Π΅ΠΊΡƒΡ€Ρ€Π΅Π½Ρ‚Π½ΠΎΠ³ΠΎ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π°: Π² ΠΏΡ€ΠΎΡ‚ΠΈΠ²Π½ΠΎΠΌ случаС, вычислСниС всСх Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΉ ΠΏΠ°Ρ€, Π΄Π²ΠΎΠ΅ΠΊ, Ρ‚Ρ€ΠΎΠ΅ΠΊ, k-Π½Π°Π±ΠΎΡ€ΠΎΠ² для всСй ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ сразу ΠΏΡ€ΠΈΠ²Π΅Π»ΠΎ Π±Ρ‹ ΠΊ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ слоТности O(nk).

Визуализация Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ для мноТСства {1, 5, 15} ΠΈ k = 12
***

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

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

admin
11 дСкабря 2018

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

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

13 рСсурсов, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π²Ρ‹ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΡƒ

Π‘Ρ€Π΅Π΄ΠΈ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΎΠ² часто Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡŽΡ‚ споры ΠΎ Ρ‚ΠΎΠΌ, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π»ΠΈ ΠΈΠ·ΡƒΡ‡Π°Ρ‚ΡŒ ΠΌΠ°Ρ‚Π΅...
admin
13 фСвраля 2017

ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π½Π° Python: ΠΎΡ‚ Π½ΠΎΠ²ΠΈΡ‡ΠΊΠ° Π΄ΠΎ профСссионала

Пошаговая инструкция для всСх, ΠΊΡ‚ΠΎ Ρ…ΠΎΡ‡Π΅Ρ‚ ΠΈΠ·ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π½Π° Python...