Поиск всех пифагорейских триплетов от 100 до 1000

Я написал программу для поиска пифагорейских триплетов от 100 до 1000.
Здесь идет код для того же.

#include<iostream>
#include<cmath>

using namespace std;

bool checkWhetherInteger(int x, int y);
int getInteger(int x, int y);

int main()
{
cout << "This program is to print all pythagorean triplets from 100 to 1000. \n";

int x=100;
int y=100;

for(; x<=1000; x++)
{
for (; y<=1000; y++)
{
if (checkWhetherInteger(x,y))
{
cout << "Triplet : " << x << "  " << y << "  " << getInteger(x,y) << "\n";
}
}
y=100;
}
return 0;
}

bool checkWhetherInteger(int x, int y)
{
for (int i=141; i<=1415; i++)
{
if(hypot(x,y) == i )
{
return true;
}
}
}

int getInteger(int x, int y)
{
return static_cast<int>(hypot(x,y));

}

Есть две проблемы, с которыми я сталкиваюсь сейчас.

  1. Основная проблема в том, что он выполняется медленно. В то время как он дал мне все триплеты, он занял около 553,7 секунд. Так есть ли какой-нибудь алгоритм, с помощью которого то, чего я хочу достичь, можно сделать за 1-2 секунды или меньше.

  2. Из-за двух независимых переменных х и у я получаю один триплет дважды. Что можно с этим сделать.

Если я сделал какую-то ошибку, пожалуйста, потерпите меня. Я ученик.

-1

Решение

Самый быстрый способ найти все тройки включает использование этой формулы:

a = k(x^2 - y^2)
b = k(2xy)
c = k(x^2 + y^2)

https://en.wikipedia.org/wiki/Pythagorean_triple

Стандартный (и один из самых быстрых) способов удаления дубликатов: используйте std :: set<>.

Пример кода:

#include <iostream>
#include <string>
#include <vector>
#include <set>

struct Triple {
int a;
int b;
int c;
};

struct comp {
inline bool operator ()(const Triple & first, const Triple & second) const {
if (first.a != second.a) {
return first.a < second.a;
}
if (first.b != second.b) {
return first.b < second.b;
}
return first.c < second.c;
}
};

int main() {
int n = 1000;
std::set<Triple, comp> set;
for (int x = 2; x <= n; ++x) {
for (int y = 1; y < x && x * x + y * y <= n; ++y) {
int a = x * x - y * y;
int b = 2 * x * y;
if (a > b) {
std::swap(a, b);
}
int c = x * x + y * y;
for (int k = 1; k * c <= n; ++k) {
if (a * k >= 100 && a * k <= n &&
b * k >= 100 && b * k <= n &&
c * k >= 100 && c * k <= n)
set.insert({k * a, k * b, k * c});
}
}
}
for (const auto & triple : set) {
std::cout << triple.a << " " << triple.b << " " << triple.c << std::endl;
}
return 0;
}

coliru

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]