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

Thêm vào BST

Báo xấu

247
lượt xem 60
download

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ủ đề:

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

Lưu

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

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.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ước
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
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ớ.
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
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
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
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.
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
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
•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
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
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
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
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
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
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.
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
Khối xuất dữ liệu In a, b,… Khối dừng (kết thúc) END