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

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
2


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:

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?
4


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
5


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 k 0 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



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


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

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?
9

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?
10


Ví dụ:
XAU.INP
XAU.OUT
ABCBA
1
ABCDEDCAB

begin
trace[v]:=u;
thamdfs(v);
End;
End;
Begin
Input → Đồ thị G, đỉnh xuất phát s, đỉnh đích t;
For v ∈ V do Avail[v] :=true;
Dfstham(s)
11


if avail[t] then
truy theo vết từ t để tìm đường đi từ s tới t
End.
Kết quả của thuật toán tìm kiếm theo chiều sâu
Một cách tự nhiên, kết quả của giải thuật tìm kiếm theo chiều sâu là một cây phủ
qua tất cả các đỉnh được duyệt của đồ thị.
Duyệt các đỉnh
Có thể dùng giải thuật này để tạo một danh sách tuần tự các đỉnh của một đồ
thị (hoặc cây). Có ba cách hiện thực phương pháp này:
•
Duyệt tiền thứ tự (preordering): tạo ra một danh sách mà trong đó các
đỉnh xuất hiện theo đúng trật tự nó được thăm đến khi chạy thuật toán. Đây
chính là biểu diễn tự nhiên của quá trình thực hiện giải thuật tìm kiếm theo
chiều sâu. Một biểu thức ở dạng tiền thứ tự được gọi là kí pháp tiền tố.
•
Duyệt hậu thứ tự (postordering): tạo ra một danh sách mà trong đó các
đỉnh xuất hiện theo thứ tự của lần duyệt đến sau cùngkhi thực hiện giải thuật.
Một lần duyệt hậu thứ tự một cây biểu thức sẽ cho ra một kí pháp hậu tố.


2

V

…

…

Thăm trước tất cả các đỉnh v

Thăm trước tất cả các đỉnh u

2

Tư tưởng của thuật toán tìm kiếm theo chiều rộng BFS là “lập lịch” tất cả các
đỉnh. Việc thăm một đỉnh sẽ lên lịch duyệt các đỉnh nối từ nó sao cho thứ tự duyệt
là ưu tiên chiều rộng (tức là đỉnh nào gần đỉnh xuất phát s hơn sẽ được duyệt
trước). Đầu tiên ta thăm đỉnh s. Việc thăm đỉnh s sẽ phát sinh thứ tự thăm những
đỉnh u1, u2, …nối từ s ( những đỉnh gần s nhất). Tiếp theo ta thăm đỉnh u 1, khi thăm
u1 sẽ lại phát sinh yêu cầu thăm các đỉnh v 1,v2,…nối từ u1. Nhưng rõ ràng các đỉnh v
này xa s hơn những đỉnh u nên chúng chỉ được thăm khi tất cả những đỉnh u đã
thăm. Tức thứ tự duyệt sẽ là: s, u1, u2, ...,v1, v2,...
Thuật toán tìm kiếm theo chiều rộng chỉ sử dụng một danh sách để chứa những
đỉnh đang chờ thăm. Tại mỗi bước, ta thăm một đỉnh đầu danh sách, loại nó ra khỏi
danh sách và cho những đỉnh chưa xếp hàng kế với nó xếp hàng thêm vào cuối
danh sách. Thuật toán sẽ kết thúc khi danh sách rỗng.
Vì nguyên tắc vào trước ra trước, danh sách chứa những đỉnh đang chờ thăm
được tổ chức dưới dạng hàng đợi (Queue): Nếu ta có Queue là một hàng đợi với
thủ tục PUSH(v) để đẩy một đỉnh v vào hàng đợi và hàm POP trả về một đỉnh lấy

