Giáo án Tin học Lớp 10 - Chương I, Bài 4: Bài toán và thuật toán

MÔN TIN HỌC LỚP 10
CHƯƠNG I: 
Bài 4. BÀI TOÁN VÀ THUẬT TOÁN
I. MỤC ĐÍCH – YÊU CẦU
1. Kiến thức :
Hiểu đúng khái niệm “Bài toán” trong Tin học và 2 thành phần cơ bản : Input, Output.
Hiểu rõ khái niệm “Thuật toán” – Cách biểu diễn thuật toán (liệt kê, sơ đồ khối). Nắm chắc các biểu tượng thể hiện thao tác trên sơ đồ khối, “đọc” được sơ đồ khối đơn giản.
Hiểu được quan hệ giữa các khái niệm : “Bài toán” – “Thuật toán” – “Ngôn ngữ lập trình”
Học sinh hình dung rõ hơn một bước 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, từ đó xác định được Input, Output.
Mô tả được các thao tác trong thuật toán của một số bài toán đơn giản bằng 2 cách : liệt kê, vẽ sơ đồ khối.
Có khái niệm ban đầu về biến, cách dùng biến.
II. ĐỒ DÙNG DẠY HỌC 
Giáo viên chuẩn bị máy vi tính, projector, CD tài liệu liên quan.
Học sinh chuẩn bị bảng phấn, phiếu học tập, tham khảo (photo trước).
III. CÁC PHƯƠNG PHÁP DẠY HỌC
Phương pháp vấn đáp gợi mở là chủ yếu, kết hợp việc tạo tình huống có vấn đề, hướng dẫn trực quan bằng các slide mô phỏng thuật toán giúp học sinh tham gia tích cực vào giờ học.
IV. HOẠT ĐỘNG DẠY HỌC :
Hoạt động 
của GV
Hoạt động 
của HS
Nội dung
Hoạt động 1 : Kiểm tra bài cũ
Mục tiêu : Giúp HS ôn lại kiến thức trong bài “Giới thiệu về máy tính”. Nhấn mạnh lại qui trình xử lí : Nhập à Tính toán, xử lí à Xuất để liên hệ qua bài mới
Gọi 1 học sinh trả bài, 1 học sinh vẽ lại sơ đồ xử lí thông tin trên máy tính
Chú ý theo dõi
Câu hỏi kiểm tra :
Khái niệm hệ thống tin học?
Các thành phần của 1 hệ thống tin học?
Kể tên một số thiết bị nhập, xuất dữ liệu (Input/Output Device) ?
Vai trò của CPU?
Qui trình, sơ đồ xử lí thông tin trên hệ thống tin học ?
Nhấn mạnh : 
Nhập 	à Tính toán	à Xuất 
dữ liệu	 Xử lí 	 thông tin
(sơ đồ 1)
Hoạt động 2 : Khái niệm Bài toán trong Tin học
Dẫn nhập
Bổ sung sơ đồ 1 à 2
1. Mục tiêu : Giúp HS hiểu khái niệm Bài toán tin học.
2. Cách tiến hành
* Giới thiệu khái niệm Bài toán trong Tin học 
* Sự khác biệt giữa bài toán trong Tin học và các bài toán thông thường : HS chia nhóm thảo luận và đánh dấu chọn đúng các bài toán tin học
* GV tổng kết à Kết luận
Làm việc theo nhóm
Các nhóm báo cáo kết quả.
Lắng nghe, ghi chép
Nhập 	à Tính toán	à Xuất 
dữ liệu	 Xử lí 	 thông tin
	Bài toán
INPUT ==========è OUTPUT
(sơ đồ 2)
§4. BÀI TOÁN – THUẬT TOÁN
I. BÀI TOÁN
1. Khái niệm
Chọn đúng các bài toán trong Tin học:
ÿ Giải phương trình bậc 2
ÿ Quản lí sách trong thư viện
ÿ Tìm USCLN của 2 số nguyên dương
ÿ Xếp loại học tập của HS
Kết luận : 
Trong phạm vi Tin học các yêu cầu trên đều được xem là bài toán. “Bài toán là một việc mà ta muốn máy tính thực hiện”
Hoạt động 3 : Input, Output của bài toán
1. Mục tiêu : Giúp HS nắm rõ 2 thành phần cơ bản này. 
2. Cách tiến hành :
Yêu cầu các nhóm thảo luận xác định dữ liệu vào, ra của các ví dụ trên.
* GV nhận xét, hướng dẫn HS tìm Input, Output à Kết luận 2 các thành phần cơ bản Input, Output
* Yêu cầu mỗi HS suy nghĩ, đặt một bài toán với Input, Output của nó. Ghi kết quả vào phiếu học tập của mình.
Làm việc theo nhóm
Các nhóm báo cáo kết quả.
Lắng nghe, ghi chép
Suy nghĩ nhanh, ghi Phiếu học tập
2. Các thành phần của 1 bài toán tin học
- Vào a, b, c à x1, x2
- Vào tên đầu sách, loại, số lượt mượn à tổng đầu sách mỗi loại, top 10 đầu sách hay nhất
- Vào 2 số nguyên dương a, b à USCLN m
- Vào điểm số các môn à G, Kh, TB, Y, K
Kết luận :
Các bài toán cấu tạo bởi 2 thành phần :
INPUT : Các thông tin đã có (giả thiết)
OUTPUT : Các thông tin cần tìm (kết luận, yêu cầu)
Hoạt động 4 : Khái niệm Thuật toán
1. Mục tiêu :
Giúp HS hiểu khái niệm thuật toán 
2. Cách tiến hành :
Bổ sung sơ đồ 2, trình bày khái niệm thuật toán thông qua sơ đồ này 
Lắng nghe, quan sát, ghi chép
II. THUẬT TOÁN
Khái niệm
	 Bài toán 
INPUT ==========è OUTPUT
	Bằng cách nào?
	Giải bài toán
	Hướng dẫn các thao tác Thuật toán
	cho máy thực hiện
Kết luận :
	Bài toán	(sơ đồ 3)
	 Thuật toán
INPUT ==========è OUTPUT
	(thao tác 1;  ; thao tácn)
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 (tính dừng)
- Các thao tác được tiến hành theo một trình tự xác định (tính xác định)
- Sau khi thực hiện xong dãy các thao tác đó ta nhận được Output của bài toán (tính đúng đắn)
Hoạt động 5 : Mô tả các thao tác trong thuật toán
1. Mục tiêu : Giúp HS biết, hiểu 2 cách mô tả thuật toán: Liệt kê, dùng sơ đồ
2. Cách tiến hành :
* Yêu cầu HS thảo luận theo nhóm và nêu các bước tiến hành tìm nghiệm PTB2 ax2 + bx + c = 0. 
* Gợi ý, giúp HS sắp xếp ‎ tưởng hợp ly
* Chú ý : Giải thích sơ lược về ý nghĩa của biến, phép gán (¬) 
* Diễn đạt bằng cách liệt kê đôi khi dài dòng và do có sự khác biệt ngôn ngữ và cách diễn đạt à diễn đạt bằng sơ đồ khối thống nhất, rõ ràng. GV chuyển từ các bước đã liệt kê sang sơ đồ khối
* Nêu ‎ý nghĩa các biểu tượng trong sơ đồ
* 2 cách trên diễn đạt trên được sử dụng cho con người, còn máy phải thông qua ngôn ngữ lập trình. 
Thực hiện yêu cầu của GV theo nhóm
Mỗi nhóm liệt kê các bước tiến hành 
Lắng nghe, ghi chép
- Có được khái niệm về Ngôn ngữ lập trình và Chương trình máy tính.
Mô tả các thao tác trong thuật toán
Bước 1 : Nhập a, b, c;
Bước 2 : Tính D ¬ b2 – 4ac;
Bước 3 : Nếu D < 0 thì thông báo vô nghiệm, rồi kết thúc;
Bước 4 : Nếu D = 0 thì thông báo nghiệm kép x = -b/2a, rồi kết thúc;
Bước 5 : Thông báo có 2 nghiệm 
x1, x2 = (-b±√D)/2a, rồi kết thúc;
Biến : Một ô nhớ lưu giữ giá trị của 1 đại lượng có thể thay đổi trong quá trình thực hiện thuật toán.
Phép gán (¬):
- Tính giá trị biểu thức bên phải dấu ¬
- Lưu giá trị tính được vào tên biến bên trái
Cách liệt kê :
Nêu tuần tự các bước cần tiến hành.
Cách vẽ sơ đồ khối
S
S
Đ
Đ
Ý nghĩa các biểu tượng
Ngôn ngữ lập trình được dùng để diễn tả các thuật toán cho máy tính hiểu và thực hiện được. Kết quả diễn tả thuật toán như vậy gọi là một chương trình máy tính.
Hoạt động 6 : Khảo sát ví dụ tìm giá trị lớn nhất của một dãy số nguyên
1. Mục tiêu : Củng cố kiến thức đã tiếp thu, vận dụng vào bài toán cụ thể
2. Cách tiến hành
* Yêu cầu HS xác định bài toán : Input, Output
* Dùng slide mô phỏng cho ý tưởng bài toán. Hướng dẫn HS từng bước liệt kê các thao tác.
* GV tổng kết à xây dựng thuật toán từ các bước đã liệt kê 
* Chuyển thuật toán sang cách biểu diễn bằng sơ đồ tương ứng. GV gợi ý và thực hiện các bước lặp, nhảy, so sánh
* Yêu cầu HS tự vẽ lại sơ đồ khối cho bài toán tìm giá trị nhỏ nhất của dãy số này
* Nhấn mạnh các bước xây dựng một thuật toán :
- Xác định bài toán
- Hình thành ý tưởng
- Xây dựng thuật toán
- Chú ý quan sát, trả lời theo hướng dẫn từng bước của GV
* HS tham gia xây dựng sơ đồ khối những bước đơn giản
* HS thực hiện trên Phiếu học tập.
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.
Xây dự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.
a) Sơ đồ:
Hoạt động 7 : Thuật toán kiểm tra tính nguyên tố của một số nguyên dương
1. Mục tiêu : Giúp HS nắm bắt ý tưởng thuật toán. Đi từ đơn giản à phức tạp. Vấn đề cải tiến thuật toán à tính hiệu quả của thuật toán
2. Cách tiến hành :
* Nhắc lại các bước tiến hành xây dựng 1 thuật toán
* Yêu cầu các nhóm xác định bài toán đặt ra, nhắc lại định nghĩa số nguyên tố
* GV bổ sung thêm các tính chất cần thiết để hình thành ‎ý tưởng thuật toán 1 (đơn giản)
* Gợi ý tìm ước số i > 1 đầu tiên của N và quan hệ i với N trong 2 trường hợp N nguyên tố và không nguyên tố. Xác định điểm dừng và tính đúng đắn của thuật toán
* Gọi từng nhóm tham gia xây dựng thuật toán (với sự hướng dẫn của GV)
* So sánh thuật toán do HS xây dựng với thuật toán đúng thể hiện trên slide
* Mô phỏng thuật toán với các trường hợp N=9, N=7
* Nêu vấn đề khi áp dụng thuật toán này cho những số N lớn à Yêu cầu cải tiến à thuật toán 2 (hiệu quả hơn)
* GV trình bày các bước hình thành thuật toán. 
* Kết luận về tính hiệu quả của một thuật toán 
* Dặn dò HS xem lại, đối chiếu những điểm khác nhau giữa sơ đồ thuật toán trên slide và trong SGK – Làm thêm các bài toán tương tự theo gợi ý trên Phiếu học tập
* Thảo luận theo nhóm, xác định Input, Output
* Phát biểu lại định nghĩa số nguyên tố
* Nhận xét, tham gia hình thành ‎ý tưởng thuật toán
* Các nhóm tham gia xây dựng thuật toán
* Quan sát, theo dõi
* Góp ý hình thành ‎ý tưởng thuật toán mới
* Quan sát, theo dõi, so sánh, phát hiện những điểm khác nhau giữa sơ đồ trên slide và SGK
III. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN
A. KIỂM TRA TÍNH NGUYÊN TỐ
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ố
ĐN : “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”
TC : 	- 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ơ đồ :
“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ố”
* Cải tiến thuật toán
Ý 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ố
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 : i ¬ 2 ;
Bước 4 : 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 5 : 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ơ đồ :
Ngoài các tính chất đã nêu khi nói đến thuật toán, người ta còn chú trọng đến tính hiệu quả của nó.
Hoạt động 8 : Bài toán sắp xếp bằng cách tráo đổi
1. Mục tiêu : Hiểu rõ tầm quan trọng của thuật toán sắp xếp à Hình thành kỹ năng làm việc theo trình tư khoa học và hợp ly.
2. Cách tiến hành :
* GV dẫn nhập bằng cách nêu lên tầm quan trọng của thuật toán sắp xếp. Mục đính của việc sắp xếp các đối tượng.
* GV xác định bài toán yêu cầu các nhóm thảo luận đề xuất các phương án sắp xếp
* GV tổng kết các phương án do HS đưa ra à Kết luận có nhiều cách sắp xếp
* Một cách đơn giản, tương đối hiệu quả và dễ hình thành thuật toán là sắp xếp bằng cách đổi chỗ trực tiếp à Giới thiệu ý tưởng thuật toán
* GV trình diễn mô phỏng thuật toán (slide minh họa)
* Xác định các yếu tố cần quan tâm của thuật toán, gọi tên chúng :
- Số số hạng cần so sánh
- Số phép so sánh, thứ tự mỗi lần so sánh
- Nhấn mạnh điểm dừng của thuật toán khi “số số hạng cần so sánh < 2”
* Dùng suy dẫn từng bước phát biểu các mệnh đề đúng, đối chiếu à hình thành các bước.
(slide minh họa).
* Gợi ‎ý các nhóm tham gia chuyển các bước đã liệt kê sang dạng sơ đồ
* GV nhận xét, tổng hợp và đưa ra sơ đồ chính xác
* Tổng kết GV có thể : 
- Mô tả thêm thuật toán tráo đổi giá trị 2 biến cho nhau khắc họa 1 bước khái niệm về biến cho các em
- Cũng cố : trình bày thêm ‎ý tưởng của các thuật toán sắp xếp đơn giản khác (mỗi lượt tìm phần tử lớn nhất, đổi chỗ với phần tử ở vị trí cuối – kết hợp với thuật toán tìm số lớn nhất đã học. Gợi ý, khuyến khích các em tham gia xây dựng thuật toán, nộp bài ở tiết học sau) 
* Các nhóm tham gia cho ví dụ về các bài toán sắp xếp thường gặp trong đời sống 
* Nhóm thảo luận, đề xuất phương án
* Quan sát, theo dõi
* Các nhóm tham gia vẽ, chỉnh sửa sơ đồ
* HS theo dõi, nêu câu hỏi nếu chưa rõ
B. SẮP XẾP BẰNG CÁCH TRÁO ĐỔI
Đời sống thường ngày và trong xã hội luôn bảo đảm tính trật tự theo các tiêu chí :
- Buổi sáng : Vệ sinh cá nhân, ăn sáng, đến trường
- Danh sách lớp : Sắp xếp theo thứ tự abc..., thứ tự giảm dần của ĐTB
Mục đích của sắp xếp :
Tìm kiếm, truy xuất đối tượng một cách dễ dàng
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
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 ta đổi chỗ chúng cho nhau. (Các số lớn sẽ được đẩy dần về vị trí xác định cuối dãy)
Việc này lặp lại nhiều lượt, mỗi lượt tiến hành nhiều lần so sánh cho đến khi không có sự đổi chỗ nào xảy ra nữa.
3. Xây dựng thuật toán 
* Gọi tên & giải thích ý nghĩa các đại lượng (biến)
Nhập N, các số hạng a1, a2,,an
Đầu tiên gọi M là số số hạng cần 
so sánh, vậy M sẽ chứa giá trị 
của N : M ¬ N
Nếu số số hạng cần so sánh < 2 
thì dãy đã được sắp xếp. 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
Gọi i là số thứ tự của mỗi lần so sánh, 
đầu tiên i ¬ 0.
Để thực hiện lần so sánh mới, 
i 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 cần so sánh mới 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
a) Đối chiếu, hình thành các bước liệt kê
B.1 : Nhập N, 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, rồi 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;
b) Sơ đồ
Hoạt động 9 : Bài toán tìm kiếm. 
1. Mục tiêu : Nắm vững 1 số thuật toán tìm kiếm và quan hệ không thể tách rời của sắp xếp – tìm kiếm. Sự linh động của các thuật toán để tăng tính hiệu quả.
2. Cách tiến hành :
* GV củng cố bài cũ và dẫn nhập bài mới bằng cách nêu lên tầm quan trọng của thuật toán tìm kiếm, mối quan hệ, sự gắn bó của thuật toán sắp xếp và tìm kiếm. Nêu câu hỏi “Giữa vô số các trang Web trên mạng Internet làm sao các cỗ máy tìm kiếm như Google tìm chính xác và nhanh vậy?”
* Thuật toán này tương đối đơn giản, tự nhiên nên GV có thể xây dựng thuật toán trước và trình bày mô phỏng sau. 
* Trình bày các slide minh họa 
* Nêu 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 ?” 
* GV xác định bài toán mới
* GV nói rõ về mặt nguyên tắc có thể so sánh k với bất kỳ ai nào trên dãy nhưng để dễ quản ly chỉ số i, ta nên chọn điểm giữa phạm vi tìm kiếm (có thể cho ví dụ khi N lẻ, chẵn). Nhấn mạnh 
Khi thay đổi phạm vi tìm kiếm thì chỉ phải thu hẹp 1 đầu mà thôi :
- Khi agiữa > k Þ thu hẹp phía trái Þ ađầu thay đổi
- Khi agiữa < k Þ thu hẹp phía phải Þ acuối thay đổi
Phạm vi tìm kiếm rỗng 
Û ađầu > acuối
* Mô phỏng thuật toán
* GV gợi ý từng bước bằng các câu hỏi
* Mời nhóm đại diện lên bảng chuyển các bước liệt kê à sơ đồ (GV hướng dẫn, gợi ý)
* GV kết luận bằng cách chiếu slide sơ đồ thuật toán.
* HS tham gia phát biểu để thấy rõ quan hệ giữa thuật toán sắp xếp và tìm kiếm
* Quan sát, theo dõi
* Thảo luận nhóm, trình bày ‏‎ kiến
* Theo dõi các ví dụ của GV để nắm rõ ý tưởng thuật toán
* Chú ý quan sát slide mô phỏng
* Các nhóm tham gia liệt kê các bước
C. BÀI TOÁN 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 lớp học
- Tìm một quyển sách trên kệ sách
- Tìm một trang Web trang mạng Internet
C1. TÌM KIẾM TUẦN TỰ 
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.
3. Xây dựng 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à 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;
b) Sơ đồ
C2. TÌM KIẾM NHỊ PHÂN (trên dãy tă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.
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.
3. Xây dựng 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à 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.
b) Sơ đồ
V. TỔNG KẾT ĐÁ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 khái niệm chính : Bài toán, Input, OutPut, Thuật toán, Sơ đồ khối, mối quan hệ giữa Bài toán – Thuật toán – Ngôn ngữ Lập trình.
Dặn HS xem lại các ví dụ trong sách GK.
Giao bài tập về nhà trang 27-28, bổ sung, hoàn chỉnh Phiếu học tập.
Hướng dẫn học sinh tìm kiếm thông tin liên quan trên Internet, giới thiệu vài tựa sách HS có thể tham khảo
Nhận xét tiết học
Yêu cầu các em xem trước bài “Ngôn ngữ lập trình”