bài 4 bài toán và thuật toán tiết 1

1
Tiết 10
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN
1. Khái niệm bài toán
VD:Xét các yêu cầu sau :
Giải phương trình bậc hai ax2+bx+c=0
Viết một dòng chữ ra màn hình máy tính.
Quản lý các cán bộ trong một cơ quan.
Tìm ước chung lớn nhất của hai số nguyên dương a và b.
Xếp loại học tập các học sinh trong lớp.
2
Trong TIN HỌC
Trong TOÁN HỌC
Yêu cầu 1 và 4 được xem là bài toán
Tất cả các yêu cầu trên đều được xem là bài toán
Trong các yêu cầu trên, yêu cầu nào được xem như là một bài toán?
Khái niệm bài toán trong
Tin học?
Trong phạm vi tin học, Bài toán là việc nào đó ta muốn máy tính thực hiện.
3
Các yếu tố cần quan tâm khi giải một bài toán
 Trong Tin học, để phát biểu một bài toán, ta cần trình bày rõ Input và Output của bài toán đó.
4
TOÁN HỌC?
CÁC VÍ DỤ
VD1 : Giải phương trình bậc hai
ax2 + bx + c = 0 (a ≠ 0).
Input : Các số thực a,b,c (a ≠ 0)
Output : Số thực x thỏa : ax2+bx+ c = 0

VD2 : Tìm giá trị nhỏ nhất của các số trong một dãy số.
Input : Các số trong dãy số.
Output : Giá trị nhỏ nhất trong dãy số.
5
CÁC VÍ DỤ (tt)

6
VD3 : Tìm ước chung lớn nhất của hai số nguyên dương a và b.
Input :
Output :

VD4 : Xếp loại học tập các học sinh trong lớp.
Input :
Output :
ƯCLN của a và b.
Hai số nguyên dương a và b.
?
?
?
?
Bảng điểm của học sinh.
Bảng xếp loại học tập.
Nêu một bài toán và chỉ rõ Input, Output của bài toán đó?
7
Xem thêm các ví dụ trong SGK/32
TÓM LẠI
Một bài toán được cấu tạo bởi 2 thành phần cơ bản :

Input (Các thông tin đã có)
Output (Các thông tin cần tìm từ Input)
8
2. Thuật toán
9
Hướng dẫn các thao tác cho máy thực hiện để tìm ra lời giải
Bài toán
Input
Output
Bằng cách nào?
Giải bài toán
Thuật toán
Em hãy nêu các bước để nấu cơm
10
11
Input
Output
THUẬT TOÁN
(Thao tác 1Thao tác 2...Thao tác n)
Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ Input của bài toán này, ta nhận được Output cần tìm.
BÀI TOÁN
Thuật toán để giải một bài toán là :
Một dãy hữu hạn các thao tác.
Các thao tác được sắp xếp theo một trình tự xác định.
Sau khi thực hiện dãy thao tác đó, từ Input ta tìm được Output của bài toán.
a. Thuật toán là gì ?
Thuật toán có 2 cách để biểu diễn:
+ Liệt kê
+ Sơ đồ khối
12
LIỆT KÊ
13

Giải toán thông thường:
Nếu a = 0 thì () không phải là pt bậc nhất.
+ Neáu b = 0 thì () voâ số nghieäm.
+ Neáu b ≠ 0 thì () voâ nghieäm.
Nếu a ≠ 0 thì () có nghiệm x = -b/a.
LIỆT KÊ :
Bước 1 : Nhập a, b.
Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3.
Bước 3 : Gán cho x giá trị -b/a, rồi qua bước 4.
Bước 4 : Đưa ra kết quả x và kết thúc.
Tìm nghiệm phương trình bậc nhất tổng quát ax + b = 0 ()
DÙNG SƠ ĐỒ KHỐI
Trong sơ đồ khối, người ta dùng một số biểu tượng thể hiện các thao tác như :
14
: Thể hiện các thao tác so sánh
: Thể hiện các phép toán
: Quy định trình tự thực hiện các thao tác
: Thể hiện các thao tác nhập, xuất dữ liệu
15
VD: Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0
Nhập a, b
a = 0
x = -b/a
Sai
Đưa ra x và kết thúc

Bước 1 : Nhập a, b.
Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3.
Bước 3 : Gán cho x giá trị -b/a, rồi qua bước 4.
Bước 4 : Đưa ra kết quả x và kết thúc.
SƠ ĐỒ KHỐI
LIỆT KÊ
c. Tính chất thuật toán
16
Tính dừng
Tính xác
định
TÍnh đúng
đắn
Tính chất
Chương I Một số khái niệm cơ bản
của tin học
17
Tiết 11, 12
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN
NỘI DUNG BÀI HỌC
18
1.Khái niệm bài toán
2.Khái niệm thuật toán
a. VD 1 : Kiểm tra tính nguyên tố của một số nguyên dương
3.Một số ví dụ về thuật toán
KIỂM TRA TÍNH NGUYÊN TỐ CỦA 1 SỐ NGUYÊN DƯƠNG N.
19
Biểu diễn thuật toán
theo 2 cách :
Liệt kê
Sơ đồ khối
Ý tưởng
Xác định
bài toán
Bước 1
Bước 2
Bước 3
20
XÁC ĐỊNH BÀI TOÁN
Nhắc lại :
*INPUT và OUTPUT là gì?

+ Input: là các thông tin đã có (giả thiết)
+ Output: là các thông tin cần tìm dựa vào các thông tin có từ Input (kết luận)
21
XÁC ĐỊNH BÀI TOÁN
BÀI TOÁN :
Kiểm tra tính nguyên tố của một số nguyên dương N.
+Input:
?
Nhập số nguyên dương N.

+Output:
?
“N là một số nguyên tố” hoặc “ N không phải là một số nguyên tố”.

XÁC ĐỊNH BÀI TOÁN
Nhắc về số nguyên tố:
22
Một số là số nguyên tố nếu nhau

nguyên dương N
có đúngnó khác hai ước số
là 1 và chính nó
Ví dụ : Trong hai số này số nào là số nguyên tố : 7, 9.
7 có 2 ước là 1, 7 7 là số nguyên tố.
9 có 3 ước là 1, 3, 9 9 không phải là số nguyên tố.
XÁC ĐỊNH BÀI TOÁN
Quay lại bài toán :
Input : Nhập số nguyên dương N.
Output : “N là số nguyên tố” hoặc “N không là số nguyên tố.”
23
Nội dung bài toán :
Nhập số nguyên dương N.
Xuất ra câu thông báo “N là số nguyên tố ” hoặc “N không là số nguyên tố ”
Ví dụ : Nhập N= 5. Xuất ra “5 là số nguyên tố ”
Ý TƯỞNG
Nhận xét :
Số 1 có phải là số nguyên tố không ?
Số 1 chỉ có 1 ước là chính nó.

Các số 2, 3 có phải là số nguyên tố không ?
Số 2 chỉ có 2 ước là : 1 và 2.
Số 3 chỉ có 2 ước là : 1 và 3.


24
1 không phải là số nguyên tố.
2, 3 là các số nguyên tố.
Nghĩa là các số nguyên N trong khoảng 1< N < 4 là các số nguyên tố.

Ý TƯỞNG
25
Vậy còn với các số nguyên N ≥ 4 thì sao ?
Thông thường:
Người ta xét xem N có ước từ 2 đến [ ] hay không ? (xét lần lượt từ trái sang phải ).
Nếu có thì N không là số nguyên tố và ngược lại.
Ý TƯỞNG
TÓM LẠI Ý TƯỞNG CỦA BÀI TOÁN
Nhập số nguyên dương N nếu :
N = 1 thì N không là số nguyên tố.
N thuộc khoảng 1< N <4 thì N là số nguyên tố.
N ≥ 4 và N không có ước trong đoạn từ 2 đến phần nguyên căn bậc hai của N ( ký hiệu là
[ ] ) thì N là số nguyên tố.
26
27
Thuật toán:
a) Cách liệt kê:

Bước 1: Nhập số nguyên dương N.
Bước 2: Nếu N =1 thì thông báo N không nguyên tố rồi kết thúc
Bước 3: Nếu N <4 thì thông báo N là nguyên tồ rồi kết thúc.
Bước 4: i=2.
Bước 5: Nếu i> [ VN ] thì thông báo N là nguyên tố rồi kết thúc.
Bước 6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc.
Bước 7: i i+1 rồi quay lại bước 5.
b) Sơ đồ khối
N = 1 ?
Nhập N
N < 4 ?
i >[ ] ?
N chia hết
cho i ?

Thông báo N là số
nguyên tố
rồi kết thúc
Thông báo N không
là số nguyên tố
rồi kết thúc


i 2
i i+1
Đúng
Sai
Đúng
Sai
Đúng
Sai
Đúng
Sai
28
i 2
Thông báo N là số nguyên tố rồi kết thúc
N < 4?
N chia hết cho i ?
Thông báo N không là số nguyên tố rồi kết thúc
i >[ VN ] ?
i i +1
Nhập N
N = 1 ?
a
b
c
d
e
f
g
h
i
1
2
3
4
5
6
7
8
9
CỦNG CỐ
NỘI DUNG BÀI HỌC
29
1.Khái niệm bài toán.
2.Khái niệm thuật toán.
3.Một số ví dụ về thuật toán.
b. Ví dụ 2 : Bài toán sắp xếp: Sắp xếp bằng tráo đổi (Exchange Sort)
Mô tả bài toán
Cho dãy A gồm N số nguyên a1,a2,…,aN . Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm.
Ví dụ: Dãy A gồm các phần tử 5, 6, 8, 2, 4, 7 ta sẽ sắp lại thành 2, 4, 5, 6, 7, 8.
30
Sắp xếp bằng tráo đổi
31
Biểu diễn thuật toán
theo 2 cách :
Liệt kê
Sơ đồ khối
Ý tưởng
Xác định
bài toán
Bước 1
Bước 2
Bước 3
32
Thuật toán sắp xếp bằng tráo
đổi (Exchange Sort):
Xác định bài toán:
Input:
Dãy A gồm N số nguyên
a1, a2, a3,…,aN ( N>0)
Dãy A được sắp xếp lại thành dãy tăng.
Output:
Vd: Dãy A gồm 5,6,8,2,4,7 ta sắp lại thành 2,4,5,6,7,8
33
5
6
8
2
4
7
>
<
>
>
>
>
<
<
<
THÀNH CÔNG!
Ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại cho đến khi không có đổi chỗ nào xảy ra nữa
34

NHẬN XÉT
Sau mỗi lần đổi chỗ, giá trị lớn nhất sẽ chuyển dần về cuối
Sau mỗi lượt có ít nhất một số hạng xếp đúng và không tham gia vào quá trình đổi chỗ nữa
35
Bước 1: Nhập N, các số hạng a1, a2, a3,…,aN ( N>0)
Bước 2: M  N;
Bước 3: Nếu M < 2 thì đưa ra dãy A đã
được sắp xếp rồi kết thúc;
Bước 4: M  M – 1, i  0;
Bước 5: i  i + 1;
Bước 6: Nếu i > M thì quay lại bước 3;
Bước 7: Nếu ai> ai+1 thì đổi chỗ ai
và ai+1;
Bước 8: quay lại bước 5.
36
Nhập N và a1, a2,…aN
MN
M<2?
Đưa ra A rồi kết thúc
MM-1;i 0
ii+1
i>M?
ai>ai+1?
Tráo đổi ai và ai+1
SƠ ĐỒ KHỐI
M giảm dần sau mỗi lượt. Sau mỗi lượt có 1 phần tử không tham gia so sánh
Ngừng khi chỉ còn 1 phần tử tham gia vào quá trình
M là số phần tử tham gia so sánh trong lượt
Đ
Đ
S
Đ
S
S
Nội dung bài học
37
Khái niệm bài toán
Khái niệm thuật toán
Một số ví dụ về thuật toán
Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương
Ví dụ 2: Bài toán sắp xếp
1.
2.
3.
Kiểm tra bài cũ
38
N = 27
N = 1 ?
Nhập N
N < 4 ?
i >[ ] ?
N chia hết
cho i ?

Thông báo N là số
nguyên tố
rồi kết thúc
Thông báo N không
là số nguyên tố
rồi kết thúc


i 2
i i+1
Đúng
Sai
Đúng
Sai
Đúng
Sai
Đúng
Sai
Phân tích tính dừng của thuật toán?
Chương I Một số khái niệm cơ bản của tin học
39
Tiết 13
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)
Sắp xếp bằng tráo đổi
40
5
6
8
2
4
7
>
<
>
>
>
>
<
<
<
THÀNH CÔNG!
Hãy tìm vị trí của phần tử có giá trị là 7
1
2
3
4
5
6
Tìm thấy phần tử có giá trị là 7 ở vị trí thứ 5
Ví dụ:
TÌM 1 QUYỂN SÁCH TRONG 50 QUYỂN???
41
Ví dụ:
42
CÒN 10.000 QUYỂN THÌ SAO
Một số công việc tìm kiếm
43
Tìm một quyển sách trên kệ sách;
Tìm 1 từ trong cuốn từ điển;
Tìm 1 học sinh trong danh sách lớp nào đó;
…
Bài toán tìm kiếm
44
TÌM KIẾM
NHỊ PHÂN
TÌM KIẾM
TUẦN TỰ
CÓ 2
THUẬT TOÁN
Nội dung bài học
45
Khái niệm bài toán
Khái niệm thuật toán
Một số ví dụ về thuật toán
Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương
Ví dụ 3: Bài toán tìm kiếm - Thuật toán tìm kiếm tuần tự (Sequential Search)
Ví dụ 2: Bài toán sắp xếp
1.
2.
3.
Mô tả bài toán:
46
9
- 4
1
8
- 3
2
6
Với i = 5 thì a5 = 9
9
5
6
3
7
1
2
4
A
i
k
Cho dãy A gồm N số nguyên khác nhau: a1,a2,...,aN và số nguyên k.
Tìm i để ai =k ? với i=1...N
Ví dụ: Với N = 7
Xác định bài toán:
47
Dãy A gồm N số nguyên khác nhau: a1,a2,...,aN và số nguyên k;
Chỉ số i sao cho ai =k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.
Thuật toán tìm kiếm tuần tự
Ý TƯỞNG
Tìm kiếm tuần tự được thực hiện lần lượt từ số hạng thứ 1 đến số hạng thứ i;
So sánh giá trị số hạng đang xét với khóa k;
Nếu ai =k hoặc i >N thì kết thúc thuật toán.

