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

Ngày soạn: 28/09/2006;	 	 ngày giảng: 02/10/2006; Lớp: 10
Bài: 	 §4. BÀI TOÁN VÀ THUẬT TOÁN
Tiết PPCT: 10, 11, 112,13, 14 
I. MỤC TIÊU BÀI HỌC:
1. Kiến thức : 
-Hiểu khái niệm “bài toán” trong Tin học và biết 2 thành phần cơ bản của một bài toán (Input, Output).
-Hiểu khái niệm “thuật toán” và 2 cách mô tả các thao tác trong thuật toán (liệt kê, sơ đồ khối). Nắm chắc các biểu tượng thể hiện các thao tác trong sơ đồ khối.
-Hiểu được khái niệm sơ lược ban đầu về “ngôn ngữ lập trình”.
-Nắm được các thuật ngữ chính trong bài.
-Qua bài học, HS hình dung rõ hơn một bước nữa về cách thức hoạt động của máy tính.
2. Kỹ năng :
-Biết cho ví dụ một số bài toán trong Tin học.
-Xác định được Input và Output của các bài toán.
-Mô tả được các thao tác trong thuật toán của một số bài toán cụ thể bằng 2 cách: liệt kê và dùng sơ đồ khối.
3. Thái độ :
Nghiêm túc, cẩn thận, đoàn kết, có tinh thần giúp đỡ nhau trong xây dựng bài học.
II. CHUẨN BỊ:
1. Tài liệu, bài tập:
2. Dụng cụ, thiết bị:
III. TIẾN TRÌNH LÊN LỚP:
1. Ổn định, tổ chức lớp:
2. Kiểm tra bài cũ:	
Câu hỏi:
Đáp án:
 1/ -Khái niệm hệ thống tin học?
 -Các thành phần của một hệ thống tin học?
 2/ -CPU là gì?
 -Kể tên một số thiết bị vào?
1/ (SGK).
2/ (SGK).
3. Bài giảng:
Hoạt động của Thầy và Trò
Nội dung ghi bảng
GV: (ĐVĐ) Để 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à bài toán và thuật toán. Hôm nay ta sang bài 4.
Hoạt động 1:
-Nội dung: Khái niệm bài toán.
-Mục tiêu: HS nắm được khái niệm bài toán.
-Cách tiến hành:
+GV: Trong Toán học ta nhắc nhiều đến khái niệm “bài toán” và ta hiểu đó là những việc mà con người cần phải thực hiện sao cho từ những dữ kiện đã có phải tìm ra hay chứng minh một kết quả nào đó.
 Vậy khái niệm “bài toán” trong Tin học có gì khác không? Để khẳng định cho vấn đề này, chúng ta xét các yêu cầu sau.
+HS: Thảo luận các yêu cầu trên bảng.
+GV: 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?
 *Trong phạm vi Toán học?
 *Trong phạm vi Tin học?
+HS: Đưa ra kềt quả.
+GV: Nhận xét kết quả.
§4. BÀI TOÁN VÀ THUẬT TOÁN
 I/ BÀI TOÁN:
 1/ Khái niệm bài toán:
*Xét các yêu cầu sau:
1)Giải phương trình bậc hai
 ax2 + bx + c = 0;
2)Viết 1 dòng chữ ra màn hình máy tính;
3)Tìm giá trị nhỏ nhất của các số trong một dãy số.
4)Tìm ƯCLN của 2 số nguyên dương a 
 và b;
5)Xếp loại học tập các HS trong lớp.
6)Quản lý các cán bộ trong 1 cơ quan;
→Yêu cầu nào được xem như là một bài toán?
*Kết quả:
 -Trong phạm vi Toán học: 
 Yêu cầu 1) và 4) được xem là bài toán.
 -Trong phạm vi Tin học: 
Tất cả các yêu cầu trên được xem là bài toán.
 +GV: Từ kết quả trên, em nào có thể đưa ra khái niệm “bài toán” trong Tin học.
 +HS: nêu khái niệm bài toán.
