SKKN Phương pháp ứng dụng thuật toán tìm kiếm vào dạy lập trình tin học trong công tác bồi dưỡng học sinh giỏi

MỤC LỤC
I. MỞ ĐẦU	1
1.1. LÍ DO CHỌN ĐỀ TÀI 	1
1.2. Mục đích nghiên cứu 	1
1.3. Đối tượng nghiên cứu	2
1.4. Phương pháp nghiên cứu	2
II. NỘI DUNG	3
2.1. CƠ SỞ LÍ LUẬN	3
2.2. THỰC TRẠNG VẤN ĐỀ TRƯỚC KHI ÁP DỤNG SKKN	4
2.3. CÁC THUẬT TOÁN TÌM KIẾM NỘI	5
2.3.1. Tìm kiếm tuần tự	5
2.3.2. Tìm kiếm nhị phân	7
2.4. TÌM KIẾM THEO CHIỀU SÂU 	10
2.4.1 Ý tưởng	10
2.4.2. Thủ tục đệ quy THAMDFS	10
2.5. TÌM KIẾM THEO CHIỀU RỘNG	12
2.5.1. Ý tưởng:	12
2.5.2. Giải thuật	13
2.6. HIỆU QUẢ CỦA SKKN ĐỐI VỚI HOẠT ĐỘNG GIÁO DỤC	17
III.KẾT LUẬN VÀ KIẾN NGHỊ	19
 3.1. KẾT LUẬN	19
 3.2. KIẾN NGHỊ	19I. MỞ ĐẦU
