Advertisement
DMG

Euler's triangle sum (dynamic)

DMG
Apr 2nd, 2015
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. unsigned get_number_of_levels(int number) {
  6.  
  7.     unsigned levels = 1;
  8.  
  9.     while (number > 0) {
  10.         number -= levels++;
  11.     }
  12.  
  13.     return levels - 1;
  14. }
  15.  
  16. int main() {
  17.  
  18.     unsigned triangle_array[] = {75, 95, 64, 17, 47, 82, 18, 35, 87, 10, 20, 4, 82, 47, 65, 19, 1, 23, 75, 3, 34, 88, 2, 77, 73, 7, 63, 67, 99, 65, 4, 28, 6, 16, 70, 92, 41, 41, 26, 56, 83, 40, 80, 70, 33, 41, 48, 72, 33, 47, 32, 37, 16, 94, 29, 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14, 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57, 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48, 63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23};
  19.     // unsigned triangle_array[] = {3, 7, 4, 2, 4, 6, 8, 5, 9, 3};
  20.  
  21.     unsigned levels = get_number_of_levels(sizeof(triangle_array)/sizeof(*triangle_array));
  22.     int a, b;
  23.    
  24.     for (int i = levels; i > 0; --i) {
  25.         a = i * (i-1) / 2;
  26.         for (int j = 0; j < i - 1; ++j) {
  27.             b = (i-1)*(i-2)/2;
  28.             if (triangle_array[a + j] > triangle_array[a + j + 1]) {
  29.                 triangle_array[b + j] += triangle_array[a + j];
  30.             }
  31.             else {
  32.                 triangle_array[b + j] += triangle_array[a + j + 1];
  33.             }
  34.         }
  35.     }
  36.  
  37.     cout << triangle_array[0] << endl;
  38.  
  39.     return 0;
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement