大於p的最小三角數

我們將討論三角形數以及如何找到僅大於給定數字「​​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 時，我們將獲得所需的盒子編號，因此我們將截斷循環。 < /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

方法 2：基於公式的方法

在這個方法中，我們首先產生一個計算所需數字的通用公式，然後直接應用該公式來獲得僅大於給定數字的最小三角形數。

第 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中文網其他相關文章！