2016-01-19 57 views
-1

我寫了一個程序,以發現勾股數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. 由於兩個獨立的變量x和y我得到一個三重的兩倍。對此可以做些什麼。

如果我犯了一些錯誤,請耐心等待。我是一名學習者。

+0

你必須運行的每個約1000倍三個嵌套循環。這使得內部代碼運行約十億次。可能需要一段時間!我想也許你可以做'double h = hypot(x,y);返回h == int(h);'使其運行速度提高1000倍。 –

+0

工作正常!在不到3秒內執行;順便說一句你可以告訴什麼int()呢? – Vaibhav

+0

爲什麼你不使用像國際象棋程序使用開放書籍的所有準備結果?你將在毫秒內獲得結果! (「think differnent」 - 史蒂夫喬布斯)^^ –

回答

1

,找到所有的三元組的最快方式涉及該式的用法:

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

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

標準(和最快的一個)的方式來刪除重複:使用std ::設置<> 。

代碼示例:

#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