BÀI TOÁN - THUẬT TOÁN
Chương I - Bài 4 :
(Môn Tin học lớp 10)
Chỉ mục
Khái niệm bài toán
Khái niệm thuật toán
Khái niệm
Tính chất thuật toán
Thể hiện một thuật toán
Các bước xây dựng một thuật toán
Ví dụ thuật toán tìm số lớn nhất
Mối quan hệ giữa các khái niệm
Các ví dụ
Kiểm tra tính nguyên tố của một số nguyên dương
Bài toán sắp xếp
Bài toán tìm kiếm

1. Khái niệm bài toán
Ví dụ :

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

Bài toán xếp loại học tập của một lớp.
Input : Bảng điểm của học sinh trong lớp.
Output : Bảng xếp loại học lực của học sinh.
Là việc nào đó ta muốn máy thực hiện để từ thông tin đưa vào (Input) tìm được kết quả đầu ra (Output).
2. Khái niệm thuật toán
Từ Input
làm thế nào để tìm ra Output ?
Các bạn cần tìm ra cách giải
của bài toán.
2.1 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 ấy, từ Input của bài toán, ta nhận được Output cần tìm.


2.2 Tính chất thuật toán:
Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần
thực hiện các thao tác.
Tính xác định: Sau khi thực hiện một thao tác thì hoặc thuật
toán kết thúc hoặc là có đúng một thao tác xác định để thực hiện
tiếp theo.
Tính đúng đắn: Khi thuật toán kết thúc, ta phải nhận được
Output cần tìm
2.3 Thể hiện một thuật toán:

Cách 1: Liệt kê các bước.
Cách 2: Vẽ sơ đồ khối.
Qui ước cách biểu diễn trên sơ đồ khối :

Thể hiện thao tác nhập, xuất dữ liệu
Thể hiện các phép tính toán
Thể hiện thao tác so sánh
Qui định trình tự thực hiện các thao tác
Xác định bài toán :
- Input
- Output
2.4 Các bước xây dựng thuật toán
Hình thành ý tưởng chính để giải quyết bài toán, lưu ý xác định điểm dừng của thuật toán.
Mô phỏng để kiểm tra tính đúng đắn.
Xây dựng thuật toán bằng 1 trong 2 :
- Cách liệt kê
- Vẽ sơ đồ
Xác định bài toán:
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ố.
Ý tưởng:
- Đặt giá trị Max = a1.
- Lần lượt cho i đi từ 2 đến N, so sánh giá trị ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai.
2.5 Thuật toán tìm số lớn nhất:
Quả này
lớn nhất
Quả này
mới lớn nhất
Tìm ra quả lớn nhất rồi!
Ồ! Quả này lớn hơn
Mô phỏng thuật toán:
a) Cách liệt kê:


Bước 1: Nhập N và dãy a1,a2…, aN;
Bước 2: Max  a1; i  2;
Bước 3: Nếu i > N thì đưa ra giá trị
Max rồi kết thúc;
Bước 4: Nếu ai > Max thì Max  ai;
Bước 5: i  i+1 rồi quay lại B3.

b) Sơ đồ khối:
Xây dựng thuật toán
Nhập
dữ liệu
Xuất
thông tin
Tính toán
xử lý
thao tác 1; thao tác 2; …; thao tác N
Liệt kê - Sơ đồ
Ngôn ngữ lập trình Chương trình
2.6 Mối quan hệ giữa các khái niệm
Kiểm tra tính nguyên tố của một số nguyên dương
Ví dụ 1 :
3. Các ví dụ
1. Xác định bài toán
Input : N là một số nguyên dương
Output : N là số nguyên tố hoặc
N không là số nguyên tố
Số nguyên tố :
Định nghĩa : “Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N”
Các tính chất :
- Nếu N = 1  N không là số nguyên tố
- Nếu 1 < N < 4  N là số nguyên tố
2. Ý tưởng
N<4 : Xem như bài toán đã được giải quyết
N>=4 : Tìm ước i đầu tiên > 1 của N
- Nếu i < N  N không là số nguyên tố
(vì N có ít nhất 3 ước 1, i, N)
- Nếu i = N  N là số nguyên tố

