java - 确定给定数N是否可以变为所有3个整数边的直角三角形的斜边的算法

假设给定一个直角三角形的斜边，那么如何确定给定的斜边是否有两个整数的较小边。

例如，给定斜角为5，然后必须确定给定直角三角形的整数边是否较小。答案将为yes，因为我们可以将较小的边数设为3和4，因此得到3-4- 5个直角三角形。

同样，对于斜边为7的情况，我们不能有这样的直角三角形。

换句话说，我们必须确定给定的数字N是否可以用作所有3个边均为整数的直角三角形的斜边。

我浏览了有关Pythagorean triples的整篇文章，但仍然没有成功。我很困惑要检查哪些条件。请帮忙。

最佳答案

您需要一个原始的毕达哥拉斯三联体:

(p^2 - q^2)^2 + (2 * p * q))^2 = (p^2 + q^2)^2 = N^2

假设p> = q。那我们有

N >= 2 * q^2 or q <= sqrt(N / 2)

假设N =13。那么我们需要q
q = 2 => p ^ 2 = 13-4 = 9，这是一个正方形。

因此，您可以从1..sqrt(N/2)中得到一个小的数字“i”循环，并检查N-(i ^ 2)是否为平方。

对于原始勾股元组的成员，这将是 O(sqrt(N))。

C/C++中的示例代码:

#include <stdio.h>
#include <math.h>

void CheckTuple(int n)
{
    int k = sqrt(n/2.0);

    for (int i = 1; i <= k; i++) {
        int tmp = sqrt((double)(n - i * i));
        if ((tmp * tmp) == (n - i * i)) {
            printf("%d^2 + %d^2 = %d^2\n", (tmp*tmp - i*i), 2 * tmp * i, n);
            return;
        }
    }
    printf("%d is not part of a tuple\n", n);
    return;
}


int main(int argc, char *argv[])
{

    CheckTuple(5);
    CheckTuple(6);
    CheckTuple(13);
    CheckTuple(10);
    CheckTuple(25);

    return 0;
}

输出:

3^2 + 4^2 = 5^2
6 is not part of a tuple
5^2 + 12^2 = 13^2
8^2 + 6^2 = 10^2
7^2 + 24^2 = 25^2