1.1. LÍ DO CHỌN ĐỀ TÀI 
Với sự phát triển mạnh mẽ của ngành tin học và truyền thông đã tạo nên một xã hội học tập, mọi người đều có quyền bình đẳng được học, được nghiên cứu. Trước sự đổi mới của sự nghiệp giáo dục và đào tạo nên xã hội yêu cầu nhà trường không ngừng phải nâng cao chất lượng giáo dục toàn diện cho học sinh. Bằng cách cung cấp cho học sinh đầy đủ kiến thức để theo kịp thời đại. Do vậy tin học đã được đưa đồng bộ vào nhà trường phổ thông từ năm 2006 với tư cách là một môn học chính thống. Vấn đề đặt ra là nhà trường và ngành giáo dục cần phải tìm biện pháp để nâng cao chất lượng truyền thụ kiến thức và rèn luyện kỹ năng cho người học.
Ở khối 11 THPT, môn tin học với tư tưởng là sử dụng ngôn ngữ Pascal để rèn luyện kỹ năng lập trình cho học sinh, nhưng để thực hiện được việc hình thành và rèn luyện kỹ năng học lập trình cho học sinh thì còn gặp rất nhiều khó khăn vì yêu cầu học sinh phải có kiến thức liên môn của môn Toán và tiếng Anh và thuật toán hay là cấu trúc dữ liệu và giải thuật. 
Hiện nay năm 2017 tức là đã 12 năm đưa môn tin học vào dạy ở THPT nhưng thực trạng việc dạy học lập trình ở các trường phổ thông còn tồn tại nhiều phương pháp khác nhau, hình thức truyền dạy không đồng bộ nên kết quả thu được trong đào tạo chưa cao. Mặt khác do thiếu tài liệu hướng dẫn dạy học lập trình mang tính hệ thống, thống nhất nên trong khi dạy và học lập trình thì giáo viên và học sinh đang phải chịu những khó khăn, hạn chế nhất định nào đó.
Bản thân một giáo viên sư phạm ngành tin học tôi luôn trăn trở muốn khắc phục những khó khăn trong việc dạy học, hình thành những kỹ năng lập trình cho học sinh. Hơn thế nữa trong suốt thời gian dạy học tại trường THPT Quảng Xương 3 tôi nhận thấy việc tiếp nhận từng đơn vị kiến thức về lập trình của học sinh lớp 11 thực sự gặp khó khăn do đó đã nhen nhóm trong tôi ý tưởng có một đề tài nghiên cứu để khắc phục các vấn đề trên. Chính vì những lẽ đó mà xin chon đề tài: “Phương pháp ứng dụng thuật toán tìm kiếm vào dạy lập trình tin học trong công tác bồi dưỡng học sinh giỏi” làm đề tài viết sáng kiến kinh nghiệm. Đây là một vấn đề nhỏ trong vô số vấn đề có thể xây dựng để khai thác làm tăng hiệu quả cho quá trình dạy bồi dưỡng học sinh giỏi môn tin học lớp 11.
1.2. MỤC ĐÍCH NGHIÊN CỨU 
nâng cao chất lượng tiếp thu và lĩnh hội kiến thức về tư duy thuật toán, lập trình các giải thuật tìm kiếm giúp học sinh hiểu bài toán và phương pháp giải quyết vấn đề một cách nhanh nhất.
bản thân tôi và các đồng nghiệp khác trong tổ bộ môn tin học luôn luôn trao đổi phương pháp làm sao để dạy cho học sinh có kiến thức tốt về môn lập trình, học tốt tư duy thuật toán và cũng để các em tư duy tốt khi học các môn học khác.
với đề tài này tôi không có tham muốn gì hơn ngoài mục đích: đổi mới nội dung, phương pháp, hình thức tổ chức giáo dục nhằm tìm ra biện pháp nâng cao chất lượng, hiệu quả giảng dạy và giáo dục học sinh, bồi dưỡng đội ngũ học sinh có học tháo gỡ những khó khăn vướng mắc trên, đồng thời cũng đóng góp phần nhỏ trong việc cải cách, nâng cao chất lượng giáo dục nói chung và dạy học bộ môn tin học nói riêng.
1.3. đối tượng nghiên cứu
qua quá trình dạy học môn tin học ở thpt và cụ thể là dạy học sinh rèn luyện với kiến thức lập trình ở lớp 11, đồng thời nhận trách nhiệm bồi dưỡng học sinh giỏi tỉnh. với thực trạng chất lượng tiếp thu bài của học sinh mà tôi người thầy giáo giảng dạy bộ môn tin, tôi quyết định chọn đề tài nhằm đưa ra phương án cho học sinh học tốt hơn vào các năm học tới và giải quyết 2 vấn đề sau:
- nghiên cứu bài 4: bài toán và thuật toán - sgk tin học 10 sau đó làm sáng tỏ được bản chất của vấn đề nghiên cứu.
- nghiên cứu kiến thức sách giáo khoa tin học 11 (kiến thức liên quan đến việc thi cử học sinh giỏi tỉnh và các cuộc thi khác như: tin học trẻ)
- nghiên cứu học sinh khối 11 trường thpt quảng xương 3 làm sao gây hứng thú cho học sinh khi học dạng toán lập trình có giải thuật tìm kiếm như thế này.
1.4. phương pháp nghiên cứu
mọi vấn đề, mọi đề tài nghiên cứu thì khâu chuẩn bị và xác định mục đích nghiên cứu bao giờ cũng đóng một vai trò hết sức quan trọng. ở trong đề tài này điều quan trọng của khâu chuẩn bị là việc chọn phương pháp để kết quả của đề tài đi đến đích thì cần phải xác định được một phương pháp hiệu quả không lãng phí thời gian cũng như công sức. như kinh nghiệm cho thấy đề tài có thành công hay không còn phụ thuộc vào phương pháp tiến hành vì lẽ trên trong đề tài nghiên cứu này tôi đã sử dụng một số phương pháp sau:
phương pháp nghiên cứu lí thuyết: tài liệu về lí luận dạy học, những vấn đề chung về đổi mới phương pháp giáo dục trung học phổ thông, chương trình sách giáo khoa 11, một số tài liệu chuyên tin học
phương pháp nghiên cứu thực tiễn: thực tiễn dạy tin học từ năm 2006 đến nay, thực tiễn về công tác bồi dưỡng học sinh giỏi.
phương pháp điều tra sư phạm: trao đổi với các thầy cô, đồng nghiệp và học sinh ở trường, nhất là giáo viên bộ môn tin học, sau đó xử lí thông tin và rút ra kết luận khoa học.
phương pháp kiểm tra đánh giá học sinh thực nghiệm sư phạm: soạn giảng thành chương trình bài giảng, bộ đề kiểm tra, dạy thể nghiệm và rút kết luận khoa học, mang tính phổ biến.
phương pháp tổng hợp và đánh giá kết quả: tổng hợp cụ thể, chi tiết, kiểm chứng rút ra biện pháp đúng, loại trừ biện pháp không hợp lí. 
trên đây là một số phương pháp cơ bản mà tôi đã vận dụng trong nghiên cứu và hoàn thiện đề tài.
II. NỘI DUNG
2.1. CƠ SỞ LÍ LUẬN
Hàng năm Sở giáo dục và đào tạo tỉnh Thanh Hóa luôn tổ chức kỳ thi chọn học sinh giỏi tỉnh môn Tin học. Kết quả học sinh giỏi cũng là một tiêu chi thi đua đánh giá chất lượng trường học, đánh giá năng lực sư phạm của giáo viên. Như vậy ta nhận thấy việc bội dưỡng học sinh giỏi là nhiệm vụ quan trọng trong công tác chuyên môn của mỗi bộ môn, giáo viên luôn cố gắng để truyền tải kiến thức để học sinh được bồi dưỡng có kết quả cao trong các kỳ thi. Và đối với bộ môn tin học cũng vậy, trong công tác Bồi dưỡng học sinh giỏi tin học, các đề thi thường xuất hiện các bài toán có độ phức tạp lớn, các bài toán liên quan đến xử lí các tình huống thực tế trong đó thường có các bài toán trong đề thi có tình huống như: Bài toán tìm kiếm và sắp xếp dữ liệu trong một hệ thống thông tin, xử lí các vấn đề về bộ số, mảng, xâu...
Ta cũng thấy rằng: Bài toán tìm kiếm cũng thông dụng như bài toán sắp xếp. Bài toán tìm kiếm thường là “bạn” đồng hành với bài toán sắp xếp. Sắp xếp để tìm kiếm thuận lợi và ngược lại tìm kiếm tạo điều kiện cho sắp xếp. Vậy nội dung bài toán tìm kiếm là gì?
- Trong hầu hết các hệ lưu trữ, quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhất để khai thác thông tin:
Ví du: Tra cứu từ điển, tìm sách trong thư viện...
Do các hệ thống thông tin thường phải lưu trữ một khối lượng dữ liệu đáng kể, nên việc xây dựng các giải thuật cho phép tìm kiếm nhanh sẽ có ý nghĩa rất lớn. Nếu dữ liệu trong hệ thống đã được tổ chức theo một trật tự nào đó, thì việc tìm kiếm sẽ tiến hành nhanh chóng và hiệu quả hơn:
Ví dụ: các từ trong từ điển được sắp xếp theo từng vần, trong mỗi vần lại được sắp xếp theo trình tự  alphabet; sách trong thư viện được xếp theo chủ đề ...
Ví dụ: Tìm số lớn nhất trong một tập các số nguyên, tìm số hoàn hảo,
Vì thế, khi xây dựng một hệ quản lý thông tin trên máy tính, bên cạnh các thuật toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong những chủ đề được quan tâm hàng đầu.
Có thể phân chia nội dung tìm kiếm theo các loại sau:
+ Tìm một phần tử trong một tập các đối tượng
Ví dụ 1: Tìm giá trị lớn nhất của một dãy số nguyên (VD-trang 33-sgk tin 10)
Ví dụ 2: Tìm các số nguyên tố trong các số nguyên không vượt quá số nguyên dương N cho trước.
Ví dụ 3: Tìm những học sinh có học lực Khá trong lớp học 12A1.
Tuy nhiên bài toán tìm kiếm một phần tử trong một tập các đối tượng vẫn là bài toán cơ bản nhất. Ngoài ra bài toán tìm kiếm cũng thường gắn liền với bài toán đếm và liệt kê ví dụ: đếm số lượng các phần tử thõa mãn một điều kiện cho trước hoặc có bao nhiêu số nguyên tố không vượt quá 100?
Ví dụ 4: Cho dãy N số nguyên và số nguyên x. Cho biết chỉ số những phần tử có giá trị bằng x. Có bao nhiêu phần tử như vậy?
INPUT: file văn bản DAYSO.INP
dòng đầu là N và x
N dòng sau, lần lượt ghi các số nguyên thuộc dãy từ vị trí 1 đến vị trí N, mỗi số trên một dòng
OUTPUT: File DAYSO.OUT
Dòng đầu là số lượng các phần tử của dãy bằng x;
Nếu dòng đầu là dương thì dòng tiếp theo ghi chỉ số của những phần tử bằng x
Và nhiều bài toán, dạng toán tìm kiếm khác nữa.
Và ta cũng biết, hiện nay đã có nhiều giải thuật tìm kiếm và sắp xếp được xây dựng, mức độ hiệu quả của từng giải thuật còn phụ thuộc vào tính chất của cấu trúc dữ liệu cụ thể mà nó tác động đến. Dữ liệu được lưu trữ chủ yếu trong bộ nhớ chính và trên bộ nhớ phụ, do đặc điểm khác nhau của thiết bị lưu trữ, các thuật toán tìm kiếm và sắp xếp được xây dựng cho các cấu trúc lưu trữ trên bộ nhớ chính hoặc phụ cũng có những đặc thù khác nhau. Tôi thấy đây là một vấn đề mới để giúp học sinh nắm phương pháp giải các bài toán phức tạp. Vì vậy tôi chọn các thuật toán đặc trưng là thuật toán tìm kiếm nội, thuật toán tìm kiếm chiều rộng, thuật toán tìm kiếm chiều sâu để trình bày nội dung sau đây để dạy cho học sinh khi học lập trình tin học.
2.2. THỰC TRẠNG VẤN ĐỀ TRƯỚC KHI ÁP DỤNG SKKN
	Trong quá trình ôn luyện đội tuyển học sinh giỏi, nhiều giáo viên đặc biệt là những giáo viên trẻ, non kinh nghiệm gặp những bài toán tìm kiếm còn lúng túng, chưa tìm ra phương pháp để truyền đạt những ý tưởng để giải bài toán. Bên cạnh đó những học sinh lần đầu gặp những bải toán tìm kiếm cũng khá bỡ ngỡ, không biết áp dụng thuật toán nào để làm, từ đó làm theo kiểu mày mò, thử nghiệm dẫn đến tốn rất nhiều thời gian mà đôi khi không mang lại kết quả như mong đợi.
	Trong mỗi đề thi bao giờ cũng có yêu cầu về thời gian xử lý dữ liệu. Vì vậy việc áp dụng những thuật toán vừa mang lại kết quả chính xác, lại vừa có thời gian xử lý nhanh thì đó là thuật toán tối ưu. Để có được các thuật toán như vậy đòi hỏi người giáo viên phải có lượng kiến thức tốt, kết hợp với khả năng sư phạm thì sẽ truyền đạt lại cho học sinh hiểu và vận dụng vào các bài tập cụ thể.