Các thành phố xem như là các đỉnh của một đồ thị vô hướng gồm N đỉnh
được mã số từ 1 đến N (1 ≤ i ≤ 100). Chỉ một số cặp thành phố mới có đường bay
còn lại thì không. Giả sử đỉnh xuất phát không trùng đỉnh đích.
Dữ liệu vào: được cho trong tệp GAPNHAU.INP gồm có các dòng:
- Dòng đầu tiên, được gọi là dòng 0, chứa 4 số tự nhiên N, H, T, D(1≤ H,T,D≤ N),
trong đó N là số thành phố có sân bay, H là nơi Hoà đang sinh sống và công tác còn
T là thành phố mà Thân sống và làm việc, D là mã số của thành phố Hồ Chí Minh
nơi mà Hoà và Thân hẹn gặp. (các số cách nhau ít nhất 1 khoảng cách)
- Dòng thứ i (1 ≤ i ≤ N - 1), trong N-1 dòng tiếp theo cho biết có hay không đường
bay nối thành phố i với thành phố j (j=N-j+1) bằng các số 0, 1 (số 0 nghĩa là không
có đường bay giữa hai đỉnh i , j; số 1 nghĩa là tồn tại đường bay giữa hai đỉnh i , j)
các số cách nhau ít nhất 1 khoảng cách.

14


Ví dụ:

GAPNHAU.INP
9627
10111000
1100000
000100
01100
0000
000
00
1

GAPNHAU.OUT

liệt kê các đỉnh j>i tạo thành đường đi (i,j).
Dữ liệu ra: được ghi trong tệp văn bản GAPNHAU.OUT:
- Dòng đầu tiên ghi số tự nhiên k, l là số đỉnh trên đường đi từ H đến D và số đỉnh
trên đường từ T tới D (nếu không có đường đi thì ghi số 0).
- Dòng thứ 2 ghi lần lượt các đỉnh có trên đường đi từ H đến D. (Nếu không có
thì ghi 0)
- Dòng thứ 3 ghi lần lượt các đỉnh có trên đường đi từ T đến D. (Nếu không có thì
ghi 0)
* Cài đặt thuật toán:
Xuất phát từ đỉnh v[1] = s, mỗi bước lặp i ta thực hiện các kiểm tra sau. Gọi
k là số đỉnh đã đi qua và được tích luỹ trong mảng giải trình đường đi v, cụ thể là
xuất phát từ đỉnh v[1] = s, sau một số lần duyệt ta quyết định chọn đường đi qua
các đỉnh v[1], v[2], v[3],…, v[k]. Có thể gặp các tình huống sau:
a) (Đến đích?) nếu v[k] = t tức là đã đến được đỉnh t: thông báo kết quả,
dừng thuật toán, ngược lại thực hiện b.
b) (Thất bại?) k = 0: nếu đã quay trở lại vị trí xuất phát v[i] = s mà từ đó
không còn đường đi nào khác thì phải lùi một bước nữa, do đó k = 0. Trường hợp
15


này chứng tỏ bài toán vô nghiệm, tức là, do đồ thị không liên thông nên không có
đường đi từ đỉnh s đến đỉnh t. Ta thông báo vô nghiệm và dừng thuật toán.
c) (Đi tiếp?) nếu từ đỉnh v[k] tìm được một cạnh chưa đi qua và dẫn đến một
đỉnh i nào đó thì tiến theo đường đó, nếu không: thực hiện bước d.
d) (Lùi một bước) Bỏ đỉnh v[k], lùi lại đỉnh v[k-1].
Nhận xét: Thuật toán trên có tên là sợi chỉ Arian được phỏng theo một
truyền thuyết cổ Hy Lạp sau đây. Anh hùng Te-dây phải tìm diệt con quái vật nhân
ngưu (đầu người, mình trâu) Minotav ẩn náu trong một phòng của mê cung có
nhiều ngõ ngách rắc rối đã từng làm lạc bước nhiều dũng sĩ và những người này
đều trở thành nạn nhân của Minotav. Người yêu của chàng Te-dây là công chúa của



(Thuat toan Arian)
s: dinh xuat phat
t: dinh ket.
------------------------------------------*)
procedure MC;
var i: byte;
begin
Doc; {doc du lieu}
{---------------------------khoi tao mang d,
danh dau cac dinh da tham:
d[i] = 1: dinh da tham
d[i] = 0: dinh chua tham
-----------------------------}
fillchar(d,sizeof(d),0);
k := 1; {k – dem so dinh da chon }
v[k] := s; {dinh xuat phat }
d[s] := 1; {da tham dinh s }
repeat
if v[k] = t then {den dich }
begin
ket(k); {ghi ket qua: giai trinh duong di }
exit;
end;
if k < 1 then {vo nghiem }
begin
ket(0);
exit;
end;

