大於 p 的最小三角數

---

我們將討論三角形數以及如何找到恰好大於給定數字“num”的最小三角形數。我們首先將討論什麼是三角形數，然後找出恰好大於“num”的最小三角形數。

我們將看到兩種不同的方法來解決這個問題。在第一種方法中，我們將執行一個簡單的迴圈來生成輸出，而在我們的第二種方法中，我們將首先生成一個計算所需數字的通用公式，然後將直接應用該公式來獲得最小的三角形數。

問題陳述

我們必須找出恰好大於“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 來計算三角形數。我們同時計算了給定數字和三角形數之間的差值。在第二種方法中，我們生成了一個數學公式來計算我們所需的輸出。