Требуется найти максимальную сумму квадратов двух натуральных чисел, которая будет близка(или равна) к заданному числу.
Примеры:
20 -> 20 т.к. (42 + 22)
50 -> 50 т.к. (52 + 52 или 72 + 12)
30 -> 29 т.к. (52 + 22)
Не пойму, почему моя программа неверна.
res = int((N)**0.5)
res1 = int(((N-res**2)**0.5))
print(res**2+res1**2)
Ответ
Ваше решение неверное так как int(N**.5)**2 не обязан быть одним из слагаемых в сумме. К примеру, 18 = 32 + 32, а ваше решение возвращает 17 = 42 + 12 для N=18 (17 < 18 поэтому это не является наибольшей суммой квадратов чисел близких к N).
Помимо перебора, можно построить решение на основе теоремы о сумме двух квадратов, из которой следуют разрешённые варианты разложения числа на простые множители — целое число m > 1 является суммой квадратов тогда и только тогда когда у него нет простых множителей вида 4*n+3 в нечётной степени:
def is_sum_of_two_squares(m):
p = 2
while m > 1:
multiplicity = 0
while m % p == 0: # found prime factor
multiplicity += 1
m //= p
if multiplicity & 1: # odd power
if p % 4 == 3: # 4*n+3 form
return False
p += 1
return True
Имея способ определить является ли натуральное число суммой квадратов, можно найти наибольшую сумму близкую к числу, перебирая рядом стоящие числа (от близких к далёким, от больших к маленьким числам):
def max_sum_of_two_squares_nearest(m):
for i in range(m + 1):
if is_sum_of_two_squares(m + i):
return m + i
elif is_sum_of_two_squares(m - i):
return m - i
assert 0
Пример:
for m in range(21):
print(m, "->", max_sum_of_two_squares_nearest(m))
Результат
0 -> 0
1 -> 1
2 -> 2
3 -> 4
4 -> 4
5 -> 5
6 -> 5
7 -> 8
8 -> 8
9 -> 9
10 -> 10
11 -> 10
12 -> 13
13 -> 13
14 -> 13
15 -> 16
16 -> 16
17 -> 17
18 -> 18
19 -> 20
20 -> 20
Комментариев нет:
Отправить комментарий