使用 Python 查詢最大的 N，使得前 N 個自然數的平方和不超過 X

假設我們給定一個整數 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

輸出

2

更新於: 2020年8月25日

144 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告