#include <iostream>
#include <Cmath>
#include <complex>
#include <vector>
#include "math.h"

using namespace std;

complex<double> root[4];
int k = 0;

vector<complex<double>> coef = { complex<double>(2,0),complex<double>(16,0),
complex<double>(18,0), complex<double>(10,0),complex<double>(19,0), complex<double>(0,1) };

vector<complex<double>>Horner(complex<double> z, vector<complex<double>> coef)
{
	vector<complex<double>> newcoef;
	newcoef.push_back(coef[0]);
	for (int i = 1; i < coef.size(); i++)
	{
		newcoef.push_back(z*newcoef[i - 1] + coef[i]);
	}
	return newcoef;
}

double Abs(complex<double>z)
{
	return sqrt(z.real()*z.real() + z.imag()*z.imag());
}

double F(complex<double>z, vector<complex<double>> coef)
{
	vector<complex<double>> newcoef = Horner(z, coef);
	return Abs(newcoef[newcoef.size() - 1]);
}

//complex<double>
complex<double> SpuskCoordinates(complex<double> a, complex<double> b, double Epsilon, vector<complex<double>> coef)
{
	complex<double> z0 = a;
	complex<double> minz = z0;
	complex<double>z = b;
	double min = F(a,coef);
	while (Abs(F(z,coef) - F(minz,coef)) > Epsilon) {
		a = z0;
		z = minz;
		int k = (b.real() - a.real()) / Epsilon;
		for (int i = 0; i < k; i++)
		{
			if (F(a+ complex<double>(i*Epsilon, 0), coef) < min)
			{
				minz = a + complex<double>(i*Epsilon, 0);
				min = F(minz, coef);
				//cout << minz << endl;
			//cout << minz << " " << F(minz, coef) << endl;
			}
		}
		a = minz;
		k = (b.imag() - a.imag()) / Epsilon;
		for (int i = 0; i < k; i++)
		{
			if (F(a + complex<double>(0, i*Epsilon), coef) < min)
			{
				minz = a + complex<double>(0, i*Epsilon);
				min = F(minz, coef);
				//cout << minz << endl;
				//cout << minz << " " << F(minz, coef) << endl;
			}

		}
		//cout << minz << " " << z << endl;
	}
	z = minz;
	return z;
}

vector<complex<double>>DerCoef(vector<complex<double>> coef)
{
	vector<complex<double>> dercoef;
	int s = coef.size() - 1;
	for (int i = 0; i < s; i++)
	{
		dercoef.push_back(coef[i] * (double)(s - i));
	}
	return dercoef;
}

complex<double>Gradient(complex<double> z, vector<complex<double>> coef)
{
	complex<double> G = Horner(z, coef).back();
	complex<double> Gconj(G.real(), -G.imag());
	complex<double> G1 = Horner(z, DerCoef(coef)).back();
	complex<double> grad = Gconj * G1;
	grad = complex<double>(grad.real(), -grad.imag());
	return grad;
}

int N = 0;

complex<double> GradientDrob(complex<double>z, double epsilon, double delta, double alpha, vector<complex<double>> coef)
{
	complex<double>zi, zi1;
	complex<double> grad = Gradient(z, coef);
	N++;
	double fi, fi1;
	zi1 = z;
	fi = F(zi1, coef);
	while (Abs(grad) > delta)
	{
		zi = zi1;
		zi1 = zi - alpha * grad;
		fi1 = F(zi1, coef);
		grad = Gradient(zi1, coef);
		N++;
		if (fi1 - fi > -alpha * epsilon*Abs(grad))
			alpha /= 10;
		//cout << fi1 << " " << zi1 << " " << grad << endl;
	}
	N = 0;
	return zi1;
}

double Lx(vector<complex<double>> coef)
{
	double max = Abs(coef[0].real());
	for (int i = 1; i < coef.size(); i++) {
		if (Abs(coef[i].real()) > max)
			max = Abs(coef[i].real());
	}

	return 1+(max/Abs(coef[0]));
}

complex<double> GradientConst(complex<double> z,double epsilon, vector<complex<double>> coef)
{
	cout << "CHECK1" << endl;
	complex<double> zi, zi1;
	cout << "CHECK1" << endl;
	complex<double> grad = Gradient(z, coef);
	cout << "CHECK1" << endl;
	double fi1;
	cout << "CHECK1" << endl;
	double x = Lx(coef);
	vector<complex<double>>Der1 = DerCoef(coef);
	cout << "CHECK2" << endl;
	int L = (int)round(pow(Horner(complex<double>(x, 0), Der1).back().real(), 2) +
		Horner(complex<double>(x, 0), coef).back().real() *
		Horner(complex<double>(x, 0), DerCoef(Der1)).back().real());
	zi1 = z;
	cout << "L= " << L << endl;
	double alpha = (1 - epsilon) / (double)L;
	cout << "A = " << alpha<<endl;
	cout << "CHECK3" << endl;
	alpha = -alpha;
	while(Abs(grad) > epsilon)
	{
		//cout << "CHECK4" << endl;
		zi1 -= alpha * grad;
		fi1 = F(zi1, coef);
		grad = Gradient(zi1, coef);
		//cout << fi1 << " " << zi1 << " " << grad << endl;
	}
	cout << "CHECK5" << endl;
	complex<double>minz, min;
	return minz;
}

