5

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

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

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

换句话说，我们必须找出一个给定的数 N 是否可以作为一个直角三角形的斜边，该直角三角形的所有 3 个边都是整数。

我浏览了有关毕达哥拉斯三元组的整篇文章，但仍然没有成功。我很困惑要检查什么条件。请帮忙。

4

5 回答 5

3

你有一个原始的毕达哥拉斯三元组：

(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 <= sqrt(13 / 2) = 2.54

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
于 2013-10-17T20:54:03.013 回答
2 
int hypo = 5, i;
double other = 0;
for (i=1;i<hypo;i++)
{
    other = Math.sqrt(hypo*hypo - i*i);
    if (other == (int)other)
        break;
}

if (i<hypo)
   System.out.println("Yes - (" + (int)other + ", " + i +")" );
else
   System.out.println("No");

上）

于 2013-10-12T11:07:59.513 回答
1

编辑：不需要执行以下步骤，因为它总是返回 false。

//For each element in the array check whether twice its value equals N^2. If no match occurs then continue to the following.

.

Have two counters I1 and I2 -> Initialize I1 = 1 and I2 = N-1.
1. Check the sum I1^2 + I2^2;  
2. If the sum is > N^2, decrement the right counter (I2).  
3. If it is < N^2, increment the left counter (I1).

Keep doing the above 3 statements until one of the following happens.    
-> If the sum matches N^2, then a right angled triangle can be formed.
-> If I2 <= I1, then it is not possible to form a triangle.

复杂度：O(N)

编辑：正如 Dukeling 指出的那样，没有必要存储数组。您可以随时直接平方 I1 和 I2。

于 2013-10-12T10:18:23.553 回答
0

这个如何？

  • 显然，“较小”的边应该小于三角形的斜边。
  • 我们将需要另外两个方面。

-> 2 个 for 循环继续到斜边。像这样的东西：

public static boolean isAnIntegerTriangle(int hypotenuse) {
    for (int i = 0; i < hypotenuse; i++) {
        for (int j = 0; j < hypotenuse; j++) {
            boolean b = ((hypotenuse * hypotenuse) == (i * i + j * j));
            if (b)
                return true;
        }
    }
    return false;
}

测试：

public static void main(String[] args) {
    System.out.println(isAnIntegerTriangle(5));
    System.out.println(isAnIntegerTriangle(10));
    System.out.println(isAnIntegerTriangle(7));
}

输出：

true
true
false
于 2013-10-17T21:10:55.760 回答
0

这个问题一直是我在网上搜索最多的话题之一。但解决方案很简单。得出答案，让 n 可以是直角三角形的斜边。n^2 = a^2 + b^2。（n，a 和 b 是整数）。那么显然对于任何整数 k，k*n 可以是斜边。(4*l+1) 形式的任何素数都可以是斜边（l 是整数）。因此，将一个数字拆分为其主要因素。如果至少一个素数是 4*l+1 的形式，那么显然这个数可以是斜边。例如：5 可以表示为 4*1+1 和 5^2 = 3^2 + 4^2。类似地，78 = 2*3*13 和 13 可以表示为 4*3+1。和 13^2 = 5^2 + 12^2 =>78^2 = 30^2 + 72^2

于 2015-10-09T15:16:49.347 回答