Bài toán
Tìm ước chung lớn nhất của 2 số nguyên dương M và N?
Với các giá trị:
M = 25 N = 5
M = 88 N = 121
M = 997 N = 29
M= 2006 N = 1998
1. XÁC ĐỊNH…
Mục đích của bước đi xác định bài toán?
1. XÁC ĐỊNH BÀI TOÁN
Việc xác định bài toán có quan trọng không? Vì sao?
Ví dụ: Tìm UCLN của 2 số nguyên dương M, N
Input: Cho M, N nguyên dương
Output: UCLN 2 số nguyên M, N
1. XÁC ĐỊNH…
1 bài toán có nhiều thuật toán, nhưng 1 thuật toán chỉ giải được 1 bài toán
Thuật toán tối ưu
VD: Tìm giá trị lớn nhất (GTLN) của 2 số nguyên a,b
1. XÁC ĐỊNH…
2. LỰA CHỌN
2. LỰA CHỌN VÀ THIẾT KẾ THUẬT TOÁN
a. Lựa chọn thuật toán
Để lựa chọn thuật toán tối ưu cần dựa vào những tiêu chí nào?
1. XÁC ĐỊNH…
2. LỰA CHỌN
2. LỰA CHỌN VÀ THIẾT KẾ THUẬT TOÁN
b) Diễn tả thuật toán
Cách 1: Phương pháp liệt kê
Cách 2: Phương pháp sơ đồ khối
VD: Tìm ước chung lớn nhất (UCLN) của 2 số nguyên dương M, N.
1. XÁC ĐỊNH…
2. LỰA CHỌN
B1: Nhập M, N;
B2: Nếu M = N thì lấy giá trị chung này làm UCLN rồi chuyển đến B5;
B3: Nếu M>N thì M M – N rồi quay lại B2;
B4: Nếu M < N thì N N – M rồi quay lại B2;
B5: Đưa ra kết quả UCLN rồi kết thúc.
C1: Dạng liệt kê
Đ
Đ
S
S
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
Đưua ra UC; 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 ?
UCLN (25,10) = 5
M
N
C2: Sơ đồ khối
1. XÁC ĐỊNH…
2. LỰA CHỌN
2. LỰA CHỌN VÀ THIẾT KẾ THUẬT TOÁN
Bài tập: Mô phỏng thuật toán tìm UCLN của các cặp số nguyên M, N?
M=15; N= 2
M= 20; N= 4
M= 30; N= 10
M=18; N= 3
3. VIẾT CHƯƠNG TRÌNH
1. XÁC ĐỊNH…
2. LỰA CHỌN
3. VIẾT C TR
Viết chương trình trong ngôn ngữ lập trình nào ta cần phải tuân theo đúng quy định ngữ pháp của ngôn ngữ lập trình đó
1. XÁC ĐỊNH…
2. LỰA CHỌN
3. VIẾT C TR
1. XÁC ĐỊNH…
2. LỰA CHỌN
3. VIẾT C TR
4. HIỆU CHỈNH
4. HIỆU CHỈNH
Thử chương trình bằng cách thực hiện nó với 1 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
TEST:
M = 15; N = 2 ? UCLN = ?
M = 20; N = 4 ? ưUCLN = ?
M = 30; N = 10 ? UưCLN = ?
M = 18; N = 3 ? ưUCLN = ?
1. XÁC ĐỊNH…
2. LỰA CHỌN
3. VIẾT C TR
4. HIỆU CHỈNH
5. VIẾT TL
5. VIẾT TÀI LIỆU
Mô tả chi tiết toàn bộ quá trình giải bài toán và hướng dẫn sử dụng chương trình cài đặt.
Đề xuất thêm các phương án tối ưu hơn cho bài toán.
1. XÁC ĐỊNH…
2. LỰA CHỌN
3. VIẾT C TR
4. HIỆU CHỈNH
5. VIẾT TL
Củng cố bài
Bài học đến đây là kết thúc cảm ơn quý thầy cô và các em.
1. XÁC ĐỊNH…
2. LỰA CHỌN
3. VIẾT C TR
4. HIỆU CHỈNH
5. VIẾT TL
Củng cố bài
KẾT THÚC
nguon VI OLET
