Giáo án môn Tin học 10 - Bài 4: Bài toán và thuật toán

hông lý do:................ Tên HS:...........................
2. Kiểm tra bài cũ: Không.
3. Giảng bài mới: 
Nội dung bài học
Hoạt động của giáo viên
Hoạt động của học sinh
1. Khái niệm bài toán
- Bài toán là những việc mà con người muốn máy tính thực hiện.
Ví dụ: Giải một phương trình, quản lý thông tin về học sinh ... đó là những bài toán.
- Khi giải một bài toán trên máy tính cần quan tâm đến 2 yếu tố: Input và Output.
+ Input (Thông tin đưa vào máy)
+ Output (Thông tin muốn lấy ra từ máy)
Ví dụ 1: Hãy xác định Input và Output của bài toán Tìm UCLN của 2 số M và N.
Trả lời: Input: M, N là 2 số nguyên dương
 Output: UCLN(M, N)
Ví dụ 2: Cho biết Input và Output của bài toán giải phương trình bậc 2 ax2+ bx+ c = 0
Trả lời: Input: a, b, c là các số thực
 Output: Nghiệm x của phương trình.
Ví dụ 3: Kiểm tra n có phải là một số nguyên tố hay không ?
Trả lời: Input: n là số ngyuên
 Output: Trả lời câu hỏi "n có phải là một số nguyên tố hay không?
Ví dụ 4: Cho biết Input và Output của bài toán xếp loại học tập.
Trả lời: Input: Bảng điểm của học sinh 
 Output: Bảng xếp loại học tập
2. Khái niệm thuật toán:
- Thuật toán để giải 1 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.
- Ví dụ: 
Thuật toán tìm UCLN của 2 số M, N.
* Xác định bài toán
 + Input: M, N
 + Ontput: UCLN(M, N)
* ý tưởng: - Nếu M = N thì gán UCLN=M
 - Nếu M > N thì gán M = M - N
 - Nếu M < N thì gán N = N - M
* Thuât toán: (Theo cách liệt kê từng bước)
-B1: Nhập M, N
-B2: Nếu M = N thì UCLN = M
-B3: Nếu M > N thì thay M= M - N, 
 rồi quay lại B2.
-B4: Nếu M<N thì thay N = N - M 
 rồi quay lại B2
-B5: Gán UCLN là M và kết thúc.
* Ngoài ra thuật toán còn được diễn tả bằng sơ đồ khối với các qui định:
- Hình elip: Các thao tác nhập, xuất dữ liệu
- Hình thoi: Các thao tác so sánh
- Hình chữ nhật: Các phép toán
- Mũi tên: Qui định trình tự các thao tác.
* Thuật toán được mô tả bằng sơ đồ sau:
NhËp M vµ N
M=N ?
M>N ?
§­a raUCNN lµ M
 vµ KÕt thóc
