我们将讨论三角形数以及如何找到仅大于给定数字“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 using namespace std;int main(){ int num = 1234; int triangular_number = 0; for (int n=1; triangular_number=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 )
示例
此方法的代码由以下给出 –
#includeusing 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的最小三角数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445542.html
微信扫一扫 
支付宝扫一扫 
