Quadratische Pyramidenzahlen (Quadratsumme)
Sep 04, 2023 pm 11:57 PMEine 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!

Heißer Artikel

Hot-Tools-Tags

Heißer Artikel

Heiße Artikel -Tags

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen

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?

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

So quadrieren Sie das Quadrat in Excel

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)

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
