THUẬT TOÁN TÌM KHOẢNG CÁCH LY NGHIỆM


Định nghĩa:
Khoảng [a,b] nào đó gọi là khoảng phân ly nghiệm của phương trình f(x) = 0 nếu nó chỉ chứa một và chỉ một nghiệm của phương trình đó.
Định lý: Nếu [a,b] là một khoảng trong đó hàm số f(x) liên tục, đơn điệu và đồng thời f(a).f(b)<0 thì [a,b] là một khoảng phân ly nghiệm của phương trình f(x)=0.

1. Ý TƯỞNG CÀI ĐẶT
- Phương pháp cài đặt: vét cạn.
- Các bước thực hiện:
o Xác định [a,b] tồn tại nghiệm ở trong khoảng đó.
o Xác định bước nhảy cần vét từ a đến b.
o Tiến hành vét từ a đến b với bước nhảy. Nếu trong quá trình vét tồn tại f(i).f(i+bước nhảy)<0 (i thuộc [a,b]) thì khoảng [i,i+bước nhảy] là một khoảng cách ly nghiệm.

2. CÀI ĐẶT
Mã:
#include "conio.h"
#include "iostream.h"
/*Cau truc du lieu luu tru khoang phan ly*/
typedef struct PhanLy {
	int n;
	double*a;
	double*b;
};
/*Khoi tao khoang phan ly nghiem */
PhanLy KhoiTaoPhanLy(int n) {
	PhanLy PL;
	PL.a = new double [n];
	PL.b = new double [n];
	PL.n = 0;
	return PL;
}
/*Nhap vao mot da thuc*/
double*NhapDaThuc(int Bac) {
	double *A = new double [Bac+1];
	for(int i= 0; i<=Bac; i++) {
		cout<<"a"<<i<<" = ";
		cin>>A[i];
	}
	return A;
}
/*Xuat da thuc co he so A[] va Bac*/
void XuatDaThuc( double*A,int Bac, char*s) {
	cout<<"Da Thuc Vua Nhap la:\n";
	cout<<s<<" = "<<A[0];
	for(int i=1; i<=Bac; i++){
		if(A[i]>0)
			cout<<" + "<<A[i]<<"x^"<<i;
		if(A[i]<0) 
			cout<<A[i]<<"x^"<<i;
	}
}
/*Tinh gia tri cua da thuc tai diem x su dung luoc do hoocner*/
double f(double*A, int Bac, double x) {
	 double KetQua = A[Bac];
	for(int i=Bac-1; i>=0; i--)
		KetQua=KetQua*x + A[i];
	return KetQua;
}
/*Tim Moi Khoang Phan Ly Nghiem*/
PhanLy TimPhanLy( double*A, int Bac,  double Xa,  double Xb, double BuocNhay) {
	PhanLy PL = KhoiTaoPhanLy(Bac);
	double k=Xa;
	while(k<=Xb){
		if(f(A,Bac,k)*f(A,Bac,k+BuocNhay)<0){
			PL.a[PL.n] = k;
			PL.b[PL.n] = k+BuocNhay;
			PL.n++;
		}
		k=k+BuocNhay;
	}
	return PL;
}
/*Xuat Moi Khoang Phan Ly Nghiem*/
void XuatPhanLy(PhanLy PL) {
	if(PL.n==0)
		cout<<"\nKhong Tim Duoc Khoang Phan Ly";
	else {
		for(int i = 0; i<PL.n; i++)
			cout<<"("<<PL.a[i]<<","<<PL.b[i]<<")\t";
	}
}

/*Chuong Trinh Chinh*/
void main(){
	clrscr();
	double*Fx,a,b,BuocNhay;
	int n;
	cout<<"Nhap Vao Bac Cua Phuong Trinh:";
	cin>>n;
	Fx = NhapDaThuc(n);
	XuatDaThuc(Fx,n,"f(x)");
	cout<<"\nNhap [a,b] Can Tim Khoang Phan Ly Nghiem:\n";
	cout<<"a = ";
	cin>>a;
	cout<<"b = ";
	cin>>b;
	cout<<"Nhap Buoc Nhay: ";
 	cin>>BuocNhay;
	PhanLy PL = TimPhanLy(Fx,n,a,b,BuocNhay);
	cout<<"Khoang Phan Ly Tim Duoc:";
	XuatPhanLy(PL);
	getch();
	delete Fx;
}