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

Question

假设您给出了一个直角三角形的斜边,那么如何确定给定的斜边是否有两个可能的整体较小的边.

例如,你将斜边视为5.然后你必须确定给定的直角三角形是否有较小的积分边.答案是yes因为我们可以将较小的边用作3和4,因此得到3-4-5直角三角形.

同样,对于斜边7,我们可以没有这样的直角三角形.

换句话说,我们必须找出给定数字N是否可以作为右三角形的斜边,所有三边都是整数.

我阅读了关于毕达哥拉斯三重奏的整篇文章,但仍然没有成功.我很困惑要检查哪些条件.请帮忙.

Answer 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 求平方。