Thuận lợi:
	Nhà trường có hệ thống cơ sở vật chất khá đầy đủ cho việc dạy tin học, được sự quan tâm giúp đỡ của đồng nghiệp, học sinh nhiệt tình và ham học hỏi.
	Việc tiếp cận tài liệu cho nghiên cứu cũng tương đối thuận lợi. Bản thân cũng đã nhiều năm ôn luyện đội tuyển nên cũng có đôi chút kinh nghiệm.
Khó khăn:
	Việc chọn học sinh cho đội tuyển Tin học gặp nhiều khó khăn vì những học sinh khá, giỏi thì các môn Toán, Lý, Hóa chọn trước. Bên cạnh đó phụ huynh học sinh cũng không muốn con mình vào đội tuyển Tin học, để dành thời gian cho việc học các môn phục vụ thi đại học.
2.3. CÁC THUẬT TOÁN TÌM KIẾM NỘI
Ðể đơn giản trong việc trình bày giải thuật, bài toán được đặc tả như sau:
Bài toán tổng quát: Cần tìm kiếm một phần tử trong tập N đối tượng cho trước, chúng ta lưu dữ liệu phản ánh các đối tượng này vào mảng một chiều A[1..N], mỗi phần tử của mảng là một bản ghi gồm các trường lưu giá trị các đặc tính của một đối tượng. Trong các trường này giả sử chọn trường k làm khóa so sánh giữa các phần tử. Bài toán đặt ra là tìm một phần tử có giá trị khóa k0 trong tập N đối tượng này. Có 2 giải thuật thường được áp dụng để tìm kiếm dữ liệu là tìm tuần tự và tìm nhị phân. 
2.3.1. Tìm kiếm tuần tự
Bắt đầu từ bản ghi đầu tiên chuyển dần về phía cuối mảng, lần lượt so sánh giá trị khóa của bản ghi này với k0 , nếu giá trị của bản ghi nào bằng k0 thì hiện bản ghi đó ( hoặc lưu trữ lại chỉ số của bản ghi đó; đồng thời tăng biến đếm số lượng phần tử có giá trị bằng khóa k0). Nếu duyệt hết mọi  bản ghi mà biến đếm có giá trị bằng 0 thì kết luận trong tập đối tượng đã cho không có phần tử nào có giá trị bằng khóa k0. 
Cài đặt Giải thuật
Tìm tuần tự là một kỹ thuật tìm kiếm rất đơn giản và cổ điển. 
Các bước tiến hành như sau :
Procedure Timkiem;
Var i: integer;
Begin
 For i:=1 to n do
 If a[i].k= k0 then
 Begin 
 Inc(soluong);
	 Luu(soluong):=i;
 End;
End;
* Trong chương trình con trên, biến soluong và luu[1..N] là biến toàn cục, phục vụ đưa ra kết luận sau khi tìm kiếm 
 Ví dụ
Cho dãy số a: 12           2        8          5          1          6          4          15
Nếu giá trị cần tìm là 8, giải thuật được tiến hành như sau :
Hình 2.2
i = 1
Hình 2.3
i = 2
i = 3 -> Dừng.
 Ðánh giá giải thuật
Có thể ước lượng độ phức tạp của giải thuật tìm kiếm qua số lượng các phép so sánh được tiến hành để tìm ra ko. Trường hợp giải thuật tìm tuần tự, có:
Trường hợp
Số lần so sánh
Giải thích
Tốt nhất
1
Phần tử đầu tiên có giá trị k0 
Xấu nhất
n+1
Phần tử cuối cùng có giá trị k0
Trung bình
(n+1)/2
Giả sử xác suất các phần tử trong mảng nhận giá trị k0 là như nhau.
Vậy giải thuật  tìm tuần tự có độ phức tạp tính toán cấp n:  T(n) = O(n)
NHẬN XÉT
 - Giải thuật tìm tuần tự không phụ thuộc vào thứ tự của các phần tử mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy số bất kỳ.
- Một thuật toán có thể được cài đặt theo nhiều cách khác nhau, kỹ thuật cài đặt ảnh hưởng đến tốc độ thực hiện của thuật toán.
2.3.2. Tìm kiếm nhị phân
Phép tìm kiếm nhị phân chỉ được sử dụng sau khi mảng các bản ghi đã được sắp xếp (tăng hoặc giảm) theo khóa k. Giả sử giá trị khóa của bản ghi ở đầu mảng (đã sắp xếp) là k1 và giá trị khóa của bản ghi ở cuối mảng (đã sx) là k2. Phần tử cần tìm kiếm có giá trị khóa là k0.
Ta phân tích cách tìm kiếm nhị phân diễn ra như sau:
Chọn ra một bản ghi ở vị trí trung gian là vị trí vtgiua = (vtdau+vtcuoi) div 2, giả sử giá trị khóa của bản ghi ở vị trí trung gian này là kgiua;
Nếu k0<kgiua thì phần tử cần tìm chỉ có thể trong đoạn từ vtdau đến vtgiua-1. Vì vậy chỉ cần tìm kiếm tiếp trong đoạn [vtdau .. vtgiua-1] bằng đệ quy.
Nếu k0>kgiua thì phần tử cần tìm chỉ có thể trong đoạn từ vtgiua+1 đến vtcuoi. Vì vậy chỉ cần tìm kiếm tiếp trong đoạn [vtgiua+1 .. vtcuoi] bằng đệ quy.
Nếu k0=kgiua thì ghi nhận chỉ số bản ghi hoặc hiện ngay bản ghi này là phần tử cần tìm.
Cài đặt Giải thuật
Procedure TIMKIEM2 (vtdau,vtcuoi:integer);
Var vtgiua:integer;
Begin
 Vtgiua:=(vtdau+vtcuoi) div 2;
If a[vtgiua].k = k0 then
 Begin
 { thông báo tìm kiếm kết quả thành công hoặc hiện số hiệu phần tử tìm được}
End
ELSE
 If (a[vtgiua].k>k0) and (vtdau>vtgiua) then timkiem2(vtdau,vtgiua-1)
 Else
 If (a[vtgiua].k<k0) and (vt0<vtcuoi) then timkiem2(vtgiua+1,vtcuoi);
End;
Ví dụ
Cho dãy số a gồm 8 phần tử: 
 1     2        4          5          6          8          12         15
Nếu giá trị cần tìm là 8, giải thuật được tiến hành như sau:
left = 1, right = 8, midle = 4
left = 5, right = 8, midle = 6
Dừng.
Ðánh giá giải thuật
Trường hợp giải thuật tìm nhị phân, có bảng phân tích sau :
Trường hợp
Số lần so sánh
Giải thích
Tốt nhất
1
Phần tử giữa của mảng có giá trị x
Xấu nhất
log 2 n
Không có x trong mảng
Trung bình
log 2 n/2
Giả sử xác suất các phần tử trong mảng nhận giá trị x là như nhau
Vậy giải thuật  tìm nhị phân có độ phức tạp tính toán cấp n:  T(n) = O(log 2 n)
      NHẬN XÉT