Hoạt động 2 :
-Nội dung: Tìm hiểu các yếu tố cơ bản của một bài toán.
-Mục tiêu: Giúp HS nắm được 2 yếu tố cơ bản (Input, Output) của một bài toán.
-Cách tiến hành:
+GV: Ghi vấn đề lên bảng.
 +HS thảo luận vấn đề trên bảng.
+GV: Để giải 1 bài toán công việc đầu tiên chúng ta phải làm gì?
+HS: Trà lời. (xác định đâu là dữ kiện đã cho và đâu là cái cần tìm).
 +GV: Nhận xét câu trả lời của HS, đưa ra kết luận và giới thiệu 2 thành phần tuơng ứng của một bài toán trong Tin học.
*Kết luận:
 Trong phạm vi Tin học, bài toán là một việc nào đó ta muốn máy tính thực hiện.
2. Các thành phần cơ bản của một bài toán :
* Vấn đề thảo luận:
 Các yếu tố cần quan tâm khi giải một bài toán trong Toán học?
-Giả thiết (cái đã biết)
-Kết luận (cái cần tìm)
 Trong Tin học :
 -Giả thiết àInput (Các thông tin đã có)
 (Đầu vào: Các T.tin đưa vào máy)
-Kết luận à Output (Các t. tin cần tìm)
 (Đầu ra: Các t.tin cần lấy ra từ máy)
*Kết luận :
 Các bài toán được cấu tạo bởi hai yếu tố cơ bản :
 -Input : Các thông tin đã có
 (Các giả thiết)
 -Output : Các thông tin cần tìm 
 (Kết luận)
+GV: Hướng dẫn học sinh tìm Input và Ouput của một số bài toán thông qua các ví dụ.
+HS: Theo dõi sự hướng dẫn của GV và áp dụng giải quyết các bài toán còn lại.
 +GV: Qua các VD trên ta thấy bài toán được cấu tạo bởi hai yếu tố cơ bản, đó là:
 *input: Các thông tin đã có.
 * Output : Các thông tin cần tìm.
3. Các ví dụ : Tìm input và output của bài toán
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ị lớn nhất trong dãy số.
VD3: Tìm ước chung lớn nhất của hai số nguyên dương a và b.
-Input: Hai số nguyên dương avà b.
-Output: Ước chung lớn nhất của a và b.
VD4: Xếp loại học tập các học sinh trong lớp. 
-Input : Bảng đđiểm của học sinh.
-Output :Bảng xếp loại học tập của học sinh.
VD5: Viết 1 dòng chữ ra màn hình máy tính.
-Input: Các kí tự.
-Output: Một dòng chữ. 
Hoạt động 3 : 
-Nội dung: Khái niệm thuật toán.
-Mục tiêu: Giúp HS hiểu và nắm được khái niệm thuật toán.
-Cách tiến hành:
 +GV: (ĐVĐ) Chúng ta đã biết khái niện về “bài toán” và các yếu tố cơ bản của một bài toán đó là: input, output. Để tìm được output từ input của bài toán, ta làm bằng cách nào? Hôm nay chúng ta sang phần tiếp theo. (II. Thuật toán)
 +GV: Trình bày khái niệm thuật toán thông qua sơ đồ.
 +HS: Lắng nghe và quan sát sơ đồ trên bảng.
 +GV: Muốn tìm ra kết luận từ giả thiết của bài toán, thì chúng ta phải làm gì?
 +HS: Đứng tại chỗ trả. (Giải bài toán).
 +GV: Yêu cầu HS dựa vào sơ đồ đó phác thảo khái niệm “thuật toán”.
 +HS: Trình bày theo cách hiểu của bản thân.
 +GV: Nhận xét và đưa ra kết luận.
II. THUẬT TOÁN 
 1. Khái niệm thuật toán:
*Sơ đồ:
 Bài tốn
Input
Output
Bằng cách nào?
Giải bài tốn
Hướng dẫn các thao tác cho máy thực hiện để tìm ra lời giải
Thuật tốn 
(GT)
(KL)
Nói cách khác : 
BÀI TỐN
 Input
