用于确定给定数量N是否可以成为具有所有3个整数边的直角三角形的斜边的算法
假设您给出了一个直角三角形的斜边，那么如何确定给定的斜边是否有两个可能的小边。
例如，你将斜边视为5.然后你必须确定给定的直角三角形是否有较小的整数边。答案是yes因为我们可以将较小的边用作3和4，因此得到3-4- 5直角三角形。
同样，对于斜边7，我们可以没有这样的直角三角形。
换句话说，我们必须找出给定数字N是否可以作为右三角形的斜边，所有三边都是整数。
我阅读了关于毕达哥拉斯三重奏的整篇文章，但仍然没有成功。我很困惑要检查哪些条件。请帮忙。
你有一个原始的毕达哥拉斯三重奏：
(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 #include 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
int hypo = 5, i; double other = 0; for (i=1;i
上）
编辑：无需执行以下步骤，因为它将始终返回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指出的那样，没有必要存储arrays。 您可以直接将I1和I2平方。
这个如何？
- 显然，“较小”的边应该比三角形的斜边小。
- 我们还需要两个方面。
– > 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
这个问题一直是我在网上搜索最多的话题之一。 但解决方案很简单。 得出答案，让n可以是一个直角三角形的斜边。 n ^ 2 = a ^ 2 + b ^ 2。 （n，a和b是整数）。 那么显然对于任何整数k，k * n可以是斜边的。 forms（4 * l + 1）的任何素数都可以是斜边（l是整数）。 因此，将一个数字分成其主要因素。 如果至少有一个素因子是4 * l + 1的forms，那么显然这个数字可以是斜边的。 例如：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