//求非線性方程的根
//程序中共給出了以下幾種方法求非線性方程的根
//  (1)二分法 (2)牛頓法 (3)普通迭代法 (4)斯蒂芬森迭代法 (5)弦截法
//程序中用到的函數為： f(x)=x^3-x-1
//其中:(1)普通迭代法用的迭代函數為：x=(x+1)^(1/3)
//     (2)斯蒂芬森迭代法用的迭代函數為：x=x^3-1

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

int Num;   //全局變量 保存迭代次數
int flag=0;//全局標示符 
           //flag=1時標示發生了函數微分值為零，不能在繼續計算(主要針對牛頓迭代法)
           //flag=2標示牛頓迭代法中超過最大迭代次數，迭代失敗

float fFunction(float); //函數f(x)
float fFunWeifen(float);//函數f(x)的導函數f'(x)
float fFunDiedai(float);//斯蒂芬森迭代法用的迭代函數
float fFunComonDiedai(float);//普通迭代法用的迭代函數
float ErFenMethold(float,float,float);//二分法
float Newton(float,float,int);//牛頓法
float Steffensen(float,float,float);//斯蒂芬森迭代法
float DiedaiMethold(float,float,float);//普通迭代法
float XianjieMethold(float,float,float,float);//弦截法

void main()
{
	float cdd;
	cout<<"(1)二分法求非線性方程的根"<<endl;
	cout<<"k"<<"  "<<"a1"<<"    "<<"b1"<<"   "<<"x"<<endl;
	ErFenMethold(1,1.5,0.00001);

	cout<<endl;
	cout<<"(2)牛頓法求非線性方程的根"<<endl;
	Newton(1.25,0.00001,100); //設定最大迭代次數為10次

	cout<<endl;
	cout<<"(3)普通迭代法求非線性方程的根"<<endl;
	DiedaiMethold(1.5,0.00001,1000);

	cout<<endl;
	cout<<"(4)斯蒂芬森迭代法求非線性方程的根"<<endl;
	Steffensen(1.25,0.00001,100);  //設定最大迭代次數為10次

	cout<<endl;
	cout<<"(5)弦截法求非線性方程的根"<<endl;
	XianjieMethold(1.25,1.29,0.00001,100);
}

//二分法
float ErFenMethold(float a,float b,float xlon) 
{
	float result,a1,b1,y,y0,x;
	a1=a;
	b1=b;
	y0=fFunction(a);
	int k=0;
	do 
	{
		x=(a1+b1)/2;
		y=fFunction(x);
		if ((y*y0) > 0)
		a1=x;
		else
		b1=x;
		k++;
		cout<<k<<"  "<<a1<<"  "<<b1<<"  "<<x<<endl;
	} while ((b1-a1)>=xlon);
	result=x;
	Num=k;
	return result;//返回結果
}

//牛頓迭代法
float Newton(float x0,float xlon,int N) 
{
	int k=1;
	float result,x1;
	for (k;k<N;k++)
	{
		if (fFunWeifen(x0)==0)
		{
			flag=1;
			return 0;
		}
		else
		{
			x1=x0-fFunction(x0)/fFunWeifen(x0);
			if (fabs(x1-x0)<xlon)
			{
				result=x1;
				cout<<k<<"  "<<result<<endl;
				return result;
			}
			x0=x1;
		}
	}
	if (k==N)
	{
		flag=2;
		cout<<" !!!此種情況下迭代法不收斂"<<endl;
		return 0;
	}
	
}

//普通迭代法
float DiedaiMethold(float x0,float xlon,float N)
{
	float result;
	int k=0;
	float x,x1;
	x1=x0;
	for (k;k<=N;k++)
	{
		x=fFunComonDiedai(x1);
		if (fabs(x-x1)<xlon)
		{
			result=x;
			cout<<k<<"  "<<result<<endl;
			return result;
		}
		x1=x;
	}
	if (k=N)
	{
		cout<<" !!!此種情況下迭代法不收斂"<<endl;
	}
}

//斯蒂芬森迭代法
float Steffensen(float x0,float xlon,float N)
{
	float result;
	float x,x1;
	int k=0;
	x1=x0;
	for (k;k<=N;k++)
	{
		x=x1-(fFunDiedai(x1)-x1)*(fFunDiedai(x1)-x1)/(x1-2*fFunDiedai(x1)+fFunDiedai(fFunDiedai(x1)));
		if (fabs(x-x1)<xlon)
		{
			result=x;
			cout<<k<<"  "<<result<<endl;
			return result;
		}
		x1=x;
	}
	if (k=N)
	{
		cout<<" !!!此種情況下迭代法不收斂"<<endl;
	}

}

//弦截法
float XianjieMethold(float x1,float x2,float xlon,float N)
{
	float result;
	int k=0;
	float xFirst,xSecond,xThird;
	xFirst=x2;
	xSecond=x1;
	for (k;k<=N;k++)
	{
		xThird=xSecond-fFunction(xSecond)*(xSecond-xFirst)/(fFunction(xSecond)-fFunction(xFirst));
		if (fabs(xThird-xSecond)<xlon)
		{
			result=xThird;
			cout<<k<<"  "<<result<<endl;
			return result;
		}
		xFirst=xSecond;
		xSecond=xThird;
	}
	if (k=N)
	{
		cout<<" !!!此種情況下迭代法不收斂"<<endl;
	}
}

//初始給定的函數f(x)
float fFunction(float x)
{
	float result;
	result=x*x*x-x-1;
	return result;
}
float fFunComonDiedai(float x)
{
	float result;
	result=pow(x+1,0.3333);
	return result;
}

float fFunDiedai(float x)
{
	float result;
	result=x*x*x-1;
	return result;
}

//函數f(x)的導函數f'(x)
float fFunWeifen(float x)
{
	float result;
	result=3*x*x-1;
	return result;
}