Питагорине тројке - Решење

Груба сила

Задатак можемо да решимо формирањем свих тројки \((a, b, c)\), у којима је \(a \leq b \leq c \leq n\) и исписивањем оних које испуњавају Питагорин услов \(a^2 + b^2 = c^2\).

Границе за \(a, b, c\) можемо да одредимо и нешто прецизније. Пошто тражимо такве \(a, b, c\) да \(a \leq b, a^2 + b^2 = c^2 \leq n^2\), следи да тражени бројеви морају да испуњавају и \(a^2 + a^2 \leq n^2\), одакле даље следи да је горња граница за \(a\) једнака \(\sqrt{\frac{n^2}{2}}\).

На сличан начин долазимо и до граница за \(b\): \(a \leq b \leq \sqrt{n^2-a^2}\), док је границе за \(c\) нешто једноставније одредити: \(b < c \leq n\).

#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;

  for (int a = 1; 2*a*a <= n*n; a++)
    for (int b = a; a*a + b*b <= n*n; b++)
      for (int c = b+1; c <= n; c++)
        if (a*a + b*b == c*c)
          cout << a << " " << b << " " << c << " " << endl;
    return 0;
}

Израчунавање хипотенузе

Приметимо да, када су вредности катета \(a, b\) фиксиране, хипотенузу можемо да израчунамо као \(\sqrt{a^2+b^2}\). Тако, уместо да за вредност хипотенузе испробавамо све вредности од \(b\) до \(n\), довољно је да испитамо да ли је израчуната вредност целобројна. Тиме задатак решавамо помоћу двоструке, уместо троструке петље, чиме решење постаје значајно брже.

#include <iostream>
#include <cmath>

using namespace std;

int main() {
  int n;
  cin >> n;

  for (int a = 1; 2*a*a <= n*n; a++)
    for (int b = a; a*a + b*b <= n*n; b++) {
      double cr = sqrt(a*a + b*b);
      int c = round(cr);
      if (c == cr)
        cout << a << " " << b << " " << c << " " << endl;
    }
    return 0;
}