BM 01-Bìa SKKN
SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI
Đơn vị: Trường Thpt Chuyên Lương Thế Vinh
Mã số: ................................
(Do HĐKH Sở GD&ĐT ghi)
SÁNG KIẾN KINH NGHIỆM
PHÂN LOẠI BÀI TẬP THEO CHUYÊN ĐỀ TIN 10
Người thực hiện: NGUYỄN HOÀNG ANH
Lĩnh vực nghiên cứu:
- Quản lý giáo dục
- Phương pháp dạy học bộ môn: ...TIN HỌC........
(Ghi rõ tên bộ môn)
- Lĩnh vực khác: .......................................................
(Ghi rõ tên lĩnh vực)
Có đính kèm: Các sản phẩm không thể hiện trong bản in SKKN
Mô hình Đĩa CD (DVD)
Phim ảnh
Hiện vật khác
(các phim, ảnh, sản phẩm phần mềm)
Năm học: 2014-2015
BM02-LLKHSKKN
SƠ LƯỢC LÝ LỊCH KHOA HỌC
––––––––––––––––––
I. THÔNG TIN CHUNG VỀ CÁ NHÂN
1. Họ và tên: NGUYỄN HOÀNG ANH
2. Ngày tháng năm sinh: 08-09-1987
3. Nam, nữ: NAM
4. Địa chỉ: 10/8, TỔ 1, KP1, PHƯỜNG BỬU LONG, BIÊN HÒA, ĐỒNG NAI
5. Điện thoại:
0945 648 411
6. Fax:
E-mail:
[email protected]
7. Chức vụ: GIÁO VIÊN
8. Nhiệm vụ được giao: GIẢNG DẠY BỘ MÔN TIN HỌC THPT, PHỤ
TRÁCH MỘT SỐ CHUYÊN ĐỀ CHUYÊN TIN 10, CHỦ NHIỆM LỚP 10
TIN
9. Đơn vị công tác: TRƯỜNG THPT CHUYÊN LƯƠNG THẾ VINH
II. TRÌNH ĐỘ ĐÀO TẠO
- Học vị (hoặc trình độ chuyên môn, nghiệp vụ) cao nhất: CỬ NHÂN
- Năm nhận bằng: 2010
- Chuyên ngành đào tạo: SƯ PHẠM TIN HỌC
III. KINH NGHIỆM KHOA HỌC
- Lĩnh vực chuyên môn có kinh nghiệm: TIN HỌC
Số năm có kinh nghiệm: 05
- Các sáng kiến kinh nghiệm đã có trong 5 năm gần đây: 02
o Thuật toán hàm Z
o Thuật toán hàm Z trong ứng dụng xử lý các bài toán về xâu ký tự.
BM03-TMSKKN
Tên SKKN: PHÂN LOẠI BÀI TẬP THEO CHUYÊN ĐỀ TIN 10
I. LÝ DO CHỌN ĐỀ TÀI
-
Nhu cầu có một khung bài tập hiệu quả, định hướng giảng dạy cho lớp
chuyên Tin 10 sao cho có thể đáp ứng được yêu cầu của các kỳ thi tuyển
chọn học sinh giỏi được đặt ra và cần được định hình một cách cụ thể, phù
hợp với từng đối tượng học sinh.
II. CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN
a) Trong chương trình giảng dạy chuyên Tin, hiện đang sử dụng bộ tài liệu giáo
khoa chuyên Tin (gồm 3 quyển) và một số tài liệu chuyên đề. Các tài liệu này được thiết
kế theo dạng chuyên đề lý thuyết và hệ thống bài tập tham khảo, luyện tập được đưa ra
theo nhiều mức độ cho chuyên đề đó bao quát toàn bộ cho 3 khối và nhiều trình độ học
sinh. Song song với hệ thống bài tập đã phân loại còn có nhiều hệ thống bài tập trực
tuyến bao gồm cả phân loại theo chuyên đề cụ thể và không phân loại theo chuyên đề cụ
thể. Khi giảng dạy, giáo viên sẽ dựa vào để chọn lọc ra cho học sinh các bài tập phù hợp.
b) Trong thực tế giảng dạy cho thấy: hệ thống bài tập đã có trong các bộ
SGK có thể giúp các em phát triển khả năng tư duy và rèn luyện theo chuyên đề
tương đối khá đầy đủ. Tuy nhiên, có một số bài khá khó và việc giải các bài này
đòi hỏi học sinh phải được tiếp cận một số kỹ thuật lập trình mà chỉ có sau một
thời gian tích lũy mới có thể làm được. Nếu các em không được giao bài tập phù
hợp thì có thể dẫn đến sự chán nản và ảnh hưởng rất lớn đến kết quả học tập. Từ đó
nhu cầu cần có một hệ thống các bài tập phù hợp với đối tượng học sinh lớp 10
theo từng chuyên đề là cần thiết nên tôi chọn thực hiện đề tài này với mục đích
nâng cao hơn nữa hiệu quả trong công tác giảng dạy và bồi dưỡng học sinh giỏi
ngay từ khối 10, tạo nền tảng vững chắc cho các em nâng cao hơn nữa kỹ năng và
năng lực của mình một cách hoàn thiện.
Trong thời gian thực hiện đề tài, tôi đã tham khảo ý kiến của các giáo viên nhiều
kinh nghiệm và có tham gia giảng dạy để có thể đưa ra được một hệ thống bài tập
cơ bản thuộc về các chuyên đề mà tôi phụ trách phù hợp với trình độ và đối tượng
học sinh của lớp 10 Tin.
Hệ thống bài tập được xem là một giải pháp mang tính tham khảo, có thể được tùy
chỉnh, thêm, bớt tùy vào nhu cầu giảng dạy và trình độ học sinh cụ thể. Nó được
tổng hợp từ các nguồn bài tập sẵn có (sắp xếp, phân loại lại) và một số bài tập phát
triển. Song song đó, quá trình dạy học còn áp dụng một số biện pháp tích cực, chủ
động giúp học sinh nắm chắc hơn kiến thức và phát triển khả năng diễn đạt thuật
toán một cách trôi chảy.
1
III. TỔ CHỨC THỰC HIỆN CÁC GIẢI PHÁP
1. Giải pháp 1:Phân loại hệ thống bài tập theo từng chuyên đề
a) Trong quá trình giảng dạy từ chuyên đề mở đầu (cơ bản), giáo viên tiến hành
phân loại bài tập và hướng dẫn học sinh luyện tập theo hệ thống từ dễ đến khó, từ cơ bản
đến những bài tập có tính kết hợp và suy luận.
b) Hệ thống phân loại bài tập dành cho học sinh lớp 10 chuyên Tin:
Dưới đây là hệ thống bài tập đã được phân loại trong các chuyên đề mà tôi phụ
trách ở lớp 10 chuyên Tin năm học 2014-2015.
Phần 1: Kỹ thuật lập trình
-
Phần cơ bản, làm quen với ngôn ngữ lập trình: Sử dụng hệ thống bài tập trong bộ
tài liệu “Tài liệu giảng dạy lập trình khối THPT” quyển 1 đã được phân loại cụ thể
và hợp lý, phù hợp với trình độ học sinh vừa tiếp cận với bộ môn lập trình Pascal.
Phần 2: Sắp xếp, tìm kiếm:
-
Hệ thống bài tập trong phần “Sắp xếp, tìm kiếm” thuộc “Tài liệu giảng dạy lập
trình khối THPT” quyển 2 .
Một số bài tập phát triển dùng để tham khảo:
1. NKSGAME
Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn
trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là:
b1, b2,..., bn , còn dãy số mà bạn thứ hai chọn là c 1, c2, ..., cn. Mỗi lượt chơi
mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra
số hạng bi (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng cj (1 ≤ j ≤ n) thì giá
của lượt chơi đó sẽ là |bi+cj|.
Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai
chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi
có thể là 0 tương ứng với giá của lượt chơi (-2, 2).
Yêu cầu
-
Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.
Input
Dòng đầu tiên chứa số nguyên dương n (n ≤ 105)
Dòng thứ hai chứa dãy số nguyên b1, b2, ..., bn (|bi| ≤ 109, i=1, 2, ..., n)
Dòng thứ hai chứa dãy số nguyên c1, c2, ..., cn (|ci| ≤ 109, i=1, 2, ..., n)
Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.
Output
2
-
Ghi ra một dòng duy nhất giá nhỏ nhất tìm được.
NKSGAME.IN
P
2
1 -2
23
NKSGAME.OU
T
0
Ràng buộc
60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.
2. LTVTour1
Các thành viên trong một đoàn du lịch được giới thiệu đến một địa điểm khá
thú vị. Đoạn đường mà họ sắp đi qua có một cây cầu được đặt tên là cây cầu
Đoàn kết. Các du khách đi đến đây chỉ được đi qua cầu nếu họ tìm được một
người trong đoàn chịu cõng mình qua bên kia. Vì yêu cầu tải trọng của cầu
chỉ có thể chịu được sức nặng K nên họ phải tìm được người phù hợp với
mình. Các cặp sau khi lựa chọn xong thì lần lượt qua cầu và không được
quay lại đón thêm ai cả (tại một thời điểm chỉ có hai người đang cõng nhau
qua cầu).
Yêu cầu: Hãy cho biết đoàn du lịch có thể qua cầu hết hay không?
Input:
- Dòng đầu là số nguyên dương N, K (2<=N<=105, (|K| <= 109). Trong đó N
là số lượng du khách. K là tải trọng tối đa của cầu.
- Dòng tiếp theo chứa N số nguyên Ai (|Ai| <= 102) các số cách nhau một dấu
khoảng trắng là trọng lượng của mỗi du khách.
Output:
- Xuất ra ‘Yes’ nếu đoàn du lịch có thể đi qua hết, ‘No’ trong trường hợp
ngược lại.
- Ví dụ:
LTVTour1.INP
LTVTour1.OUT
5 120
No
30 43 53 96 70
6 120
Yes
30 43 53 86 70 50
6 120
No
30 43 53 100 70
50
3. LTVTour2
Các thành viên trong một đoàn du lịch được giới thiệu đến một địa điểm khá
thú vị. Đoạn đường mà họ sắp đi qua có một cây cầu được đặt tên là cây cầu
Đoàn kết. Các du khách đi đến đây chỉ được đi qua cầu nếu họ tìm được một
người trong đoàn chịu cõng mình qua bên kia. Vì yêu cầu tải trọng của cầu
chỉ có thể chịu được sức nặng K nên họ phải tìm được người phù hợp với
mình. Các cặp sau khi lựa chọn xong thì lần lượt qua cầu và không được
3
-
quay lại đón thêm ai cả (tại một thời điểm chỉ có hai người đang cõng nhau
qua cầu).
Yêu cầu: Hãy cho biết đoàn du lịch có thể qua cầu hết hay không? Nếu
không, cho biết số du khách phải đi đường khác qua sông?
Input:
Dòng đầu là số nguyên dương N, K (2<=N<=105, (|K| <= 109 ). Trong đó N
là số lượng du khách. K là tải trọng tối đa của cầu.
Dòng tiếp theo chứa N số nguyên Ai (|Ai| <= 102) các số cách nhau một dấu
khoảng trắng là trọng lượng của mỗi du khách.
Output:
Xuất ra ‘Yes’ nếu đoàn du lịch có thể đi qua hết, ‘No’ trong trường hợp
ngược lại. Trong trường hợp ‘No’, dòng thứ 2 là số du khách phải đi đường
vòng qua sông.
Ví dụ:
LTVTour2.INP
LTVTour1.OUT
5 120
No
30 43 53 96 70
1
6 120
Yes
30 43 53 86 70 50
6 120
No
30 43 53 100 70
2
50
4. LTVSearch1
Cho dãy số nguyên N phần tử A1, A2,…, An và số nguyên K. Hãy cho biết vị
trí xuất hiện đầu tiên của K trong dãy đã cho.
Input:
- Dòng đầu là số nguyên dương N, K (2<=N<=105, (|K| <= 109 )
- Dòng tiếp theo chứa N số nguyên Ai (|Ai| <= 109) các số cách nhau một dấu
khoảng trắng.
Output:
- Xuất ra một số duy nhất là vị trí đầu tiên xuất hiện của K.
Ví dụ:
LTVSearch1.INP
30
101
52
12125
LTVSearch1.OUT
2
2
Giải thích:
5. LTVSearch2
Cho dãy số nguyên N phần tử A1, A2,…, An và số nguyên K. Hãy cho biết vị
trí xuất hiện cuối cùng của K trong dãy đã cho.
Input:
- Dòng đầu là số nguyên dương N, K (2<=N<=105, (|K| <= 109 )
4
-
Dòng tiếp theo chứa N số nguyên Ai (|Ai| <= 109) các số cách nhau một dấu
khoảng trắng.
Output:
Xuất ra một số duy nhất là vị trí cuối cùng xuất hiện của K.
Ví dụ:
LTVSearch2.INP LTVSearch2.OUT
30
2
101
52
4
12125
6. LTVSearch3
Cho dãy số nguyên N phần tử A1, A2,… An và số nguyên K. Đếm số cặp i,j (1
<= i
b;
Như vậy, với 3 đối tượng (a, b, c) có thể tồn tại 13 quan hệ phân loại như sau:
a = b = c; a = b < c; c < a = b; a < b = c
b = c < a; a = c < b; b < a = c; a < b < c
a < c < b; b < a < c; b < c < a; c < a < b
c < b < a;
Cho số n, hãy xác định số lượng quan hệ phân loại khác nhau.
Input
Gồm nhiều số n. Mỗi số trên 1 dòng. Kết thúc file là -1.
Output
16
Với mỗi n, đưa ra số lượng quan hệ phân loại tìm được, mỗi số trên 1 dòng (không có
dòng trống).
Example
Input:
2
3
-1
Output:
3
13
16. Bulls and Cows- CTNBULLS
Nông dân john muốn sắp xếp n con bò(bao gồm cả bò đực và bò cái) của ông ta trên 1
hàng .Ông ta biết rằng những con bò đực rất hung hăng – Nếu 2 con bò đực đứng quá gần
nhau thì chúng sẽ trở nên hung dữ và bắt đầu húc nhau , vì thế chúng sẽ phá hòng mất trật
tự trên hàng mà ông ta vừa sắp xếp được.
Theo kinh nghiệm lâu năm của mình , john biết được nếu ở giữa hai con bò đực có ít nhất
K con bò cái thì sẽ ngăn chặn được việc chúng húc nhau (+_+)
Vì thế , ông ta nhờ các Vcoders giúp đỡ để tính toán xem có bao nhiêu cách sắp xếp đàn
bò của ông ta lại sao cho không có “chiến tranh” xảy ra giữa những chú bò (^_^), (Tất cả
những con bò đực và những con bò cái đều giống nhau). Hai dãy ( B1..Bn ) và (A1..An )
được cho là khác nhau nếu tồn tại một vị trí I (1<=i<=n) sao cho Ai <> Bi
1<=N<=100000. 0<=k<=n.
Input : gồm 1 dòng duy nhất chứa 2 số n và k cách nhau 1 dấu cách
Output: gồm duy nhất một số là kết quả theo modun 2111992
Eg:
Input :
42
Output
6
Giải thích output(C=bò cái , B:bò đực)
CCCC
17
BCCC
CBCC
CCBC
CCCB
BCCB
Có 1/3 số test với n<=15
17. Dãy có tổng bằng S- NTSEQS
Cho N số nguyên dương tạo thành dãy A={A1, A2, ..., AN}. Tìm ra một dãy con của dãy
A (không nhất thiết là các phần tử liên tiếp trong dãy) có tổng bằng S cho trước.
Input:
Dòng đầu tiên ghi hai số nguyên dương N và S (0
- Xem thêm -