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

BÀI 5:
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
(Tiếp theo)
KIỂM TRA BÀI CŨ
1. Thuật toán là gì, nêu các bước giải một bài toán trên máy tính?
2. Hãy chỉ ra input và output của bài toán sau ?

Số bạn đạt học lực giỏi trong lớp em.

b) Số lớn nhất trong dãy n số cho trước
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
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 là b và một hình bán nguyệt bán kính a . Hãy tính diện tích của hình A?
Hình A

Em hãy xác định bài toán (Input, Output) ?
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
INPUT
OUTPUT
a là ½ chiều rộng hình chữ nhật và là bán kính của hình bán nguyệt , b là chiều dài hình chữ nhật.
Diện tích S của hình A
a)- Xác định bài toán:
Hãy nêu các bước tính diện tích
hình A ?
Hình A
b)- Mô tả thuật toán


Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
a)- Xác định bài toán:
Cách tính diện tích hình A:
Tính diện tích hình chữ nhật: S1 = 2ab
Tính diện tích hình bán nguyệt: S2 =
Tính diện tích hình A: S = S1+ S2
b)- Mô tả thuật toán
Hình A
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
a)- Xác định bài toán:
b)- Mô tả thuật toán
Hình A
Bước 1: S1 2ab {Tính diện tích hình chữ nhật }

Bước 2: S2 {Tính diện tích hình bán nguyệt}

Bước 3: S S1+ S2 và kết thúc {Tính diện tích hình A}
Lưu ý: Trong biểu diễn thuật toán kí hiệu ? để chỉ phép gán giá trị cho biến. VD S ? 0 (Gán giá trị 0 cho biến S)

Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
Ví du 3: Tính tổng của 100 số tự nhiên đầu tiên.

Em hãy xác định
bài toán
(Input, Output)?
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
Ví du 3: Tính tổng của 100 số tư nhiên đầu tiên.
a)- Xác định bài toán:
INPUT
UTPUT
Dãy 100 số tự nhiên đầu tiên: 1, 2, …, 100
Giá trị của tổng 1+2+…+100

Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
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.
a)- Xác định bài toán:
b)- Mô tả thuật toán
Hãy nêu các bước tính tổng S của 5 số tự nhiên
đầu tiên?
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
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.
a)- Xác định bài toán:
b)- Mô tả thuật toán
Bước1: S 0
Bước2: S S + 1
Bước3: S S + 2
Bước4: S S + 3

Bước 5: S S + 4
Bước 6: S S + 5
S= 1
S= 3
S= 6
S= 10
S= 0
2
1
2
3
4
5
1
3
+
+
+
+
S=
4
5
S= 15
S= 0
+
+
+
+
+
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
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.
a)- Xác định bài toán:
b)- Mô tả thuật toán
Bước1: S 0
Bước2: S S + 1
Bước3: S S + 2
...........

Bước 101: S S + 100
S= 1
S= 4950
S= 0
2
1
2
3
1
+
+
+
+
S=
100
S= 5050
S= 0
+
+
+
100
…
…………………
S= 4851
99
+
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
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.
a)- Xác định bài toán:
b)- Mô tả thuật toán
Bước1: S 0
Bước2: S S + 1
Bước3: S S + 2
...........

Bước 101: S S + 100
Nhận xét:

Thuật toán quá dài dòng.

Ở các bước chỉ có 1 phép cộng được thực hiện lặp lại theo quy luật: Ssau = Strước+ i.

+ Với i tăng lần lượt 1 đơn vị i=i+1,
từ 1 … 100.

+ Việc tính tổng chỉ thực hiện khi

I ≤ 100



Em có nhận xét gì về thuật toán ?
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
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.
a)- Xác định bài toán:
b)- Mô tả thuật toán
Buớc1 : S ← 0; i ← 0;
Buớc 2 : i ← i + 1;
Buớc 3 : Nếu i ≤ 100, thì S ← S + i và
quay lại buớc 2 ;
Buớc 4 : Thông báo kết quả và kết thúc thuật toán.

Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
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.
a)- Xác định bài toán:
b)- Mô tả thuật toán
Bước1 : S ← 0; i ← 0;
Bước 2 : i ← i + 1;
Bước 3 : Nếu i ≤ 5,
thì S ← S + i và quay lại bước 2 ;
Bước 4 : Thông báo kết quả và kết thúc thuật toán.

Mô phỏng thuật toán
Tính tổng của n số tự nhiên đầu tiên với n = 5
0
1
Đ
1
2
Đ
3
3
Đ
6
4
Đ
10
5
Đ
15
6
S
KT
0
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
Ví dụ 4: Đổi giá trị của hai biến x, y
Cốc A chứa nước màu đỏ, cốc B chứa nước màu xanh.
Làm cách nào để tráo đổi cốc A có nước màu xanh, cốc B có nước màu đỏ?
(Giả thiết cốc A và cốc B có thể tích như nhau)

