Don't like ads? PRO users don't see any ads ;-)
Guest

Untitled

By: a guest on May 20th, 2012  |  syntax: None  |  size: 3.23 KB  |  hits: 20  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include<iostream>
  2. #include<fstream>
  3. #include<vector>
  4. #include<stdlib.h>
  5. #include<string>
  6.  
  7. using namespace std;
  8.  
  9. int main() {
  10. const int ROWS = 15;
  11. vector < vector <int> >triangle;  // vector of vector<ints>
  12. streamsize s = sizeof(int);
  13. fstream file;
  14. file.open("triangle");
  15.  
  16.     for (int i = 0; i < ROWS; i++) {
  17.         vector<int> row;
  18.         for (int j = 0; j < i + 1; j++) {
  19.             /*
  20.              * Get two characters which will form the numbers
  21.              */
  22.             char num[2];
  23.                 if (file.good()) {
  24.                     file.get(num, s);
  25.                 } else {
  26.                     cout << "Problem?" << endl;
  27.                 }
  28.             int number = (int) ((num[0] - 48) * 10) + (num[1] - 48);
  29.             cout << number << endl;
  30.             row.push_back(number); // Insert the number linearl
  31.         }
  32.          triangle.push_back(row); // Place a vector into the triangle vector
  33.         row.clear();
  34.         /*
  35.          * Should be at the end of the line, push the
  36.          * internal pointer forward one to enter the
  37.          * next line
  38.          */
  39.         file.seekg(1, ios::cur);
  40.     }
  41.     return 0;
  42.  
  43.     /*
  44.      * Now onto the actual production of the answer!
  45.      * Work from the bottom up, calculating the greatest
  46.      * two number and adding them up. This will effectively
  47.      * flatten the triangle up
  48.      */
  49.  
  50.     for (int i = triangle.size(); i > 0; i--) {
  51.         vector<int> row = triangle.at(i);
  52.          for (unsigned int j = 0; j < row.size(); j++) {
  53.             if (i > 1) {
  54.             vector<int> above = triangle.at(i-1);
  55.                 if (j == 0) {
  56.                 /*
  57.                  * Left hand edge of the pyramid
  58.                  * Check up and right
  59.                  */
  60.                 int left = row.at(j) + above.at(j);
  61.                 int right = row.at(j) + above.at(j+1);
  62.                 // Set the valve above to the greatest answer
  63.                     if (left >= right) {
  64.                         above.at(j) = left;
  65.                     } else {
  66.                         above.at(j) = right;
  67.                     }                        
  68.                 } else {
  69.                 /*
  70.                  * Either in between other numbers
  71.                  * or on the right hand edge
  72.                  * Check up and left
  73.                  */
  74.                 int left = row.at(j) + above.at(j-1);
  75.                 int right = row.at(j) + above.at(j);
  76.                     if (left >= right) {
  77.                         above.at(j) = left;
  78.                     } else {
  79.                         above.at(j) = right;
  80.                     }
  81.                 }
  82.             } else if (i == 1) {
  83.             vector<int> above = triangle.at(i-1);
  84.             /*
  85.              * Program has reached row 1 (second row down)
  86.              * Simply add the current element to the only
  87.              * element above
  88.              */
  89.             int result = row.at(j) + above.at(0);
  90.                 if (result > above.at(0)) {
  91.                     above.at(0) = result;
  92.                 }
  93.             } else {
  94.             /*
  95.              * Should be at the top of the triangle
  96.              */
  97.             cout << row.at(0) << endl;
  98.             }
  99.         }
  100.     }
  101. }