#include <iostream>
#include <math.h>


double functionFirst(double x)
{
	return 2.0 * x * x * x - 27.0 * x * x + 48.0 * x + 5.0;
}

double functionSecond(double x)
{
	return 6.0 * x * x - 54.0 * x + 48.0;
}


void gridSearch(double x_start, double x_end, long double epsilon, int& counter, double& ekstremum)
{
	double x_before = 0;
	double x_current = 0;

	x_before = functionFirst(x_start);
	x_current = functionFirst(x_start + epsilon);

	counter += 2;

	while (x_start + epsilon * counter < x_end)
	{
		x_before = x_current;
		x_current = functionFirst(x_start + counter * epsilon);

		counter++;

		if (x_before < x_current)
		{
			ekstremum = x_start + counter * epsilon;
			break;
		}
	}

}


double gridSearchRecurrent(double x_start, double x_end, long double epsilon, int& counter, double& ekstremum)
{
	int k = 8;

	double delta = (x_end - x_start) / k;

	if (delta < epsilon)
	{
		return (x_start + delta);
	}

	double x_before = functionFirst(x_start);
	double x_current = functionFirst(x_start + delta);

	counter += 2;

	int check_last;
	int check_current = 0;

	if (x_before < x_current)
	{
		check_current = 1;
	}

	int i;
	for (i = 2; i < k; i++)
	{
		x_before = x_current;
		x_current = functionFirst(x_start + delta * (double)i);

		counter++;

		check_last = check_current;

		if (x_before < x_current)
		{
			check_current = 1;
		}
		if (check_last != check_current)
		{
			break;
		}
		ekstremum = x_start;
	}

	return gridSearchRecurrent(x_start + (delta * ((double)i - 2)), x_start + (delta * (double)i), epsilon, counter, ekstremum);
}


void goldenRatio(double x_start, double x_end, double epsilon, int& counter, double& ekstremum)
{
	double z = 0.61803398874989490;
	double x_left = 0.0;
	double x_right = 0.0;
	double f_x_left = 0.0;
	double f_x_right = 0.0;

	x_left = x_end - (x_end - x_start) * z;
	x_right = x_start + (x_end - x_start) * z;

	f_x_left = functionFirst(x_left);
	f_x_right = functionFirst(x_right);

	counter += 2;

	while (true)
	{
		counter++;

		if (f_x_right <= f_x_left)
		{
		x_start = x_left;
		x_left = x_right;
		f_x_left = f_x_right;
		x_right = x_start + (x_end - x_start) * z;
		f_x_right = functionFirst(x_right);
		}
		else
		{
			x_end = x_right;
			x_right = x_left;
			f_x_right = f_x_left;
			x_left = x_end - (x_end - x_start) * z;
			f_x_left = functionFirst(x_left);
		}


		if (abs(x_end - x_start) > epsilon) {
			break;
		}

		ekstremum = (x_end + x_start) / 2.;

	}
}

void falsi(double x_start, double x_end, double epsilon, int& counter, double& ekstremum)
{
	double ekstremum_last = 0.0;
	double x1 = x_start;
	double x2 = x_end;
	double value = 0.0;

	ekstremum = 0.0;
	counter = 0;

	if (functionSecond(x_start) < 0.0)
		while (true)
		{
			ekstremum_last = ekstremum;

			ekstremum = x1 - (functionSecond(x1) * ((x1 - x2) / (functionSecond(x1) - functionSecond(x2))));

			value = functionSecond(ekstremum);

			counter++;

			if (value < 0.0)
				x1 = ekstremum;
			else if (value > 0.0)
				x2 = ekstremum;

			if (value == 0.0 || fabs(ekstremum_last - ekstremum) < epsilon)
				break;

		}

	else if (functionSecond(x_start) > 0.0)
		while (true)
		{
			ekstremum_last = ekstremum;

			ekstremum = x1 - (functionSecond(x1) * ((x1 - x2) / (functionSecond(x1) - functionSecond(x2))));

			value = functionSecond(ekstremum);

			counter++;

			if (value > 0.0)
				x_start = ekstremum;
			else if (value < 0.0)
				x_end = ekstremum;

			if (value == 0.0 || fabs(ekstremum_last - ekstremum) < epsilon)
				break;

		}
}

int main()
{

	double epsilon = 0.1;
	double x_start = 3.0;
	double x_end = 10.0;
	int counter_gridSearch = 0;
	int counter_gridSearchRecurrent = 0;
	int counter_goldenRatio = 0;
	int counter_falsi = 0;
	double ekstremum = 0.0;

	for (int i = 1; i < 8; i++)
	{
		counter_gridSearch = 0;
		counter_gridSearchRecurrent = 0;
		counter_goldenRatio = 0;
		counter_falsi = 0;

		std::cout << "==================================================" << std::endl;
		std::cout << "EPSILON:		" << epsilon << std::endl;
		std::cout << std::endl;

		gridSearch(x_start, x_end, epsilon, counter_gridSearch, ekstremum);
		std::cout << "GRID SEARCH:		" << counter_gridSearch << "	|	" << ekstremum << std::endl;

		gridSearchRecurrent(x_start, x_end, epsilon, counter_gridSearchRecurrent, ekstremum);
		std::cout << "GRID SEARCH RECURRENT:	" << counter_gridSearchRecurrent << "	|	" << ekstremum << std::endl;

		goldenRatio(x_start, x_end, epsilon, counter_goldenRatio, ekstremum);
		std::cout << "GOLDEN RATIO:		" << counter_goldenRatio << "	|	" << ekstremum << std::endl;

		falsi(x_start, x_end, epsilon, counter_falsi, ekstremum);
		std::cout << "FALSI:			" << counter_falsi << "	|	" << ekstremum << std::endl;
		std::cout << "==================================================" << std::endl;

		epsilon *= 0.1;
	}

	system("pause");
	return 0;
}