N <= N - M
M <= M - N
§óng
§óng
Sai
Sai
* Các tính chất của thuật toán:
+ Tính dừng: Thuật toán phải dừng sau một số hữa hạn lần thực hiện các thao tác.
+ Tính xác định: Sau một thao các thì thuật toán phải kết thúc hoặc chỉ có đúng một thao tác để được thực hiện tiếp theo.
+ Tính đúng đắn: Sau khi kết thúc thuật toán, phải nhận được Output cần tìm.
3. Một số ví dụ về thuật toán:
 Ví dụ 1: Bài toán sắp xếp.
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 (tức là số hạng trước không lớn hơn số hạng sau).
Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
* Xác định bài toán
- Input: Số nguyễn dương N, dãy a1, a2,., aN.
- Output: Dãy a1, a2,., aN được sắp xếp thành dãy không giảm.
* ý tưởng: Ta so sánh lần lượt các 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 đổi chỗ được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
* 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: 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 cho nhau;
Bước 8: Quay lại bước 5.
b) Sơ đồ khối
M ¬ N
NhËp N vµ a1, a2,..., aN
M ¬ M – 1; i ¬ 0
M < 2 ? 
i > M ? 
Đ
Sai
ai > ai+1 ?
i ¬ i + 1 
§­a ra A råi 
kÕt thóc
Đúng
Sai
Sai
Đ
Tr¸o ®æi ai vµ ai+1
Ví dụ: Bài toán tìm kiếm
Cho dãy gồm N số nguyên khác nhau: a1, a2,..., aN và một số nguyên k. Cần biết có hay không chỉ số i (1 £ i £ N) mà ai = k. Nếu có hãy cho biết chỉ số đó. 
+ Thuật toán Tìm kiếm tuần tự:
* Xác định bài toán
- Input: Dãy gồm N số nguyên đôi một khác nhau a1, a2,..., aN và số nguyên k;
- Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy có giá trị bằng k.
* ý tưởng: Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá k cho đến khi hoặc gặp một số hạng bằng khoá k hoặc dãy đã được xét hết và không có giá trị nào bằng khoá k. 
* Thuật toán
a) Cách liệt kê
- Bước 1: Nhập N, các số hạng a1, a2,..., aN và 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.
b) Sơ đồ khối:
Sai
i ¬ 1
NhËp N vµ a1, a2,..., aN; k
i ¬ i + 1
ai = k
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
§óng
§
Sai
Dẫn dắt vấn đề: Để viết được chương trình cho máy tính thực hiện ta cần biết thế nào là thuật toán và bài toán. Đó chính là nội dung của bài học hôm nay.
* Hoạt động 1: Tìm hiểu về khái niệm bài toán.
- Các em đã biết bài toán trong toán học. Vậy trong tin học ta quan niệm bài toán như thế nào?
- Hãy cho ví dụ về bài toán trong tin học.
- Đứng trước 1 bài toán công việc đầu tiên là gì?
- Phân tích và nhận xét:
Công việc đầu tiên là đi xác định đâu là dữ kiện đã cho và đâu là cái cần tìm?
- Nhận xét và giới thiệu Input là thông tin đưa vào máy, output là thông tin cần lấy ra từ máy tính.
- GV: Ghi các ví dụ lên bảng và hỏi.
+ Input của bài toàn là gì?
+ Output của bài toàn là gì?
- Phân tích và nhận xét.
Ø Chốt lại, chuyển tiếp: Khi dùng máy tính để giải một bài toán ta cần quan tâm đến 2 yếu tố thông tin đầu vào (Input) và thông tin đầu ra (Output). Với mỗi bài toán người lập trình phải tìm ra cách giải thế nào để từ Input đưa ra được Output. Cách giải bài toán đó được gọi là thuật toán. Để hiểu rõ hơn về thuật toán mời các em nghiên cứu mục 2.
* Hoạt động 2: Tìm hiểu về thuật toán
- Trong toán học từ giả thiết làm sao ta tìm ra được kết luận?
- Em hiểu như thế nào về thuật toán để giải một bài toán?
K Giải thích thêm về thuật toán, nhấn mạnh câu chữ quan trọng. 
... 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 ...
... từ Input -> Output.
Ø Đối với một bài toán sau khi xác định Input và Output thì việc tìm ra thuật toán để giải bài toán là hết sức quan trọng. Và sau đây chúng ta sẽ nghiên cứu việc tìm thuật toán để giải một bài toán cụ thể (Tìm UCLN của 2 số).
- Đứng tại chỗ xác định Input và Output?
- GV: Lấy ví dụ cụ thể với 2 số (12,8) và giải thích thuật toán qua từng bước:
B1: Nhập M=12, N=8 → M>N
B2: M=12-8=4, N=8 → N>M
B3: M=4, N=8-4=4 → M=N
 => UCLN(M,N)=4
GV: Cách viết thuật toán theo từng bước như trên gọi là cách liệt kê, còn có cách làm khác đó là dùng Sơ đồ khối.
GV: Lấy lại ví dụ tìm UCLN của 2 số M,N
GV: Vẽ sơ đồ thuật toán lên bảng. Chỉ cho học sinh thấy các bước của thuật toán được mô tả trong sơ đồ.
- Qua khái niệm về thuật toán. Hãy cho biết thuật toán có những tính chất gì?
- Phân tích và nhận xét: xét với các tính chất của thuật toán với bài toán trên?
* Hoạt động 3: Tìm hiểu bài toán sắp xếp.
GV: Đặt vấn đề: Trong cuộc sống ta thường gặp những bài toán sắp xếp ví dụ sắp điểm từ thấp đến cao hay sắp xếp học sinh theo ABC.v.v... Hôm nay chúng ta đi tìm hiểu một số thuật toán sắp xếp cơ bản.
- Ví dụ: ta có 1 dãy số nguyên 6 1 5 3 7 4 10. hãy sắp xếp dãy trên thành dãy tăng dần?
GV: Đưa ra ví dụ về thuật toán sắp xếp rồi cho học sinh xác định input, output và ý tưởng thuật toán.
- Nhận xét và đưa ra thuật toán bằng cách liệt kê từng bước. Giảng giải từng bước của thuật toán để học sinh nắm kỉ về thuật toán.
GV: Tổng hợp lại, chính sửa thuật toán cho phù hợp và phân tích các bước hoạt động của thuật toán.
Ví dụ: : 6, 1, 5, 3, 7, 8, 10, 7, 12, 4
- Cho học sinh tính toán cụ thể với ví dụ trên (SGK) để minh hoạ và đưa ra nhận xét.
- Nhận xét: Ta thấy quá trình so sánh và đổi chỗ sau mỗi lượt chỉ thực hiện với dãy đã bỏ bớt số hạng cuối dãy. Để thực hiện điều đó trong thuật toán sử dụng biến nguyên M có giá trị khởi tạo là N, sau mỗi lượt M giảm một đơn vị cho đến khi M < 2. 
- Trong thuật toán trên, i là biến chỉ số các số hạng của dãy có giá trị nguyên thay đổi lần lượt từ 0 đến M + 1.
- Qua cách giải thuật toán bằng cách liệt kê, yêu cầu học sinh biểu diễn thuật toán bằng sơ đồ khối.
* Hoạt động 4: Tìm hiểu về bài toán tìm kiếm.
- Đặt vấn đề: Trong cuộc sống tìm kiếm là việc thường xuyên xảy ra vi dụ tìm một quốn sách trên giá sách hay tìm một học sinh trong lớp .v.v... Hôm nay chúng đi tìm hiểu một số thuật tìm kiếm cơ bản.
GV: Đưa ra ví dụ bài toán
GV: Giải thích, gợi ý để học sinh đưa ra ý tưởng thuật toán.
- Trong ví dụ trên k là khoá tìm kiếm 
- Ví dụ, cho dãy A gồm các số: 
5, 7, 1, 4, 2, 9, 8, 11, 25, 51.
* Với khoá k = 2, trong dãy trên có số hạng a5 có giá trị bằng k. Vậy chỉ số cần tìm là i = 5.
* Với khoá k = 6 thì không có số hạng nào của dãy A có giá trị bằng k. 
- Cho ví dụ mô phỏng quá trình thực hiện thuật toán.
GV: Dãy số trên với k=2 và k=6 ta có kết quả tìm kiếm sau:
k = 2 và N = 10
A
5
7
1
4
2
9
8
11
25
51
i
1
2
3
4
5
-
-
-
-
-
Với i = 5 thì a5 = 2.
k = 6 và N = 10
A
5
7
1
4
2
9
8
11
25
51
i
1
2
3
4
5
6
7
8
9
10
11
Với mọi i từ 1 đến 10 không có ai có 
giá trị bằng 6.
- Vậy em nào có thể biểu diễn thuật toán trên bằng cách sơ đồ khối?
- Phân tích và nhận xét.
- Học sinh chú ý nghe dẫn dắt vấn đề.
I Học sinh nghiên cứu sách giáo khoa và trả lời.
? Học sinh nghe giảng, ghi chép bài.
I Học sinh nghiên cứu sách giáo khoa và trả lời.
? Học sinh nghe giảng, ghi chép bài.
I Học sinh nghiên cứu sách giáo khoa và trả lời.
? Học sinh nghe giảng, ghi chép bài.
I Học sinh nghiên cứu sách giáo khoa và trả lời.
? Học sinh nghe giảng, ghi chép bài.
? Học sinh nghe giảng.
? Học sinh nghe giảng, ghi chép bài.
I Học sinh nghiên cứu sách giáo khoa và trả lời.
? Học sinh nghe giảng, ghi chép bài.
? Học sinh nghe giảng.
- Trả lời.
1 3 4 5 6 7 10 
I Học sinh nghiên cứu sách giáo khoa và