3. Xây dựng 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 là số nguyên tố”,
kết thúc;
Bước 3 : Nếu N<4 thì thông báo “N là số nguyên tố”,
kết thúc;
Bước 4 : i  2 ;
Bước 5 : Nếu i là ước của N thì đến bước 7
Bước 6 : i  i +1 rồi quay lại bước 5; (Tăng i lên 1 đơn vị)
Bước 7 : Nếu i = N thì thông báo “N là số nguyên tố”,
ngược lại thì thông báo “N không là số nguyên tố”,
kết thúc;
b) Sơ đồ khối :
b.1
b.2
b.3
b.4
b.5
b.6
b.7
Đ
Đ
Đ
Đ
S
S
S
S
4. Mô phỏng thực hiện thuật toán
N=9
i2
Bước 1 : Nhập N = 9
Bước 2, 3 : Vì N >= 4 nên thông qua b.2, 3
Bước 4 : i  2
Bước 5.1 : Vì 2 không là ước của 9
nên qua b.6
Bước 6.1 : i  i + 1 (i  3)
Quay lại b.5
Bước 5.2 : Vì 3 là ước của 9
nên qua b.7
Bước 7 : Vì i < N (3<9) nên thông báo
N không là số nguyên tố
2 là ước của 9 ?
i i + 1;
i3
3 là ước của 9 ?
9 không là số nguyên tô
S
S
S
S
Đ
Đ
Đ
Đ
a) Với N = 9 :
b.1
b.2
b.3
b.4
b.5
b.6
b.7
3 là ước của 7 ?
7 là số nguyên tô
N=7
i2
Bước 1 : Nhập N = 7
Bước 2, 3 : Vì N >= 4 nên thông qua b.2, 3
Bước 4 : i  2
Bước 5.1 : Vì 2 không là ước của 7
nên qua b.6
Bước 6.1 : i  i + 1 (i  3)
Quay lại b.5
Bước 5.2 : Vì 3 không là ước của 7
nên qua b.6
Bước 6.2 : i  i + 1 (i  4)
Quay lại b.5 …
2 là ước của 7 ?
i i + 1;
i3
S
S
S
S
Đ
Đ
Đ
Đ
b) Với N = 7 :
b.1
b.2
b.3
b.4
b.5
b.6
b.7
… Bước 5.6 : Vì 7 là ước của 7
nên qua b.7
Bước 7 : Vì i = N (7=7) nên thông báo
N là số nguyên tố
i7
i4
i5
i6
i i + 1;
…
7 là ước của 7 ?
Tính hiệu quả
* Vấn đề
Nếu N =2339 thì bước 5,6 ở thuật toán trên lặp lại 2338 lần. Có cách nào khác để giảm số lần thực hiện quá lớn này không ?
Dựa vào một tính chất của số nguyên tố:
Nếu N >= 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N  N là số nguyên tố
Ý tưởng : Tìm i tăng dần trong phạm vi từ 2 đến phần nguyên √ N thỏa điều kiện là ước của N :
- Nếu không tìm được  N là số nguyên tố
- Ngược lại  N không là số nguyên tố
* Cải tiến thuật toán
Xây dựng 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 là số nguyên tố”, kết thúc;
Bước 3 : Nếu N<4 thì thông báo
“N là số nguyên tố”, kết thúc;
Bước 4 : i  2 ;
Bước 5 : Nếu (i <= [√N]) và
(i không là ước của N)
thì i  i +1, rồi lặp lại bước này;
Bước 6 : Nếu (i > [√N]) thì thông báo
“N là số nguyên tố”,
ngược lại thì thông báo
“N không là số nguyên tố”,
kết thúc;
b) Sơ đồ :
Mô phỏng
thực hiện
thuật toán
a) Với N=3
N = 3
3>1
3 < 4
3 là số
nguyên tố
(3>[√72.65])
Mô phỏng
thực hiện
thuật toán
b) Với N=7
N = 7
7>1
i = 2
(2<=[√72.65]) và (2 không là ước của 7)
i = 3
(3>[√72.65])
7 là số
nguyên tố
7>4
(3 là ước của 45)
45 không là
số nguyên tố
(3<[√456.71])
N = 45
45>1
i = 2
Mô phỏng
thực hiện
thuật toán
c) Với N=45
i = 3
45 >4
(2<=[√456.71]) và (2 không là ước của 45)
Thực hiện trên Phiếu học tập của bạn
5. Bài tập tương tự và gợi ý
Xây dựng thuật toán tìm số nguyên tố lớn nhất bé hơn một số nguyên dương M cho trước.
Gợi ý : N  M-1;
(*) Nếu N là số nguyên tố thì xuất N, kết thúc;
N  N-1, rồi lặp lại bước (*);
Xây dựng thuật toán in bảng M số nguyên tố đầu tiên (M>0 cho trước).
Gợi ý : Đầu tiên Soluong  0; N  2;
Nếu Soluong=M thì kết thúc
(*) N  N+1
Nếu N là số nguyên tố thì xuất N, SoluongSoluong+1;
Lặp lại bước (*)
Suy nghĩ và cải tiến thuật toán :
Xuất 2;
Nếu M=1 thì kết thúc;
Soluong  1; N  3;
Nếu Soluong=M thì kết thúc
(*) Nếu N là số nguyên tố thì xuất N,
Soluong  Soluong+1;
N  N+2, rồi lặp lại bước (*)
Bài toán sắp xếp
Ví dụ 2 :
Trong cuộc sống, ta thường gặp những yêu cầu liên quan đến sắp xếp :
- Xếp các học sinh từ thấp đến cao
- Xếp điểm trung bình từ cao đến thấp
…
Tổng quát : Cho một dãy đối tượng hãy sắp xếp lại vị trí
các đối tượng theo một tiêu chuẩn nào đó
1. Xác định bài toán
Input : Dãy A gồm N số nguyên a1, a2,…,an

