Bài 6. Giải bài toán trên máy tính
Bài soạn
đặt vấn đề
Với các giá trị:
M = 25; N = 10.
M = 17; N = 13.

Tìm ước số chung lớn nhất (ưCLN) của hai số nguyên dương M và N.
Bước 2: Lựa chọn hoặc thiết kế thuật toán. F
Bước 1: Xác định bài toán. F
Bước 3: Viết chương trình. F
Bước 4: Hiệu chỉnh. F
Bước 5: Viết tài liệu. F
Các bước giải bài toán trên máy tính
Bước 1: Xác định bài toán
Xác định hai thành phần INPUT, OUTPUT
Và mối quan hệ giữa chúng

INPUT: M , N là hai số nguyên dương.
OUTPUT: ưCLN(M, N).
Ví dụ: Bài toán tìm ƯCLN(M,N)?
Bước 2: Lựa chọn hoặc thiết kế thuật toán
Nếu M = N
- Đúng ố ưCLN = M (hoặc N) ố Kết thúc;
- Sai � Xét: nếu M > N
- Đúng � M = M - N;
- Sai � N = N - M;
Quá trình này được lặp lại cho đến khi M = N.
a. Lựa chọn thuật toán
Lựa chọn một thuật toán tối ưu.
Ví dụ: Xét bài toán tìm ƯCLN(M,N)
b. Diễn tả thuật toán
Theo hai cách:
Cách 1: Liệt kê các bước.
Cách 2: Vẽ sơ đồ khối.
Cách 1: Liệt kê các bước
B1: Nhập M, N;
B2: Nếu M = N lấy ưCLN = M (hoặc N), 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.
Đ
Đ
S
S
Cách 2: Diễn tả thuật toán bằng sơ đồ khối
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
S
Mô phỏng thuật toán tìm ƯCLN
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 ?
ƯCLN (25,10) = 5
M
N
Bước 3: Viết chương trình
F 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:
F Lựa chọn cách tổ chức dữ liệu.
Bước 4: Hiệu chỉnh
TEST:
M = 8; N = 8 � ưCLN = 8
M = 25; N = 10 � ưCLN = 5
M = 17; N = 13 � ưCLN = 1

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.
Bước 5: Viết tài liệu

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 các khả năng hoàn thiện thêm.
Vấn đề 1: Hãy nêu tiêu chuẩn lựa chọn thuật toán?
Vấn đề 2: Hãy chỉ ra Input, Output của các bài toán dưới đây:
a) Nhập từ bàn phím ba số nguyên a, b, c Tìm số lớn nhất trong ba số?
b) Cho số nguyên dương N và dãy N số nguyên dương; Tìm số trong dãy có tổng các ước số lớn nhất? VD N =5, dãy số là 12,10,15,8,14. trả lời là 12
Củng cố
_ Trả lời câu hỏi và làm bài tập SGK Trang 51
Bài tập làm thêm:
Có một chương trình giải bài toán: Nhhạp từ bán phím ba số nguyên dương a, b, c kiểm tra xem ba số này có thể là ba cạnh của một tam giác không?
Em hãy nêu một số bộ dữ liệu kiểm thử (Test) để kiển định tính đúng đắn của chương trình này?
Bài tập về nhà