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

Code:

#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;
}