Условие
Дано число \(N\). Найти все пифагоровы тройки такие что \(a + b + c = N\). Пифагоровы тройки удовлетворяют условиям \(a^2 + b^2 = c^2\) и \(a \lt b \lt c\).
Решение
Простейшее решение перебором даёт сложность \(O(n^2)\):
1 2 3 4 5 |
for a in range(n): for b in range(a + 1, n): c = N - a - b if is_triplet(a, b, c): add_result(a, b, c) |
Оптимизации на сокращение перебора в случае когда он дальше не имеет смысла не влияют на порядок роста.
Эту же задачу можно решить за \(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\) находим все пифагоровы тройки.
1 2 3 4 5 6 7 8 9 10 11 |
def triplets_with_sum(number): res = [] n = number for a in range(1, number): b = (2 * a * n - n ** 2) / (2 * a - 2 * n) c = n - b - a if round(b) == b and a < b < c: res.append([a, b, c]) return res |