提问者:小点点

毕达哥拉斯三重嵌套循环


问候和问候;

我在找毕达哥拉斯的三倍数小于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开始!

这是什么原因?


共2个答案

匿名用户

毕达哥拉斯三元组只有一种排序方式:如果A²+B²=C²,则可以证明比A²+C²≠B²B²+C²≠A²

根据以上情况和一些特殊情况(a=0根据定义被排除,a(0,2]很容易手工检查),我们只需要检查2的三元组,这(几乎)就是树循环所做的。

这有两个原因:

>

  • 通过将循环设置为a≤b≤c,我们保证三元组不会出现一次以上

    要测试的三元组较少,因此我们以一个恒定的因子来减少执行时间。

  • 匿名用户

    对于<<; b:

    毕达哥拉斯三元组成对出现,即(a,b,c)和(b,a,c):a,b<; c,a,b,c∈. 因为如果找到一个解,这对中的另一个解就变成了一个简单的解。 设一个勾股定理三元组(a,b,c),使得aaa; 然后我们马上知道(b,a,c)也是一个毕达哥拉斯三元组,所以我们不希望我们的程序搜索它,因为它只会增加搜索域,从而增加执行时间。 为了避免这种情况,环路被设置为A≤B。 但是,您也可以将它们作为<; b或b=a+1

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

    您可以将它们作为<; b<; 因为没有一个勾股数三元组的形式(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。

    因此,一个<; b<; c