10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
1
§ 6. GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Sau bài học này các em có thể :
Nhớ lại và làm rõ hơn các khái niệm về : bài toán; thuật toán; dữ liệu; lệnh; ngôn ngữ lập trình và chương trình
Liệt kê và viết được mội dung các bước giải một bài toán trên máy tính
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
2
§ 6. GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Xác định bài toán
Lựa chọn hoặc thiết kế thuật toán
Viết chương trình
Hiệu chỉnh
Viết tài liệu
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
3
1. Xác định bài toán
Mỗi bài toán được đặc tả bởi hai thành phần: Input và Output.
Việc xác định bài toán chính là xác định rõ hai thành phần Input; Output và mối quan hệ giữa chúng.
Cần nghiên cứu cẩn thận Input và Output để có thể lựa chọn thuật toán:
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
4
1. Xác định bài toán
Cách thể hiện các đại lượng đã cho
Các đại lượng phát sinh trong quá trình giải bài toán
Ngôn ngữ lập trình thích hợp.
 Lựa chọn cấu trúc dữ liệu và ngôn ngữ lập trình thực hiện
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
5
1. Xác định bài toán
Ví dụ :
Khi cần biểu diễn một số nguyên dương N, là tuổi của một người, có thể chỉ rõ phạm vi giá trị của N từ 0 đến 150, để lựa chọn cách thể hiện N bằng kiểu dữ liệu thích hợp.
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
6
2. Lựa chọn hay thiết kế thuật toán
a) Lựa chọn thuật toán
Là bước quan trọng nhất để giải một bài toán.
Mỗi thuật toán chỉ giải một bài toán
Có thể có nhiều thuật toán khác nhau cùng giải một bài toán.
Cần thiết kế hoặc chọn một thuật toán phù hợp đã có để giải bài toán cho trước.
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
7
2. Lựa chọn hay thiết kế thuật toán
Cần quan tâm đến các tài nguyên như:
Thời gian thực hiện
Số lượng ô nhớ,...
Trong đó thời gian được quan tâm nhiều nhất vì đó là dạng tài nguyên không tái tạo được.
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
8
2. Lựa chọn hay thiết kế thuật toán
Ví dụ: với bài toán tìm kiếm, thuật toán tìm kiếm nhị phân ít thao tác so sánh hơn thuật toán tìm kiếm tuần tự.
 Thuật toán tìm kiếm nhị phân sẽ thực thi nhanh hơn thuật toán tìm kiếm tuần tự
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
9
2. Lựa chọn hay thiết kế thuật toán
Ngoài ra cần quan tâm đến thiết kế hoặc lựa chọn thuật toán sao cho việc viết chương trình cho thuật toán đó ít phức tạp.  tiêu chí của thuật toán là tính hiệu quả
Cần căn cứ vào lượng tài nguyên mà thuật toán đòi hỏi và lượng tài nguyên thực tế cho phép.
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
10
2. Lựa chọn hay thiết kế thuật toán
b) Diễn tả thuật toán
Ví dụ: Tìm ước chung lớn nhất (ƯCLN) của hai số nguyên dương M và N.
Xác định bài toán
Input: Nhập M, N;
Output: ƯCLN(M, N).
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
11
2. Lựa chọn hay thiết kế thuật toán
Ý tưởng: Sử dụng những điều đã biết sau:
Nếu M = N thì giá trị chung đó là ƯCLN của M và N;
Nếu M > N thì ƯCLN(M, N) = ƯCLN(M – N,N).
Nếu M < N thì ƯCLN(M, N) = ƯCLN(M,N- M);
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
12
2. Lựa chọn hay thiết kế thuật toán
Thuật toán
a) Thuật toán diễn tả bằng cách liệt kê
Bước 1: Nhập M, N;
Bước 2: Nếu M = N đưa ra ƯCLN(M,N)=M ; Kết thúc
Bước 3: Nếu M > N thì M  M - N rồi quay lại bước 2;
Bước 4: N  N - M rồi quay lại bước 2;
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
13
2. Lựa chọn hay thiết kế thuật toán
b) Thuật toán diễn tả bằng sơ đồ khối
Nhập M và N
M = N ?
Đưa ra M; Kết thúc
M > N ?
M  M - N
N  N - M
Đúng
Đúng
Sai
Sai
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
14
2. Lựa chọn hay thiết kế thuật toán
c) Mô tả bằng số liệu cụ thể
1. Cho hai số: M = 25 và N = 10 tìm ƯCLN
25
15
5
5
10
10
10
5
M=
N=
M > N
M = M - N
N = 10 - 5
M = N
ƯCLN(M,N) = 5
M = 25 – 10
M = 15 – 10
N > M
N = N - M
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
15
2. Lựa chọn hay thiết kế thuật toán
c) Mô tả bằng số liệu cụ thể
2. Cho hai số: M = 7 và N = 5 tìm ƯCLN
7
2
1
5
3
1
M=
N=
M > N
M = M - N
N = 3 - 2
M = N
ƯCLN(M,N) = 1
M = 7 – 5
N > M
N = N - M
N = 5 - 2
M = 2 – 1
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
16
3. Viết chương trình
Viết chương trình là tổng hợp giữa lựa chọn cách tổ chức dữ liệu và sử dụng ngôn ngữ lập trình để diễn đạt đúng thuật toán.
Nên chọn một ngôn ngữ lập trình hoặc một phần mềm chuyên dụng thích hợp với thuật toán.
Viết chương trình trong ngôn ngữ nào thì cần phải tuân theo đúng quy định cú pháp (Syntax) của ngôn ngữ đó.
Chương trình dịch chỉ có thể phát hiện và thông báo các lỗi về mặt cú pháp
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
17
4. Hiệu chỉnh
Chương trình khi viết xong vẫn có thể còn nhiều lỗi khác chưa phát hiện được nên kết quả thực thi không đúng.
Vì vậy, cần phải thử (Test) chương trình bằng một số bộ Input tiêu biểu phụ thuộc vào đặc thù của bài toán mà đã biết trước Output. Các bộ Input này được gọi là các Test.
Nếu có sai sót, ta phải sửa chương trình rồi thử lại.
 Quá trình này được gọi là hiệu chỉnh (Maintenance) .
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
18
4. Hiệu chỉnh
Ví dụ: để kiểm tra tính đúng đắn của chương trình giải phương trình bậc nhất ax + b = 0, ta có thể sử dụng ba bộ Test như sau:
a = 0; b = 0 (Thông báo pt vô định)
a = 0;b <> 0 (Thông báo pt vô nghiệm)
a <> 0 (Đưa ra nghiệm x = -b/a)
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
19
5. Viết tài liệu
 Tính chuyên nghiệp của phần mềm
Tài liệu phải mô tả:
Bài toán,
Thuật toán,
Thiết kế chương trình,
Kết quả thử nghiệm
Và hướng dẫn sử dụng.
Tài liệu này rất có ích cho người sử dụng chương trình và cho việc đề xuất những khả năng hoàn thiện thêm.
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
20
5. Viết tài liệu
Các bước trên có thể lặp đi lặp lại nhiều lần cho đến khi ta cho rằng chương trình đã làm việc đúng đắn và hiệu quả.
Bao gồm:
Sưu liệu chương trình;
Tài liệu phân tích thiết kế hệ thống;
Bộ dữ liệu thử nghiệm;
10/3/2012 10:34:37 PM
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
21
Câu hỏi và bài tập
Hãy nêu các bước giải bài toán
Nêu nội dung bước xác định bài toán
Nêu nội dung bước chọn lựa hoặc thiết kế thuật toán
Hãy viết thuật toán giải phương trình bậc 2 ax2 + bx + c = 0 và đề xuất các test tiêu biểu