2014-02-20 5 views
1

Целью этой программы является поиск всех пифагорейских троек для каждого значения (a, b, c) менее 500 с использованием формулы Евклида (a = m^2 -n^2, b = 2mn, c = m^2 + n^2.) Итак, вот мой код.Поиск всех пифагорейских троек с использованием формулы Евклида

int main() 
{ 
    clock_t start = clock()/ (CLOCKS_PER_SEC/1000); 

    for (int m = 1; m <= 500; m++) 
    { 

     for (int n = 1; n <= 500; n++) 
     { 

      int a = (m*m)-(n*n); 
      int b = 2*m*n; 
      int c = (m*m)+(n*n); 
      if (m > n && a + b == c) 
      { 
       cout << a << " + " << b << " = " << c << endl; 
      } 
     } 
    } 
    clock_t finish = clock()/ (CLOCKS_PER_SEC/1000); 
cout << "completed in " <<clock() << " ms"; 
    return 0; 
} 

Я пробовал это, и мой вывод ничего. То, как я думал, что это сработает, будет: для каждого целого числа m, меньшего или равного 500, и начиная с 1, каждый раз добавляйте один к m. Такая же сделка для n. Затем вставьте эти значения в формулу, и если a + b == c, он печатает эти значения, таким образом, найдя мои тройки. Но я не получаю никаких результатов.

+0

Сохраните дополнительные вычисления 'a, b, c', установив соответствующий цикл' for': 'for (m = 2; m <= 500; m ++)' и 'for (n = 1; n kbshimmyo

ответ

3
a + b = (m^2 + 2mn - n^2) = (m+n)^2 - 2n^2 
c = m^2 + n^2 = (m+n)^2 - 2mn 

Вы обязаны a + b = c

--> 2n^2 = 2mn 
--> m = n 

Поскольку вы также требуется m > n, вы не можете найти какое-либо решение.

0

Ваше состояние не так: вы пытаетесь получить

(м^2 - п^2) + 2тп = (т^2 + п^2)

(м - н)^2 = т^2 + п^2

но n > 0 вы всегда будете иметь следующее строгое неравенство:

(т - п)^2 < м^2 < м^2 + п^2

Согласно википедии, вы хотели, чтобы проверить, была ли сумма квадратов равна -

(а^2 + B^2) = = с^2

0

Вы сделали несколько ошибок в своей реализации (см исправить ниже):

int main() 
{ 
    for (int n = 1; n <= 500; ++n) // note the swap for the loops 
    { 
     for (int m = n + 1; m <= 500 && (m*m + n*n) <= 500; ++m) // note that m starts at n + 1 
     { 
      int a = (m*m)-(n*n); 
      int b = 2*m*n; 
      int c = (m*m)+(n*n); 
      // Euclid already proved this, so there is no need to test it. 
      std::cout << a << " + " << b << " = " << c << std::endl; 
     } 
    } 
    return 0; 
} 
  1. Формула Евклида требует m > n, поэтому нет необходимости проверять значения, которые не соответствуют этим критериям
  2. Ваш тест (a + b) == c никогда не будет работать. Формула a^2 + b^2 = c^2 - это не означает a + b = c.
+0

Я скорректировал свой код, чтобы исправить мои немые ошибки (Ха-ха, я не знаю, как я пропустил, что мне нужно проверить^2 + b^2 == c^2), но теперь я получаю бесконечный цикл. Или, по крайней мере, очень, очень длинная программа. И просто проверка выборки результатов показывает, что они не идеальные квадраты. – Santa

+0

@Santa Если вам никогда не нужны номера более 500 (то есть наибольшее число в тройке будет 500), просто ограничьте 'c' до 500, что вы можете сделать в условной проверке внутреннего цикла for. Все результаты этой формулы будут Pythagorean Triples. –

0

Я понял проблему; в последней итерации программы я должен ограничить с до < = 500:

int main() 
{ 
    clock_t start = clock()/ (CLOCKS_PER_SEC/1000); 

    for (int n = 1; n <= 500; n++) 
    { 
     for (int m = n+1; m <= 500; m++) 
     { 
      int a = (m*m)-(n*n); 
      int b = 2*m*n; 
      int c = (m*m)+(n*n); 
      if ((a*a) + (b*b) == (c*c) && c <= 500) 
      { 
       cout << a << " + " << b << " = " << c << endl; 
      } 
     } 
    } 
    clock_t finish = clock()/ (CLOCKS_PER_SEC/1000); 
cout << "completed in " <<clock() << " ms"; 
    return 0; 
} 

Таким образом, программа не идет долго, как у меня были проблемы с. Спасибо вам всем!

+0

Вы должны перенести проверку на условие внутреннего цикла, чтобы избежать ненужных итераций: 'for (int m = n + 1; m <= 500 && (m * m + n * n) <= 500; ++ m) '. И if-условие внутри вашего внутреннего цикла также не нужно - математически любые произведённые 'a',' b' и 'c' будут удовлетворять условию. –