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

Chia sẻ: Nguyen Kien | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

97
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Please purchase a personal license. personal
BÀI TOÁN A TH C
Bài toán a th c Bài toán: Cho a th c có d ng sau: P(x) = anxn+ an-1xn-1+ an-2xn-2…+ a2x2+a1x+a0 Tính giá tr a th c. Trong ó bi t giá tr A=[an,…,a0] , input x P(x)
Thu t toán cơ b n Thu to Thu t toán: result = a0 + a1*x; xpower = x; for (int i=2;i
Thu t toán Horner Thu to Phâ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+a0 Thu 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 x256 C1: 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)/2 Bài t p: Phân tích a th c sau theo 2 phương pháp Horner và X lý h s x7+6x6+4x4-2x3+3x2-7x+5