VD : Dãy A gồm các số nguyên
2 4 8 7 1 5

Output : Dãy A được sắp xếp thành dãy không giảm

Dãy A sau khi sắp xếp
1 2 4 5 7 8
3. Mô phỏng thực hiện thuật toán
Dãy ban đầu
Dãy sau khi sắp xếp
Lượt thứ nhất
Lượt thứ hai
Lượt thứ ba
Lượt thứ tư
Lượt thứ năm
2. Ý tưởng
Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước > số sau (không thỏa yêu cầu output) ta đổi chỗ chúng cho nhau.
Mỗi lượt tiến hành nhiều lần so sánh để đẩy phần tử lớn nhất trong số các phần tử chưa sắp xếp về đúng vị trí của nó. Lặp lại nhiều lượt cho đến khi không có sự so sánh nào nữa.
Lượt thứ 1 : số phần tử chưa sắp xếp bằng N, ta thực hiện N-1 lần so sánh (và đổi chổ nếu cần) để đưa phần tử lớn nhất về cuối dãy này và loại nó ra khỏi danh sách các phần tử cần sắp xếp.
Lượt thứ 2 : số phần tử chưa sắp xếp đã giảm 1, số lần so sánh cũng giảm tương ứng…
…
Cho đến khi số phần tử chưa sắp xếp < 2, không còn sự so sánh nào nữa thì kết thúc. Dãy đã được sắp xếp hoàn tất
Gọi i là số thứ tự của mỗi lần so sánh,
đầu tiên i  0.
Nhập N và các số hạng a1, a2,…,an
Đầu tiên gọi M là số số hạng
chưa sắp xếp, vậy M sẽ chứa
giá trị là N : M  N
Nếu số số hạng chưa sắp xếp < 2
thì dãy đã được xếp xong. Kết thúc.
M chứa giá trị mới là số phép so sánh
cần thực hiện trong lượt : M  M-1
Để thực hiện 1 lần so sánh mới,
i đếm tăng lên 1 (lần so sánh thứ i)
Nếu lần so sánh thứ i >số phép so sánh M :
đã hoàn tất M số phép so sánh của lượt này.
Lặp lại bước 3, bắt đầu lượt kế (với số số
hạng chưa được sắp xếp chính là M đã
giảm 1 ở bước 4).
So sánh 2 phần tử ở lần thứ i là ai và ai+1
Nếu ai > ai+1 thì tráo đổi 2 phần tử này
Quay lại bước 5
B.1 : Nhập N và các số hạng a1, a2,…,an;
B.2 : M  N ;
B.3 : Nếu M < 2 thì đưa ra dãy A đã được
xếp xong. Kết thúc;
B.4 : M  M-1 ; i  0 ;
B.5 : i  i + 1 ;
B.6 : Nếu i > M thì quay lại bước 3;
B.7 : Nếu ai > ai+1 thì tráo đổi ai và ai+1
cho nhau;
B.8 : Quay lại bước 5
4. Xây dựng thuật toán
B.1 : Nhập N và các số hạng
a1, a2,…,an;
B.2 : M  N ;
B.3 : Nếu M < 2 thì đưa ra
dãy A đã được sắp xếp.
Kết thúc;
B.4 : M  M-1 ; i  0 ;
B.5 : i  i - 1 ;
B.6 : Nếu i > M thì quay lại
bước 3;
B.7 : Nếu ai > ai+1 thì tráo
đổi ai và ai+1 cho nhau;
B.8 : Quay lại bước 5;
a) Cách liệt kê :
b) Sơ đồ khối :
5. Bài tập tương tự và gợi ý
Quan sát mô phỏng trong việc hình thành ý tưởng sắp xếp mới từ sự kết hợp thuật toán tìm số lớn nhất và thuật toán sắp xếp bằng cách tráo đổi vừa học. Em hãy liệt kê các bước hoặc vẽ sơ đồ khối cho ý tưởng thuật toán này
Ý tưởng :
Mỗi lượt tìm phần tử lớn nhất trong số các phần tử chưa sắp xếp. Đổi chỗ phần tử này với phần tử cuối dãy (phần chưa sắp xếp)
Việc này lặp lại nhiều lượt, cho đến khi dãy
chỉ còn duy nhất 1 phần tử chưa sắp xếp.
Mô phỏng thuật toán
Dãy ban đầu
Dãy sau khi sắp xếp
2
4
8
5
7
Bạn chỉ cần
xem lại và
ráp thuật toán
tìm số lớn
nhất trong dãy
các phần tử từ
a1  aM vào đây
Nhớ lưu lại
vị trí của Max
vào k
Sơ đồ thuật toán
Đã học
(Trang 34 SGK)
Bài toán tìm kiếm
Ví dụ 3 :
Tìm kiếm là một thao tác thường gặp trong cuộc sống :
- Tìm một học sinh trong danh sách một lớp học
- Tìm một quyển sách trên kệ sách
…
Tổng quát : Tìm và chỉ ra vị trí (nếu có) của một đối tượng
cụ thể nào đó trong một dãy các đối tượng đã cho.
1. Xác định bài toán
Input : Dãy A gồm N số nguyên khác nhau a1, a2,…,an
và một số nguyên k (khóa)

