1
Tiết 10
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN
Chương I Một số khái niệm cơ bản
của tin học
2
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.
1. Khái niệm bài toán
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?
3
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.
4
TOÁN HỌC?
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 đó.
5
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ố.
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.
CÁC VÍ DỤ (tt)

?
?
?
?
Bảng điểm của học sinh.
Bảng xếp loại học tập.
7
Nêu một bài toán và chỉ rõ Input, Output của bài toán đó?
Xem thêm các ví dụ trong SGK/32
8
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)
9
2. Thuật toán
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
10
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ì ?
11
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Ê

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 ()
12
: Thể hiện các thao tác so sánh
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ư :
: 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
13
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Ê
14
c. Tính chất thuật toán
Tính dừng
Tính xác
định
TÍnh đúng
đắn
Tính chất
15
Tiết 11, 12
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN
Chương I Một số khái niệm cơ bản
của tin học
16
NỘI DUNG BÀI HỌC
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
17
KIỂM TRA TÍNH NGUYÊN TỐ CỦA 1 SỐ NGUYÊN DƯƠNG N.
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
18
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)
19
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ố”.

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

nguyên dương N
có đúng 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ố.
21
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ố.”
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ố ”
XÁC ĐỊNH BÀI TOÁN
22
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.


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
23
Ý TƯỞNG
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.
24
Ý 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ố.
25
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
26
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Ố
27
NỘI DUNG BÀI HỌC
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)
28
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.
29
Sắp xếp bằng tráo đổi
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
30
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:
31
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
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
32

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
33
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.
34
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
35
Nội dung bài học
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.
36
Kiểm tra bài cũ
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?
37
Tiết 13
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)
Chương I Một số khái niệm cơ bản của tin học
38
5
6
8
2
4
7
>
<
>
>
>
>
<
<
<
THÀNH CÔNG!
Sắp xếp bằng tráo đổi
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
39
Ví dụ:
TÌM 1 QUYỂN SÁCH TRONG 50 QUYỂN???
40
Ví dụ:
CÒN 10.000 QUYỂN THÌ SAO
41
Một số công việc tìm kiếm
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 đó;
…
42
Bài toán tìm kiếm
TÌM KIẾM
NHỊ PHÂN
TÌM KIẾM
TUẦN TỰ
CÓ 2
THUẬT TOÁN
43
Nội dung bài học
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.
44
Mô tả bài toán:
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
45
Xác định bài toán:
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.
46
Ý 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.

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ự
47
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
Thuật toán tìm kiếm tuần tự
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
48
Minh họa thuật toán với N = 5, k= 6
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
49
Nhập N và a1, a2, a3,..., aN; k
Thử tài nhanh nhẹn
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
50
Tiết 14
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)
Chương I Một số khái niệm cơ bản của tin học
51
Nội dung bài học
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
52
ƯCLN???
A được gọi là ước của B nếu B chia hết cho A;
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.
53
Xác định bài toán:
Hai số nguyên dương A và B;
Ước chung lớn nhất của A và B.
54
B1: Nhập A, B
Thuật toán tìm ước chung lớn nhất
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
55
Minh họa thuật toán với A =54, B=90
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
56
A > B?
Thử tài nhanh nhẹn
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
57
Minh họa thuật toán với A=20, B=30
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
58
Tiết 15
BÀI TẬP
Chương I Một số khái niệm cơ bản của tin học
59
Thuật toán tìm kiếm nhị phân (Binary Search)

60
Xác định bài toán:
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
61
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;
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;
Thuật toán tìm kiếm nhị phân
Ý TƯỞNG
LIỆT KÊ
62
Thuật toán tìm kiếm nhị phân
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
63
Minh họa thuật toán
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
64
Cuoi  Giua - 1
Thử tài nhanh nhẹn
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
65