Ứng dụng của thuật toán tìm kiếm theo chiều rộng
Thuật toán tìm kiếm theo chiều rộng được dùng để giải nhiều bài toán trong lý
thuyết đồ thị, chẳng hạn như:
• Tìm tất cả các đỉnh trong một thành phần liên thông
• Thuật toán Cheney cho việc dọn rác
• Tìm đường đi ngắn nhất giữa hai đỉnh u và v (với chiều dài đường đi tính
bằng số cung)
• Kiểm tra xem một đồ thị có là đồ thị hai phía
• Thuật toán Cuthill–McKee
• Thuật toán Ford–Fulkerson để tìm luồng cực đại trong mạng
Tìm các thành phần liên thông
Tập hợp các đỉnh được thăm bởi thuật toán tìm kiếm theo chiều rộng chính là
thành phần liên thông chứa đỉnh gốc.
Kiểm tra đồ thị hai phía
Có thể dùng thuật toán tìm kiếm theo chiều rộng để kiểm tra xem một đồ thị có
phải đồ thị hai phía hay không, bằng cách tìm kiếm từ một đỉnh bất kì và gán nhãn
chẵn lẻ cho các đỉnh được thăm. Nghĩa là, gán nhãn 0 cho đỉnh gốc, 1 cho tất cả các
đỉnh kề đỉnh gốc, 0 cho tất cả các đỉnh kề với một đỉnh kề đỉnh gốc, và tiếp tục như
vậy. Nếu ở một bước nào đó, có hai đỉnh kề nhau có cùng nhãn, thì đồ thị không là
hai phía. Nếu quá trình tìm kiếm kết thúc mà điều này không xảy ra thì đồ thị là hai
phía.
2.4. HIỆU QUẢ CỦA SÁNG KIẾN KINH NGHIỆM ĐỐI VỚI HOẠT ĐỘNG
GIÁO DỤC
Trong khi tiến hành thực hiện sáng kiến kinh nghiệm tôi đã suy nghĩ ngoài
việc tìm tòi những thuật toán tối ưu cho việc giải quyết bài toàn thì tôi còn phải tìm
những phương pháp tạo cảm hứng cho học sinh. Từ đó khi vận dụng vào ôn luyện
đội tuyển các em khá hứng thú và tiếp thu bài giảng cũng tốt hơn.

18


23.2
3
7.1
201211T3
43
18
41.8
15
34.8
7
16.4
3
7.0
2013
Tổng
86
32
37.2
31
36
17
19.8
6
7
11A1
41
17
40.5
17
41.5

41.5
8
19.6
1
2.4
201511A2
41
27
65.8
13
31.7
1
2.4
0
0.0
2016
Tổng
82
42
51.2
30
36.6
9
11
1
1.2
Số liệu từ bảng trên là kết quả thực nghiệm của 3 năm học 2012-2013, 20132014, 2015-2016 đem so sánh với kết quả các năm trước đó chưa áp dụng thực
nghiệm theo cách này thì thấy:
+ Các em học tốt hơn trông thấy: cụ thể là tích cực tìm tòi hơn, hợp tác tốt hơn, chủ
động tìm hiểu các nội dung hơn.

năm kinh nghiệm ôn luyện học sinh giỏi ở các trường, viết ra một cuốn cẩm nang
về kinh nghiệm và các bài tập tham khảo để cho các giáo viên trẻ học hỏi.
Quá trình thực hiện đề tài do nhiều yếu tố chủ quan và khách quan nên không
thể tránh khỏi thiếu sót mong bạn bè đồng nghiệp đóng góp ý kiến để đề tài được
tốt hơn và có nhiều ứng dụng trong dạy học bồi dưỡng học sinh giỏi lớp 11 và hơn
thể nữa là có thể ứng dụng rộng rãi ở các trường THPT. Xin chân thành cảm ơn các
bạn bè đồng nghiệp và các em học sinh đã giúp đỡ và tạo động lực cho tôi hoàn
thành sang kiến này!
XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ

Sầm Sơm, ngày 20 tháng 03 năm 2017
Tôi cam đoan sáng kiến kinh nghiệm
của tôi là do tôi viết ra, không sao chép của
người khác. Nếu sai tôi xin chịu mọi trách
nhiệm.
Người viết SKKN
Nguyễn Hữu Dũng

20


