TRƯỜNG THPT KRÔNG BUK
(TỔ TOÁN TIN)
KIỂM TRA BÀI CŨ
Em hãy so sánh ngôn ngữ máy và ngôn ngữ lập trình bậc cao?
Chương trình dịch dùng để làm gì?



Hướng dẫn trả lời
Chương trình dịch dùng để dịch từ chương trình viết bằng ngôn ngữ khác sang ngôn ngữ máy.
B1. Xác định
bài toán
B2. Lựa chọn hoặc thiết kế thuật toán
B3. Viết chương trình
B4. Hiệu chỉnh
B5. Viết
tài liệu
NỘI DUNG
TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
NỘI DUNG

1. XÁC ĐịNH
BÀI TOÁN















XÁC ĐỊNH BÀI TOÁN
Ví dụ: Cho bài toán tìm ước chung lớn nhất của hai số M và N là 2 số nguyên dương.

?
Input cho M,N
Output tìm UCLN(M,N)
Việc xác định bài toán là xác định rõ hai thành phần:
Input
Output
Input
Output
Hãy xác định bài toán trên?
TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
a. Lựa chọn thuật toán
Có thể
có nhiều
cách giải
(thuật toán)
BÀI TOÁN
Cách 1
Cách 2
Cách 3
. . .
Cần phải chọn cách giải (Thuật toán) sao cho :
Thuật toán cần ít thời gian thực hiện, chiếm ít ô nhớ, thực hiện ít phép toán. . .
Thuật toán ít phức tạp,
NỘI DUNG

1. XÁC ĐỊNH
BÀI TOÁN
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
Lựa chọn thuật toán









Lựa chọn thuật toán và tổ chức dữ liệu.
TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
KẾT QUẢ
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
b. Diễn tả thuật toán
NỘI DUNG

1. XÁC ĐỊNH
BÀI TOÁN
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
a. Lựa chọn thuật toán
b. Diễn tả thuật toán







Tìm ước chung lớn nhất của hai số nguyên dương M,N.
?
Nếu M=N thì giá trị chung là UCLN
Nếu M>N thì UCLN(M,N)=UCLN(M-N,N)
Nếu MChia M cho N lấy dư là R
Nếu R=0 thì UCLN(M,N)=N
Nếu khác 0 thì gán N cho M
gán R cho N Tiếp tục chia M cho N.
Trình bày ý tưởng một vài cách giải
Xác định bài toán
C1:
C2:
TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
b. Diễn tả thuật toán
? Thuật toán
B1: Nhập M, N
B2: Chia M cho N lấy dư là R
B3: Nếu R=0 thì UCLN(M,N)=N rồi kết thúc
B4: M N , N R chuyển sang B2
B1:Nhập M,N
B2: Nếu M=N thì giá trị chung là UCLN rồi kết thúc
B3:Nếu M>N thì M M-N chuyển sang B2
B4: N N-M chuyển sang B2
C1:
C2:
NỘI DUNG

1. XÁC ĐỊNH
BÀI TOÁN
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
a. Lựa chọn thuật toán
b. Diễn tả thuật toán







TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
b. Diễn tả thuật toán
Thuật toán
Nhập M,N
N N-M
M=N
Đưa KQ
KT
M>N
S
Đ
S
M M-N
Đ
Nhập M,N
Chia M cho N
lấy dư R
R=0
M N
N R
Đưa KQ
KT
?
Nên lựa chọn cách giải (thuật toán) nào để viết chương trình? Giải thích tại sao?
Đ
S
2
1
NỘI DUNG

1. XÁC ĐỊNH
BÀI TOÁN
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
a. Lựa chọn thuật toán
b. Diễn tả thuật toán







TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
3. VIẾT CHƯƠNG TRÌNH
Thuật toán+ Ngôn ngữ lập trình=chương trình
Program Tin UCLN;
Var M, N, R:integer;
Begin
Write(‘Nhap vao M,N); Read(M,N);
R:=M mod N;
While N<>0 and R<>0 do
Begin
M:=N; N:=R;
end;
Write(‘ uoc chung lon nhat la:’, N);
End.
Program Tin UCLN;
Var M, N, R:integer;
Begin
Write(‘Nhap vao M,N);
Read(M,N);
While M<>N do
IF M>N THEN
M:=M-N;
ELSE
N:=N-M;
Write(‘ uoc chung lon nhat la:’, M);
End.
NỘI DUNG

1. XÁC ĐỊNH
BÀI TOÁN
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
a. Lựa chọn thuật toán
b. Diễn tả thuật toán
3. VIẾT CHƯƠNG TRÌNH



TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
4. HIỆU CHỈNH
M=9,N=15;
NỘI DUNG

1. XÁC ĐỊNH
BÀI TOÁN
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
a. Lựa chọn thuật toán
b. Diễn tả thuật toán
3. VIẾT CHƯƠNG TRÌNH
4. HIỆU CHỈNH



3
3
6
9
15
N
UCLN(M,N)
0
6
4
3
9
3
6
15
2
9
9
1
R
M
LẦN
? Chạy thử chương trình với các bộ Input tiêu biểu để tìm ra Output:
Nhập M,N
Chia 9 cho 15
lấy dư 9
9=0
M 15
N 9
S
Chia 15 cho 9
lấy dư 6
6=0
M 9
N 6
Chia 9 cho 6
lấy dư 3
3=0
M 6
N 3
Chia 6 cho 3
lấy dư 0
0=0
Đ
KQ LÀ 3
KT
TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Nhập M,N
N N-M
M=N
Đưa KQ
KT
M>N
S
Đ
S
M M-N
Đ
Nhập M,N
Chia M cho N
lấy dư R
R=0
M N
N R
Đưa KQ
KT
Đ
S
4. HIỆU CHỈNH
? Chạy 2 thuật toán trên theo từng bước và điền vào phiếu học tập với bộ Input(M, N): M=6, N=1 để có được Output
Phiếu học tập
NỘI DUNG

1. XÁC ĐỊNH
BÀI TOÁN
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
a. Lựa chọn thuật toán
b. Diễn tả thuật toán
3. VIẾT CHƯƠNG TRÌNH
4. HIỆU CHỈNH



TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
5. VIẾT TÀI LIỆU
Tài liệu phải mô tả chi tiết toàn bộ 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 giúp cho việc sử dụng chương trình và đề xuất những khả năng hoàn thiện thêm.
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ả.
NỘI DUNG

1. XÁC ĐỊNH
BÀI TOÁN
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
a. Lựa chọn thuật toán
b. Diễn tả thuật toán
3. VIẾT CHƯƠNG TRÌNH
4. HIỆU CHỈNH
5. VIẾT TÀI LIỆU

TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
CÂU HỎI TRẮC NGHIỆM
Giải bài toán trên máy tính được tiến hành qua mấy bước?
a) 1; b) 3: c) 5; d) 7.
2. Thuật toán tốt là?
a) Sử dụng ít thời gian, ít bộ nhớ.. .
b) Sử dụng ít thời gian, nhiều bộ nhớ, ít phép toán.. .
c) Sử dụng nhiều thời gian, nhiều bộ nhớ, ít phép toán.. .
d) Sử dụng ít thời gian, ít bộ nhớ, ít phép toán.. .
3. Viết chương trình là?
a) Viết thuật toán;
b) Sử dụng ngôn ngữ lập trình để diễn đạt;
c) Sử dụng ngôn ngữ lập trình để diễn đạt đúng thuật toán;
d) Sữ dụng ngôn ngữ lập trình để trình bày dữ liệu.
NỘI DUNG

1. XÁC ĐỊNH
BÀI TOÁN
2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN
a. Lựa chọn thuật toán
b. Diễn tả thuật toán
3. VIẾT CHƯƠNG TRÌNH
4. HIỆU CHỈNH
5. VIẾT TÀI LIỆU

TIẾT 18: GIẢI BÀI TOÁN TRÊN MÁY TÍNH