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

1
GV: NGUYỄN THỊ KIM QUY
TỔ: TOÁN - LÝ - TIN
Bài 5: TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Với mỗi cặp số hạng đứng kề nhau trong dãy, so s�nh nếu số d?ng sau nh? hơn số d?ng tru?c ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
Ý tưởng
Bài toán sắp xếp
Cho dãy s? g?m 5 ch? s? : 8, 4, 2, 10, 7
H�y sắp xếp các số hạng tr�n để trở thành m?t dãy s? theo th? t? tang d?n.
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
Bài 5:
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Input:
Output:
x = b, y = a
x = a , y = b
x
y
4. Một số ví dụ về thuật toán:
a
b
x
y
b
a
b
x
y
b
b
Kết quả sai !
b
Ví dụ 4: Đổi giá trị của hai biến x = a và y = 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:
Bước 1: x  y
Bước 2: y  x
BÀI 5
x
b
y
* INPUT:
* OUTPUT:
* THUẬT TOÁN
BÀI 5
a
?
C1
C2
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
Làm cách nào đây?
Cốc A
Cốc B
Cốc A chứa nước màu đỏ, cốc B chứa nước màu hồng.
Làm cách nào để có cốc A chứa nước màu hồng, cốc B chứa nước màu đỏ (giả thiết cốc A và cốc B có thể tích như nhau)
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
B1: Lấy 1 cốc C không có nước có thể tích như cốc A và B.
Cốc A
Cốc B
Cốc C
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
Cốc A
Cốc B
Cốc C
B2: Đổ nước màu đỏ ở cốc A sang cốc C.
Cốc A
Cốc B
Cốc C
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
Cốc A
Cốc B
Cốc C
Cốc A
Cốc B
Cốc C
B3: Đổ nước màu hồng ở cốc B sang cốc A
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
Cốc A
Cốc B
Cốc C
Cốc C
B4: Đổ nước màu đỏ ở cốc C sang cốc B
Cốc A
Cốc B
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
x
y
b
a
x
y
b
a
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
Z
x
y
b
a
b
x
y
b
a
Bước 1: z  x
Bước 2: x  y
Bước 3: y  z
a
a

* INPUT:
* OUTPUT:
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
x
b
y
* MÔ TẢ THUẬT TOÁN
a
C1
C2
Bước 1: z  x
Bước 2: x  y
Bước 3: y  z
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
Ví dụ 5: 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ằng b”.
* Xác định bài toán
Input:
Hai số thực a và b
Output:
Kết quả so sánh

BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
Ví dụ 5: * Mô tả thuật toán
Nếu a>b
thì “a lớn hơn b”.
Nếu athì “a nhỏ hơn b”
Ngược lại
thì “a bằng b”
kết thúc thuật toán
Bước 1:
Bước 2:
..................,
..................,
..................
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
* Mô tả thuật toán
Bước 1:
Nếu a>b
thì “a lớn hơn b”.

Bước 2:
Nếu athì “a nhỏ hơn b”

Ngược lại,
thì “a bằng b”

và kết thúc thuật toán
Trường hợp: a

Bước 1:

Không thực hiện lệnh

Bước 2:

Không thực hiện lệnh


Kết thúc thuật toán
Bước 1:
Nếu a>b
>
Sai
thì “a lớn hơn b”.
Bước 2:
Nếu a<
Đúng
thì “a nhỏ hơn b”.
Thông báo kết quả là “a nhỏ hơn b”
Ngược lại,
thì “a bằng b”
và kết thúc thuật toán
* Mô tả thuật toán
Bước 1:
Nếu a>b
thì “a lớn hơn b”.

Bước 2:
Nếu athì “a nhỏ hơn b”

Ngược lại,
thì “a bằng b”

và kết thúc thuật toán
Trường hợp: a=b


Bước 1:

Không thực hiện lệnh

Bước 2:

Thông báo kết quả là
“a bằng b”

Kết thúc thuật toán
Bước 1:
Nếu a>b
>
Sai
thì “a lớn hơn b”.
Bước 2:
Nếu a<
Sai
thì “a nhỏ hơn b”.
Không thực hiện lệnh
Ngược lại,
thì “a bằng b”
và kết thúc thuật toán
* Mô tả thuật toán
Bước 1:
Nếu a>b
thì “a lớn hơn b”.

Bước 2:
Nếu athì “a nhỏ hơn b”

Ngược lại,
thì “a bằng b”

và kết thúc thuật toán
Trường hợp: a>b


Bước 1:
Thông báo kết quả là:
“a lớn hơn b”

Bước 2:

Thông báo kết quả là:
“a bằng b”

