CHƯƠNG 2 : GIẢI QUYẾT BÀI TOÁN BẰNG MÁY TÍNH

Nội dung trình bày: Thuật toán; Biểu diễn thuật toán; Các bước giải quyết bài toán trên máy tính.
Nội dung trích xuất từ tài liệu:
CHƯƠNG 2 : GIẢI QUYẾT BÀI TOÁN BẰNG MÁY TÍNHCHƯƠNG 2 : GIẢI QUYẾT BÀI TOÁN BẰNG MÁY TÍNH2.1 Thuật toán2.2 Biểu diễn thuật toán2.3 Các bước giải quyết bài toán trên máy tính2.1 Thuật toán CHƯƠNG TRÌNH = THUẬT TOÁN + CẤU TRÚC DỮ LIỆU (Programs = algorithms + Data Structures)1 Khái niệm Hệ thống các qui tắc  các đối tượng  THUẬT TOÁN Dãy hữu hạn các thao tác (bước)  Thực hiện hữu hạn lần các thao tác ta đạt được mục tiêu định trướcVD: giải phương trình ax + b = 0 (a0) Đối tượng: a,b,x Qui tắc : ax + b = 0 và các qui tắc toán học khác  Các thao tác : (1) Nhập giá trị cho a (a0), b (2) Tính x = -b/a (3) Xuất kết quả x (4) DừngChú ý :•Một vấn đề, bài toán cho trước có thể có nhiều thuật toán khác nhau. Các thao tác : Các thao tác : (1) Nhập giá trị cho a (a0), b (1) Nhập giá trị cho a (a0), b (2) Tính x = -b/a (2) Tính x1 = -b (3) Xuất kết quả x (3) Tính x2 = 1/a (4) Dừng (4) Tính x = x1*x2 (5) Xuất kết quả x (6) Dừng•Thuật toán cho kết quả với thời gian nhanh nhất được coi là thuật toán tốiưu về mặt thời gian.•Thuật toán sử dụng ít bộ nhớ nhất được coi là thuật toán tối ưu về bộ nhớ.2 Các ví dụ Đối tượng: a,b,c,x Qui tắc : ax2 + bx + c = 0 và các qui tắc toán học khác1. Giải phương trình ax2 + bx + c = 0 ( a0 ). Các thao tác : (1) Nhập giá trị cho a (a0), b, c (2) Tính DELTA=B*B-4*A*C (3) So sánh DELTA với 0 (4) Dựa vào (3) Nếu DELTA0 Tính nghiệm x1 = (-b+sqrt(DELTA))/(2*a) x2 = (-b-sqrt(DELTA))/(2*a) Xuất kết quả x1, x2 Dừng2. Tính giá trị của đa thức Pn(X)=AnXn + An-1Xn-1 +…+ A1X1 + A0 tại X=C Viết lại : Pn(C)=(…( AnC+An-1)C+An-2 )C+…+A1 )C+A0 Minh họa với n=3. P3(C) = A3C3 + A2C2 +A1C1 + A0 = (( A3C+A2)C+A1 )C+A Các thao tác : N=3 (1)Q= An ; i=n (1)Q= A3 ; i=3 (2) i:=i-1, so sánh i với 0 (2) i:=2>=0 (3) Dựa vào (2) (3) Q:=Q*C+ A2=A3*C+A2 Nếu i>=0 (2) i:=1>=0 Tính Q:=Q*C+ Ai (3) Q:=Q*C+ A1=(A3*C+A2)*C+A1 → (2) =A3*C2+A2*C+A1 Nếu i=0 Xuất kết quả Q (3) Q:=Q*C+ A0=(A3*C2+A2*C+A1)*C+A0 Dừng =A3*C3+A2*C2+A1*C+A0 (2) i:=-13. Tính tổng n số tự nhiên đầu tiên S=1+2+…+n; n>0 (S=(n+1)*n/2) Viết lại S=(…(0+1)+2)+…+n) Các thao tác : n=5 (1) S=0; i=1 (2) S:=S+i i S (3) i:=i+1 1 0+1 =1 (4) So sánh i với n 2 (0+1)+2 =3 (5) Dựa vào (4) 3 ((0+1)+2)+3 =6 Nếu in 6 * Xuất kết quả S Dừng1. Giải phương trình bậc 2 ax2 + bx + c = 0 với a tùy ý.2. Kiểm tra số nguyên dương cho trước là số nguyên tố.3. Kiểm tra số nguyên dương cho trước là số chính phương.4. Tìm ước số chung lớn nhất của 2 số nguyên dương cho trước.5. Liệt kê các số khác nhau trong 1 dãy số cho trước. Thuật toán số nguyên tố DK: j=2 và n chia hết cho 1 và chính nó. (1): Nhập n (2): j=2 (3): j  Nếu không thỏa (3) - > (5)  Nếu thỏa (3) -> (4) (4):j=j+1 -> (3) (5) Nếu j=n thì in số nguyên tố (6) Dừng3 Các đặc trưngTính dừng (kết thúc) :•thuật toán phải dừng sau hữu hạn lần thực hiện thao tác.•Trong VD1 tính dừng là rõ ràng; Trong VD2 ở (2) i giảm 1 đơn vị cho nênsau một số lần thực hiện thao tác ta sẽ có i=0 Tính Q:=Q*C+ Ai → (2) Nếu i•Trong VD3 ở (3) i tăng 1 đơn vị cho nên sau một số lần thực hiện thao tácta sẽ có i>n Các thao tác : (1) S=0; i=1 (2) S:=S+i (3) i:=i+1 (4) So sánh i với n (5) Dựa vào (4) Nếu in Xuất kết quả S ...