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

Chia sẻ: Vo An | Ngày: | Loại File: PPT | Số trang:25

0
161
lượt xem
58
download

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

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

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.

Chủ đề:
Lưu

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

  1. CHƯƠNG 2 : GIẢI QUYẾT BÀI TOÁN BẰNG MÁY TÍNH 2.1 Thuật toán 2.2 Biểu diễn thuật toán 2.3 Các bước giải quyết bài toán trên máy tính
  2. 2.1 Thuật toán CHƯƠNG TRÌNH = THUẬT TOÁN + CẤU TRÚC DỮ LIỆU (Programs = algorithms + Data Structures)
  3. 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ước
  4. VD: 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ừng
  5. Chú ý : •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ớ.
  6. 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ác 1. 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ừng
  7. 2. 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:=-1
  8. 3. 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ừng
  9. 1. 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.
  10. 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ừng
  11. 3 Các đặc trưng Tí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ên sau 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
  12. •Trong VD3 ở (3) i tăng 1 đơn vị cho nên sau một số lần thực hiện thao tác ta 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 Dừng
  13. Tính xác định : các thao tác ở mỗi bước phải rõ ràng và chỉ hiểu theo một nghĩa duy nhất
  14. Tính phổ dụng : áp dụng cho các bài toán cùng loại. Trong VD1 thuật toán không phổ dụng vì thuật toán không sử dụng được khi nhập a=0 hoặc a là một ký tự; Trong VD3 thuật toán sẽ sai khi cho n=0 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 Dừng
  15. Tính khả thi : bao gồm các thao tác mà máy có thể thực hiện được. Phép tính căn trong tính nghiệm khi giải phương trình bậc 2 ở trường hợp DELTA>0 là không thực hiện được trên máy tính
  16. Tính đầy đủ : phải vét hết các tình huống, các khả năng có thể có. Thuật toán trong VD1 nêu trên đã bỏ qua trường hợp a=0; Thuật toán trong VD3 bỏ qua trường hợp n=0
  17. Tính đúng đắn : phải chứng minh tính đúng đắn của thuật toán. Chứng minh tính đúng đắn của thuật toán là một việc làm khó, thông thường ta chỉ kiểm tra thuật toán với giá trị nhỏ (hoặc tính nhẩm được). VD : kiểm tra thuật toán trong VD3 với n=5 ta có S=15 i S 0 1 0+1=1 i
  18. 2.2 Biểu diễn thuật toán 1 Các cách biểu diễn thuật toán Ngôn ngữ tự nhiên hoặc mã giả VD : sử dụng ngôn ngữ tự nhiên để biểu diễn thuật toán giải phương trình bậc 2 với a0 Bắt đầu. Nhập a(a0), b, c. Tính Delta=b*b-4*a*c. Nếu Delta0 thì Tính x1,2=(-b± sqrt(delta))/(2*a). In x1, x2. Dừng.
  19. Lưu đồ (Flowchart) Các qui ước Khối bắt đầu START/BEGIN Nhập x,y,… Nhập x,y,… Khối nhập dữ liệu Khối thao tác, tính toán Thao tác/ Biểu thức Biểu thức Đ Khối kiểm tra ĐK S =a =b =c
  20. Khối xuất dữ liệu In a, b,… Khối dừng (kết thúc) END

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản