Задача Pythagorean Triplet

Условие

Дано число \(N\). Найти все пифагоровы тройки такие что \(a + b + c = N\). Пифагоровы тройки удовлетворяют условиям \(a^2 + b^2 = c^2\) и \(a \lt b \lt c\).

Решение

Простейшее решение перебором даёт сложность \(O(n^2)\):

Оптимизации на сокращение перебора в случае когда он дальше не имеет смысла не влияют на порядок роста.

Эту же задачу можно решить за \(O(n)\). Из условий задачи следуют два уравнения:

  • \(a + b + c = N\)
  • \(a^2 + b^2 = c^2\)

\(N\) является константой. Примем так же за константу \(a\). Остаётся система из двух уравнений с двумя неизвестными. Последовательно решаем её.

  • \(c = N - a - b\) (1)
  • \(c^2 - b^2 = a^2\)
  • \((c - b)(c + b) = a^2\) (2)
  • \((n - a - b - b)(n - a - b + b) = a^2\) (подставляем 1 в 2)
  • \((n - a - 2b)(n - a) = a^2\)
  • \(n^2 - an - 2nb - an + a^2 + 2ab = a^2\)
  • \(n^2 - 2an - 2nb + 2ab = 0\)
  • \((2a - 2n)b = 2an - n^2\)
  • \(b = \frac{2an - n^2}{2a - 2n}\)
  • \(c = N - a - b\)

Используя формулы для вычисления \(b\) и \(c\) в цикле по \(a\) находим все пифагоровы тройки.

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *