Как я могу распечатать периметр и номер прямоугольного треугольника с заданным диапазоном? - PullRequest
Новая
       58

Как я могу распечатать периметр и номер прямоугольного треугольника с заданным диапазоном?

0 голосов
/ 19 февраля 2019

Вопрос требует, чтобы пользователь ввел два значения, P и Q. Затем программа выведет номер прямоугольного целочисленного треугольника, а также его периметр от P до Q. Например:

Ввод: 154180

Выход:

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;
}

Супер, спасибо !!

1 Ответ

0 голосов
/ 19 февраля 2019

Мы можем посчитать прямоугольные целочисленные треугольники с определенным периметром по std::map, который имеет периметры в качестве ключей и количество треугольников в качестве значений: 

std::map<int, int> triangle_map;

Далее, используя симметрию треугольниковобменивая a и b с переворотом, мы можем ограничить наш поиск поиска в случае a<=b.Но если a==b, то c=sqrt(2)*a, который не является целым числом, тогда как a является целым числом.Поэтому следующий двухконтурный поиск будет хорошо работать для нас и может найти все целевые треугольники: 

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;
}
...