Em hãy nêu cách tráo đổi nước ở cốc A và B ?
Cốc A
Cốc B
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
Ví dụ 4: Đổi giá trị của hai biến x, y
Cốc A
Cốc B
Cốc C
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
Ví dụ 4: Đổi giá trị của hai biến x, y
Cốc A
Cốc B
Cốc C
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
Ví dụ 4: Đổi giá trị của hai biến x, y
Nước của 2 ly đã được hoán đổi
Cốc A
Cốc B
Cốc C
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
Ví dụ 4: Đổi giá trị của hai biến x, y

Em hãy xác định Input, Output ?
a)- Xác định bài toán:
INPUT
OUTPUT
Hai biến x và y có giá trị tương ứng là a, b
Hai biến x và y có giá trị tương ứng là b, a

Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
Ví dụ 4: Đổi giá trị của hai biến x, y
a)- Xác định bài toán:
b)- Mô tả thuật toán:
x
Z
x
y
Z
y
Input:
Output:

Em hãy mô tả thuật toán đổi giá trị của x và y ?
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
Ví dụ 4: Đổi giá trị của hai biến x, y
a)- Xác định bài toán:
b)- Mô tả thuật toán:
Bước 1: z ? x { Giá trị của z = a}
Bước 2: x ? y { Giá trị của x = b}
Bước 3: y ? z { Giá trị của y= a}
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
BÀI TẬP
Hãy tính diện tích hình A được giới hạn bởi 2 đường tròn đồng tâm
có bán kính lớn là R1 và bán kính nhỏ R2
R1
R2
A
- Input: R1, R2
- Output: Diện tích S của hình A.
Mô tả thuật toán:
Bước 1: S1  R12
Bước 2: S2  R22
Bước 3: S  S1 - S2
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
HƯỚNG DẪN VỀ NHÀ
Học bài cũ, đọc trước phần tiếp theo của bài.
Làm bài tập 4, 5 SGK/45.
1. Hướng dẫn bài tập 4:
- Nếu giá trị của x nhỏ hơn giá trị của y (thoả mãn điều kiện) thì kết thúc.
- Ngược lại thì ta phải đổi giá trị của 2 biến.
Hướng dẫn bài tập 5:
- Cho dãy số : 1, 2, 3, 4,5, …N
Thì tổng của N số tự nhiên là: S=S+i, với i lần lượt tăng 1 đơn vị và i ≤ N.
Cho dãy số: a1, a2, … aN
Thì tổng của các phần tử của dãy số là : S=S+ ai với i lần lượt tăng 1 đơn vị và i ≤ N
Ví dụ 4: Cho hai số thực a và b. Hãy cho biết kết quả so sánh hai số đó dưới dạng "a lớn hơn b","a nhỏ hơn b" hoặc "a=b"
Bước 1: So sánh a và b. Nếu a>b, cho kết quả "a lớn hơn b"
Bước 2: Nếu aInput: Hai số thực a và b
Output: Kết quả so sánh
Ta thấy, sau bước 1 ta được kết quả
Nhưng trong bước hai, khi kiểm tra aThử lại với a=6 và b=5
? a lớn hơn b
? a = b
Bước 1: So sánh a và b. Nếu a>b, cho kết quả "a lớn hơn b" và chuyển đến bước 3
Bước 2: Nếu aBước 3: Kết thúc thuật toán
Thuật toán so sánh 2 số thực
Ví dụ 5: Tỡm số lớn nhất trong dãy A các số a1, a2,..., an.
INPUT: Số nguyên dương N và dãy N số nguyên
a1,a2,.aN. (ai với i: 1?n)
OUTPUT: Số lớn nhất (Max) của dãy số.

3
Thuật toán tìm max
Người ta đặt 5 quả bóng có kích thước khác nhau trong hộp đã được đậy nắp như hỡnh bên.Chỉ dùng tay hãy tỡm ra quả bóng có kích thước lớn nhất .
Quả này lớn nhất
Quả này mới lớn nhất
ồ! Quả này lớn hơn
Tìm ra quả lớn nhất rồi!
Cùng tìm thuật toán
Bước 1: Max ? a1 ; i ? 1
Bước 3: Nếu i > N, chuyển đến bước 5
Thuật toán tìm max
Bước 2: i ?i +1
Bước 4: Nếu ai > Max thì Max ? ai rồi quay lại bước 2
trường hợp ngược lại giữ nguyên Max và quay
lại bước 2
Bước 5: Kết thúc thuật toán
Tin học 8
Ghi nhớ!
Xác định bài toán là việc xác định các điều kiện ban đầu( thông tin vào-ra INPUT) và các kết quả cần thu được( thông tin ra ( OUTPUT)
Giải bài toán trên máy tính nghĩa là hướng dẫn cho máy tính dãy hữu hạn các thao tác đơn giản( thuật toán) mà nó có thể thực hiện được để cho ta kết quả.
Quá trình giải một bài toán trên máy tính gồm các bước: xác định bài toán; xây dựng thuật toán; lập chương trình.
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 để thu được kết quả cần thiết từ những điều kiện cho trước.