Bài 5. Từ bài toán đến chương trình

GV: Huỳnh Công Kha
KIỂM TRA BÀI CŨ:
1. Nêu các bước giải bài toán trên máy tính?
TL: + Xác định bài toán (Xác định thông tin đã cho-INPUT và thông tin cần tìm – OUTPUT).
+ Mô tả thuật toán (Tìm cách giải bài toán và diễn tả các bước cần thực hiện).
+ Viết chương trình (Dựa vào mô tả thuật toán ở trên, ta viết chương trình bằng 1 NNLT cụ thể).
2. Thuật toán là gì?
TL: Thuật toán là dãy hữu hạn các thao tác cần thực hiện theo một trình tự xác định để nhận được kết quả cần tìm từ những điều kiện cho trước.
BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
1. BÀI TOÁN VÀ XÁC ĐỊNH BÀI TOÁN.
2. QT GIẢI BÀI TOÁN TRÊN MÁY TÍNH.
3. THUẬT TOÁN & MÔ TẢ THUẬT TOÁN.
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN.
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Ví dụ 2: Một hình A được ghép từ một hình chữ nhật với chiều rộng 2a,
chiều dài b và một hình bán nguyệt bán kính a như hình dưới đây:
Hãy xác định thông tin vào (Input) và thông tin ra (Output) của bài toán
Hình A
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Hãy xác định thông tin vào (Input) và thông tin ra (Output) của bài toán.
Số a là ½ chiều rộng của HCN và là bán kính của HBN, b là chiều dài HCN.
Diện tích của hình A.
INPUT:
OUTPUT:

Hình A
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
S2
S1
S
Ý tưởng:
MÔ TẢ THUẬT TOÁN
B1: Tính diện tích S1 của HCN:
S1  2ab
B2: Tính diện tích S2 của HBN:
S2   a2 /2
S  S1 + S2
B3: Tính diện tích S của hình A:
Lưu ý: Trong biểu diễn thuật toán kí hiệu  để chỉ phép gán một giá trị cho biến.
Ví dụ: S  0 : gán giá trị 0 cho biến S
Ý tưởng: S = S1 + S2

Hình A
a
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Ví dụ 3: Tính tổng của 100 số tự nhiên đầu tiên: S = 1 + 2 + … + 100.
Hãy xác định thông tin vào (Input) và thông tin ra (Output) của bài toán.
Dãy 100 số tự nhiên đầu tiên 1, 2, …, 100.
Giá trị của tổng 1 + 2 + … + 100.
INPUT:
OUTPUT:

TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Ví dụ 3: Tính tổng của 100 số tự nhiên đầu tiên: S = 1 + 2 + 3+ … + 100.
Cùng tìm cách giải
S = 1 + 2 + 3 + 4 … + 100
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Ví dụ 3: Tính tổng của 100 số tự nhiên đầu tiên: S = 1 + 2 + 3 + … + 100.
Dùng biến SUM để lưu giá trị của tổng. Đầu tiên SUM nhận giá trị bằng 0, tiếp theo lần lược thêm các giá trị 1, 2, 3, …, 100 vào SUM.
Nghĩa là:
B1: Sum  0 ;
B2: Sum  Sum + 1;
B3: Sum  Sum + 2;
B4: Sum  Sum + 3;
…
B101: Sum  Sum + 100;
Phải thực hiện nhiều thao tác.
Ý TƯỞNG:
Quá dài dòng mất nhiều thời gian.
Vậy có cách nào khác hay không?
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Ví dụ 3: Tính tổng của 100 số tự nhiên đầu tiên: S = 1 + 2 + 3 + … + 100.
THUẬT TOÁN NHƯ SAU:
B1: SUM  0; i  0.
B2: i  i + 1.
B3: Nếu i ≤ 100, thì SUM  SUM + i và quay lại bước 2.
B4: Thông báo kết quả và kết thúc thuật toán.
Mô tả thuật toán theo cách liệt kê các bước