VD : Dãy A gồm các số nguyên
5 7 1 4 2 9 8 11 25 51
Và k = 2 (k = 6)

Output : Vị trí i mà ai = k
hoặc thông báo không tìm thấy k trong dãy

Vị trí của 2 trong dãy là 5 (không tìm thấy 6)
2. Ý tưởng
Tìm kiếm tuần tự được thực hiện một cách tự nhiên : Lần lượt đi từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khóa cho đến khi gặp một số hạng bằng khóa hoặc dãy đã được xét hết mà không tìm thấy giá trị của khóa trên dãy.
Bước 1: Nhập N, các số hạng a1, a2,…, aN và
giá trị khoá k;
Bước 2: i  1;
Bước 3: Nếu ai = k thì thông
báo chỉ số i,
rồi kết thúc;
Bước 4: i  i + 1;
Bước 5: Nếu i > N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc;
Bước 6: Quay lại bước 3;
3. Xây dựng thuật toán
5
i
51
25
11
8
9
2
4
1
7
5
A
5
- Với k = 2
Tại vị trí i = 5 có a5 = 2 = k
4
3
2
1
- Với k = 6
Không tìm thấy k = 6 trên dãy
11
4. Mô phỏng thực hiện thuật toán
* Vấn đề
Nếu dãy A đã được sắp thứ tự tăng. Có cách nào tăng nhanh tốc độ tìm kiếm một giá trị khóa k trên dãy không ?
1. Xác định bài toán
Input : Dãy A là dãy tăng gồm N số nguyên khác nhau
a1, a2,…,an và một số nguyên k (khóa)

