我們將討論三角形數以及如何找到僅大于給定數字“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個自然數之和給出。
方法 1：（直接方法）
在這種方法中，我們將運行一個循環并計算給定數字和第 n 個三角數之間的差，當我們得到差值 >=0 時，我們將獲得所需的盒子編號，因此我們將截斷循環。
對于三角數，我們將繼續將 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
登錄后復制登錄后復制
方法 2：基于公式的方法
在這種方法中，我們首先生成一個計算所需數字的通用公式，然后直接應用該公式來獲得僅大于給定數字的最小三角形數。
第 n 個盒子編號的三角形數由下式給出 –
Triangular number = (n*(n+1))/2
登錄后復制
獲取最小的盒子編號“n”，使得三角形數>=num。
i.e. (n*(n+1))/2 >= num
登錄后復制
這意味著我們必須解決 –
n2 + 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的最小三角數的詳細內容，更多請關注www.xfxf.net其它相關文章！
