Необходимо найти количество троек чисел (a, b, c) таких, что a2 = b2 + c2, при этом, 10 £ a,b,c £ 99. Известно, что первое число наибольшее, то есть a > b и a > c.
Числа a,b,c должны быть взаимнопростыми, то есть НОД(a,b) = НОД(b,c) = НОД(a,c) = 1.
Для реализации функции НОД (наибольший общий делитель) можно воспользоваться алгоритмом Евклида: брать остаток от деления большего числа на меньшее, пока не будет нулевой остаток. Результатом и будет НОД.
Пример реализации функции НОД на языке программирования Python приведен в листинге 1.2‑1.
Листинг 1.2-1 – Реализация функции НОД на языке программирования Python
##
# поиск НОД для 2-х чисел
# PARAMS
# a - первое число
# b - второе число
# RETURN
# вычисленный НОД
##
def NOD(a: int, b: int):
while a != 0 and b != 0:
if a > b:
a = a % b
else:
b = b % a
return a + b
Общий цикл перебора чисел и поиска требуемых троек на языке программирования Python приведен в листинге 1.2-2.
Листинг 1.2-2 – Реализация цикла перебора на языке программирования Python
# счетчик числа найденных троек
cnt = 0
for a in range(10, 100):
for b in range(10, 100):
for c in range(10, 100):
# условие на первое максимальное число
if a > b and a > c:
# условие на пифагорову тройку
if a * a == b * b + c * c:
# условие на взаимнопростые числа
if NOD(a, b) == 1 and NOD(a, c) == 1 and NOD(b, c) == 1:
print(a, b, c)
cnt += 1 # увеличение счетчика найденных троек
# вывод общего числа троек
print('Total=' + str(cnt))
В результате программа выведет следующие комбинации:
29 20 21
29 21 20
37 12 35
37 35 12
53 28 45
53 45 28
61 11 60
61 60 11
65 16 63
65 33 56
65 56 33
65 63 16
73 48 55
73 55 48
85 13 84
85 36 77
85 77 36
85 84 13
89 39 80
89 80 39
97 65 72
97 72 65
Total=22
Под условия задачи подходит 22 комбинации. Учитывая, что время ввода комбинации 1 секунда и задержка между соседними комбинациями 1 секунда, общее время, требуемое на ввод всех комбинаций T = 22 + 21 = 43 секунды (после ввода последней комбинации нет задержки).