大于 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 来计算三角形数。我们同时计算了给定数字和三角形数之间的差值。在第二种方法中，我们生成了一个数学公式来计算我们所需的输出。