BÀI 3: THUẬT TOÁN
Giáo viên:
Gmail: thayhuetnh@gmail.com
SĐT, Zalo: 0382.1682.32
Blog: thayhuetnh.blogspot.com
1
Chương II: Các khái niệm về thuật toán và độ phức tạp của thuật toán
BÀI 3: THUẬT TOÁN
I. Bài toán và các bước giải bài toán trên máy tính
1. Khái niệm về bài toán
Mọi bài toán đều có thể diễn đạt theo một sơ đồ chung:
A B
Trong đó:
A là giả thiết, điều kiện ban đầu hoặc là cái đã cho, đã có khi bắt đầu giải bài toán.
B là kết luận, mục tiêu cần đạt hoặc là cái phải tìm, phải làm ra khi kết thúc bài toán.
là suy luận, giải pháp, các thao tác cần thực hiện, cần thi hành để có thể được cái phải tìm B từ cái đã có A.
2
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
I. Bài toán và các bước giải bài toán trên máy tính
1. Khái niệm về bài toán
- Bài toán trên máy tính: một bài toán là một công việc, một vấn đề nào đó cần giải quyết với sự trợ giúp của máy tính.
Một bài toán trên máy tính mang đầy đủ các tính chất của bài toán tổng quát trên, nhưng có thể diễn đạt theo cách nói khác như sau:
A: Input (thông tin đầu vào)
B: Output (thông tin đầu ra)
🡪 là chương trình tạo ra từ các lệnh cơ bản của máy tính cho phép biến đổi từ A thành B.
3
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
I. Bài toán và các bước giải bài toán trên máy tính
2. Các bước giải bài toán trên máy tính
4
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
I. Bài toán và các bước giải bài toán trên máy tính
2. Các bước giải bài toán trên máy tính
a. Xác định bài toán
Từ phát biểu của một bài toán, ta cần xác định rõ dữ liệu đầu vào Input và dữ liệu đầu ra Output của bài toán đó.
VD1: Tìm ước chung lớn nhất (UCLN) của 2 số M và N
+ Input: 2 số nguyên dương M và N
+ Output: d = UCLN (M, N) thỏa
d là ước của M, d là ước của N.
d là phần tử lớn nhất trong tập các ước chung của M và N.
5
input:
output:
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
I. Bài toán và các bước giải bài toán trên máy tính
2. Các bước giải bài toán trên máy tính
a. Xác định bài toán
VD2: Giải phương trình bậc 2 ax2 + bx + c =0 (a≠0)
+ Input: các hệ số a, b, c
+ Output: nghiệm x thoả phương trình
VD3: Kiểm tra số nguyên dương N có phải là số nguyên tố hay không?
+ Input: số nguyên dương N
+ Output: N là số nguyên tố hoặc N không là số nguyên tố
6
input:
output:
input:
output:
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
I. Bài toán và các bước giải bài toán trên máy tính
2. Các bước giải bài toán trên máy tính
b. Thiết kế và lựa chọn thuật toán
Mỗi thuật toán chỉ giải một bài toán nhưng một bài toán có thể được giải bằng nhiều thuật toán. Vì vậy với từng bài toán cụ thể ta phải lựa chọn thuật toán cho thích hợp để tiết kiệm được không gian nhớ và thời gian thực hiện chương trình (với các chương trình ứng dụng người ta còn chọn NNLT cho phù hợp với loại ứng dụng).
Còn đối với các bài toán nhỏ, số lần giải toán không nhiều, tiêu chí chọn thuật toán làm sao để dễ cài đặt ít tốn thời gian và công sức người lập trình.
7
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
I. Bài toán và các bước giải bài toán trên máy tính
2. Các bước giải bài toán trên máy tính
c. Viết chương trình:
Gồm các công việc sau: Lựa chọn cấu trúc dữ liệu, chọn ngôn ngữ lập trình và sử dụng chúng để diễn tả đúng thuật toán.
d. Kiểm thử và hiệu chỉnh:
Chương trình sau khi viết xong vẫn còn có thể có lỗi và sẽ cho kết quả không đúng. Vì vậy, ta phải xây dựng một số bộ Input tiêu biểu phụ thuộc vào đặc thù của bài toán mà bằng cách nào đó ta biết trước được bộ kết quả Output tương ứng.
Trong quá trình kiểm thử nếu phát hiện sai sót ta sẽ hiệu chỉnh lại chương trình và tiếp tục kiểm thử lại.
8
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
I. Bài toán và các bước giải bài toán trên máy tính
2. Các bước giải bài toán trên máy tính
e. Viết tài liệu:
Tài liệu trình bày liên quan đến việc mô tả bài toán, thuật toán, cấu trúc dữ liệu, thiết kế và hướng dẫn sử dụng chương trình nhằm người sử dụng có thể khai thác tốt chương trình.
9
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
1. Khái niệm thuật 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 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, ta nhận được Output cần tìm.
Tác dụng của thuật toán: là để giải 1 bài toán.
10
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
- Các bước tìm thuật toán để giải 1 bài toán:
1. Xác định bài toán
2. Ý tưởng
3. Thuật toán:
Để biểu diễn thuật toán ta dùng phương pháp
11
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
2. Biểu diễn thuật toán:
a. Phương pháp liệt kê có một số thao tác cơ bản:
+ Bắt đầu, thông báo yêu cầu
+ Lệnh gán trị
+ Lệnh thực hiện: các phép tính số học, phép tính logic
+ Lệnh kiểm tra điều kiện
+ Lệnh chuyển không điều kiện, lệnh chuyển có điều kiện
+ Lệnh lặp lại
+ Kết thúc
12
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
2. Biểu diễn thuật toán:
b. Phương pháp sơ đồ khối :
Dùng các hình vẽ mô tả các động tác, các mũi tên chỉ thứ tự thực hiện các động tác:
13
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
2. Biểu diễn thuật toán:
Ví dụ 1: Viết thuật toán tìm giá trị lớn nhất (Max) của dãy gồm N số nguyên dương số a1,a2,…,an
* Xác định bài toán
* Ý tưởng:
14
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
A1=4
A2=6
A3=1
A4=9
A5=8
Dãy A
Max=4
Max=6
Max=9
BÀI 3: THUẬT TOÁN
II. Thuật toán.
2. Biểu diễn thuật toán:
Ví dụ 1: Viết thuật toán tìm giá trị lớn nhất (Max) của dãy gồm N số nguyên dương số a1,a2,…,an
* Thuật toán (liệt kê):
+ B1: Nhập N và dãy a1,a2,…,an
+ B2: Max 🡨 a1 , i 🡨 2
+ B3: Nếu i > N thì đưa ra Max. Rồi kết thúc.
+ B4:
B4.1: Nếu ai> Max thì Max 🡨 ai
B4.2: i 🡨 i + 1. Quay lại B3.
15
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
2. Biểu diễn thuật toán:
Ví dụ 1: Viết thuật toán tìm giá trị lớn
nhất của dãy gồm N số nguyên dương
* Thuật toán (sơ đồ khối):
N=5; A=[18, 24, 9, 39, 28]
16
i | | | | | | |
Ai | | | | | | |
Max | | | | | | |
1
2
4
5
6
3
18
24
39
28
9
18
24
39
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
Nhập n, a1,a2,..an
Max🡨a1, i 🡨 2
ai>Max
i>N?
Max🡨ai
i 🡨 i + 1
Đưa ra Max roi KT
Đ
S
Đ
S
5
18,24,9,39,28
2>5?
Max🡨18, i 🡨 2
24>Max
Max🡨24
i 🡨 2 + 1
3>5?
9>Max
4>5?
39>Max
Max🡨39
5>5?
28>Max
6>5?
Max=39
i 🡨 3 + 1
i 🡨 4 + 1
i 🡨 5 + 1
BÀI 3: THUẬT TOÁN
II. Thuật toán.
3. Các đặc trưng chính của thuật toán:
17
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
3. Các đặc trưng chính của thuật toán:
+ Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện thao tác.
Ví dụ: thuật toán tìm Max sẽ kết thúc sau đúng N-1 lần thực hiện phép so sánh và đưa ra giá trị Max cần tìm.
Tính "dừng" hay hữu hạn là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thuật toán. Dĩ nhiên, mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau một thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi không thỏa tính chất này, ta nói rằng thuật toán bị lặp vô tận.
18
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
3. Các đặc trưng chính của thuật toán:
+ Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện thao tác.
Ví dụ: thuật toán lau bảng như sau:
B1: Vẽ hình tròn
B2: Giặt khăn
B3: Lau bảng
B4: Quay lại B1
Thuật toán này sẽ bị lập vô hạn.
19
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
3. Các đặc trưng chính của thuật toán:
+ Tính xác định: Sau khi thực hiện 1 thao tác thì hoặc là thuật toán kết thúc, hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo.
*Thuật toán tìm Max của dãy số (cách liệt kê):
+ B1: Nhập N và dãy a1,a2,…,an
+ B2: Max 🡨 a1 , i 🡨 2
+ B3: Nếu i > N thì đưa ra Max. Rồi kết thúc.
+ B4:
B4.1: Nếu ai> Max thì Max 🡨 ai
B4.2: i 🡨 i + 1. Quay lại B3.
20
Tính xác định của thuật toán tìm Max:
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
3. Các đặc trưng chính của thuật toán:
+ Tính đúng đắn: Sau khi thuật toán Kết Thúc, ta phải nhận được output cần tìm.
Đây là một tính chất khá hiển nhiên nhưng là tính chất khó đạt tới nhất.
+ Tính phổ dụng: thể hiện ở chỗ thuật toán để giải một bài toán phải đảm bảo giải được bài toán đó với nhiều bộ dữ liệu vào khác nhau chứ không dùng để giải bài toán với một bộ dữ liệu cụ thể duy nhất.
Ví dụ: thuật toán tìm max nêu trên có thể áp dụng cho bất kì dãy số nào và với số các số hạng N là tùy chọn.
21
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
3. Các đặc trưng chính của thuật toán:
+ Tính hiệu quả: Tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành.
Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh giá, chọn lựa cách giải quyết vấn đề bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán.
22
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
3. Các đặc trưng chính của thuật toán:
+ Tính khả thi khi cài đặt thuật toán: quan tâm tới việc thuật toán đó có chuyển đổi được thành chương trình thực hiện được trên máy tính hay không? Để xét 1 thuật toán có khả thi không ta phải xem có thỏa điều kiện sau không:
⮚ Kích thước phải đủ nhỏ: bộ nhớ mà nó yêu cầu không vượt quá khả năng lưu trữ của hệ thống máy tính.
⮚ Thuật toán phải chuyển được thành chương trình.
⮚ Thuật toán phải được máy tính thực hiện trong thời gian cho phép.
23
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
4. Một số ví dụ về thuật toán (cho học sinh làm theo 2 cách)
Ví dụ 2: Kiểm tra tính nguyên tố của một số nguyên dương N.
* Xác định bài toán
* Ý tưởng:
24
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
II. Thuật toán.
4. Một số ví dụ về thuật toán (cho học sinh làm theo 2 cách)
VD1: Kiểm tra tính nguyên tố của một số nguyên dương N.
* Thuật toán (cách liệt kê)
25
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I
BÀI 3: THUẬT TOÁN
Củng cố
I. Bài toán và các bước giải bài toán trên máy tính
1. Khái niệm về bài toán
2. Các bước giải bài toán trên máy tính
a. Xác định bài toán (input, output)
b. Thiết kế và lựa chọn thuật toán
c. Viết chương trình
d. Kiểm thử và hiệu chỉnh
II. Thuật toán
1. Khái niệm thuật toán
2. Biểu diễn thuật toán (liệt kê, sơ đồ khối)
3. Các đặc trưng chính của thuật toán: tính dừng, tính xác định, tính đúng đắn
4. Một số ví dụ về thuật toán
26
Trường THPT chuyên Thoại Ngọc Hầu Tin học 10 Chuyên
Tổ Tin học Chương I