48
LIỆT KÊ
B1: Nhập N, các số hạng a1, a2, a3,…, aN và khóa k;
B2: i ← 1;
B3: Nếu ai = k thì thông báo chỉ số i rồi kết thúc;
B4: i ← i+1
B5: Nếu i >N, dãy A không có số hạng nào có giá trị bằng k, kết thúc
B6: Quay lại bước 3.
Thuật toán tìm kiếm tuần tự
49
LIỆT KÊ

B1: Nhập N, số hạng a1,..,aN và khóa k.
B2: i ← 1
B3: Nếu ai =k, thông báo chỉ số i rồi kết thúc.
B4: i ← i+1
B5: Nếu i >N, dãy A không có số hạng nào có giá trị bằng k, kết thúc.
B6: Quay lại bước 3
SƠ ĐỒ KHỐI
Sai
Đúng
Sai
Nhập N và a1, a2,…,aN; k
i  1
ai = k
Đưa ra i và kết thúc
i i + 1
i > N
Thông báo dãy A không có số
hạng có giá trị bằng k rồi kết thúc
Đúng
Minh họa thuật toán với N = 5, k= 6
50
SƠ ĐỒ KHỐI
Sai
Đúng
Sai
Nhập N và a1, a2,…,aN; k
i  1
ai = k
Đưa ra i và kết thúc
i i + 1
i > N
Thông báo dãy A không có số
hạng có giá trị bằng k rồi kết thúc
Đúng
a5
a3
a1
a2
a4
N = 5
i = 1
i = 2
i = 3
i = 4
k = 6
9
- 3
2
1
6
Thử tài nhanh nhẹn
51
Nhập N và a1, a2, a3,..., aN; k
SƠ ĐỒ KHỐI
Sai
Đúng
Sai
Đúng
ai = k
i  1
i  i + 1
i > N
Đưa ra i rồi kết thúc
Thông báo dãy A không có số hạng có giá trị bằng k rồi kết thúc
1
2
3
4
5
6
7
a
b
c
d
e
f
g
Chương I Một số khái niệm cơ bản của tin học
52
Tiết 14
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)
Nội dung bài học
53
Một số ví dụ về thuật toán
Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương
Ví dụ 3: Thuật toán tìm kiếm tuần tự (Sequential Search)
Ví dụ 2: Thuật toán sắp xếp bằng tráo đổi
3.
Ví dụ 4: Bài toán tìm ƯCLN của 2 số nguyên dương
ƯCLN???
A được gọi là ước của B nếu B chia hết cho A;
54
1, 2, 3, 6, 12 là ước của 12

