在 Python 中查找最大 N,使得前 N 个自然数的平方和不超过 X

pythonserver side programmingprogramming更新于 2025/10/10 16:44:17

假设我们有一个给定的整数 X,我们必须找到最大值 N,使得前 N 个自然数的平方和不超过值 X。

因此,如果输入为 X = 7,则输出将为 2,因为 2 是 N 的最大可能值,对于 N = 3,系列的总和将超过 X = 7,因此,1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14。

为了解决这个问题,我们将遵循以下步骤 −

  • 定义一个函数 sum_of_squares()。这将需要 N

  • res :=(N *(N + 1) *(2 * N + 1)) / 6

  • 返回 res

  • 从主方法中,执行以下操作 −

  • low := 1

  • high := 100000

  • N := 0

  • 当 low −= high 时,执行

    • mid :=(high + low) / 2

    • 如果 sum_of_squares(mid) −= X,则

      • N := mid

      • low := mid + 1

    • 否则,

      • high := mid - 1

  • 返回 N

示例

让我们看看下面的实现以便更好地理解 −

def sum_of_squares(N):
   res = (N * (N + 1) * (2 * N + 1)) // 6
   return res
def get_max(X):
   low, high = 1, 100000
   N = 0
   while low <= high:
      mid = (high + low) // 2
      if sum_of_squares(mid) <= X:
         N = mid
         low = mid + 1
      else:
         high = mid - 1
   return N
X = 7
print(get_max(X))

输入

7

Output

2

相关文章


有用资源