数据结构
网络
关系数据库管理系统 (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 次浏览
广告