VD : Dãy A gồm các số nguyên
2 4 5 6 9 21 22 30 31 33
Và k = 21 (k = 25)

Output : Vị trí i mà ai = k
hoặc thông báo không tìm thấy k trong dãy

Vị trí của 21 trong dãy là 6 (không tìm thấy 25)
2. Ý tưởng
Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh vùng tìm kiếm bằng cách so sánh k với số hạng ở giữa phạm vi tìm kiếm (agiữa), khi đó chỉ xảy ra một trong ba trường hợp:
- Nếu agiữa= k  tìm được chỉ số, kết thúc;
- Nếu agiữa > k  việc tìm kiếm thu hẹp chỉ xét từ
ađầu (phạm vi)  agiữa - 1;
- Nếu agiữa < k  việc tìm kiếm thu hẹp chỉ xét từ agiữa + 1  acuối (phạm vi).
Quá trình trên được lặp lại cho đến khi tìm thấy khóa k trên dãy A hoặc phạm vi tìm kiếm bằng rỗng.
31
30
33
31
30
33
21
22
21
22
21
22
6
9
10
9
8
7
5
4
3
2
1
i
6
5
4
2
A
9<21
30>21
21=21
3. Mô phỏng thực hiện thuật toán
k = 21
Lượt thứ nhất: agiữa là a5 = 9; 9 < 21
 vùng tìm kiếm thu hẹp trong phạm vi từ a6 a10;
Lượt thứ hai: agiữa là a8 = 30; 30 > 21
 vùng tìm kiếm thu hẹp trong phạm vi từ a6 a7;
Lượt thứ ba: agiữa là a6 = 21; 21= 21
 Vậy số cần tìm là i = 6
30>25
21<25
31
30
33
31
30
33
21
22
21
22
21
22
6
9
10
9
8
7
5
4
3
2
1
i
6
5
4
2
A
9<25
k = 25
Lượt thứ nhất: agiữa là a5 = 9; 9 < 25
 vùng tìm kiếm thu hẹp trong phạm vi từ a6 a10;
Lượt thứ hai: agiữa là a8 = 30; 30 > 25
 vùng tìm kiếm thu hẹp trong phạm vi từ a6 a7;
Lượt thứ ba: agiữa là a6 = 21; 21< 25
 vùng tìm kiếm thu hẹp chỉ còn a7;
Lượt thứ tư: agiữa là a7 = 22; 22< 25
 Đầu=Giữa + 1 = 8 > Cuối = 7
 Thông báo không tìm thấy 25;
Bước 1: Nhập N, các số hạng
a1, a2,…, aN và giá trị khoá k;
Bước 2: Đầu  1; Cuối  N;
Bước 3: Giữa [(Đầu+Cuối)/2];
Bước 4: Nếu aGiữa = k thì thông báo
chỉ số Giữa, rồi kết thúc;
Bước 5: Nếu aGiữa > k thì đặt
Cuối = Giữa - 1
rồi chuyển sang bước 7;
Bước 6: Đầu  Giữa + 1;
Bước 7: Nếu Đầu > Cuối thì thông báo không tìm thấy khóa k trên
dãy, rồi kết thúc;
Bước 8: Quay lại bước 3.
4. Xây dựng thuật toán
Tài liệu tham khảo
Sách giáo khoa Tin học 10
Sách Giáo viên Tin học 10
Tài liệu Phương Pháp Giảng dạy Tin học
(Trường ĐHSP Tp.HCM)
Bách khoa toàn thư mở http://vi.wikipedia.org
CD-ROM Giáo án điện tử môn Tin học 10
(Nhà Xuất bản Giáo dục)

Tháng 9 / 2006