毕达哥拉斯三重嵌套循环的误解

Question

问候和问候；

我试图找到小于 毕达哥拉斯三元组 的数字 1000.

幸运的是我找到了它的算法，这里是：

for (int a = 1; a < 1000; a++)
{
    for (int b = a; b < 1000; b++)
    {
        for (int c = b; c < 1000; c++)
        {
            if ((a * a) + (b * b) == (c * c))
            {
                cout << "( " << a << ", " << b << ", " << c << " )";
                cout << endl;
            }
        }
    }
}

但是我对这段代码一无所知！为什么每次循环的初始值都从上一次循环的值开始？虽然每个循环的初始值可以从 1 !

开始

这是什么原因？

Answer 1

毕达哥拉斯三元组只有一种排序方式：如果 a² + b² = c² 那么可以证明比 a² + c² ≠ b² 和 b² + c² ≠ a².

从上面和一些特殊情况（a = 0被定义排除，a ∊ (0, 2]很容易手工检查），因此只需要检查三胞胎2 < a ≤ b < c，这（几乎）就是树循环所做的。

这有两个原因：

通过设置循环使得a ≤ b ≤ c我们保证没有三元组出现超过一次
要测试的三元组较少，因此我们将执行时间减少一个常数因子。

Answer 2

对于 a < b :

毕达哥拉斯三元组成对出现，即 (a,b,c) 和 (b,a,c) : a,b < c ∀ a,b,c ∈ ℕ。因为如果找到一个，那么一对中的另一个就变成了一个微不足道的解决方案。假设找到一个毕达哥拉斯三元组 (a,b,c) 使得 a < b 然后我们立即知道 (b,a,c) 也是一个毕达哥拉斯三元组所以我们不希望我们的程序像它那样搜索它只需增加搜索域，从而增加执行时间。为避免这种情况，循环设置为 a≤b。但是，您也可以将它们初始化为 a < b 或 b = a + 1

对于 b < c 或 a < b < c:

您可以将它们初始化为 a < b < c 或 (c = b + 1 and b = a + 1) 因为没有毕达哥拉斯三元组的形式 (b,b,c) 为 b^2 + b ^2 = 2 * b^2 = c^2，即c = b * sqrt(2) 其中c为整数，b * sqrt(2)为无理数，因此两者永远不可能相等且为整数解决方案永远不存在。但是 c = b * sqrt(2) 也说 c > b.

因此，a < b < c

毕达哥拉斯三重嵌套循环的误解

Pythagorean triple nested loops missunderstanding

c++

algorithm

math

computer-science