Advertisement
makispaiktis

Project Euler 39 - Integer right triangles

May 20th, 2020 (edited)
1,255
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.78 KB | None | 0 0
  1. /*
  2. If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
  3. {20,48,52}, {24,45,51}, {30,40,50}
  4. For which value of p ≤ 1000, is the number of solutions maximised?
  5. */
  6.  
  7.  
  8. #include <iostream>
  9. #include <stdlib.h>
  10. #include <math.h>
  11. #include <vector>
  12. #include <algorithm>
  13. #define LIMITPERIMETER 1000
  14.  
  15. using namespace std;
  16.  
  17. int main()
  18. {
  19.     // 1. First, I will create a vector, in which i will place the counter of solution of each perimeter
  20.     // In index = 0 there will be the number of solutions when perimeter = 3 = min, in index = 1, the solutions of perimeter = 4, ....
  21.     // Therefore, the length will be: length = LIMITPERIMETER  - 3 + 1
  22.     vector <int> counterOfPerimSolutions = vector <int> ();
  23.     // Initialization of the vector
  24.     for(int i=0; i<LIMITPERIMETER-3+1; i++){
  25.         counterOfPerimSolutions.push_back(0);
  26.     }
  27.  
  28.     // 2. I make 2 for-loops
  29.     for(int a=1; a<=999; a++){
  30.         for(int b=1; b<=999; b++){
  31.             double c = sqrt(a*a + b*b);
  32.             if(c == int(c) && a+b+c <= LIMITPERIMETER){
  33.                     // That means that a,b,c are integers, that create
  34.                     int perimeter =  a + b + c;
  35.                     // This value is in index perimeters - 3 in the vector
  36.                     cout << "a = " << a << ", b = " << b << ", c =  " << c << " ----> perimeter = " << perimeter << endl;
  37.                     counterOfPerimSolutions[perimeter-3]++;
  38.             }
  39.         }
  40.     }
  41.  
  42.     /*
  43.     for(int i=0; i<counterOfPerimSolutions.size(); i++){
  44.         cout << counterOfPerimSolutions[i] << " sols for perim = " << i+3 << endl;
  45.     }
  46.     */
  47.  
  48.     // 3. Now, the vector contains all the solutions, but each solution is twice, because there are 2 different combinations of a and b (and therefore c), that lead to the same perimeter
  49.     // For perimeter = 120, I can have a=30, b=40, c=50 and a=40, b=30, c=50, but that's the same solution
  50.     for(unsigned int i=0; i<counterOfPerimSolutions.size(); i++){
  51.         counterOfPerimSolutions[i] /= 2;
  52.     }
  53.  
  54.     // 4. Find the perimeter, with the most solutions
  55.     int maxIndex = 0;
  56.     int maxSolutions = counterOfPerimSolutions[0];
  57.     for(unsigned int i=1; i<counterOfPerimSolutions.size(); i++){
  58.         if(counterOfPerimSolutions[i] > maxSolutions){
  59.             maxSolutions = counterOfPerimSolutions[i];
  60.             maxIndex = i;
  61.         }
  62.     }
  63.  
  64.     // 5. Now, I have the value of maxIndex. But this index is connected with a perimeter's value, especially the value: maxIndex + 3
  65.     cout << "\nIn range: 3 <= perimeter <= " << LIMITPERIMETER << ", the max different solutions are " << counterOfPerimSolutions[maxIndex] << " and the value of this perimeter is " << maxIndex + 3 << endl;
  66.     return 0;
  67.  
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement