最快的方法确定一个数是否为三角形数

Question

最快的方法确定一个数是否为三角形数

13

三角数是从1到n的n个自然数之和。如何快速找到一个给定的正整数是否为三角数？

以下是前1200个至1300个三角数的一部分，您可以在此处轻松查看位模式（如果无法查看，请尝试缩小视图）：

(720600, '10101111111011011000')
(721801, '10110000001110001001')
(723003, '10110000100000111011')
(724206, '10110000110011101110')
(725410, '10110001000110100010')
(726615, '10110001011001010111')
(727821, '10110001101100001101')
(729028, '10110001111111000100')
(730236, '10110010010001111100')
(731445, '10110010100100110101')
(732655, '10110010110111101111')
(733866, '10110011001010101010')
(735078, '10110011011101100110')
(736291, '10110011110000100011')
(737505, '10110100000011100001')
(738720, '10110100010110100000')
(739936, '10110100101001100000')
(741153, '10110100111100100001')
(742371, '10110101001111100011')
(743590, '10110101100010100110')
(744810, '10110101110101101010')
(746031, '10110110001000101111')
(747253, '10110110011011110101')
(748476, '10110110101110111100')
(749700, '10110111000010000100')
(750925, '10110111010101001101')
(752151, '10110111101000010111')
(753378, '10110111111011100010')
(754606, '10111000001110101110')
(755835, '10111000100001111011')
(757065, '10111000110101001001')
(758296, '10111001001000011000')
(759528, '10111001011011101000')
(760761, '10111001101110111001')
(761995, '10111010000010001011')
(763230, '10111010010101011110')
(764466, '10111010101000110010')
(765703, '10111010111100000111')
(766941, '10111011001111011101')
(768180, '10111011100010110100')
(769420, '10111011110110001100')
(770661, '10111100001001100101')
(771903, '10111100011100111111')
(773146, '10111100110000011010')
(774390, '10111101000011110110')
(775635, '10111101010111010011')
(776881, '10111101101010110001')
(778128, '10111101111110010000')
(779376, '10111110010001110000')
(780625, '10111110100101010001')
(781875, '10111110111000110011')
(783126, '10111111001100010110')
(784378, '10111111011111111010')
(785631, '10111111110011011111')
(786885, '11000000000111000101')
(788140, '11000000011010101100')
(789396, '11000000101110010100')
(790653, '11000001000001111101')
(791911, '11000001010101100111')
(793170, '11000001101001010010')
(794430, '11000001111100111110')
(795691, '11000010010000101011')
(796953, '11000010100100011001')
(798216, '11000010111000001000')
(799480, '11000011001011111000')
(800745, '11000011011111101001')
(802011, '11000011110011011011')
(803278, '11000100000111001110')
(804546, '11000100011011000010')
(805815, '11000100101110110111')
(807085, '11000101000010101101')
(808356, '11000101010110100100')
(809628, '11000101101010011100')
(810901, '11000101111110010101')
(812175, '11000110010010001111')
(813450, '11000110100110001010')
(814726, '11000110111010000110')
(816003, '11000111001110000011')
(817281, '11000111100010000001')
(818560, '11000111110110000000')
(819840, '11001000001010000000')
(821121, '11001000011110000001')
(822403, '11001000110010000011')
(823686, '11001001000110000110')
(824970, '11001001011010001010')
(826255, '11001001101110001111')
(827541, '11001010000010010101')
(828828, '11001010010110011100')
(830116, '11001010101010100100')
(831405, '11001010111110101101')
(832695, '11001011010010110111')
(833986, '11001011100111000010')
(835278, '11001011111011001110')
(836571, '11001100001111011011')
(837865, '11001100100011101001')
(839160, '11001100110111111000')
(840456, '11001101001100001000')
(841753, '11001101100000011001')
(843051, '11001101110100101011')
(844350, '11001110001000111110')

例如，您是否也可以看到一个旋转的正态分布曲线，由807085和831405之间的零表示？这种模式会定期重复。

- psihodelia

2

这里的“最快”究竟是什么目的？像 int n = sqrt((double) (2*k)); n*(n+1)/2 == k 这样的代码对您的目的来说不够快吗？ - Cascabel

