Technical Questionnaire for P.I. Works
unknown
plain_text
4 years ago
2.3 kB
7
Indexable
#include <iostream> #include <fstream> using namespace std; //CHECKS IF GIVEN NUMBER IS PRIME, RETURNS TRUE IF IT IS bool isPrime(int n) { int i, flag = 0; if (n == 1 || n==0) return false; for(i=2; i<=n/2; ++i) { if(n%i==0) { flag=1; break; } } if (flag==0) return true; else return false; } //ALGORITHM TO CALCULATE THE MAXIMUM SUM OF THE ROAD WITHOUT PRIMES //@param row = row index of the pyramid //@param column = column index of the pyramid //@param pyramid = pyramid structure as 2 dimensional array //@param height = height of the pyramid int algorithm(int row, int column, int** pyramid, int height) { if (row == height) return 0; //if you can not go further, return 0 if (pyramid[row][column] == -1) return 0; //if prime, return 0 you can't go further int left = algorithm(row+1, column, pyramid, height); //get the max sum of left road int right = algorithm(row+1, column+1, pyramid, height);//get the max sum of right road //return the larger one recursively if (left > right) { return left+pyramid[row][column]; } else return right+pyramid[row][column]; } int main() { //file read ifstream fp("file.txt"); string line; if(!fp.is_open()) { cout << "File could not be opened." << endl; } //calculate the height of the pyramide int height = 0; while(fp.good()) { getline(fp, line); if (line.length() == 0) break; height++; } //go at the beginning of the file fp.clear(); fp.seekg(0); //write numbers according to pyramid structure int* pyramid[height]; int temp; for (int i = 0; i < height; i++) { pyramid[i] = new int[i+1]; for (int j = 0; j < i+1; j++) { fp >> temp; if (isPrime(temp)) { pyramid[i][j] = -1; //write -1 if prime }else { pyramid[i][j] = temp; } } } //run the algorithm and print int sum = algorithm(0,0,pyramid,height); cout << sum << endl; //give back dynamically allocated memory for (int i = 0; i < height; i++) { delete pyramid[i]; } }
Editor is loading...