Nombres de pyramides carrées (somme des carrés)

Un nombre pyramidal carré fait référence à la somme des carrés des nombres naturels. Les nombres naturels incluent tous les nombres de 1 à l’infini. Par exemple, les 4 premiers nombres carrés de la pyramide sont 1, 5, 14 et 30.

Pour une meilleure compréhension, considérons le fait suivant : si nous prenons la pyramide carrée des nombres au début et empilons les boules numérotées par ordre décroissant, elles formeront une pyramide.

Énoncé du problème

Étant donné un nombre Somme. Si Sum est la somme des carrés des n premiers nombres naturels, renvoie n, sinon renvoie false.

Exemple 1

Exemple 1

Input = 30
Output = 4

Explication = 30 est la somme des carrés des 4 premiers nombres naturels.

1*1 + 2*2 + 3*3 +4*4 = 30.

Par conséquent, la sortie devrait être 4.

Exemple 2

Input = 54
Output = -1

Explication = Il n’existe pas de somme des carrés de n nombres naturels égale à 54. Par conséquent, la sortie devrait être -1.

Solution à l'énoncé du problème

Il existe deux solutions à ce problème.

Méthode 1 : Solution violente

La méthode de la force brute commence à n = 1. Créez une variable « total » qui ajoute le carré du nombre naturel suivant à la valeur précédente du total. Renvoie n si le total est égal à Sum, sinon renvoie false si le total est supérieur à Sum.

pseudocode

start
n =1 
While (total < sum ):
   Total += n*n
   n=n+1
if(total == sum) : 
   Return n
Else:
   Return false
end

Exemple

Vous trouverez ci-dessous un programme C++ pour vérifier si un nombre donné est la somme des carrés de nombres naturels.

#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;
}

Sortie

Number of Square Pyramidal Numbers whose sum is 30: 
4

Complexité temporelle - O(sum), où sum est l'entrée donnée.

Complexité spatiale - O(1) : aucun espace supplémentaire utilisé.

Méthode 2 utilisant la méthode Newton-Raphson

Une autre méthode est la méthode Newton-Raphson. La méthode de Newton-Raphson est utilisée pour trouver les racines d'une fonction donnée f(x) et une première estimation des racines.

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

Donc n est la racine de cette équation cubique et peut être calculé à l'aide de la méthode de Newton-Raphson qui consiste à partir d'une valeur initiale x0 et à utiliser la formule suivante pour trouver la valeur suivante x qui est obtenue à partir de la valeur précédente xn xn+ 1.

$$mathrm{x_{1}=x_{0}-frac{f(x_{0})}{f^{'}(x_{0})}}$$

pseudocode

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

Exemple

Vous trouverez ci-dessous un programme C++ pour vérifier si un nombre donné est la somme des carrés de nombres naturels.

#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;
}

Sortie

Number of Square Pyramidal Numbers whose sum is 91: 
6

Complexité temporelle - O((log n) F(n)) où F(n) est le coût de calcul de f(x)/f'(x), avec une précision à n chiffres.

Complexité spatiale - O(1) : aucun espace supplémentaire utilisé.

Conclusion

Cet article résout le problème de trouver le numéro de la pyramide carrée d'une somme donnée. Nous introduisons deux méthodes : l’une est une méthode par force brute et l’autre est une méthode efficace. Les deux méthodes fournissent des programmes C++.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!