Ví dụ: 12 chia hết cho 1, 2, 3, 6, 12
1, 2, 3, 6, 9, 18 là ước của 18
Ví dụ: 18 chia hết cho 1, 2, 3, 6, 9, 18
Vậy, ước chung lớn nhất của 12 và 18 là
6.
Xác định bài toán:
55
Hai số nguyên dương A và B;
Ước chung lớn nhất của A và B.
Thuật toán tìm ước chung lớn nhất
56
B1: Nhập A, B
Sơ đồ khối
Sai
Đúng
Nhập A và B
A=B?
Đưa ra A và kết thúc
Liệt kê
B2: Nếu A=B thì lấy giá trị chung này làm ƯCLN rồi chuyển đến bước 5;
B3: Nếu A>B thì A A - B, ngược lại B  B - A
B4: Quay lại bước 2;
B5: Đưa ra kết quả ƯCLN rồi kết thúc.
Sai
Đúng
A>B?
A=A-B
B=B-A
Minh họa thuật toán với A =54, B=90
57
A
Sai
Đúng
Nhập A và B
A=B?
Đưa ra A; kết thúc
Sai
Đúng
A>B?
A = A - B
B = B - A
B
54
90
36
18
18
Vậy ƯCLN là 18
Thử tài nhanh nhẹn
58
A > B?
A = A - B
A = B?
B = B - A
Đưa ra A rồi kết thúc
Nhập A và B
Sai
Đúng
Sai
Đúng
a
b
c
d
e
f
1
2
3
4
5
6
Minh họa thuật toán với A=20, B=30
59
Sai
Đúng
Nhập A và B
A=B?
Đưa ra A; kết thúc
Sai
Đúng
A>B?
A = A - B
B = B - A
Chương I Một số khái niệm cơ bản của tin học
60
Tiết 15
BÀI TẬP
Thuật toán tìm kiếm nhị phân (Binary Search)

61
Xác định bài toán:
62
Dãy A gồm N số nguyên a1,a2,...,aN khác nhau và số nguyên k;
Chỉ số i sao cho ai =k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.
là dãy tăng
Thuật toán tìm kiếm nhị phân
A là dãy tăng;
Thu hẹp phạm vi để so sánh khóa với số hạng được chọn;
Chọn aGiua để so sánh k, với Giua= (N+1)/2;
Nếu aGiua=k thì i=giua, kết thúc;
Nếu aGiua> k thì xét dãy mới a1,..aGiua-1;
Nếu aGiua< k thì xét dãy mới aGiua+1,…, aN;
63
B1: Nhập N, các số hạng a1,.., aN và khoá k;
B2: Dau ← 1, Cuoi ← N;
B3: Giua ← [ (Dau + Cuoi)/2];
B4 : Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết thúc;
B5: Nếu aGiua> k thì đặt Cuoi =Giua +1, rồi chuyển đến B 7;
B6: Dau ← Giua +1;
B7: Nếu Dau > Cuoi thì thông báo dãy A không có số cần tìm, rồi kết thúc;
B8: Quay lại B 3;
Ý TƯỞNG
LIỆT KÊ
Thuật toán tìm kiếm nhị phân
64
SƠ ĐỒ KHỐI
Sai
Đúng
Nhập N và a1, a2,…,aN; k
Dau 1; Cuoi N
aGiua = k?
Đưa ra Giua và kết thúc
B1: Nhập N, các số hạng a1,.., aN và khoá k;
B2: Dau ← 1, Cuoi ← N;
B3: Giua ← [ (Dau + Cuoi)/2];
B4 : Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết thúc;
B5: Nếu aGiua> k thì đặt Cuoi =Giua -1, rồi chuyển đến B 7;
B6: Dau ← Giua +1;
B7: Nếu Dau > Cuoi thì thông báo dãy A không có số cần tìm, rồi kết thúc;
B8: Quay lại B 3;
LiỆT KÊ
Giua [(Dau+Cuoi)/2]
Đúng
aGiua > k?
Cuoi  Giua - 1
Dau Giua+1
Sai
Dau > Cuoi?
Đúng
Thông báo dãy A không có số hạng có giá trị bằng k rồi kết thúc
Minh họa thuật toán
65
Sai
Đúng
Nhập N và a1, a2,…,aN; k
Dau 1; Cuoi N
aGiua = k?
Đưa ra Giua và kết thúc
Giua [(Dau+Cuoi)/2]
Đúng
aGiua > k?
Cuoi  Giua - 1
Dau Giua+1
Sai
Dau > Cuoi?
Đúng
Thông báo dãy A không có số hạng có giá trị bằng k rồi kết thúc
N = 8
A = {-2, 0, 1, 4, 7, 8, 11, 15}
k = 7
Dau = , Cuoi =
Giua =
a4
a4
1
8
5
Sai
4
6
a6
a6
5
5
a5
Vậy i = 5
Thử tài nhanh nhẹn
66
Cuoi  Giua - 1
Dau 1; Cuoi N
Dau > Cuoi?
aGiua = k?
Giua [(Dau+Cuoi)/2]
Đưa ra Giua và kết thúc
Dau Giua+1
Sai
Đúng
Đúng
Sai
Đúng
Thông báo dãy A không có số hạng có giá trị bằng k rồi kết thúc
a
b
c
d
e
f
g
h
aGiua > k?
Nhập N và a1, a2, a3,..., aN; k
1
2
3
4
5
6
7
8
67