1

该问题需要用户输入两个值，P 和 Q。然后程序将输出直角整数三角形的个数以及从 P 到 Q 的周长。例如：

输入：154 180

输出：

154 1

156 1

160 1

168 3

176 1

180 3

我想我需要找出 PQ 范围内的毕达哥拉斯三元组，但是如何计算“直角三角形的数量”？这是我的代码：

#include <iostream>
#include <math.h>
using namespace std;
int main() {
int P, Q, a, b, c, i = 0;
cin >> P >> Q;
for ( a = P; a <= Q; ++a)
{
   for ( b = a; b <= Q; ++b)
   {
      for ( c = b; b <= Q; ++c)
      {
         if ((pow(a, 2) + pow(b, 2)) == pow(c, 2) && a + b + c <= Q)
         {
             i +=1;
             cout << a + b + c << " " << i << endl;
             }
      }
    }
}
return 0;
}

超级感谢！！

4

1 回答 1

0

我们可以计算具有特定周长的直角整数三角形，std::map其中周长作为键，三角形的数量作为值：

std::map<int, int> triangle_map;

接下来，使用交换三角形a和b翻转三角形的对称性，我们可以将我们的发现搜索限制在 的情况下a<=b。但是如果a==bthen c=sqrt(2)*awhich 不是整数 whena是整数。因此，下面的双循环搜索很适合我们，并且可以找到所有目标三角形：

const int Qmax_a = (Q-1)/2; // 1 is the minimum value of c.

for (int a = 1; a <= Qmax_a; ++a)
{
    const int a_sqr = a*a;

    for (int b = a+1; b <= Q-a-1; ++b)
    {
        const int two_side_sqr = a_sqr + b*b;

        // possible candidate
        const int c = static_cast<int>(std::round(std::sqrt(two_side_sqr)));
        const int perimeter = (a+b+c);

        if((c*c == two_side_sqr) && (P <= perimeter) && (perimeter <= Q)){
            triangle_map[perimeter] += 1;
        }
    }
}

最后，我们可以从结果映射中获得所需的输出：

演示

for(const auto& p : triangle_map){
    std::cout << p.first << "," << p.second << std::endl;
}
于 2019-02-19T17:53:16.857 回答