Поиск максимальной суммы квадратов чисел

#python #алгоритм #поиск

Требуется найти максимальную сумму квадратов двух натуральных чисел, которая будет
близка(или равна) к заданному числу.  

Примеры: 


  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)

    

Ответы

Ответ 1

Ваше решение неверное так как 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


Ответ 2

Ваша программа неверна потому что она рассматривает только один случай. Так, 89 =
64 + 25 но ваша программа найдет только 85 = 81 + 4.

Вместо "жадного" выбора первого числа по формуле int((N)**0.5) правильнее будет перебрать
все варианты от 0 до int((N)**0.5) и выбрать среди них наилучший. Формулу для второго
числа можете оставить ту же самую.


Ответ 3

Вот моё решение на Питоне, перебирает меньшее из двух чисел в отрезке [1, sqrt(n)]
а второе вычисляет по формуле, находит все ответы для максимальной из найденных сумм,
для максимального числа 10^9 отрабатывает алгоритм мгновенно.

Вот код на Питоне, можно запустить онлайн:

n = 1000000000
sqrt_n = int(n ** 0.5)
max_sum = 0
result = []

for i in range(1, sqrt_n + 1):
    j = int((n - i * i) ** 0.5)
    if j < i:
        break
    s = i * i + j * j
    if (s > max_sum):
        max_sum = s
        result = []        
    if (s == max_sum):
        result.append((i, j))

print(max_sum, result)


Вот какой вывод для примера 10^9:

1000000000 [(1200, 31600), (7696, 30672), (10000, 30000), (18000, 26000), (19920, 24560)]


Ответ 4

Предполагая, что Вам таки не важно(могу ошибаться) в какие именно суммы разложимо
число, предлагаю решение полным перебором до sqrt(N):

from math import sqrt

x = int(input())

def check(x):
  sn = int(sqrt(x))+1
  for i in range(1, sn):
    j = int(sqrt(x - i*i))
    if (i*i+j*j == x):
      # print("{0}^2 + {1}^2".format(i, j))
      return True
  return False

while x > 0:
  if check(x):
      print(x)
      break
  x = x - 1

if x == 0:
  print("Not found\n")



  30
  29
  
  
  
  50
  50
  
  
  
  1000000000
  1200^2 + 31600^2
  1000000000
  (4ms)