TÀI LIỆU THAM KHẢO
1. Lê Văn Doanh, Trần Khắc Tuấn- 101 Thuật toán và chương trình-NXB Khoa
Học Kỹ Thuật.
2. Quách Tuấn Ngọc - Bài tập ngôn ngữ lập trình Pascal-NXB Thống Kê.
3. PGS.PTS Bùi Thế Tâm - Bài tập lập trình Turbo Pascal 7.0-NXB Giao Thông
Vận Tải.
4. Hồ Sĩ Đàm-Tin học 10,11 - NXB Giáo Dục.
5. Ths Trần Đức Huyên - Phương pháp giải các bài toán trong tin học - NXB
Giáo dục

G i a o vien G
hoa
i
xa
a
hoi
o
vien
Bài 2: (5,5 điểm)
Số lõm
Cho mảng A kích thước MxN (M,N ≤ 100; -2000 ≤ Aij ≤ 2000). Phần tử Aij được
gọi là phần tử lõm nếu nó là phần tử nhỏ nhất trong hàng của nó đồng thời là phần
tử nhỏ nhất trong cột của nó.
Hãy lập chương trình tìm phần tử lõm sâu nhất của mảng A? (Phần tử lõm sâu
nhất là phần tử có giá trị nhỏ nhất trong các phần tử lõm)
Dữ liệu vào từ tệp solom.inp gồm M dòng, mỗi dòng có N giá trị Aij, các giá trị
các nhau 1 ký tự trắng
Dữ liệu ra tệp solom.out, một dòng ghi 2 giá trị là số dòng, số cột của phần tử lõm
sâu nhất, các giá trị cách nhau 1 ký tự trắng. Nếu không tìm được thì ghi -1
Ví dụ
Solom.inp
Solom.out
15 5 9
33
55 4 6
76 7 2
22


Bài 3: (3,5 điểm)

nguyên tố.
Yêu cầu: Cho số n chẵn lớn hơn 2, hãy xác định số lượng các cặp số nguyên tố có
tổng bằng số n.
Kết quả : Đưa ra tệp văn bản GONBAC.OUT chứa duy nhất một số theo yêu cầu
của bài.
Ví dụ :
GONBAC.INP
GONBAC.OUT
16

2

Bài 2: (4 điểm) Mua hàng
Có n người xếp thành hàng theo thứ tự để mua hàng. Thòi gian người bán hàng
phục vụ cho người thứ i là ti đơn vị thời gian. Hãy tìm thời gian mà người thứ k
phải chờ để mua hàng.
Dữ liệu: Vào từ tệp văn bản MH.INP
- Dòng 1: chứa 2 số n, j nguyên dương (1≤k≤n≤100);
23


- Dòng 2: chứa n số t1, t2,...tn ( Các giá trị ti đều nguyên dương va nhỏ hơn 1000).
Kết qủa : Đưa ra tệp văn bản MH.OUT chứa duy nhất số C thở mãn yêu cầu của
dữ liệu vào.
Ví dụ:
MH.INP
MH.OUT
53
13241


quả là các số siêu nguyên tố có N chữ số cùng số lượng của chúng.
Bài 3(9 điểm) -Tô màu
Cho một bảng gồm các ô vuông kích thước M x N (M, N ≤ 100), trong đó có một
số ô đen, còn lại là các ô trắng.

24


Yêu cầu: Hãy tô màu tất cả các ô trắng bằng hai màu xanh và vàng sao cho trên
mỗi dòng cũng như trên mỗi cột số các ô màu xanh và vàng lệch nhau không quá 1.
Dữ liệu vào: Được cho trong file văn bản BAI3.INP
- Dòng đầu ghi hai số M, N
- M dòng tiếp theo mỗi dòng ghi N số, gồm các số 0 hoặc 1 biểu diễn bảng ô
vuông, với 0 biểu thị ô trắng, 1 biểu thị ô đen.
Kết quả: Ghi ra file văn bản BAI3.OUT gồm M dòng, mỗi dòng gồm N ký tự viết
liền nhau biểu diễn trạng thái màu đã tô của bảng với D: màu đen, X: màu xanh, V:
màu vàng.
Ví dụ:
BAI3.INP
BAI3.OUT
64
DVDX
1010
DXXV
1000
XDVD
0101
DDVX
1100
VDXD