Kết thúc thuật toán
Bước 1:
Nếu a>b
>
ĐÚNG
thì “a lớn hơn b”.
Bước 2:
Nếu a<
SAI
thì “a nhỏ hơn b”.
Không thực hiện
Ngược lại,
thì “a bằng b”
và kết thúc thuật toán
Ví dụ 5: Thuật toán so sánh hai số
Bước 1:
Nếu a>b, thì “a lớn hơn b” và Chuyển đến bước 3
Bước 2:
Nếu aNgược lại, thì “a bằng b”
Bước 3: Kết thúc thuật toán
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t2)
c.Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
Ví dụ 6: Tìm số lớn nhất trong dãy A các số a1, a2, a3,…, an cho trước.
Hãy xác định bài toán (xác định input và Output)
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH (t2)
Ví dụ 4: Đổi giá trị của hai biến x = a và y = b
4. Một số ví dụ về thuật toán:
Input: Dãy A các số a1, a2, a3,…, an
Output: Max(a1, a2, a3,…, an )=?
6
8
10
13
Ví dụ 6: Tìm số lớn nhất trong dãy A các số a1, a2, . . ., an
a1
a2
a3
a4
Bài 5:
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Max =
i = 1
<
Với n = 5
7
a5
i = 2
6
Cho A= { 6; 8; 10; 13; 7}
4. Một số ví dụ về thuật toán:
Thuật toán:
Bước 1: MAX  a1; i  1
Bước 2: i  i + 1
8
6
8
10
13
Ví dụ 6: Tìm số lớn nhất trong dãy A các số a1, a2, . . ., an
a1
a2
a3
a4
Bài 5:
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Max =
i = 1
<
7
a5
i = 2
8
i = 3
10
4. Một số ví dụ về thuật toán:
Thuật toán:
Bước 1: MAX  a1; i  1
Bước 2: i  i + 1
Bước 4: Nếu ai > MAX thì MAX  ai quay lại bước 2
Bước 3: Nếu i > 5 thì chuyển đến bước 5
Bước 5: Kết thúc thuật toán
6
8
10
13
Ví dụ 6: Tìm số lớn nhất trong dãy A các số a1, a2, . . ., an
a1
a2
a3
a4
Bài 5:
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Max =
i = 1
<
7
a5
i = 2
10
i = 3
10
i = 4
13
4. Một số ví dụ về thuật toán:
Thuật toán:
Bước 1: MAX  a1; i  1
Bước 2: i  i + 1
Bước 4: Nếu ai > MAX thì MAX  ai quay lại bước 2
Bước 3: Nếu i > 5 thì chuyển đến bước 5
Bước 5: Kết thúc thuật toán
6
8
10
13
Ví dụ 6: Tìm số lớn nhất trong dãy A các số a1, a2, . . ., an
a1
a2
a3
a4
Bài 5:
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Max =
i = 1
>
7
a5
i = 2
13
i = 3
10
i = 4
13
i = 5
i = 6
Kết thúc
4. Một số ví dụ về thuật toán:
Thuật toán:
Bước 1: MAX  a1; i  1
Bước 2: i  i + 1
Bước 4: Nếu ai > MAX thì MAX  ai quay lại bước 2
Bước 3: Nếu i > 5 thì chuyển đến bước 5
Bước 5: Kết thúc thuật toán
Ví dụ 6: Tìm số lớn nhất trong dãy A các số a1, a2, . . ., an
Bài 5:
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán:
Thuật toán:
Bước 1: MAX  a1; i  1
Bước 2: i  i + 1
Bước 4: Nếu ai > MAX thì MAX  ai quay lại bước 2
Bước 3: Nếu i > thì chuyển đến bước 5
Bước 5: Kết thúc thuật toán
Thay 5 bởi n thì thụât tóan
được viết thế nào?
5
n
Sơ đồ tư duy
Bài toán
xác định
bài toán
xác định
bài toán
mô tả thuật toán
Viết chương trình
vd6
vd5
vd4
vd3
vd2
Thuật toán: là dãy hữu hạn các thao tác cần thực hiện
Mô tả thuật toán:Liệt kê các bước để thực hiện một công việc
B1
B2: i  i + 1
B1: MAX  a1; i  1
B3: Nếu i > n thì chuyển đến bước 5
B4:Nếu ai > MAX thì MAX  ai quay lại bước 2
B5: Kết thúc thuật toán

B3
B2
B1
B3
B2
B1
B3
B2
B1
B3
B2
Bước 1: z  x
Bước 2: x  y
Bước 3: y  z
Thuật toán:
Bước 1: MAX  a1; i  1
Bước 2: i  i + 1
Bước 4: Nếu ai > MAX thì MAX  ai quay lại bước 2
Bước 3: Nếu i > n thì chuyển đến bước 5
Bước 5: Kết thúc thuật toán
Qua thuật toán hoán đổi giá trị x,y và thuật toán tìm giá trị lớn nhất em hãy nhận xét thứ tự thực hiện của các câu lệnh trong hai thuật toán?
N =
10
1
8
7
4
2
Cho dãy s? g?m 5 ch? s? : 8, 4, 2, 10, 7
H�y sắp xếp các số hạng tr�n để trở thành m?t dãy s? theo th? t? tang d?n.
Bài tập củng cố: Bài toán sắp xếp