找到一个毕达哥拉斯三重线（项目欧拉）

我很清楚这个蛮力方法是坏的，我应该使用类似欧几里德公式的东西，并且最终循环不需要c = 1000 - （a + b）等......但现在我只是想让这个工作。找到一个毕达哥拉斯三重线（项目欧拉）

bool isPythagorean(int a, int b, int c) { 
    if((a*a + b*b) == c*c && a < b && b < c) { 
     cout << a << " " << b << " " << c << endl; 
     return true; 
    } else { 
     return false; 
    } 
} 

int main() 
{ 
    int a = 1; 
    int b = 2; 
    int c = 3; 

    for(a = 1; a < b; ++a) { 
     for(b = 2; b < c; ++b) { 
      for(c = 3; a + b + c != 1000 && !isPythagorean(a, b, c); ++c) { 
      } 
     } 
    } 

    return 0; 
}

大部分情况下，代码的工作方式与我预期的一样。我想不通为什么它被停止害羞A + B + C = 1000

我最后的三重的是280 406，共计980

如果我删除一个< b < C检，三重变成332，249，415共计996

所有结果符合勾股定理 - 我只是不能土地+ b + C = 1000

什么在阻止我吗？

来源

2011-03-15 monkeySeeMonkeyDo

我搜索看着类似的帖子，其中没有分享我的问题。 – monkeySeeMonkeyDo 2011-03-15 21:03:34

如果你想要'a 2011-03-15 21:26:54

你最内层的for循环中的条件明确地说永远不会测试任何其中a + b + c等于1000的东西。你的意思是a + b + c <= 1000？

来源

2011-03-15 21:08:56

我忘记提及，我确实接受了这一点，输出与...相同...... = 1000. – monkeySeeMonkeyDo 2011-03-15 21:11:17

的代码循环的这部分很奇怪：

for(a = 1; a < b; ++a) { 
    for(b = 2; b < c; ++b) { 
     for(c = 3; a + b + c != 1000 && !isPythagorean(a, b, c); ++c) { 
     } 
    } 
}

最初，a = 1, b = 2, c = 3。但是在第一个for(c),c=997，所以第二次迭代for(b)将运行到b=996。继续这样做，在某个时候你会发现一个三元组(a,b,c)，那时，c可能不会接近1000，b会迭代到c处于的状态......等等。我认为你无法准确预测它将会产生三倍的方式。

我建议你的东西去像

for(a = 1; 3*a < 1000; ++a) { 
    for(b = a+1; a+2*b < 1000; ++b) { 
     for(c = b+1; a + b + c != 1000 && !isPythagorean(a, b, c); ++c) { 
     } 
    } 
}

这样的话，循环将不依赖于先前发现的三倍。

...你真的应该使用欧几里得的方法。

来源

2011-03-15 21:12:41 Pablo

原谅我的无知，但为什么应该将b和c初始值设为a + 1和b + 1。这与仅使用1,2和3有何不同？ – monkeySeeMonkeyDo 2011-03-15 21:25:37

当暴力时，使用一些小的观察来减少问题的大小是明智的。例如因为b> 0，a * a + b * b> a * a，所以c * c> a * a和c> a。然后c + a> 2 * a和2 * a + b 2011-03-15 21:32:43

'b = a + 1'确保'b> a'。 'c = b + 1'确保'c> b'。它的不同之处在于你之前的边界（'; a Pablo 2011-03-15 23:14:01

替代可能的解决方案：

#include <iostream> 
#define S(x) x*x 

int main() { 
int c = 0; 
for(int a=1;a<(1000/3);++a) { 
    // a < b; so b is at-least a+1 
    // If a < b < c and a + b + c = 1000 then 'a' can't be greater than 1000/3 
    // 'b' can't be greater than 1000/2. 
    for(int b=a+1;b<(1000/2);++b) {   
     c = (1000 - a - b); // problem condition 
     if(S(c) == (S(a) + S(b))) 
      std::cout<<a*b*c; 
     } 
    }  
return 0; 
}

有关其他参考，请参阅下列职位 Finding Pythagorean Triples: Euclid's Formula Generating unique, ordered Pythagorean triplets

来源

2013-07-12 15:50:57 SridharKritha

找到一个毕达哥拉斯三重线（项目欧拉）

回答

相关问题