Die kleinste Dreieckszahl größer als p

Wir besprechen Dreieckszahlen und wie man die kleinste Dreieckszahl findet, die nur größer als die angegebene Zahl „num“ ist. Lassen Sie uns zunächst besprechen, was trigonometrische Zahlen sind, und dann die kleinste trigonometrische Zahl finden, die größer als „num“ ist

Wir werden zwei unterschiedliche Ansätze für dasselbe Problem sehen. Bei der ersten Methode führen wir eine einfache Schleife aus, um die Ausgabe zu generieren, während wir bei der zweiten Methode zunächst eine allgemeine Formel zur Berechnung der erforderlichen Zahl generieren und diese Formel dann direkt anwenden, um die minimale Dreieckszahl zu erhalten. p>

Problemstellung

Wir müssen die kleinste Anzahl an Dreiecken finden, die nur größer als „num“ ist.

Wir haben mehrere Kisten mit Bällen. Die Anzahl der Bälle, die die Box enthält, ist bei allen Boxen eine unterschiedliche Dreieckszahl. Die Kästchen sind von 1 bis n nummeriert. Wir müssen herausfinden, welche Box die Mindestanzahl an Bällen enthält, nachdem wir „num“ Bälle aus der Box entfernt haben.

Lassen Sie uns dies anhand eines Beispiels verstehen

Input number was: num = 5

Wir müssen herausfinden, welche Box die wenigsten Bälle hat, nachdem wir 5 Bälle herausgenommen haben

Output:3rd box will contain a minimum of balls after removing 4 balls.

Lösung für dieses Beispiel –

Boxes with number of balls: {1 3 6 10 ....}
Box 3 will contain only 1 ball after removing 4 balls from it.

Was sind trigonometrische Zahlen?

Dreieckige Zahlen sind Zahlen, die in Form eines gleichseitigen Dreiecksgitters dargestellt werden können. Die Anzahl der Punkte in einer Zeile ist immer gleich der Zeilennummer, d. h. die erste Zeile enthält 1 Punkt, die zweite Zeile enthält 2 Punkte und so weiter. Mehrere Dreieckszahlen sind: 1, 3, 6, 10, 15…. Lassen Sie uns nun die Formel für die n-te Dreieckszahl herleiten –

Wir wissen, dass die n-te Reihe einer Dreieckszahl n Punkte enthält, sodass die Dreieckszahl als Summe der Punkte in jeder Reihe ausgedrückt werden kann. Wir wissen auch, dass die n-te trigonometrische Zahl n Zeilen hat, sodass die n-te trigonometrische Zahl durch die Summe der ersten n natürlichen Zahlen gegeben werden kann.

Methode 1: (Direkte Methode)

Bei dieser Methode führen wir eine Schleife aus und berechnen die Differenz zwischen der gegebenen Zahl und der n-ten trigonometrischen Zahl. Wenn wir die Differenz >= 0 erhalten, erhalten wir die erforderliche Boxnummer, sodass wir die Schleife abschneiden.

Für trigonometrische Zahlen addieren wir weiterhin n zur vorhandenen (n-1)-ten trigonometrischen Zahl, um den Wert der nächsten trigonometrischen Zahl zu berechnen.

Algorithmus

• Schritt 1 – Initialisieren Sie die Variable triangular_number auf 0.

• Schritt 2 – Führen Sie die for-Schleife aus und fügen Sie bei jeder Iteration n hinzu.

• Schritt 3 - Berechnen Sie weiterhin die Differenz zwischen der Dreieckszahl und der angegebenen Zahl „num“.

• Schritt 4 – Wenn wir die Differenz >=0 erhalten, geben wir n als gewünschte Boxnummer aus.

Beispiel

Die Implementierung dieser Methode in C++ ist wie folgt -

#include <iostream>
using namespace std;
int main(){
   int num = 1234;
   int triangular_number = 0;
   for (int n=1; triangular_number<=num; n++){
      triangular_number = triangular_number + n;
      if((triangular_number-num)>=0){
         cout<<"The smallest triangular number larger than "<<num<<" is "<<n;
         return 0;
      }
   }
}

Ausgabe

The smallest triangular number larger than 1234 is 50

Methode 2: Formelbasierte Methode

Bei dieser Methode generieren wir zunächst eine allgemeine Formel zur Berechnung der erforderlichen Zahl und wenden die Formel dann direkt an, um die kleinste Anzahl von Dreiecken zu erhalten, die nur größer als die angegebene Zahl ist.

Die Dreieckszahl der n-ten Boxnummer ist gegeben durch -

Triangular number = (n*(n+1))/2

Ermitteln Sie die kleinste Boxnummer „n“, sodass die Anzahl der Dreiecke >= num ist.

i.e. (n*(n+1))/2 >= num

Das heißt, wir müssen lösen –

n<sup>2</sup> + n – 2*num >= 0

Mit dieser Gleichung erhalten wir

n = ceil( (sqrt(8*num+1)-1)/2 )

Beispiel

Der Code für diese Methode ist unten angegeben -

#include<bits/stdc++.h>
using namespace std;
int boxnum(int num){
   return ceil( ( sqrt( 8*num + 1 ) -1 ) / 2 ) ;
}
int main(){
   int num = 1234 ;
   cout << "The smallest triangular number larger than "<<num<<" is "<<boxnum(num);
   return 0;
}

Ausgabe

The smallest triangular number larger than 1234 is 50

Zeitliche Komplexität dieser Methode – O(logn)

Raumkomplexität – O(1), da wir nur ständig zusätzlichen Raum nutzen.

In diesem Artikel haben wir zwei verschiedene Methoden besprochen, um die kleinste Anzahl von Dreiecken zu finden, die nur größer als eine bestimmte Zahl „num“ ist. Die erste Methode berechnet einfach die trigonometrischen Zahlen, indem eine Schleife ausgeführt und bei jeder Iteration n hinzugefügt wird. Wir haben auch die Differenz zwischen der angegebenen Zahl und der trigonometrischen Zahl berechnet. Im zweiten Ansatz generieren wir eine mathematische Formel, um unsere gewünschte Ausgabe zu berechnen.

Das obige ist der detaillierte Inhalt vonDie kleinste Dreieckszahl größer als p. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!