Output
THUẬT TỐN
(Thao tác 1àThao tác 2à...àThao tác n)
*Kết luậ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 này đượ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.
Hoạt động 4 : 
-Nội dung: Mô tả các thao tác trong thuật toán.
-Mục tiêu : Giúp HS biết được 2 cách mô tả thuật toán: liệt kê và dùng sơ đồ khối.
-Cách tiến hành:
+ GV: Đưa ra bài toán giải “Tìm giá trị lớn nhất của dãy số nguyên” và yêu cầu HS xác định các yếu tố cơ bản của bài toán: Input và Output. 
+GV: Trong Toán học sau bước xác định yêu cầu bài toán, bước kế tiếp chúng ta phải làm công việc gì?
+HS: Trả lời (xác định hướng hay phương pháp giải)
+GV: Đó là ý tưởng của bài toán.
 +GV: sau bước xác định yêu cầu bài toán và phương pháp giải, công việc còn lại chúng ta phải làm gì để tìm ra kết luận từ giả thiết của bài toán?
+HS: Trả lời (Giải bài toán).
 +GV: Nhận xét và giải thích: “Giải bài toán”là trong Toán học, còn trong Tin học gọi là “Thuật toán”.
 Từ đó, GV hướng dẫn HS cách chuyển từ ý tưởng của bài toán này sang mô tả thuật toán bằng cách liệt kê. 
+ HS: Lắng nghe và hiểu được các bước mô tả thuật toán. 
2. Mô tả các thao tác trong thuật toán:
Có 2 cách : 
 Liệt kê và dùng sơ đồ khối.
Bài toán : “Tìm giá trị lớn nhất của dãy số nguyên”
*Xác định bài toán:
 -Input: Số nguyên dương N và dãy N số nguyên dương a1, a2, . . . , aN.
 -Output: Giá trị lớn nhất Max của dãy số.
*Ý tưởng:
-Khởi tạo giá trị Max = a1;
-Lần lượt với i từ 2 đến N, so sánh số hạng ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai.
*Thuật toán:
a. Mô tả theo cách liệt kê:
(Nêu ra tuần tự các thao tác cần tiến hành).
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 kết quả và 
 kết thúc; ngược lại thì sang Bước 4;
Bước 4:
 4.1: Nếu ai > Max thì Max ß ai ;
 4.2: i ß i + 1 rồi quay lại Bước 3.
+GV: Ngoài cách liệt kê các thao tác như trên, ta có thể dùng sơ đồ khối để mô tả thuật toán.
+GV: Ghi các qui ước trong sơ đồ lên bảng.
 (Đặc biệt yêu cầu HS học thuộc tại lớp các biểu tượng thể hiện các thao tác trong sơ đồ khối).
+GV: Lấy lại VD: Bài toán “Tìm giá trị lớn nhất của dãy số nguyên”
+GV: Hướng dẫn HS chuyển từng bước trong mô tả thuật toán theo cách liệt kê sang cách mô tả thuật toán bằng sơ đồ khối tương ứng.
+HS: Phân biệt được điểm giống và khác nhau giữa 2 cách mô tả này. Thuộc lòng tại lớp ý nghĩa các biểu tượng trong sơ đồ khối.
b. Biểu diễn bằng sơ đồ khối:
 Trong sơ đồ khối ta qui ước:
-Hình ô van : thể hiện thao tác
 nhập, xuất dữ liệu;
-Hình thoi : thể hiện thao tác so sánh;
-Hình chữ nhật : thể hiện phép tính
 toán;
-Các mũi tên : qui định trình tự thực 
 hiện các thao tác.
VD: Bài toán “Tìm giá trị lớn nhất của dãy số nguyên” ở trên được mô tả bằng sơ đồ khối như sau:
§ĩng
§ĩng
Sai
Sai
NhËp N vµ d·y a1,..., aN
Max ¬ a i
aii > Max
i > N 
Max ¬ a1, i ¬ 2
§­a ra Max råi kÕt thĩc
i ¬ i + 1
 *Ghi chú: 
-Mũi tên ß hiểu là gán giá trị của biểu thức bên phải mũi tên cho biến ở bên trái mũi tên;
-VD: i ß i + 1: Đặt cho biến I giá trị mới bằng giá trị trước đó tăng thêm 1 đơn vị.
 +GV: Thông qua Khái niệm thuật toán và VD trên, nêu tính chất của thuật toán và giải thích và đưa ra VD từng tính chất.
 +HS: Chú ý theo dõi và ghi chép.
