Quadratische Pyramidenzahlen (Quadratsumme)

Eine quadratische Pyramidenzahl bezieht sich auf die Summe der Quadrate natürlicher Zahlen. Zu den natürlichen Zahlen zählen alle Zahlen von 1 bis unendlich. Die ersten vier quadratischen Pyramidenzahlen lauten beispielsweise 1, 5, 14 und 30.

Berücksichtigen Sie zum besseren Verständnis folgende Tatsache: Wenn wir die quadratische Zahlenpyramide am Anfang nehmen und die Zahlenkugeln in absteigender Reihenfolge stapeln, bilden sie eine Pyramide.

Problemstellung

Gegeben eine Zahlensumme. Wenn Sum die Summe der Quadrate der ersten n natürlichen Zahlen ist, wird n zurückgegeben, andernfalls wird false zurückgegeben.

Beispiel 1

wird übersetzt als:

Beispiel 1

Input = 30
Output = 4

Erklärung = 30 ist die Summe der Quadrate der ersten 4 natürlichen Zahlen.

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

Die Ausgabe sollte also 4 sein.

Beispiel 2

Input = 54
Output = -1

Erklärung = Es gibt keine Quadratsumme von n natürlichen Zahlen gleich 54. Daher sollte die Ausgabe -1 sein.

Lösung zur Problemstellung

Es gibt zwei Lösungen für dieses Problem.

Methode 1: Gewaltsame Lösung

Die Brute-Force-Methode beginnt bei n = 1. Erstellen Sie eine Variable „total“, die das Quadrat der nächsten natürlichen Zahl zum vorherigen Wert von „total“ addiert. Gibt n zurück, wenn „total“ gleich „Sum“ ist, andernfalls wird „false“ zurückgegeben, wenn „total“ größer als „Sum“ ist.

Pseudocode

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

Beispiel

Unten finden Sie ein C++-Programm, mit dem Sie überprüfen können, ob eine bestimmte Zahl die Summe der Quadrate natürlicher Zahlen ist.

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

Ausgabe

Number of Square Pyramidal Numbers whose sum is 30: 
4

Zeitkomplexität – O(sum), wobei sum die gegebene Eingabe ist.

Raumkomplexität – O(1): kein zusätzlicher Raum belegt.

Methode 2 mit der Newton-Raphson-Methode

Eine weitere Methode ist die Newton-Raphson-Methode. Die Newton-Raphson-Methode wird verwendet, um die Wurzeln einer gegebenen Funktion f(x) zu finden und eine erste Schätzung der Wurzeln vorzunehmen.

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 ist also die Wurzel dieser kubischen Gleichung und kann mit der Newton-Raphson-Methode berechnet werden, bei der man von einem anfänglichen Schätzwert x0 ausgeht und die folgende Formel verwendet, um den nächsten Wert x zu finden, der aus dem vorherigen Wert xn xn+ erhalten wird 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

Beispiel

Unten finden Sie ein C++-Programm, mit dem Sie überprüfen können, ob eine bestimmte Zahl die Summe der Quadrate natürlicher Zahlen ist.

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

Ausgabe

Number of Square Pyramidal Numbers whose sum is 91: 
6

Zeitkomplexität – O((log n) F(n)) wobei F(n) der Aufwand für die Berechnung von f(x)/f'(x) mit n-stelliger Genauigkeit ist.

Raumkomplexität – O(1): kein zusätzlicher Raum belegt.

Fazit

Dieser Artikel löst das Problem, die quadratische Pyramidenzahl einer gegebenen Summe zu finden. Wir stellen zwei Methoden vor: Eine ist eine Brute-Force-Methode und die andere ist eine effiziente Methode. Beide Methoden stellen C++-Programme bereit.

Das obige ist der detaillierte Inhalt vonQuadratische Pyramidenzahlen (Quadratsumme). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!