Как ускорить алгоритм? Доброе время суток.
У меня вот такая задача: дано две точки А(х1, х2) и В(у1, у2), они соединены с началом координат О(0,0) и между собой образуя треугольник АВО. Нужно найти сколько будет таких прямоугольных треугольников удовлетворяющих условию: 0 <= x1, x2, y1, y2 <= N
Вот что у меня вышло, но мне за это стыдно(def prod(A, B):
return A[0]*B[0] + A[1]*B[1]
def check_triangle(x1, x2, y1, y2):
OX = (x1, x2)
OY = (y1, y2)
XY = (y1 - x1, y2 - x2)
sides = sorted([prod(OX, OX), prod(OY, OY), prod(XY,XY)], reverse = True)
if sides[0] == sides[1] + sides[2] and not 0 in sides:
return sides
n = int(input()) + 1
def right_triangles(n):
triangles = [[x1, x2, y1, y2] for x1 in range(n) for x2 in range(n) for y1 in range(n) for y2 in range(n) if check_triangle(x1, x2, y1, y2)]
return len(triangles) // 2
print (right_triangles(n))
Есть идеи как сделать это быстрее? Буду очень благодарен за помощь.
UPD. Координаты целые числа
Как ускорить алгоритм? Доброе время суток.
У меня вот такая задача: дано две точки А(х1, х2) и В(у1, у2), они соединены с началом координат О(0,0) и между собой образуя треугольник АВО. Нужно найти сколько будет таких прямоугольных треугольников удовлетворяющих условию: 0 <= x1, x2, y1, y2 <= N
Вот что у меня вышло, но мне за это стыдно(def prod(A, B):
return A[0]*B[0] + A[1]*B[1]
def check_triangle(x1, x2, y1, y2):
OX = (x1, x2)
OY = (y1, y2)
XY = (y1 - x1, y2 - x2)
sides = sorted([prod(OX, OX), prod(OY, OY), prod(XY,XY)], reverse = True)
if sides[0] == sides[1] + sides[2] and not 0 in sides:
return sides
n = int(input()) + 1
def right_triangles(n):
triangles = [[x1, x2, y1, y2] for x1 in range(n) for x2 in range(n) for y1 in range(n) for y2 in range(n) if check_triangle(x1, x2, y1, y2)]
return len(triangles) // 2
print (right_triangles(n))
Есть идеи как сделать это быстрее? Буду очень благодарен за помощь.
UPD. Координаты целые числа
У меня вот такая задача: дано две точки А(х1, х2) и В(у1, у2), они соединены с началом координат О(0,0) и между собой образуя треугольник АВО. Нужно найти сколько будет таких прямоугольных треугольников удовлетворяющих условию: 0 <= x1, x2, y1, y2 <= N
Вот что у меня вышло, но мне за это стыдно(def prod(A, B):
return A[0]*B[0] + A[1]*B[1]
def check_triangle(x1, x2, y1, y2):
OX = (x1, x2)
OY = (y1, y2)
XY = (y1 - x1, y2 - x2)
sides = sorted([prod(OX, OX), prod(OY, OY), prod(XY,XY)], reverse = True)
if sides[0] == sides[1] + sides[2] and not 0 in sides:
return sides
n = int(input()) + 1
def right_triangles(n):
triangles = [[x1, x2, y1, y2] for x1 in range(n) for x2 in range(n) for y1 in range(n) for y2 in range(n) if check_triangle(x1, x2, y1, y2)]
return len(triangles) // 2
print (right_triangles(n))
Есть идеи как сделать это быстрее? Буду очень благодарен за помощь.
UPD. Координаты целые числа
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для ускорения алгоритма можно попробовать следующие оптимизации:
Использовать множества для хранения уже проверенных треугольников, чтобы избежать повторных проверок.
Оптимизировать функцию check_triangle - вместо вычисления произведения можно сразу же сравнивать квадраты длин сторон треугольника, это ускорит процесс.
Можно не перебирать все возможные координаты (x1, x2, y1, y2) в диапазоне от 0 до N, а ограничиться только теми значениями, при которых сумма квадратов координат не превышает N^2.
Можно использовать симметрию относительно осей OX и OY, чтобы сократить количество проверок.
Использовать параллельные вычисления (многопоточность) для ускорения работы алгоритма.
Попробуйте внести эти изменения в ваш код и посмотреть, насколько это улучшит скорость выполнения. Если у вас останутся сложности, не стесняйтесь задавать вопросы.