TRẦN HỮU TRANG
TRU?NG TRUNG H?C PH? THƠNG

TIN HỌC 10
Đặng Hữu Hoàng
Với các giá trị sau :
M = 25; N = 5.
M = 88; N = 121.
M = 997; N = 29.
M = 2006; N=1998.
Tìm ước số chung lớn nhất của hai số nguyên dương M và N .
BÀI TOÁN NÊU VẤN ĐỀ
Hãy 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ÀI 6
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Thời gian 1 tiết
CÁC BƯỚC GIẢI BÀI TOÁN
1. Xác định bài toán
2. Lựa chọn hoặc thiết kế thuật toán
3. Viết chương trình
4. Hiệu chỉnh
5. Viết tài liệu
Xác định hai thành phần : INPUT và OUTPUT

BƯỚC 1 : XÁC ĐỊNH BÀI TOÁN
Ví dụ : Tìm ước số chung lớn nhất của hai số nguyên dương M và N .
INPUT : M, N là hai số nguyên dương .
OUTPUT : ƯCLN ( M, N ) .
BƯỚC 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
a. LỰA CHỌN THUẬT TOÁN
Lựa chọn một thuật toán tối ưu nhất trong những thuật toán đưa ra
Thuật toán tối ưu : là thuật toán phải dễ hiểu, trình bày dễ nhìn,thời gian chạy nhanh, tốn ít bộ nhớ .
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.
Ví dụ :Tìm ước số chung lớn nhất của hai số nguyên dương M và N .
DIỄN TẢ THUẬT TOÁ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);
TÌM ƯỚC SỐ CHUNG LỚN NHẤT (ƯCLN) CỦA HAI SỐ NGUYÊN DƯƠNG M VÀ N
THUẬT TOÁN
B1: Nhập M, N;
B2: Nếu M = N thì 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 lại B2;
Cách 1 : Liệt kê các bước
TÌM ƯỚC SỐ CHUNG LỚN NHẤT (ƯCLN) CỦA HAI SỐ NGUYÊN DƯƠNG M VÀ N
B5: Đưa ra kết quả ƯCLN rồi kết thúc;
Đ
Đ
S
S
Nhập M ,N
M = N ?
M > N ?
N N - M
M M - N
Đưa ra M ; Kết thúc
SƠ ĐỒ THUẬT TOÁN
TÌM ƯỚC SỐ CHUNG LỚN NHẤT CỦA HAI SỐ NGUYÊN DƯƠNG M VÀ N
Đ
Đ
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
Đư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
MÔ PHỎNG THUẬT TOÁN
Đ
Đ
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
Đư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
MÔ PHỎNG THUẬT TOÁ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 :
BƯỚC 3 : VIẾT CHƯƠNG TRÌNH
Lựa chọn cách tổ chức dữ liệu .
Khi viết chương trình cần chọn ngôn ngữ thích hợp, viết chương trình trong ngôn ngữ nào thì phải tuân theo qui định ngữ pháp của ngôn ngữ đó .
TEST:
M = 8; N = 8  ƯCLN = 8
M = 25; N = 10  ƯCLN = 5
M = 88; N = 121  ƯCLN = 11
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 4 : HIỆU CHỈNH
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 đề xuất các khả năng hoàn thiện thêm .
DẶN DÒ
1. Trả lời câu hỏi 1, 2, 3 _ trang 51 _ sách giáo khoa .
2. Thực hiện phần B “ Câu hỏi và bài tập “ _ trang 23
và trang 24 _ Sách bài tập
3. Xem trước §7 “Phần mềm máy tính“ & §8 “Những ứng dụng của tin họ c”_ Sách giáo khoa
Thực hiện tháng 8 năm 2006
Bài học đã
KẾT THÚC
Thân Ái Chào Các Em