3. Tính chất 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.
-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.
-Tính đúng đắn: 
 Sau khi thuật toán kết thúc, ta nhận đượ Output cần tìm.
VD: Víi thuËt to¸n t×m Max ®· xÐt:
-TÝnh dõng: 
 V× gi¸ trÞ cđa i  ...  th­êng gỈp nh÷ng viƯc liªn quan ®Õn s¾p xÕp chẳng hạn như: Danh sách häc sinh của lớp 10C được xếp theo thứ tự từ A đến Z (thứ tự ABC); XÕp lo¹i häc lùc häc sinh trong líp;... 
 Nãi mét c¸ch tỉng qu¸t, cho mét d·y ®èi t­ỵng, cÇn s¾p xÕp l¹i vÞ trÝ c¸c ®èi t­ỵng theo mét tiªu chÝ nµo ®ã.
 VD: Cho 10 chiÕc cäc cã chiỊu cao kh¸c nhau (hình a), cÇn xÕp l¹i sao cho cäc thÊp ë tr­íc, cäc cao ë sau (hình b).
 a) D÷ liƯu gèc b) Sau khi s¾p xÕp
 VD: Víi A lµ d·y gåm N sè nguyªn ( N = 10):
 6, 1, 5, 3, 7, 8, 10, 7, 12, 4,
 Sau khi s¾p xÕp ta cã d·y: 
 1, 3, 4, 5, 6, 7, 7, 8, 10, 12.
 +GV Giới thiệu sơ qua PP Sắp xếp: Sắp xếp được chia làm 2 loại đó là: SX trong và SX ngoài.
 *Sắp xếp TRONG: 
 → +Phương pháp Chọn (Selection Sort);
 + PP Đổi chỗ (Exchange Sort);
 + PP Chèn (Insertion Sort ).
 *Sắp xếp NGOÀI:
 → PP Trộn tự nhiên (Natural Merge Sort).
 Trong phạm vi SGK chúng ta chỉ học thuật toán sắp xếp bằng PP Đổi chỗ hay còn gọi là tráo đổi (Exchange Sort).
 +GV: Hướng dẫn các bước thực hiện bài toán trong VD.
 +HS: Theo dõi sự hướng dẫn của giáo viên.
VÝ dơ 2. 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: D·y A gåm N sè nguyªn a1, a2,..., aN.
- Output: D·y A ®­ỵc s¾p xÕp l¹i thµnh d·y kh«ng gi¶m.
*Ý 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ã sù ®ỉi chç nµo x¶y ra n÷a.
*ThuËt to¸n
a) C¸ch liƯt kª:
NhËp N, c¸c sè h¹ng a1, a2,..., aN;
M ← N;
NÕu M < 2 th× ®­a ra d·y A ®· ®­ỵc s¾p xÕp råi kÕt thĩc;
M ← M - 1, i ← 0;
i ← i + 1;
NÕu i > M th× quay l¹i b­íc 3;
NÕu ai > ai+1 th× tr¸o ®ỉi ai vµ ai+1 cho nhau;
Quay l¹i b­íc 5.
 +GV: Ta thÊy r»ng, sau mçi lÇn ®ỉi chç, gi¸ trÞ lín nhÊt cđa d·y A sÏ ®­ỵc chuyĨn dÇn vỊ cuèi d·y vµ sau l­ỵt thø nhÊt th× gi¸ trÞ lín nhÊt xÕp ®ĩng vÞ trÝ lµ ë cuèi d·y. T­¬ng tù, sau l­ỵt thø hai, gi¸ trÞ lín thø hai ®­ỵc xÕp ®ĩng ë vÞ trÝ s¸t cuèi,... Cã thĨ h×nh dung, sau mçi l­ỵt cã Ýt nhÊt mét sè h¹ng ®· xÕp ®ĩng vÞ trÝ vµ kh«ng cßn tham gia vµo qu¸ tr×nh ®ỉi chç n÷a, gièng nh­ c¸c bät n­íc tõ ®¸y hå nỉi dÇn vµ khi ®· lªn mỈt n­íc råi th× tan biÕn. Cã thĨ v× thÕ mµ s¾p xÕp b»ng tr¸o ®ỉi cßn cã tªn gäi lµ s¾p xÕp nỉi bät (Bubble Sort).
Ghi chĩ: 	
 - Qua nhËn xÐt trªn, 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.
 b) S¬ ®å khèi:
 M ¬ N
NhËp N vµ a1, a2,..., aN
M ¬ M – 1; i ¬ 0
M < 2 ? 
i > M ? 
§ĩng
Sai
ai > ai+1 ?
i ¬ i + 1 
§­a ra A råi 
kÕt thĩc
§ĩng
Sai
Sai
§ĩng
Tr¸o ®ỉi ai vµ ai+1
D­íi ®©y lµ vÝ dơ m« pháng c¸c b­íc thùc hiƯn cđa
ThuËt to¸n S¾p xÕp b»ng tr¸o ®ỉi (Exchange Sort).
 D·y A 
6
1
5
3
7
8
10
7
12
4
L­ỵt 1
1
5
3
6
7
8
7
10
4
12
L­ỵt 2
1
3
5
6
7
7
8
4
10
L­ỵt 3
1
3
5
6
7
7
4
8
L­ỵt 4
1
3
5
6
7
4
7
L­ỵt 5
1
3
5
6
4
7
L­ỵt 6
1
3
5
4
6
L­ỵt 7
1
3
4
5
L­ỵt 8
1
3
4
L­ỵt 9
1
3
L­ỵt 10
1
-GV: T×m kiÕm lµ viƯc th­êng lµm cđa mçi ng­êi, ch¼ng h¹n t×m cuèn s¸ch gi¸o khoa Tin häc 10 trªn gi¸ s¸ch ®Ĩ chuÈn bÞ cho giê häc ngµy h«m sau, cần tìm một HS trong danh sách một lớp Nãi mét c¸ch tỉng qu¸t lµ cÇn t×m mét ®èi t­ỵng cơ thĨ nµo ®ã trong tËp c¸c ®èi t­ỵng cho tr­íc.
-GV: Sè nguyªn k ®­ỵc gäi lµ kho¸ t×m kiÕm (gäi t¾t lµ kho¸). 
 VD: 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.
 -GV: Hướng dẫn các bước thực hiện bài toán và mô tả thuật toán bằng liệt kê.
 -HS: Chú ý theo dõi sự hướng dẫn của giáo viên.
 -GV: Gọi 1HS lên bảng mô tả thuật toán bằng sơ đồ khối.
 -GV cùng Lớp nhận xét và sửa sai (nếu có).
VÝ dơ 3. Bµi to¸n t×m kiÕm: 
 Cho d·y A gåm N sè nguyªn, ®«i mét kh¸c nhau: a1, a2,..., aN vµ mét sè nguyªn k. CÇn biÕt cã hay kh«ng chØ sè i () mµ ai = k. NÕu cã h·y cho biÕt chØ sè ®ã. 
A.ThuËt to¸n T×m kiÕm tuÇn tù 
 (Sequential Search)
*X¸c ®Þnh bµi to¸n
- Input: D·y A 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 A 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¸ cho ®Õn khi 
hoỈc gỈp mét sè h¹ng b»ng kho¸ (Tìm thấy) 
hoỈc d·y ®· ®­ỵc xÐt hÕt vµ kh«ng cã gi¸ trÞ nµo b»ng kho¸ (Không tìm thấy). 
*ThuËt to¸n
a) C¸ch liƯt kª
NhËp N, c¸c sè h¹ng a1, a2,..., aN vµ kho¸ k;
i ← 1;
NÕu ai = k th× th«ng b¸o chØ sè i, råi kÕt thĩc;
i ← i + 1;
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;
Quay l¹i b­íc 3.
Ghi chĩ:	Trong thuËt to¸n trªn, i lµ biÕn chØ sè c¸c sè h¹ng cđa d·y vµ nhËn gi¸ trÞ nguyªn lÇn l­ỵt tõ 1 ®Õn N + 1.
 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
§ĩng
Sai
D­íi ®©y lµ VD m« pháng c¸c b­íc thùc hiƯn cđa 
ThuËt to¸n T×m kiÕm tuÇn tù (Sequential Search)
k = 2 vµ N = 10
k = 6 vµ N = 10
A
5
7
1
4
2
9
8
11
25
51
A
5
7
1
4
2
9
8
11
25
51
i
1
2
3
4
5
-
-
-
-
-
i
1
2
3
4
5
6
7
8
9
10
11
Víi i = 5 th× a5 = 2.
Víi mäi i tõ 1 ®Õn 10 kh«ng cã ai cã 
gi¸ trÞ b»ng 6.
GV: Bài toán tìm kiếm ngoài thuật toán tìm kiếm nhị phân, ta có thể dùng thuật toán tìm kiếm nhị phân để thực hiện việc tìm kiếm, nhưng với điều kiện dãy A phải được sắp xếp theo thứ tự tăng (hoặc giảm)
VD: Cho dãy A gồm N = 6 như sau:
i
1
2
3
4
5
6
ai
2
4
5
7
8
9
và một số nguyên k = 7
-GV: Để thu hẹp lại phạm vi tìm kiếm, ta chia dãy A thành 2 phần có thể hơn kém nhau đúng 1 số hạng, số hạng nằm giữa 2 phần này ta gọi là: aGiua .
 Muốn biết aGiua cụ thể là a? thì ta đi tìm chỉ số Giua bằng chỉ số i (1 ≤ i ≤ N) nào ?
 Ta tìm chỉ số Giua bàng cách:
 Giua = = 
 = = 3,5 => Giua = 3
=> aGiua = a3 = 5.
 Cuối cùng ta so sánh aGiua(aGiua = a3 = 5) với khoá k(k = 7). Khi ®ã, chØ x¶y ra mét trong ba tr­êng hỵp sau:
aGiua = k
aGiua > k
aGiua < k
=> aGiua = a3 = 5 < khoá k = 7. Do đó ta tiếp tục việc tìm kiếm trên dãy mới (nửa dãy bên phải).
Ghi chĩ:	
 Tuú thuéc aGiua > k hoỈc aGiua < k mµ chØ sè ®Çu hoỈc chØ sè cuèi cđa d·y ë b­íc t×m kiÕm tiÕp theo sÏ thay ®ỉi. §Ĩ thùc hiƯn ®iỊu ®ã, trong thuËt to¸n chØ sư dơng c¸c biÕn nguyªn t­¬ng øng Dau vµ Cuoi cã gi¸ trÞ khëi t¹o Dau = 1 vµ Cuoi = N.
B.ThuËt to¸n T×m kiÕm nhÞ ph©n (Binary Search)
* 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;
- 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 A cã gi¸ trÞ b»ng k.
*Ý t­ëng: Sư dơng tÝnh chÊt d·y A lµ d·y t¨ng, ta t×m c¸ch thu hĐp nhanh ph¹m vi t×m kiÕm sau mçi lÇn so s¸nh kho¸ víi sè h¹ng ®­ỵc chän. §Ĩ lµm ®iỊu ®ã, ta chän sè h¹ng aGiua ë "gi÷a d·y" ®Ĩ so s¸nh víi k, trong ®ã Giua = .
 Khi ®ã, chØ x¶y ra mét trong ba tr­êng hỵp sau:
 -NÕu aGiua = k th× Giua lµ chØ sè cÇn t×m. ViƯc t×m kiÕm kÕt thĩc.
 -NÕu aGiua > k th× do d·y A lµ d·y ®· ®­ỵc s¾p xÕp nªn viƯc t×m kiÕm tiÕp theo chØ xÐt trªn d·y a1, a2,..., aGiua–1 (ph¹m vi t×m kiÕm míi b»ng kho¶ng mét nưa ph¹m vi t×m kiÕm tr­íc ®ã). 
 -NÕu aGiua < k th× thùc hiƯn t×m kiÕm trªn d·y aGiua+1, aGiua+2,..., aN. 
 Qu¸ tr×nh trªn sÏ ®­ỵc lỈp l¹i mét sè lÇn cho ®Õn khi hoỈc ®· t×m thÊy kho¸ k trong d·y A hoỈc ph¹m vi t×m kiÕm b»ng rçng.