2

快速测试这个问题，无论如何，基本上等同于测试一个整数是否为平方数，正如其他人所指出的那样。这里有一个非常广泛的问题专门讨论这个主题：https://dev59.com/X3VC5IYBdhLWcg3wbglT - Cascabel

这是您试图解决的更大问题的一部分吗？如果是，也许您想解释一下？ - Bart Kiers

@Bart：是的，我需要快速检查网络拓扑是否为全互连。 - psihodelia

9个回答

14

如果且仅如果8x + 1是一个完全平方数，那么整数x就是三角形数。

- Mihai Toader

如果您遵循Sparky的答案，您将到达上面的测试。现在的问题是如何轻松检查一个数字是否为平方数：）。请参考Interjay的答案。 - Mihai Toader

你的答案太棒了！简单而优雅。顺便说一下，它可以用至少两种不同的方法轻松地演示出来。#1是通过解二次方程来计算。#2是在你的方程中用n(n+1)/2代替x并进行因式分解。 - Sparky

你可以在代码中测试sqrt(8x+1)是否为整数，对吧？ - SingularityFuture

3

我不知道这是否是最快的方法，但这里有一些数学公式可以帮助你朝着正确的方向前进...

S = n (n + 1) / 2
2*S = n^2 + n
n^2 + n - 2*S = 0

现在你有一个二次方程。

解出n的值。

如果n没有小数位，那么你就可以继续了。

- Sparky

2

我们只需要检查8*（您要检查的整数）+1是否为完全平方数即可！

public Boolean isSquare(int x)
{
    return(Math.sqrt(x)==(int)Math.sqrt(x));    // x will be a perfect square if and only if it's square root is an Integer.
}

}
public Boolean isTriangular(int z)
{
    return(isSquare(8*z+1));
}

- Vishal

2

家庭作业？

从1加到N的数字总和

1 + 2 + 3 + 4 + ... n-1 + n

如果你把第一个数和最后一个数相加，然后把第二个数和倒数第二个数相加，以此类推...

= (1+n) + (2+n-1) + (3+n-2) + (4+n-3) + ... (n/2 + n/2+1)

= (n=1) + (n+1) + (n+1) + ... (n+1); ....重复n/2次

= n(n+1)/2

这应该能帮助您入门...

- Charles Bretana

1

   int tri=(8*number)+1;// you can remove this for checking the perfect square and remaining all same for finding perfect square
   double trinum=Math.sqrt(tri);
int triround=(int) Math.ceil(trinum);
if((triround*triround)==tri)
     {
     System.out.println("Triangular");
     }
    else
    {
    System.out.println("Not Triangular");
    }

在这里，ceil函数总是取下一个更高的数字，因此这将为验证提供完美的机会。

- Shivaram Tolanur

0

这里是一个非常（最？）高效的Python变体（在3.8和3.9中可用）。

def isTriangular(n: int) -> bool:
    """
    when 8.0*n+1.0 is a perfect square it is triangular
    """
    x = 8.0*n+1.0
    return x % x**0.5 == 0.0

- Marcel Wilson

0

要找出一个数是否为三角形数，可以使用以下公式：

const pagesInBook = (num) => Number.isInteger((Math.sqrt(8 * num+1) -1 )/2)

- Stanislav Mozolevskiy

0

接受的答案会带你进一步检查这个数字是否是一个完全平方数。为什么不直接这样做呢？这和找到一个完全平方数所需的努力是一样的。

public final static boolean isTriangularNumber(final long x)
{
    if (x < 0)
        return false;

    final long n = (long) Math.sqrt(2 * x);
    return n * (n + 1) / 2 == x;
}

- Jatin Sanghvi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- interjay · Accepted Answer

如果n是第m个三角数，那么n=m*(m+1)/2。使用二次公式求解m：

m = (sqrt(8n+1) - 1) / 2

如果且仅当8n+1是一个完全平方数时，n才是三角形数。要快速确定一个数字是否是完全平方数，请参阅此问题：确定一个整数的平方根是否是整数的最快方法。

请注意，如果8n+1是一个完全平方数，则上述公式中的分子始终为偶数，因此无需检查它是否可被2整除。