@AnanasMaks

Найдите все пифагоровы тройки, в которых все числа находятся в диапазоне [1; 5000]?

Пифагоровой тройка назовём тройку чисел (a, b, c), такую что a ≤ b ≤ с и a2+b2=c2. Найдите все пифагоровы тройки, в которых все числа находятся в диапазоне [1; 5000]. Запишите в ответе количество подходящих троек, а затем – значение c для тройки, в которой сумма a+b+c максимальна.
Помогите пожалуйста, код нужен на python, в ответе к заданию (5681 4988)
  • Вопрос задан
  • 342 просмотра
Пригласить эксперта
Ответы на вопрос 4
@Vindicar
Не пойму почему делаете так. Можно куда проще.
Можно сгенерировать список квадратов чисел:
squares = [i*i for i in range(1, 5001)]
При этом индекс элемента в списке i всегда будет на один меньше, чем число, чей квадрат находится по индексу i.
Теперь задача переформулируется таким образом: найти все пары чисел из этого списка, сумма которых тоже в этом списке.
for a,a2 in enumerate(squares, 1):
  for b,b2 in enumerate(squares[a:], a+1):
    if (a2+b2) in squares:
      c = squares.index(a2+b2) + 1
      print(a,b,c)

Работает не очень быстро, но работает.

EDIT: можно резко ускорить код, если учесть следующее: нам не обязательно искать сумму во всем списке. Мы знаем, что сумма будет больше чем b^2, т.е. будет иметь индекс больше чем b. Также мы знаем, что a^2 + b^2 < (a+b)^2, т.е. сумма будет иметь индекс меньше чем a+b. Отсюда:

for a,a2 in enumerate(squares, 1):
  for b,b2 in enumerate(squares[a:], a+1):
    if (a2+b2) in squares[b+1:a+b]:
      c = squares.index(a2+b2) + 1
      print(a,b,c)
Ответ написан
Комментировать
trapwalker
@trapwalker Куратор тега Python
Программист, энтузиаст
Начните с самого простого не оптимизированного решения:
Вам нужно перебрать все целые A от 1 до 5000. Для каждого такого A вы можете перебрать все целые B от A+1 до 5000. Если корень из суммы их квадратов - целое число, то это, очевидно, тройка пифагора. Но вам нужно, чтобы C было меньше или равно 5000.
Для отимизации вы можете не спешить извлекать корень, а сперва проверить его на превышение 5000*"2. Так вы немного сэкономите. Ещё вы каждый раз можете вычислять правую границу внутреннего цикла, так вы будете искать решение среди вдвое меньшего количества вариантов.
Не знаю какие там требования сейчас по эффективности решения задачь, но для школьников такое решение я бы считал приемлемым. Да и не для школьников. Хотя н апитоне такая задача будет считаться с десяток секунд без оптимизаций. Однако временнЫе ограничения не были озвучены. Эдак и методом Монтекарло можно решать=)
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
в википедии есть статья про пифагоровы тройки.
там приведена "формула евклида".
по ней можно быстро и беспощадно нагенерить примитивные тройки, которые потом ещё домножать на 2, 3, 4,...

https://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%84%D...
Ответ написан
@alexbprofit
Junior SE
# Брютфорс, найдите решение пооптимальнее
def get_all_thriads(size):
  res = []
  for i in range(1, size):
    for j in range(1, size):
      for k in range(1, size):
        if i**2 + j**2 == k**2:
          res.append([i, j, k])
  return res

# Тест (возможно наличие одинаковых троек но в разном порядке)
x = [print(el) for el in get_all_thriads(100)]
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы