一个平方金字塔数是指自然数的平方之和。自然数包括从1到无穷大的所有数字。例如，前4个平方金字塔数分别为1、5、14、30。
为了更好地理解，考虑以下事实：如果我们以一开始的平方金字塔数为基础，将数字球堆叠在降序中，它们会形成一个金字塔。
问题陈述给定一个数sum。如果sum是前n个自然数的平方和，返回n，否则返回false。
example 1的翻译为：示例 1input = 30output = 4
explanation = 30是前4个自然数的平方和。
1*1 + 2*2 + 3*3 +4*4 = 30.
因此，输出应该是4。
example 2input = 54output = -1
explanation = 没有任何n个自然数的平方和等于54。因此，输出应该是-1。
问题陈述的解决方案这个问题有两个解决方案。
方法一：暴力解法暴力破解方法是从n = 1开始。创建一个变量'total'，将下一个自然数的平方加到total的前一个值上。如果total等于sum，则返回n，否则，如果total大于sum，则返回false。
伪代码startn =1 while (total < sum ): total += n*n n=n+1if(total == sum) : return nelse: return falseend
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 -1int 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})}}$$
伪代码startcalculate func(x) and derivativefunction(x) for given initial xcompute h: h = func(x) / derivfunc(x)while h is greater than allowed error ε h = func(x) / derivfunc(x) x = x – hif (x is an integer): return xelse: return -1;end
example下面是一个c++程序，用于检查一个给定的数字是否是自然数的平方和。
#include<bits/stdc++.h>#define epsilon 0.001using 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 + 1double derivativefunction(double k){ return 6*k*k + 6*k + 1;}// function to check if double is an integer or notbool 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*sumint 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 programint 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++程序。
以上就是平方金字塔数（平方和）的详细内容。