Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- using namespace std;
- const int sizeOfPyramid = 15;
- int absoluteValue(int a)
- {
- if(a >= 0)
- return a;
- else
- return a * (-1);
- }
- bool isPrime(int a)
- {
- if(a == 1 || a == -1 || a == 0)
- return false;
- if(a == 2 || a == -2)
- return true;
- for(int n = 2; n < absoluteValue(a); n++)
- {
- if((a % n) == 0)
- return false;
- }
- return true;
- }
- 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)
- {
- if(r >= ps || c > r)
- return;
- if(isPrime(a[r][c]))
- return;
- total = total + a[r][c];
- depth = depth + 1;
- path[r] = a[r][c];
- if((depth < ps) & (maxDepth < ps) & (depth > maxDepth))
- {
- max = total;
- maxDepth = depth;
- for(int g = 0; g < ps; g++)
- {
- Fpath[g] = path[g];
- }
- }
- if((depth < ps) & (maxDepth < ps) & (maxDepth == depth) & (total > max))
- {
- max = total;
- for(int g = 0; g < ps; g++)
- {
- Fpath[g] = path[g];
- }
- }
- if((depth == ps) & (maxDepth < ps))
- {
- max = total;
- maxDepth = ps;
- for(int g = 0; g < ps; g++)
- {
- Fpath[g] = path[g];
- }
- }
- if((depth == ps) & (maxDepth == ps) & (total > max))
- {
- max = total;
- for(int g = 0; g < ps; g++)
- {
- Fpath[g] = path[g];
- }
- }
- pyramidSummer(a, ps, Fpath, path, maxDepth, depth, r + 1, c, max, total);
- pyramidSummer(a, ps, Fpath, path, maxDepth, depth, r + 1, c + 1, max, total);
- }
- int maxSumFinder(int a[sizeOfPyramid][sizeOfPyramid], int pyramidSize, int & maxDepth, int Fpath[sizeOfPyramid])
- {
- int maximum = 0;
- int depth = 0;
- int total = 0;
- int path[pyramidSize];
- for(int l = 0; l < pyramidSize; l++)
- {
- path[l] = 0;
- }
- pyramidSummer(a, pyramidSize, Fpath, path, maxDepth, depth, 0, 0, maximum, total);
- return maximum;
- }
- int main()
- {
- int Fpath[sizeOfPyramid];
- for(int l = 0; l < sizeOfPyramid; l++)
- {
- Fpath[l] = 0;
- }
- int md = 0;
- int a[sizeOfPyramid][sizeOfPyramid] = {
- {215},
- {193 ,124},
- {117 ,237 ,442},
- {218 ,935 , 347,235},
- {320 ,804 ,522 ,417, 345},
- {229 ,601 ,723 ,835 ,133, 124},
- {248 ,202 ,277 ,433, 207, 263, 257},
- {359 ,464 ,504 ,528 ,516, 716, 871, 182},
- {461 ,441 ,426 ,656 ,863, 560, 380, 171, 923},
- {381 ,348 ,573 ,533 ,447, 632, 387, 176, 975, 449},
- {223 ,711 ,445 ,645 ,245, 543, 931, 532, 937, 541, 444},
- {330 ,131 ,333 ,928 ,377, 733, 017, 778, 839, 168, 197, 197},
- {131 ,171 ,522 ,137, 217, 224, 291, 413, 528, 520, 227, 229, 928},
- {223, 626 ,034 ,683, 839, 053, 627, 310, 713, 999, 629, 817, 410, 121},
- {924, 622 ,911, 233, 325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233}};
- int b = maxSumFinder(a, sizeOfPyramid, md, Fpath);
- cout<<"max sum is ";
- cout<<b<<endl;
- cout<<"and path of this sum is "<<endl;
- for(int l = 0; l < sizeOfPyramid; l++)
- {
- cout<<Fpath[l]<<endl;
- }
- //this program finds maximum sum and also the path that generates max sum
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement