Technical Questionnaire for P.I. Works
unknown
plain_text
5 years ago
2.3 kB
14
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...