Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Tin học Skkn phân loại bài tập theo chuyên đề tin 10...

Tài liệu Skkn phân loại bài tập theo chuyên đề tin 10

.PDF
33
1930
83

Mô tả:

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à c1, 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 - Ghi ra một dòng duy nhất giá nhỏ nhất tìm được. 2 NKSGAME.INP 2 1 -2 23 NKSGAME.OUT 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 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? 3 - - - 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 ) - 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ụ: 4 LTVSearch2.INP 30 101 52 12125 LTVSearch2.OUT 2 4 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 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: 16 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 BCCC CBCC CCBC CCCB 17 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 -

Tài liệu liên quan