#include <stdio.h>
#include <math.h>
#include <malloc.h>
#include <stdlib.h>

double Func(double);
int BisectRoot(double,double,double,double,double *,int,int *);

void main()
{
	int i,n,m;
	double a,b,h,eps,*x;
	n = 3;						/*方程根的個數的預估值*/
	x = (double*)calloc(n,sizeof(double));		/*開辟內存空間*/
	if(x == NULL)
	{
		printf("內存分配失敗\n");
		exit(1);
	}
	a = -3;								/*區間起始端點*/
	b = 7;								/*區間終止端點*/
	h = 0.1;							/*步長*/
	eps = 1.e-8;						/*要求達到的精度*/
	BisectRoot(a,b,h,eps,x,n,&m);		/*調用二分法函數*/
	printf("y=sin(x)在范圍%2.0f和%2.0f之間的根有%d個根\n",a,b,m);
	printf("它們分別是：\n");
	for(i = 0;i<n;i++)
	printf("x[%d] = %e\n",i,x[i]);
	free(x);					/*釋放內存空間*/
}

double Func(double x)
{
	return(sin(x));
}

int BisectRoot(a,b,h,eps,x,n,m)
double a;			/*實型變量，輸入參數，求根區間的起始端點*/
double b;			/*實型變量，輸入參數，求根區間的終止端點*/
double h;			/*利用逐步掃描法確定根位置時的步長*/
double eps;			/*實型變量，輸入參數，控制精度的參數*/
double *x;			/*實型一維數組，輸出參數，存放計算得到的數組*/
int n;				/*輸入參數，區間內方程根的個數的預估值*/
int *m;				/*輸出參數，實際求得的根的個數*/
{
	double z,z0,z1,y,y0,y1;
	*m = 0;
	z = a;
	y = Func(z);
	while(1)		/*無限循環，直到遇到return或者break語句*/
	{/*如果逐步掃描到求根區間的右端點或者得到的根的個數達到預估根的個數*/
		if((z>b+h/2)||(*m==n))	
			return(1);
		if(fabs(y)<eps)		/*如果當前根z對應的函數f(z)滿足精度要求*/
		{
			*m+=1;
			x[*m-1] = z;	/*將此時的z值賦值給x數組*/
			z+=h/2;
			y = Func(z);
			continue;		/*結束本次循環，即跳過循環體中下面尚未執行
							 的語句接著進行下一次是否執行循環的判定*/
		}
	
		z1 = z+h;			/*逐步掃描中小區間的右端點*/
		y1 = Func(z1);		/*小區間右端點對應的函數值*/
		if(fabs(y1)<eps)	/*如果右端點恰好滿足根的精度要求*/
		{
			*m+=1;
			x[*m-1] = z1;
			z = z1+h/2;
			y = Func(z);
			continue;
		}
		if(y*y1>0)			/*如果對應根乘積大于零，說明該區間內沒有根*/
		{
			y = y1;			
			z = z1;
			continue;
		}
		while(1)		/*如果本while循環執行，說明逐步掃描小區建z和z1間有根*/
		{
			if(fabs(z1-z)<eps)		/*如果滿足精度要求*/
			{
				*m+=1;
				x[*m-1]=(z1+z)/2;
				z = z1+h/2;
				y = Func(z);
				break;
			}
			z0 = (z1+z)/2;			/*二分發求根公式*/
			y0 = Func(z0);
			if(fabs(y0)<eps)
			{
				*m = *m+1;
				x[*m-1] = z0;
				z =z0+h/2;
				y = Func(z);
				break;
			}
			if(y*y0<0)			/*如果乘積小于零，說明根在z和z0之間*/
			{
				z1 = z0;
				y1 = y0;
			}
			else				/*否則根在z0和z1之間*/
			{
				z = z0;
				y = y0;
			}
		}
	}
}