#include <stdio.h>
#include <math.h>
#define K 10000000 // параметр K
double epsilon; //значение машинного эпсилон
double f(double x); //функция F(x), вариант #9
double f_for_iteration(double x); //функций f(x) для вычисление методом итераций
double g(double x); // функция G(x), вариант #23
double g_for_iteration(double x); // функция g(x) для вычисления методом итераций
typedef double(*FUNCTION)(double x);
double dichotomy(FUNCTION f, double a, double b); // метод дихотомии
double iteration(FUNCTION f, double a, double b); // метод итерации
double Newton(FUNCTION f, double a, double b); // метод Ньютона
double diff(FUNCTION f, double x); // производная функции в точке x
double diff_second(FUNCTION f, double x); // вторая производная функции в точке x
double iteration_check(FUNCTION f, double a, double b); // провера сходимости метода итераций
double Newton_check(FUNCTION f, double a, double b); // проверка сходимости метода Ньютона
int nDichotomy=0;
int nIteration=0;
int nNewton=0;

double f(double x)
{
	return acos(x)-sqrt(1-0.3*x*x*x);
}
double f_for_iteration(double x)
{
	return cos(sqrt(1-0.3*x*x*x));
}
double dichotomy(FUNCTION f, double a, double b)
{
	double a0, b0;
	while(fabs(a - b) > epsilon*K)
	{
		a0 = a;
		b0 = b;
		++nDichotomy;
		if (f(a0)*f((a0+b0)/2.0)>0)
		{
			a = (a0 + b0)/2.0;
			b = b0;
		}
		else
		{
			a = a0;
			b = (a0+b0)/2.0;
		}
	}
	return (a+b)/2;
}
double iteration(FUNCTION f, double a, double b)
{
	double x0 = (a+b)/2.0;
	double x = f(x0);
	while(fabs(x - x0)>epsilon*K)
	{
		++nIteration;
		x0 = x;
		x = f(x0);
	}
	return x;
}
double diff(FUNCTION f, double x)
{
	double h = 0.0000001;
	return (f(x+h)-f(x))/h;
}
double diff_second(FUNCTION f, double x)
{
	double h = 0.0000001;
	return (f(x-h)+f(x+h)-2*f(x))/(h*h);
}
double Newton(FUNCTION f, double a, double b)
{
	double x0 = (a+b)/2.0;
	double x = x0-f(x0)/diff(f, x0);
	while(fabs(x - x0)>epsilon)
	{
		++nNewton;
		x0 = x;
		x = x0-f(x0)/diff(f, x0);
	}
	return x;
}
double iteration_check(FUNCTION f, double a, double b)
{
	double step = 0.005;
	double x;
	for(x=a; x<b; x+=step)
	{
		if(fabs(diff(f, x))>1.0)
		{
			return 0;
			break;
		}
	}
	return 1;
}
double Newton_check(FUNCTION f, double a, double b)
{
	double step = 0.005;
	double x, differential;
	for(x=a; x<b; x+=step)
	{
		differential = diff(f, x);
		if(fabs(f(x)*diff_second(f,x))>differential*differential)
		{
			return 0;
			break;
		}
	}
	return 1;
}

int main()
{
	// вычисляем машинный эпсилон fixed
	epsilon = 1.0;
	while(epsilon/2.0 + 1.0 > 1.0)
	{
		epsilon = epsilon/2.0;
	}

	// вариант #22
	printf("Problem#22\n");
	printf("Dichotomy: %f,Steps:%d\n", dichotomy(f, 0.0, 1.0),nDichotomy);
	if(iteration_check(f_for_iteration, 0.0, 1.0))
		printf("Iteration: %f,Steps:%d\n", iteration(f_for_iteration, 0.0, 1.0),nIteration);
	else
		printf("Iteration: No");
	if(Newton_check(f, 0.0, 1.0))
		printf("Newton: %f, Steps:%d\n", Newton(f, 0.0, 1.0),nNewton);
	else
		printf("Newton: No");
	return 0;
}