我們將討論三角形數(shù)以及如何找到僅大于給定數(shù)字“num”的最小三角形數(shù)。我們先討論什么是三角數(shù)，然后找出比“num”大的最小三角數(shù)
我們將看到針對(duì)同一問題的兩種不同方法。在第一種方法中，我們將運(yùn)行一個(gè)簡(jiǎn)單的循環(huán)來生成輸出，而在第二種方法中，我們將首先生成一個(gè)用于計(jì)算所需數(shù)字的通用公式，然后直接應(yīng)用該公式來獲得最小的三角形數(shù)。 p>
問題陳述
我們必須找出僅大于“num”的最小三角形數(shù)。
我們有多個(gè)裝有球的盒子。對(duì)于所有盒子來說，盒子包含的球的數(shù)量都是一個(gè)不同的三角形數(shù)字。這些盒子從 1 到 n 編號(hào)。我們必須找出從盒子中取出“num”個(gè)球后哪個(gè)盒子將包含最少數(shù)量的球。
讓我們通過一個(gè)例子來理解這一點(diǎn)
Input number was: num = 5
登錄后復(fù)制
我們必須找出取出 5 個(gè)球后哪個(gè)盒子里的球數(shù)最少
Output:3rd box will contain a minimum of balls after removing 4 balls.
登錄后復(fù)制
此示例的解決方案 –
Boxes with number of balls: {1 3 6 10 ....}
Box 3 will contain only 1 ball after removing 4 balls from it.
登錄后復(fù)制
什么是三角數(shù)？
三角形數(shù)是可以用等邊三角形網(wǎng)格形式表示的數(shù)。一行中的點(diǎn)數(shù)始終等于行號(hào)，即第一行將包含 1 個(gè)點(diǎn)，第二行將包含 2 個(gè)點(diǎn)，依此類推。幾個(gè)三角形數(shù)字是：1、3、6、10、15……。現(xiàn)在讓我們推導(dǎo)出第 n 個(gè)三角形數(shù)的公式 –
我們知道，三角形數(shù)的第n行包含n個(gè)點(diǎn)，因此三角形數(shù)可以表示為每行中的點(diǎn)之和。我們還知道，第n個(gè)三角數(shù)有n行，因此第n個(gè)三角數(shù)可以由前n個(gè)自然數(shù)之和給出。
方法 1：（直接方法）
在這種方法中，我們將運(yùn)行一個(gè)循環(huán)并計(jì)算給定數(shù)字和第 n 個(gè)三角數(shù)之間的差，當(dāng)我們得到差值 >=0 時(shí)，我們將獲得所需的盒子編號(hào)，因此我們將截?cái)嘌h(huán)。
對(duì)于三角數(shù)，我們將繼續(xù)將 n 與現(xiàn)有的第 (n-1) 個(gè)三角數(shù)相加，以計(jì)算下一個(gè)三角數(shù)的值。
算法
第 1 步 – 將變量 triangular_number 初始化為 0。
第 2 步 – 運(yùn)行 for 循環(huán)并為每次迭代不斷添加 n。
第 3 步 – 繼續(xù)計(jì)算三角形數(shù)與給定數(shù)字“num”之間的差。
第 4 步 – 當(dāng)我們得到差異 >=0 時(shí)，我們將打印 n 作為所需的框編號(hào)。
示例
這種方法在 C++ 中的實(shí)現(xiàn)如下 –
#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;
}
}
}
登錄后復(fù)制
輸出
The smallest triangular number larger than 1234 is 50
登錄后復(fù)制登錄后復(fù)制
方法 2：基于公式的方法
在這種方法中，我們首先生成一個(gè)計(jì)算所需數(shù)字的通用公式，然后直接應(yīng)用該公式來獲得僅大于給定數(shù)字的最小三角形數(shù)。
第 n 個(gè)盒子編號(hào)的三角形數(shù)由下式給出 –
Triangular number = (n*(n+1))/2
登錄后復(fù)制
獲取最小的盒子編號(hào)“n”，使得三角形數(shù)>=num。
i.e. (n*(n+1))/2 >= num
登錄后復(fù)制
這意味著我們必須解決 –
n2 + n – 2*num >= 0
登錄后復(fù)制
使用這個(gè)方程，我們得到
n = ceil( (sqrt(8*num+1)-1)/2 )
登錄后復(fù)制
示例
此方法的代碼由以下給出 –
#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;
}
登錄后復(fù)制
輸出
The smallest triangular number larger than 1234 is 50
登錄后復(fù)制登錄后復(fù)制
此方法的時(shí)間復(fù)雜度 – O(logn)
空間復(fù)雜度 – O(1)，因?yàn)槲覀冎皇褂煤愣ǖ念~外空間。
在本文中，我們討論了兩種不同的方法來查找僅大于給定數(shù)字“num”的最小三角形數(shù)。第一種方法只是通過運(yùn)行循環(huán)并為每次迭代添加 n 來計(jì)算三角數(shù)。我們同時(shí)計(jì)算了給定數(shù)和三角數(shù)之間的差。在第二種方法中，我們生成了一個(gè)數(shù)學(xué)公式來計(jì)算我們所需的輸出。
以上就是大于p的最小三角數(shù)的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注www.xfxf.net其它相關(guān)文章！
