我們將討論三角形數以及如何找到僅大於給定數字「num」的最小三角形數。我們先討論什麼是三角數，然後找出比「num」大的最小三角數
我們將看到針對相同問題的兩種不同方法。在第一種方法中，我們將執行一個簡單的循環來產生輸出，而在第二種方法中，我們將首先產生一個用於計算所需數字的通用公式，然後直接應用該公式來獲得最小的三角形數。 p>
我們必須找出僅大於「num」的最小三角形數。
我們有多個裝有球的盒子。對於所有盒子來說，盒子包含的球的數量都是一個不同的三角形數字。這些盒子從 1 到 n 編號。我們必須找出從盒子中取出“num”個球後哪個盒子將包含最少數量的球。
讓我們透過一個例子來理解這一點
Input number was: num = 5
我們必須找出取出 5 個球後哪個盒子裡的球數最少
Output:3rd box will contain a minimum of balls after removing 4 balls.
此範例的解決方案 -
Boxes with number of balls: {1 3 6 10 ....}
Box 3 will contain only 1 ball after removing 4 balls from it.
三角形數是可以用等邊三角形網格形式表示的數。一行中的點數總是等於行號，即第一行將包含 1 個點，第二行將包含 2 個點，依此類推。幾個三角形數字是：1、3、6、10、15……。現在讓我們推導出第 n 個三角形數的公式 -
我們知道，三角形數的第n行包含n個點，因此三角形數可以表示為每行中的點總和。我們也知道，第n個三角數有n行，因此第n個三角數可以由前n個自然數和給出。
在這種方法中，我們將運行一個循環併計算給定數字和第n 個三角數之間的差，當我們得到差值>=0 時，我們將獲得所需的盒子編號，因此我們將截斷循環。 < /p>
對於三角數，我們將繼續將 n 與現有的第 (n-1) 個三角數相加，以計算下一個三角數的值。
第 1 步 - 將變數 triangular_number 初始化為 0。
第 2 步 - 運行 for 迴圈並為每次迭代不斷新增 n。
第 3 步 - 繼續計算三角形數與給定數字「num」之間的差。
第 4 步 - 當我們得到差異 >=0 時，我們將列印 n 作為所需的框編號。
這種方法在 C 中的實作如下 -
#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;
}
}
}
The smallest triangular number larger than 1234 is 50
在這個方法中，我們首先產生一個計算所需數字的通用公式，然後直接應用該公式來獲得僅大於給定數字的最小三角形數。
第 n 個盒子編號的三角形數由下式給出 -
Triangular number = (n*(n+1))/2
取得最小的盒子編號“n”，使得三角形數>=num。
i.e. (n*(n+1))/2 >= num
這意味著我們必須解決 -
n<sup>2</sup> + n – 2*num >= 0
使用這個方程，我們得到
n = ceil( (sqrt(8*num+1)-1)/2 )
此方法的程式碼由以下給出 -
#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;
}
The smallest triangular number larger than 1234 is 50
此方法的時間複雜度 - O(logn)
空間複雜度 - O(1)，因為我們只使用恆定的額外空間。
在本文中，我們討論了兩種不同的方法來尋找僅大於給定數字「num」的最小三角形數。第一種方法只是透過運行循環並為每次迭代添加 n 來計算三角數。我們同時計算了給定數和三角數之間的差。在第二種方法中，我們產生了一個數學公式來計算我們所需的輸出。
以上是大於p的最小三角數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
