資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在 C++ 中查詢最大的 N，使得前 N 個自然數的平方和不大於 X
概念
對於給定的整數 X，我們的任務是確定最大的 N 值，使得前 N 個自然數的平方和不超過 X。
輸入
X = 7
輸出
2
2 是 N 的最大可能值，因為當 N = 3 時，級數之和將超過 X，即 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14
輸入
X = 27
輸出
3
3 是 N 的最大可能值，因為當 N = 4 時，級數之和將超過 X，即 1^2 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30
方法
簡單解法 − 這裡，一個簡單的解法是從 1 迴圈到最大 N，使得 S(N) ≤ X，其中 S(N) 表示前 N 個自然數的平方和。前 N 個自然數的平方和由公式 S(N) = N * (N + 1) * (2 * N + 1) / 6 給出。
需要注意的是，這種方法的時間複雜度為 O(N)。
高效解法 − 我們可以實現另一種基於二分查詢方法的高效解法。
我們按照以下逐步解釋的演算法：
在較大陣列中開始二分查詢，並將中間值設為 (low + high) / 2
如果兩個陣列的值相同，則元素必須在右側，因此將 low 設為 mid
否則，如果中間元素不相等，則將 high 設為 mid，因為元素必須在較大陣列的左側。
需要注意的是，這種方法的時間複雜度為 O(log N)。
示例
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Shows function to return the sum of the squares
// of first N1 natural numbers
ll squareSum(ll N1){
ll sum1 = (ll)(N1 * (N1 + 1) * (2 * N1 + 1)) / 6;
return sum1;
}
// Shows function to return the maximum N such that
// the sum of the squares of first N
// natural numbers is not more than X
ll findMaxN(ll X){
ll low1 = 1, high1 = 100000;
int N1 = 0;
while (low1 <= high1) {
ll mid1 = (high1 + low1) / 2;
if (squareSum(mid1) <= X) {
N1 = mid1;
low1 = mid1 + 1;
}
else
high1 = mid1 - 1;
}
return N1;
}
// Driver code
int main(){
ll X = 27;
cout << findMaxN(X);
return 0;
}輸出
3
更新於：2020年7月25日
345 次瀏覽
廣告