[ create a new paste ] login | about

Link: http://codepad.org/eZSolgsw    [ raw code | output | fork ]

mohit_at_codepad - C++, pasted on Apr 16:
// Print the sides of right angled triangle whose sides are whole numbers and the perimeter is 1000.
// Whole numbers are analogous to unsigned integers in C.
// 12 is a whole number, but 12.5 is NOT a whole number.
// What are the optimizations possible?

#include <cassert>
#include <iostream>
using namespace std;

// If a, b, c are sides such that c > a > b (a can not be equal to be if c is whole number)
// c = 1000 - a - b
// As c*c = a*a + b*b
// a = 1000 * (500-b) / (1000-b)
// Also b = 1000 * (500-a) / (100-a)
// A simple reasoning can tell a*b is a multiple of 1000
// Also one of a and b is odd and the other is even (Property of pythagorus triplet)
// In a = 1000 * (500-b) / (1000-b) if b is even a is multiple of 5 and vice versa

// Main logic in this program
int main() {
  int numIterations = 0;
  for(int i = 5, d = 995, n = 1000 * 495; i < 490; i += 5, ++numIterations, d -= 5, n -= 5 * 1000) {
    if(375 == i) cout << "i=" << i << endl;
    if(375 == i) cout << "n=" << n << endl;
    if(375 == i) cout << "d=" << d << endl;
    if(375 == i) cout << "other=" << (n/d) << endl;
    if(n % d) continue;
    const int ab[] = {i, n / d};
    int c = 1000 - ab[0] - ab[1];
    if(c*c == ab[0] * ab[0] + ab[1] * ab[1]) {
      cout << "Answer is {" << ab[0] << ',' << ab[1] << ',' << c << "} calculated after " << numIterations << " iterations" << endl;
      return 0;
    }
  }
  cout << "Answer not found. Number of iterations = " << numIterations << endl;
  return -1;
}


Output:
1
Answer is {200,375,425} calculated after 39 iterations


Create a new paste based on this one


Comments: