一个平方金字塔数是指自然数的平方之和。自然数包括从1到无穷大的所有数字。例如，前4个平方金字塔数分别为1、5、14、30。
为了更好地理解，考虑以下事实：如果我们以一开始的平方金字塔数为基础，将数字球堆叠在降序中，它们会形成一个金字塔。
问题陈述
给定一个数Sum。如果Sum是前n个自然数的平方和，返回n，否则返回false。
Example 1
的翻译为：
示例 1
Input = 30
Output = 4
登录后复制
Explanation = 30是前4个自然数的平方和。
1*1 + 2*2 + 3*3 +4*4 = 30.
登录后复制
因此，输出应该是4。
Example 2
Input = 54
Output = -1
登录后复制
Explanation = 没有任何n个自然数的平方和等于54。因此，输出应该是-1。
问题陈述的解决方案
这个问题有两个解决方案。
方法一：暴力解法
暴力破解方法是从n = 1开始。创建一个变量'total'，将下一个自然数的平方加到total的前一个值上。如果total等于Sum，则返回n，否则，如果total大于Sum，则返回false。
伪代码
start
n =1
While (total < sum ):
Total += n*n
n=n+1
if(total == sum) :
Return n
Else:
Return false
end
登录后复制
Example
下面是一个C++程序，用于检查给定的数字是否是自然数的平方数之和。
#include <iostream>
using namespace std;
// This function returns n if the sum of squares of first
// n natural numbers is equal to the given sum
// Else it returns -1
int square_pyramidal_number(int sum) {
// initialize total
int total = 0;
// Return -1 if Sum is <= 0
if(sum <= 0){
return -1;
}
// Adding squares of the numbers starting from 1
int n = 0;
while ( total < sum){
n++;
total += n * n;
}
// If total becomes equal to sum return n
if (total == sum)
return n;
return -1;
}
int main(){
int S = 30;
int n = square_pyramidal_number(S);
cout<< "Number of Square Pyramidal Numbers whose sum is 30: "<< endl;
(n) ? cout << n : cout << "-1";
return 0;
}
登录后复制
输出
Number of Square Pyramidal Numbers whose sum is 30:
4
登录后复制
时间复杂度 - O(sum)，其中sum是给定的输入。
空间复杂度 - O(1)：没有使用额外的空间。
使用牛顿拉弗森方法的方法2
另一种方法是牛顿拉夫逊法。 牛顿拉夫逊法 用于找到给定函数 f(x) 的根和一个根的初始猜测。
sum of squares of first n natural numbers = n * (n + 1) * (2*n + 1) / 6,
n * (n + 1) * (2*n + 1) / 6 = sum or
k * (k + 1) * (2*k + 1) – 6*sum = 0
登录后复制
所以n是这个三次方程的根，可以使用牛顿-拉弗森方法来计算，该方法涉及从初始猜测值x0开始，使用下面的公式来找到下一个值x，即从先前的值xn得到的xn+1。
$$mathrm{x_{1}=x_{0}-frac{f(x_{0})}{f^{'}(x_{0})}}$$
伪代码
Start
calculate func(x) and derivativeFunction(x) for given initial x
Compute h: h = func(x) / derivFunc(x)
While h is greater than allowed error ε
h = func(x) / derivFunc(x)
x = x – h
If (x is an integer):
return x
Else:
return -1;
end
登录后复制
Example
下面是一个C++程序，用于检查一个给定的数字是否是自然数的平方和。
#include<bits/stdc++.h>
#define EPSILON 0.001
using namespace std;
// According to Newton Raphson Method The function is
// k * (k + 1) * (2*k + 1) – 6*sum or 2*k*k*k + 3*k*k + k - 6*sum
double func(double k, int sum){
return 2*k*k*k + 3*k*k + k - 6*sum;
}
// Derivative of the above function is 6*k*k + 6*k + 1
double derivativeFunction(double k){
return 6*k*k + 6*k + 1;
}
// Function to check if double is an integer or not
bool isInteger(double N){
int X = N;
double temp2 = N - X;
if (temp2*10 >=1 ) {
return false;
}
return true;
}
// Function that finds the root of k * (k + 1) * (2*k + 1) – 6*sum
int newtonRaphson(double k, int sum){
double h = func(k, sum) / derivativeFunction(k);
while (abs(h) >= EPSILON){
h = func(k, sum)/derivativeFunction(k);
// k(i+1) = k(i) - f(k) / f'(k)
k = k - h;
}
if (isInteger(k)) {
return (int)k;
}
else {
return -1;
}
}
// Driver program
int main(){
double x0 = 1; // Initial values assumed
int sum = 91;
int n = newtonRaphson(x0,sum);
cout<< "Number of Square Pyramidal Numbers whose sum is 91: "<< endl;
(n) ? cout << n : cout << "-1";
return 0;
}
登录后复制
输出
Number of Square Pyramidal Numbers whose sum is 91:
6
登录后复制
Time Complexity - O((log n) F(n)) where F(n) is the cost of calculating f(x)/f'(x), with n-digit precision.
空间复杂度 - O(1)：没有使用额外的空间。
结论
本文解决了找到给定和的平方金字塔数的问题。我们介绍了两种方法：一种是蛮力方法，另一种是高效方法。这两种方法都提供了C++程序。
以上是平方金字塔数（平方和）的详细内容。更多信息请关注PHP中文网其他相关文章！