complex<double>GradientPredict(complex<double>z,double epsilon,vector<complex<double>> coef)
{
	complex<double> zi;
	complex<double> grad = Gradient(z, coef);
	int k = 10000;
	zi = z;
	while (Abs(grad) > epsilon)
	{
		zi -= (1 / (double)(k))*grad;
		grad = Gradient(zi, coef);
		k++;
	}
	complex<double> minz, min;
	minz = zi;
	min = F(minz, coef);
	return zi;
}

//vector<complex<double>>
void root_search(vector<complex<double>>coef)
{
	complex<double>a = complex<double>(-7, -1);
	complex<double>b = complex<double>(2,1);
	vector<complex<double>> roots;
	int deg = coef.size();
	vector<complex<double>> tempcoef = coef;
	complex<double> root;
	double alpha = 10e-5;
	double alpha1 = 0.5;
	double alpha2 = 0.5;
	double Epsilon = 10e-4;
	double delta = 10e-3;
	for (int i = 1; i < deg; i++)
	{
		root = SpuskCoordinates(a, b, Epsilon, tempcoef);
		tempcoef = Horner(root, tempcoef);
		tempcoef.resize(deg - i);
		roots.push_back(root);
	}
	for (int i = 0; i < roots.size(); i++)
	{
		cout << "Корни" << roots[i] << " " << "F(z)= " << F(roots[i], coef) << endl;
	}
	roots.clear();
	tempcoef = coef;
	cout << "GradDrop" << endl;
	for (int i = 1; i < deg; i++)
	{
		root = GradientDrob(complex<double>(0, 0), Epsilon, delta, alpha, tempcoef);
		tempcoef = Horner(root, tempcoef);
		tempcoef.resize(deg - i);
		roots.push_back(root);
	}
	for (int i = 0; i < roots.size(); i++)
	{
		cout << "Корни" << roots[i] << " " << "F(z)= " << F(roots[i], coef) << endl;
	}
	tempcoef = coef;
	roots.clear();
	cout << "GradPredict" << endl;
	for (int i = 1; i < deg; i++)
	{
		root = GradientPredict(complex<double>(0, 0), Epsilon, tempcoef);
		tempcoef = Horner(root, tempcoef);
		tempcoef.resize(deg - i);
		roots.push_back(root);
	}
	for (int i = 0; i < roots.size(); i++)
	{
		cout << "Корни" << roots[i] << " " << "F(z)= " << F(roots[i], coef) << endl;
	}
	tempcoef = coef;
	roots.clear();
	cout << "GradConst" << endl;
	for (int i = 1; i < deg; i++)
	{
		root = GradientConst(complex<double>(0, 0), Epsilon, tempcoef);
		tempcoef = Horner(root, tempcoef);
		tempcoef.resize(deg - i);
		roots.push_back(root);
	}
	for (int i = 0; i < roots.size(); i++)
	{
		cout << "Корни" << roots[i] << " " << "F(z)= " << F(roots[i], coef) << endl;
	}

}

/*void SpuskCoordinates(complex<double>a, complex<double>b, double epsilon)
{
	complex<double> x0 = a;
	int k = 0;
	while (k < 4)
	{
		complex<double> minx = x0;
		complex<double> x;
		double min = 100000;
		while (abs(F(minx) - F(x)) > epsilon)
		{
			a = x0;

			int j = (real(b) - real(a)) / epsilon;
			for (int i = 0; i < j; i++)//метод пассивного поиска для целой части
			{
				if (F(a + complex<double>(i*epsilon, 0)) < min)
				{
					minx = a + complex<double>(i*epsilon, 0);
					min = F(a+complex<double>(i*epsilon, 0));
				}
			}
			a = complex<double>(real(minx), imag(x0));
			j = (imag(b) - imag(a)) / epsilon;
			for (int i = 0; i < j; i++)//метод пассивного поиска для мнимой части
			{
				if (F(a + complex<double>(0, i*epsilon)) < min)
				{
					minx = a + complex<double>(0, i*epsilon);
					min = F(a + complex<double>(0, i*epsilon));
				}
			}
			x = minx;
		}
		cout << "Целая часть:" << real(x) << " Мнимая часть:" << imag(x) << " Значение полинома:" << F(x) << endl;
		root[k] = minx;
		k++;
	}

}*/

int main()
{
	setlocale(LC_ALL, "Russian");
	root_search(coef);
	system("pause");
	return 0;
}