Advertisement
Guest User

Finding maximum sum in pyramid

a guest
Feb 23rd, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.50 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <string>
  4. using namespace std;
  5. const int sizeOfPyramid = 15;
  6. int absoluteValue(int a)
  7. {
  8.     if(a >= 0)
  9.         return a;
  10.     else
  11.         return a * (-1);
  12.  
  13. }
  14. bool isPrime(int a)
  15. {
  16.     if(a == 1 || a == -1 || a == 0)
  17.         return false;
  18.     if(a == 2 || a == -2)
  19.         return true;
  20.     for(int n = 2; n < absoluteValue(a); n++)
  21.     {
  22.         if((a % n) == 0)
  23.             return false;
  24.     }
  25.     return true;
  26. }
  27. void pyramidSummer(int a[sizeOfPyramid][sizeOfPyramid], int ps, int Fpath[sizeOfPyramid], int path[sizeOfPyramid], int &maxDepth, int depth, int r, int c, int &max, int total)
  28. {
  29.     if(r >= ps || c > r)
  30.         return;
  31.     if(isPrime(a[r][c]))
  32.         return;
  33.     total = total + a[r][c];
  34.     depth = depth + 1;
  35.     path[r] = a[r][c];
  36.     if((depth < ps) & (maxDepth < ps) & (depth > maxDepth))
  37.     {
  38.         max = total;
  39.         maxDepth = depth;
  40.         for(int g = 0; g < ps; g++)
  41.         {
  42.             Fpath[g] = path[g];
  43.         }
  44.     }
  45.     if((depth < ps) & (maxDepth < ps) & (maxDepth == depth) & (total > max))
  46.     {
  47.         max = total;
  48.         for(int g = 0; g < ps; g++)
  49.         {
  50.             Fpath[g] = path[g];
  51.         }
  52.     }
  53.     if((depth == ps) & (maxDepth < ps))
  54.     {
  55.         max = total;
  56.         maxDepth = ps;
  57.         for(int g = 0; g < ps; g++)
  58.         {
  59.             Fpath[g] = path[g];
  60.         }
  61.     }
  62.     if((depth == ps) & (maxDepth == ps) & (total > max))
  63.     {
  64.         max = total;
  65.         for(int g = 0; g < ps; g++)
  66.         {
  67.             Fpath[g] = path[g];
  68.         }
  69.     }
  70.     pyramidSummer(a, ps, Fpath, path, maxDepth, depth, r + 1, c, max, total);
  71.     pyramidSummer(a, ps, Fpath, path, maxDepth, depth, r + 1, c + 1, max, total);
  72. }
  73.  
  74. int maxSumFinder(int a[sizeOfPyramid][sizeOfPyramid], int pyramidSize, int & maxDepth, int Fpath[sizeOfPyramid])
  75. {
  76.     int maximum = 0;
  77.     int depth = 0;
  78.     int total = 0;
  79.     int path[pyramidSize];
  80.     for(int l = 0; l < pyramidSize; l++)
  81.     {
  82.         path[l] = 0;
  83.     }
  84.     pyramidSummer(a, pyramidSize, Fpath, path, maxDepth, depth, 0, 0, maximum, total);
  85.     return maximum;
  86. }
  87. int main()
  88. {
  89.     int Fpath[sizeOfPyramid];
  90.     for(int l = 0; l < sizeOfPyramid; l++)
  91.     {
  92.         Fpath[l] = 0;
  93.     }
  94.     int md = 0;
  95.    int a[sizeOfPyramid][sizeOfPyramid] = {
  96.                 {215},
  97.                 {193 ,124},
  98.                 {117 ,237 ,442},
  99.                 {218 ,935 , 347,235},
  100.                 {320 ,804 ,522 ,417, 345},
  101.                 {229 ,601 ,723 ,835 ,133, 124},
  102.                 {248 ,202 ,277 ,433, 207, 263, 257},
  103.                 {359 ,464 ,504 ,528 ,516, 716, 871, 182},
  104.                 {461 ,441 ,426 ,656 ,863, 560, 380, 171, 923},
  105.                 {381 ,348 ,573 ,533 ,447, 632, 387, 176, 975, 449},
  106.                 {223 ,711 ,445 ,645 ,245, 543, 931, 532, 937, 541, 444},
  107.                 {330 ,131 ,333 ,928 ,377, 733, 017, 778, 839, 168, 197, 197},
  108.                 {131 ,171 ,522 ,137, 217, 224, 291, 413, 528, 520, 227, 229, 928},
  109.                 {223, 626 ,034 ,683, 839, 053, 627, 310, 713, 999, 629, 817, 410, 121},
  110.                 {924, 622 ,911, 233, 325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233}};
  111.     int b = maxSumFinder(a, sizeOfPyramid, md, Fpath);
  112.     cout<<"max sum is ";
  113.     cout<<b<<endl;
  114.     cout<<"and path of this sum is  "<<endl;
  115.     for(int l = 0; l < sizeOfPyramid; l++)
  116.     {
  117.         cout<<Fpath[l]<<endl;
  118.     }
  119.     //this program finds maximum sum and also the path that generates max sum
  120.    return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement