Tiết 17: Giải bài toán trên máy tính
Mục tiêu bài dạy
- Biết các bước cơ bản khi tiến hành giải Bài toán trên máy tính: Xác định bài toán, xây dựng thuật toán, lựa chọn cấu trúc dữ liệu, viết chương trình, hiệu chỉnh, đưa ra kết quả và hướng dẫn sử dụng.
II. Phương tiện dạy học
Máy chiếu Projector.
Sơ đồ, các bước thực hiện của một vài bài toán.
III. Nội dung tiết dạy
Tổ chức lớp: ổn định lớp, kiểm tra sĩ số.
Kiểm tra bài cũ.
3. Tiến trình tiết dạy.
Câu hỏi: Nêu đặc điểm của ngôn ngữ máy
* Ưu điểm:
Là ngôn ngữ duy nhất máy tính có thể trực tiếp hiểu và thực hiện, cho phép khai thác triệt để và tối ưu khả năng của máy.
* Nhược điểm:
Ngôn ngữ phức tạp, phụ thuộc nhiều vào phần cứng, chương trình viết mất nhiều công sức, cồng kềnh và khó hiệu chỉnh.
Lệnh ở dạng mã nhị phân hoặc mã hexa
Phải nhớ máy móc các dòng số, phải dùng nhiều câu lệnh để diễn tả các thao tác
* Ngôn ngữ máy
Em chỉ ra những ưu điểm của việc giải bài toán bằng máy tính so với cách giải toán thông thường?
Bước 2: Lựa chọn hoặc thiết kế thuật toán.
Bước 1: Xác định bài toán.
Bước 3: Viết chương trình.
Bước 4: Hiệu chỉnh.
Bước 5: Viết tài liệu.
Các bước giải bài toán trên máy tính
INPUT:
OUTPUT:
Ví dụ:
Tìm ước số chung lớn nhất (ưCLN) của hai số nguyên dương M và N.
- Xác định hai thành phần
INPUT
Và OUTPUT
M , N là hai số nguyên dương.
ưCLN(M, N).
1. Xác định bài toán
- Khi lựa chọn hoặc thiết kế thuật toán thường quan tâm đến thời gian thực hiện, số lượng các ô nhớ,..
Cần lựa chọn hoặc thiết kế thuật toán sao cho việc viết chương trình cho thuật toán đó ít phức tạp.
Khi thiết kế hoặc lựa chọn thuật toán 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.
- Là bước quan trọng nhất để giải một bài toán.
a. Lựa chọn thuật toán
2. Lựa chọn hoặc thiết kế thuật toán
b. Diễn tả thuật toán
Cách 2: Vẽ sơ đồ khối.
Cách 1: Liệt kê các bước.
Theo hai cách:
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: Cho M, N;
Output: ƯCLN(M, N);
ý tưởng:
- 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-M);
- Nếu M > N thì ƯCLN(M, N) = ƯCLN(M-N, N);
Cách 2: Sử dụng sơ đồ khối
Nhóm 2,4
Hoạt động nhóm
Nhóm 1,3: Diễn tả thuật toán theo cách liệt kê
Nhóm 2,4: Diễn tả thuật toán theo cách sử dụng sơ đồ khối
B1: Nhập M, N;
B2: Nếu M = N lấy giá trị chung này làm ƯCLN rồi chuyển đến B5;
B3: Nếu M >N thì M ? M - N rồi quay lại B2;
B4: N ? N - M rồi quay B2;
B5: Đưa ra kết quả ưCLN; Kết thúc.
Cách 1: Liệt kê các bước
Đưa ra M rồi kết thúc
M = N ?
M > N ?
N  N - M
M  M - N
Nhập M và N
Sai
Sai
Đúng
Đúng
Cách 2: Vẽ sơ đồ khối
Đ
Đ
S
S
Mô phỏng việc thực hiện thuật toán
5
10
10
10
5
5
15
25
3
2
1
Lượt
Nhập M ,N
M =N ?
M > N ?
N ?N - M
M ?M - N
Đưa ra M ; Kết thúc
M= 25, N = 10
25 = 10 ?
25 >10
M ?25 - 10
15 = 10 ?
15 >10
M ?15 - 10
5 = 10 ?
5 > 10 ?
N = 10 - 5
5 = 5 ?
ƯSLN (25,10) = 5
M
N
+ Sử dụng ngôn ngữ lập trình để diễn đạt đúng thuật toán.
- Là tổng hợp giữa việc:
+ Lựa chọn cách tổ chức dữ liệu.
- Chương trình dịch chỉ có thể phát hiện và báo lỗi về mặt ngữ pháp chứ không thể phát hiện được cái sai của thuật toán.
3. Viết chương trình
Ví dụ: d? kiểm chứng tính đúng đắn của chương trình tìm ưCLN của M và N ta sử dụng bộ Input sau: M = 8; N = 8 ? ưCLN = 8
M = 25; N = 10 ? ưCLN = 5
Thử chương trình bằng cách thực hiện nó với một số bộ INPUT tiêu biểu (TEST) để kiểm tra kết quả, nếu có sai sót thì hiệu chỉnh lại. Nếu kết quả hiệu chỉnh cho thấy ngôn ngữ lập trình hoặc thuật toán không phù hợp ta phải lựa chọn hay thiết kế lại thuật toán.
4. HIệU CHỉNH
Mô tả chi tiết về bài toán, thuật toán, chương trình và kết quả thử nghiệm, hướng dẫn cách sử dụng.
Từ tài liệu này, người sử dụng đề xuất phương án để hoàn thiện thêm.
5. Viết TàI LIệU
Bước 2: Lựa chọn hoặc thiết kế thuật toán.
Bước 1: Xác định bài toán.
Bước 3: Viết chương trình.
Bước 4: Hiệu chỉnh.
Bước 5: Viết tài liệu.
Củng cố: Các bước giải bài toán trên máy tính
Trong các bước trên ta có thể bỏ qua bước xác định bài toán. Khi lựa chọn hoặc thiết kế thuật toán cần chú ý đến yêu cầu của bài toán và những điều kiện thực tế cho phép.
Câu 1 : Những phát biểu sau đúng hay sai.
1. Chương trình dịch không thể phát hiện ra lỗi trong mô tả thuật toán ở một chương trình.
2. Nếu bài toán có nhiều thuật toán để giải, ta viết chương trình dùng một thuật toán bất kì trong số đó để máy thực hiện.
3. Cần quan tâm đến thời gian thực hiện chương trình khi giao cho máy tính giải một bài toán.
Đúng
Sai



Câu 1 : Những phát biểu sau đúng hay sai.
4. Một trong những tiêu chí trong lựa chọn thuật toán để lập trình cho máy thực hiện là dễ viết chương trình.
Đúng
Sai

Câu 2 : Điền vào chỗ để trống trong các câu sau bằng cách chọn cụm từ thích hợp trong danh sách:
(1) Bước
là bước quan trọng nhất để giải một bài toán.
(2) là bước giúp người lập trình đưa ra quyết định có thay đổi một số việc đã làm trước đó hay không với mục đích có được sản phẩm tốt trong lập trình.
(3) Các quy tắc hướng dẫn sử dụng các kí hiệu của ngôn ngữ lập trình một cách hợp lệ được gọi là quy định của ngôn ngữ lập trình đó.
lựa chọn hoặc thiết kế thuật toán
xác định bài toán
viết chương trình
hiệu chỉnh
ngữ pháp
test
,
,
,
lựa chọn hoặc thiết kế thuật toán
...................................
hiệu chỉnh
ngữ pháp
........................
..................
(1) Mô tả chi tiết bài toán, thuật toán, bản thiết kế chương trình, kết quả thử nghiệm và hướng dẫn sử dụng, đây là việc.........................cho một phần mềm.
(2). Cần phải...........chương trình bằng cách đối chiếu kết quả thực hiện nó với một số bộ kiểm thử tiêu biểu theo đặc thù bài toán.
Câu 3 : Điền vào chỗ để trống trong các câu sau bằng cách chọn cụm từ thích hợp trong danh sách:
viết chương trình
, viết tài liệu
, test
dịch chương trình
viết tài liệu
test
Câu 4: Để giải bài toán trên máy tính, người ta phải thực hiện các công việc sau:
A. Lựa chọn hoặc thiết kế thuật toán
B. Xác định bài toán
C. Viết tài liệu
D. Viết chương trình
E. Hiệu chỉnh
Trong các sắp xếp dưới đây, sắp xếp nào đúng về thứ tự thực hiện các công việc nêu trên?
(a) a, b, d, e, c
(b) b, a, d, c, e
(c) b, a, d, e, c
(d) Cả 3 phương án trên đều sai
GIÁO VIÊN: HÀ ANH TUẤN

KẾT THÚC