Lưu ý: isau  itrước + 1.
SUMsau  SUMtrước + i
i  i+1= 0 + 1= 1
i  i+1 = 1 + 1= 2
SUM  SUM + i = 0 + 1= 1
SUM  SUM + i = 1 + 2= 3
SUM  0; i0
i  i + 1
i ≤ 100
SUM  SUM + i
Thông báo kquả
và kthúc TT
Đúng
Sai
Mô tả thuật toán theo cách liệt kê các bước
Mô tả thuật toán theo cách vẽ sơ đồ khối.
B1: SUM  0; i  0.
B2: i  i + 1.
B3: Nếu i ≤ 100, thì SUM  SUM + i
và quay lại bước 2.
B4: Thông báo kết quả và kết thúc
thuật toán.
MÔ TẢ THUẬT TOÁN THEO CÁCH KHÁC 
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Ví dụ áp dụng: Tính tổng của 5 số tự nhiên đầu tiên: S = 1 + 2 + 3 +4 + 5.
THUẬT TOÁN NHƯ SAU:
B1: SUM  0; i  0;
B2: i  i + 1;
B3: Nếu i ≤ 5, thì SUM  SUM + i và quay lại bước 2;
B4: Thông báo kết quả và kết thúc thuật toán.
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Ví dụ áp dụng: Tính tổng của 5 số tự nhiên đầu tiên: S = 1 + 2 + 3 + 4 + 5.
THUẬT TOÁN NHƯ SAU:
B1: SUM  0; i  0;
B2: i  i + 1;
B3: Nếu i ≤ 5, thì SUM  SUM + i và quay lại bước 2;
B4: Thông báo kết quả và kết thúc thuật toán.
Dựa vào thuật toán trên: Tính tổng 5 số tự nhiên đầu tiên?
HOẠT ĐỘNG NHÓM
HẾT GIỜ
5
10
15
20
25
30
35
40
45
50
55
60
65
70
75
80
85
90
95
100
105
110
115
120
120 giây
Khi S  0; i  0;
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Ví dụ áp dụng: Tính tổng của 5 số tự nhiên đầu tiên?
Dựa vào thuật toán trên, hãy tính tổng 5 số tự nhiên đầu tiên
Khi S  0 ; i  0
Ta có:
SUM  0; i0
i  i + 1
i ≤ 5
SUM  SUM + i
Thông báo kquả,
kết thúc TT
Đúng
Sai
B1: SUM  0; i  0.
B2: i  i + 1.
B3: Nếu i ≤ 5, thì SUM  SUM + i
và quay lại bước 2.
B4: Thông báo kết quả và kết thúc
thuật toán.
MÔ TẢ THUẬT TOÁN THEO CÁCH KHÁC 
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Với i = 5
SUM  0; i0
i  i + 1
i ≤ n
SUM  SUM + i
SUM  0; i0
i  0 + 1
1 ≤ 5
SUM  0 + 1
Đúng
Thông báo kquả,
k thúc TT
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
SUM  0; i0
i  1 + 1
2 ≤ 5
SUM  1 + 2
Đúng
Với i = 5
Thông báo k quả,
Kết thúc TT
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
SUM  0; i0
i  2 + 1
3 ≤ 5
SUM  3 + 3
Đúng
Với i = 5
Thông báo kquả,
kthúc TT
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
SUM  0; i0
i  3 + 1
4 ≤ 5
SUM  6 + 4
Đúng
Với i = 5
Thông báo kquả,
kthúc TT
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
SUM  0; i0
i  4 + 1
5 ≤ 5
SUM  10 + 5
Đúng
Với i = 5
Thông báo kquả,
kthúc TT
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
SUM  0; i0
i  5 + 1
6 ≤ 5
SUM  10 + 5
Sai
Thông báo kquả,
kthúc TT
Với i = 5
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
Cốc A
Cốc B
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
XÉT VÍ DỤ SAU:
Cốc A có nước màu đỏ, cốc B có nước màu xanh. Làm thế nào để tráo đổi cốc A có màu xanh, cốc B có nước màu đỏ? ( Cốc A,B có thể tích nước như nhau).
Cốc A
Cốc B
Cốc C
a. Lấy 1 cốc C rỗng có thể tích như cốc A,B
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Cốc A
Cốc B
Cốc C
a. Lấy 1 cốc C rỗng có thể tích như cốc A,B
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
Ví dụ 4: Đổi giá trị hai biến x và y
Hai biến x và y có giá trị tương ứng là a và b
( sau bước này giá trị của biến z sẽ bằng a).
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:

OUTPUT:
INPUT:
Hai biến x và y có giá trị tương ứng là b và a
MÔ TẢ THUẬT TOÁN
( sau bước này giá trị của biến x sẽ bằng b).
( sau bước này giá trị của biến y sẽ bằng giá Trị của biến z, giá trị của biến z chính là giá trị ban đầu a của biến x).
B1: z  x
B2: x  y
B3: y  z

Bước 1: Sum …; i 0;
Bước 2: i  i + …;
Bước 3: Nếu i  …, thì Sum  ……. + …..
Và ……………………..
Bước 4: Thông báo và kết thúc thuật toán;
Trong thuật toán tính tổng n số tự nhiên đầu tiên như sau còn thiếu một vài chỗ ở dấu…Em hãy điền vào dấu…những giá trị thích hợp để thuật toán hoàn chỉnh hơn.
0
1
n
Quay lại bước 2
Sum
i
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
BÀI TẬP
TUẦN 12 – TIẾT 21: BÀI 5 - TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t3)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN:
VÍ DỤ 2
VÍ DỤ 3
VÍ DỤ 4
HƯỚNG DẪN VỀ NHÀ
1. Ôn lại thuật toán và mô tả thuật toán.
2. Đọc kỹ ví dụ 5, 6 ở nhà để chuẩn bị cho tiết sau.
3. Làm các bài tập 2,3,4 SGK trang 45.