Inhaltsverzeichnis
Problemstellung
Beispiel
Lösung zur Problemstellung
Methode 1: Gewaltsame Lösung
Pseudocode
Ausgabe
Methode 2 mit der Newton-Raphson-Methode
Fazit
Heim Backend-Entwicklung C++ Quadratische Pyramidenzahlen (Quadratsumme)

Quadratische Pyramidenzahlen (Quadratsumme)

Sep 04, 2023 pm 11:57 PM
平方 Pyramide

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
Nach dem Login kopieren

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

1*1 + 2*2 + 3*3 +4*4 = 30.
Nach dem Login kopieren

Die Ausgabe sollte also 4 sein.

Beispiel 2

Input = 54
Output = -1
Nach dem Login kopieren

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
Nach dem Login kopieren

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;
}
Nach dem Login kopieren

Ausgabe

Number of Square Pyramidal Numbers whose sum is 30: 
4
Nach dem Login kopieren

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
Nach dem Login kopieren

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
Nach dem Login kopieren

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;
}
Nach dem Login kopieren

Ausgabe

Number of Square Pyramidal Numbers whose sum is 91: 
6
Nach dem Login kopieren

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!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße Artikel -Tags

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

So geben Sie ein Quadrat von 2 m³ auf einem Mobiltelefon ein „Detaillierte Einführung: Eingabemethode für quadratische und kubische Symbole' So geben Sie ein Quadrat von 2 m³ auf einem Mobiltelefon ein „Detaillierte Einführung: Eingabemethode für quadratische und kubische Symbole' Feb 07, 2024 am 08:31 AM

So geben Sie ein Quadrat von 2 m³ auf einem Mobiltelefon ein „Detaillierte Einführung: Eingabemethode für quadratische und kubische Symbole'

Mittleres Quadrat der natürlichen Zahlen? Mittleres Quadrat der natürlichen Zahlen? Sep 20, 2023 pm 10:29 PM

Mittleres Quadrat der natürlichen Zahlen?

C-Programm zum Ermitteln des größten Primfaktors einer Zahl C-Programm zum Ermitteln des größten Primfaktors einer Zahl Aug 27, 2023 am 10:09 AM

C-Programm zum Ermitteln des größten Primfaktors einer Zahl

So quadrieren Sie das Quadrat in Excel So quadrieren Sie das Quadrat in Excel Mar 20, 2024 am 11:10 AM

So quadrieren Sie das Quadrat in Excel

Verwenden Sie C++, um Code zu schreiben, um die N-te nichtquadratische Zahl zu finden Verwenden Sie C++, um Code zu schreiben, um die N-te nichtquadratische Zahl zu finden Aug 30, 2023 pm 10:41 PM

Verwenden Sie C++, um Code zu schreiben, um die N-te nichtquadratische Zahl zu finden

Top 10 Global Digital Virtual Currency Trading Platform Ranking (2025 Autoritative Ranking) Top 10 Global Digital Virtual Currency Trading Platform Ranking (2025 Autoritative Ranking) Mar 06, 2025 pm 04:36 PM

Top 10 Global Digital Virtual Currency Trading Platform Ranking (2025 Autoritative Ranking)

Java-Programm zum Erstellen von Pyramiden und Mustern Java-Programm zum Erstellen von Pyramiden und Mustern Sep 05, 2023 pm 03:05 PM

Java-Programm zum Erstellen von Pyramiden und Mustern

Top 10 Börsen im Währungskreis in 2025 neueste Rangliste für digitale Währung Apps Top 10 Börsen im Währungskreis in 2025 neueste Rangliste für digitale Währung Apps Feb 27, 2025 pm 06:33 PM

Top 10 Börsen im Währungskreis in 2025 neueste Rangliste für digitale Währung Apps

See all articles