Cấu trúc dữ liệu và giải thuật (phần 9)

Trong phần tài liệu này các bạn sẽ làm quen với các thuật toán cơ bản để tính toán các đã thức, tập làm quen với tối ưu các phép tính trong đa thức với các thuật toán cơ bản
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật (phần 9)Please purchase apersonal license. personalBÀI TOÁN A TH C Bài toán a th cBài toán: Cho a th c có d ng sau:P(x) = anxn+ an-1xn-1+ an-2xn-2…+ a2x2+a1x+a0Tính giá tr a th c. Trong ó bi t giá trA=[an,…,a0] , input x P(x) Thu t toán cơ b n Thu toThu t toán:result = a0 + a1*x;xpower = x;for (int i=2;i Thu t toán Horner Thu toPhân tích a th c:P(x) = anxn+ an-1xn-1+ an-2xn-2…+ a2x2+a1x+a0 ({…[(anx+an-1)*x+an-2]*x+…+a2}*x+a1)*x+a0Thu t toán:result = an;for (int i=n-1;i>=0;i--){ result = result * x; result = result + ai;} Thu t toán Horner Thu to ánh giá thu t toán:- S phép c ng: n- S phép nhân: n So v i thu t toán cơ b n, thu t toán Horner có s phép nhân gi m ½ l n Thu t toán ti n x lý h s Thu to lýVí d : Tính x256C1: for (int i=1;i Thu t toán ti n x lý h s Thu to lýThu t toán: s d ng thu t toán này thì an=1, và n = 2k-1.-- a th c P(x) lúc này có th bi u di n thành: P(x) = (xj+b)*q(x) + r(x) trong ó j = 2k-1- Ti p t c làm tương t i v i q(x) và r(x) như p(x)- V n là ph i ch n b c n th n Thu t toán ti n x lý h s Thu to lý ánh giá thu t toán:P(x)=(x4+5)*[(x2-1)*(x+4)+(x+12)]+[(x2+1)*(x-11)+(x-26)]- S phép nhân: x2 1 phép nhân x4 = x2*x2 1 phép nhân 3 phép nhân- S phép c ng: 10 So sánh v i các thu t toán khác: Thu t toán Phép nhân Phép c ng Cơ b n 13 7 Horner 7 7 X lý h s 5 10 T ng k t ng Thu t toán Phép nhân Phép c ng Cơ b n 2n-1 n Horner n n X lý h s n/2+lgn (3n-1)/2Bài t p: Phân tích a th c sau theo 2 phươngpháp Horner và X lý h s x7+6x6+4x4-2x3+3x2-7x+5