# Technical Questionnaire for P.I. Works

unknown
plain_text
3 years ago
2.3 kB
4
Indexable
Never
```#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()
{
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];
}

}```