-  Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ  tự.
-  Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm tuần tự do Tnhị phân (n) = O(log 2 n) < Ttuần tự (n) = O(n).Tuy nhiên khi muốn áp dụng giải thuật tìm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số có thứ tự. Thời gian này không nhỏ, và khi dãy số biến động cần phải tiến hành sắp xếp lại . Tất cả các nhu cầu đó tạo ra khuyết điểm chính cho giải thuật tìm nhị phân. Ta cần cân nhắc nhu cầu thực tế để chọn một trong hai giải thuật tìm kiếm trên sao cho có lợi nhất
Ví dụ khi dạy bài 4 – Bài toán thuật toán (tin học 10) ta có thể đưa ra một số bài tập như sau: 
Bài 1: viết thuật toán bằng đồ khối hoặc bằng liệt kê từng bước tìm giá trị lớn nhất trong 2 số nguyên a, b nhập từ bàn phím. sau đó viết chương trình hoàn thiện?
Bài 2: viết thuật toán bằng liệt kê từng bước hoặc bằng đồ khối tìm giá trị lớn nhất trong 3 số nguyên a, b, c nhập từ bàn phím. sau đó viết chương trình hoàn thiện?
Bài 3: viết thuật toán bằng đồ khối hoặc bằng liệt kê từng bước tìm giá trị lớn nhất trong 4 số nguyên a, b, c, d nhập từ bàn phím. sau đó viết chương trình hoàn thiện?
Bài 4: viết thuật toán bằng sơ đồ khối hoặc bằng liệt kê từng bước tìm giá trị lớn nhất của một dãy số nguyên nhập từ bàn phím. sau đó viết chương trình hoàn thiện?
Ví dụ khi dạy bài 11 – Kiểu mảng (tin học 11) giáo viên có thể đưa ra các bài tập sau:
1.   Xét mảng các số nguyên có nội dung như sau :
-9            -9            -5            -2           0           3            7           7           10            15
a. Tính số lần so sánh để tìm ra phần tử  X = -9 bằng phương pháp:
Tìm tuần tự
Tìm nhị phân
Nhận xét và so sánh 2 phương pháp tìm nêu trên trong trường hợp này và trong trường hợp tổng quát.
b. Trong trường hợp tìm nhị phân, phần tử nào sẽ được tìm thấy (thứ 1 hay 2)
2.  Xây dựng thuật toán tìm phần tử nhỏ nhất (lớn nhất) trong một mảng các số nguyên.
3. Hãy viết hàm tìm tất cả các số nguyên tố nằm trong mảng một chiều a có n phần tử.
4.  Hãy viết hàm tìm dãy con tăng dài nhất của mảng một chiều a có n phần tử (dãy con là một dãy liên tiếp các phần của a).
Ví dụ khi dạy bài 16 – lớp 11: Kiểu dữ liệu tệp giáo viên có thể ra các bài tập sau:
Bài 1: Cho dãy N số nguyên và số nguyên x. Bằng phương pháp tìm kiếm tuần tự cho biết chỉ số những phần tử có giá trị bằng x. Có bao nhiêu phần tử như vậy?
INPUT: file văn bản DAYSO.INP
dòng đầu là N và x
N dòng sau, lần lượt ghi các số nguyên thuộc dãy từ vị trí 1 đến vị trí N, mỗi số trên một dòng
OUTPUT: File DAYSO.OUT
Dòng đầu là số lượng các phần tử của dãy bằng x;
Nếu dòng đầu là dương thì dòng tiếp theo ghi chỉ số của những phần tử bằng x
Bài 2: Cho dãy N số nguyên và số nguyên x. Sắp xếp dãy tăng, bằng phương pháp tìm kiếm nhị phân cho biết chỉ số một phần tử có giá trị bằng x. 
INPUT: file văn bản DAYSO.INP
dòng đầu là N và x
N dòng sau, lần lượt ghi các số nguyên thuộc dãy từ vị trí 1 đến vị trí N, mỗi số trên một dòng
OUTPUT: File DAYSO.OUT
Dòng đầu ghi 1 hoặc 0 tương ứng với trường hợp tìm được hoặc không tìm được
Nếu dòng đầu là 1 thì dòng thứ hai ghi chỉ số một phần tử bằng x
Bài 3: Cho file văn bản XAU.INP gồm một số dòng, mỗi dòng ghi một xâu kí tự . Hãy ghi vào file văn bản XAU.OUT một số dòng, mỗi dòng ghi số 1 hoặc số 0 tùy theo xâu ở dòng tương ứng của file XAU.INP là xâu đối gương hay không?
Ví dụ:
XAU.INP
XAU.OUT
ABCBA
1
ABCDEDCAB
0
MADAM
0
A
1
..
2.4. TÌM KIẾM THEO CHIỀU SÂU 
2.4.1 Ý tưởng
Tư tưởng của thuật toán tìm kiếm theo chiều sâu (DFS) có thể trình bày như sau:
Trước hết Đỉnh s được đến từ đỉnh s, tiếp theo, với mọi cung (s,x) của đồ thị thì x cũng sẽ đến được từ s. Với mỗi đỉnh x đó thì tất nhiên những đỉnh y nối từ x cũng đến được từ s
Điều đó gợi cho ta viết một thủ tục đệ quy THAMDFS(u) mô tả việt duyệt từ đỉnh u bằng cách thăm đỉnh u và tiếp tục quá trình duyệt THAMDFS(v) với v là một đỉnh chưa thăm nối từ u. Ta phải sử dụng kỹ thuật đánh dấu để tránh việc liệt kê các cặp đỉnh: khởi tạo Avail[v]:=true, v V, mỗi lần thăm một đỉnh ta đánh dấu đỉnh đó lại, avail[v]:=false, để các bước duyệt đệ quy kế tiếp không