*ThuËt to¸n
a) C¸ch liƯt kª
NhËp N, c¸c sè h¹ng a1, a2,..., aN vµ kho¸ k;
Dau ← 1, Cuoi ← N;
Giua ← ;
NÕu aGiua = k th× th«ng b¸o chØ sè Giua, råi kÕt thĩc;
NÕu aGiua > k th× ®Ỉt Cuoi = Giua - 1 råi chuyĨn ®Õn b­íc 7;
Dau ← Giua + 1;
NÕu Dau > Cuoi th× 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;
Quay l¹i b­íc 3.
b) S¬ ®å khèi: (Binary Search)
Dau ¬ 1; Cuoi ¬ N
NhËp N vµ a1, a2,..., aN; k
aGiua = k 
Dau > Cuoi
§­a ra Giua 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
Giua ¬ [(Dau + Cuoi)/2]
Dau ¬ Giua + 1
Cuoi ¬ Giua – 1
aGiua > k 
§ĩng
Sai
Sai
§ĩng
Sai
§ĩng
D­íi ®©y lµ vÝ dơ m« pháng c¸c b­íc thùc hiƯn thuËt to¸n (Binary Search)
.
k = 21, N =10
k = 25, N =10
i
1
2
3
4
5
6
7
8
9
10
i
1
2
3
4
5
6
7
8
9
10
A
2
4
5
6
9
21
22
30
31
33
A
2
4
5
6
9
21
22
30
31
33
Dau
1
6
6
Dau
1
6
6
7
8
Cuoi
10
10
7
Cuoi
10
10
7
7
7
Giua
5
8
6
Giua
5
8
6
7
aGiua
9
30
21
aGiua
9
30
21
22
L­ỵt
0
1
2
L­ỵt
0
1
2
3
4
ë l­ỵt thø hai th× aGiua = k. VËy chØ sè cÇn t×m lµ i = Giua = 6.
T¹i l­ỵt thø t­ Dau > Cuoi nªn kÕt luËn trong d·y A kh«ng cã sè h¹ng nµo cã gi¸ trÞ lµ 25 c¶.
4.Tổng kết nội dung, đánh giá cuối bài:
-Tóm tắt bài, nhấn mạnh các điểm chính. 
-Yêu cầu một số HS nhắc lại các thuật ngữ chính trong bài : Bài toán, Thuật toán, Sơ đồ khối, Input, Output.
 -Bài tập: Cho dãy số gồm N số sau (N=5): 8 11 7 20 4
 Tìm giá trị NHỎ NHẤT của dãy số trên?
Hướng dẫn:
-Gọi Min là giá trị nhỏ nhất cần tìm.
-Gán Min bằng giá trị phần tử đầu tiên của dãy.
-Lần lượt so sánh Min với các phần tử tiếp theo trong dãy. Tại mỗi vị trí so sánh, nếu Min lớn hơn giá trị phần tử cần so sánh trong dãy thì lấy giá trị của phần tử đó gán lại cho Min.
-Khi so sánh đến phần tử cuối cùng trong dãy thì Min sẽ mang giá trị nhỏ nhất của dãy.
a.Liệt kê:
b. Sơ đồ khối:
-Bước 1 : Nhập N và dãy a1,, aN;
-Bước 2 : Đặt Min ← a1, i ← 2;
-Bước 3 : Nếu i >N thì Đưa ra Min rồi kết thúc, 
 nếu không thì chuyển đến bước 4;
-Bước 4 : 
	4.1. Nếu Min > ai thì đặt Min ← ai ;
 4.2. Tăng i một đơn vị rồi quay về bước 3.
Nhập N và dãy a1,, aN
 Min ← a1 , i ← 2
i >N
Min > ai
Min ← ai
 i ← i+1
Đưa ra Min 
rồi kết thúc
Đúng
Sai
Đúng
Sai
5.Dặn dò, kế hoạch học tập tiết sau:
-Dặn HS tham khảo thêm VD trong SGK
-Bài tập về nhà: Bài 1, 3, 4, 5, 6 trang 44 
-Yêu cầu HS đọc trước bài mới “Ngôn ngữ lập trình”.
IV. NHỮNG VẤN ĐỀ CẦN RÚT KINH NGHIỆM: