 Công tác bồi dưỡng học sinh giỏi là một công tác mũi nhọn trong việc nâng cao chất lượng giáo dục, tạo nguồn lực, bồi dưỡng nhân tài cho nhà trường nói riêng, cho địa phương nói chung. Đồng thời, thông qua kết quả học sinh giỏi phần nào khẳng định được vị thế của trường so với các trường bạn trong huyện nói riêng và trong tỉnh nói chung. Bồi dưỡng học sinh giỏi là một công việc khó khăn và lâu dài, đòi hỏi nhiều công sức của thầy và trò. Đặc biệt là những trường có chất lượng đầu vào của học sinh thấp nhất huyện như trường chúng tôi thì giấc mơ để học sinh có giải trong các kì thi học sinh giỏi Tỉnh là quá xa vời. Chất lượng học sinh giỏi môn Tin học của trường từ năm học 2011 – 2012 trở về trước là rất thấp, môn Tin học luôn trong tình trạng “trắng bảng”, chưa có học sinh nào đạt được giải học sinh giỏi môn Tin học cấp tỉnh, mặc dù một số năm vẫn có học sinh tham gia thi. Chất lượng học sinh giỏi môn Tin học còn thấp như vậy, phần vì năng lực học sinh, phần vì phương pháp giảng dạy của giáo viên chưa phù hợp. Do đó việc nâng cao chất lượng học sinh giỏi môn Tin học là cần thiết và cấp bách nhằm góp thêm vào thành tích chung của nhà trường. Mặt khác, trong quá trình dạy bồi dưỡng học sinh giỏi tôi gặp rất nhiều bài toán về số nguyên tố. Đây là dạng bài tập không khó và thường xuất hiện trong các đề thi học sinh giỏi môn Tin học. Tuy nhiên rất nhiều học sinh khi gặp dạng bài tập này bị mất điểm hoặc điểm không cao. Nguyên nhân có thể nhiều nhưng trong đó có nguyên nhân cơ bản là: chương trình cho kết quả output sai hoặc chương trình cho kết quả output đúng nhưng chỉ với các bộ input có dữ liệu nhỏ còn với những bộ input có dữ liệu lớn thì chương trình chạy quá thời gian quy định mặc dù kết quả output vẫn đúng. Với mong muốn giúp học sinh giải quyết tốt hơn các bài tập về số nguyên tố và hiểu biết sâu sắc hơn cách sử dụng giải thuật sàng nguyên tố, tôi đã dày công nghiên cứu, tìm tòi các bài tập có nội dung liên quan cũng như các đề thi của các tỉnh, trăn trở để tìm ra nhiều cách làm để học sinh biết các vận dụng để chương trình tối ưu nhất và dễ hiểu nhất. Từ đó nâng cao chất lượng bồi dưỡng học sinh giỏi môn Tin học. Từ những lý do trên tôi đã mạnh dạn trình bày sáng kiến kinh nghiệm: “Áp dụng thuật toán sàng nguyên tố để giải một số bài tập về số nguyên tố trong Tin học nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi ở trường trung học phổ thông 4 Thọ Xuân” để học sinh dễ dàng làm quen, tiếp thu và hình thành các kỹ năng trong việc tiếp cận các bài toán về số nguyên tố. Bạn đang xem tài liệu "SKKN Áp dụng thuật toán sàng nguyên tố để giải một số bài tập về số nguyên tố trong Tin học nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi ở trường trung học phổ thông 4 Thọ Xuân", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên \=250). Vừa rồi gặp phải một cơn bão quét ngang qua, vườn cây bị bão làm đổ gãy một phần. Cơ quan quản lí vườn cây lên kế hoạch thăm dò để trồng lại. Trong đó, người ta muốn tìm hiểu số cây còn lại và số lượng các cây liên tục lớn nhất. Giải thích: Cây liên tục là những cây gần nhau trên một đường thẳng theo hàng ngang hoặc hàng dọc. Yêu cầu: viết chương trình cho biết số cây còn lại và số cây liên tục lớn nhất của vườn cây. Dữ liệu vào: được ghi trên tệp vuoncay.inp bao gồm: o Dòng thứ nhất là hai số nguyên cách nhau một khoảng trắng thể hiện giá trị của m và n. o m dòng tiếp theo là các dãy số nhị phân với số 1 thể hiện vị trí cây còn sống, số 0 thể hiện cây đã bị gãy. Dữ liệu ra: lưu trong tệp vuoncay.out với hai số nguyên cách nhau một khoảng trắng thể hiện số cây còn lại và số cây liên tục lớn nhất. Ví dụ: VUONCAY.INP VUONCAY.OUT Ví dụ 1 6 8 10011001 10100011 00010101 00100001 01010001 10011001 20 6 Ví dụ 2 5 6 101010 010101 101010 101101 010111 17 3 Bài 2:Tìm số Cho số nguyên dương X, khi đảo ngược trật tự các chữ số của X ta sẽ thu được một số nguyên dương Y, Y được gọi là số đảo ngược của X. Ví dụ: X = 613 thì Y = 316 là số đảo ngược của X. Số nguyên dương Y được gọi là số nguyên tố nếu nó chỉ có hai ước số là 1 và chính nó, số 1 không phải là số nguyên tố. Cho hai số nguyên dương P và Q (1 ≤ P ≤ Q ≤ 2´109; Q - P ≤ 105). Yêu cầu: Hãy tìm tất cả các số nguyên dương X nằm thỏa mãn P ≤ X ≤ Q và số đảo ngược của số X là số nguyên tố. Dữ liệu vào: Cho trong file văn bản TIMSO.INP có cấu trúc như sau: - Dòng 1: Ghi hai số nguyên dương P Q, hai số được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản TIMSO.OUT trên nhiều dòng, mỗi dòng ghi một số nguyên X tìm dược. Ví dụ: TIMSO.INP TIMSO.OUT 10 19 11 13 14 16 17 Bài 3:Tính tổng Cho hai số nguyên dương M và N, M có p chữ số và N có q chữ số. Yêu cầu: Tính tổng của hai số M và N. Dữ liệu vào: Cho trong file văn bản TONG.INP có cấu trúc như sau: - Dòng 1:Ghi số nguyên dương p là số lượng chữ số của M (1 ≤ p ≤ 30000). - Dòng 2: Ghi p chữ số của M theo thứ tự từ trái sang phải, các chữ số được ghi cách nhau ít nhất một dấu cách. - Dòng 3:Ghi số nguyên dương q là số lượng chữ số của N (1 ≤ q ≤ 30000). - Dòng 4: Ghi q chữ số của N theo thứ tự từ trái sang phải, các chữ số được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản TONG.OUT theo cấu trúc như sau: - Dòng 1:Ghi số nguyên dương k là số lượng chữ số của tổng tìm được. - Dòng 2: Ghi k chữ số của tổng tìm được theo thứ tự từ trái sang phải, các chữ số được ghi cách nhau ít nhất một dấu cách. Ví dụ: TONG.INP TONG.OUT 6 2 2 3 2 3 9 3 2 4 7 6 2 2 3 4 8 6 Bài 4: Số hoa hồng Một số nguyên dương được gọi là số hoa hồng nếu các chữ số của số đó chỉ thuộc tập {7;9}. Hãy xác định số lượng số hoa hồng trong đoạn [X,Y] với X,Y là số nguyên dương. Dữ liệu vào từ tệp văn bản HOAHONG.INP Một dòng duy nhất chứa 2 số nguyên X,Y được phân cách bởi khoảng trắng. Dữ liệu ra ghi vào tệp văn bản HOAHONG.OUT Số lượng số hoa hồng trong đoạn [X,Y] Giới hạn 1<X<Y<1015 Ví dụ HOAHONG.INP HOAHONG.OUT 7 102 6 Bài 5: Tổng số Một dãy số được viết lần lượt theo thứ tự như sau: 1 số 1, 2 số 2, 3 số 3, 4 số 4, và 5 số 5, .... ( 1 , 2 , 2 , 3 , 3 , 3, 4 , 4, 4 , 4 , 5 , 5 , 5 , 5 , 5 ,... ) Tổng các số nguyên từ số nguyên thứ 1 đến số nguyên thứ 3 là : 1 + 2 + 2 = 5. Hãy tính tổng các số nguyên trong dãy số trên kể từ số nguyên thứ A trong dãy đến số nguyên thứ B trong dãy. Yêu cầu: * Dữ liệu vào: đọc từ file văn bản : TONGSO.INP Chỉ có 1 dòng ghi 2 số nguyên A và B ( 1<=A<=B<=10000) * Kết quả ghi ở file : TONGSO.OUT Chỉ có một dòng duy nhất ghi giá trị tổng các số trong dãy tính từ số nguyên thứ A đến số nguyên thứ B. Ghi chú: (Các số trên cùng một dòng trong file cách nhau ít nhất bởi một dấu cách trắng) Ví dụ : TONGSO.INP TONGSO.OUT TONGSO.INP TONGSO.OUT TONGSO.INP TONGSO.OUT 1 3 5 3 7 15 50 50 10 Bài 6: : Số phản nguyên tố Một số tự nhiên N được gọi là số phản nguyên tố nếu nó có nhiều ước số nhất trong N số tự nhiên đầu tiên. Yêu cầu: Cho số K (K<=10000) ghi ra số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K. Dữ liệu vào : Đọc từ file văn bản SOPNT.INP có cấu trúc như sau: Dòng đầu tiên là số M(1<M<=100): số các số cần tìm số phản nguyên tố lớn nhất của nó. M dòng tiếp theo là các số k1,k2,..kM Dữ liệu ra: Ghi ra file văn bản SOPNT.OUT có cấu trúc như sau: Gồm M dòng, Dòng thứ i (1<=i<=M) là số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng ki. Ví dụ SOPNT.INP SOPNT.OUT 3 1000 800 10000 840 720 7560 Bài 7: Số nguyên tố tương đương Hai số tự nhiên được gọi là Nguyên tố tương đương nếu chúng có chung các ước số nguyên tố. Ví dụ: Các số 15 và 75 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5. Yêu cầu: Cho trước hai số tự nhiên M, N. Hãy viết chương trình kiểm tra xem các số này có là nguyên tố tương đương với nhau hay không? Dữ liệu vào: Cho trong file văn bản PRIME.INP gồm một dòng duy nhất chứa hai số nguyên M và N, mỗi số cách nhau ít nhất một dấu cách( 2 ≤ M ≤ N ≤ 300000000000000000). Dữ liệu ra: Xuất ra file văn bản PRIME.OUT, nếu chúng là nguyên tố tương đương ghi YES, ngược lại: ghi NO. PRIME.INP PRIME.OUT 15 75 Yes 12 60 no Bài 8: Dãy số Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng 1234567891011121314..... Cho số nguyên N. Hỏi ở vị trí thứ N trong dãy là số nào? Ví dụ: n=15 thì vị trí thứ n là số 2 hoặc n=1000000 thì vị trí thứ n là số 1 Input: Đọc từ tệp DAYSO.INP gồm 1 số nguyên duy nhất N (N<=106) Output: Ghi vào tệp DAYSO.OUT 1 số nguyên duy nhất là số ở vị trí thứ N. Bài 9: Tìm xâu Cho xâu S có độ dài N(N<100).Xâu S chỉ chứa các k tự số ‘0’…’9’. Yêu cầu: Hãy viết chương trình tìm xâu S1 bằng cách hoán vị các k tự số trong xâu S sao cho xâu S1 có giá trị nhỏ nhất lớn hơn S. Đữ liệu vào: Cho trong tệp tin SO.INP, gồm 1 dòng ghi xâu S. Kết quả: Ghi trong tập tin SO.OUT, gồm 1 dòng ghi kết quả vừa tìm được (xâu s1). Ví dụ: Bài 10: Dãy số xuất hiện Nhập một dãy A có N số tự nhiên (N<40) và 1 số K. Hãy xuất ra các phần tử có số lần xuất hiện trong dãy A từ K lần trở lên ( Mỗi số chỉ xuất 1 lần) Dữ liệu nhập: file DAYSO.INP: - Dòng 1: 2 số N, K giữa 2 số cách nhau 1 khoảng trắng - Dòng 2: Dãy A Kết quả: file DAYSO.OUT: xuất các số thỏa điều kiện trên (mỗi số cách nhau bởi dấu cách), trường hợp không có số nào thỏa thì xuất số -1 Ví dụ: DAYSO.INP DAYSO.OUT 5 2 3 3 4 5 5 3 5 5 3 3 4 5 6 7 -1 Bài 11: Số dương đứng cạnh Nhập dãy số thực a và 1 số nguyên k. Xét xem trong dãy có k số dương đứng cạnh nhau hay không? Dữ liệu nhập: DUNGCANH.INP: Gồm 2 dòng - Dòng 1: Số nguyên k - Dòng 2: Dãy a Dữ liệu xuất: DUNGCANH.OUT: có xuất 1 , không có xuất 0. Ví dụ: DUNGCANH.INP DUNGCANH.OUT 3 5 -2 4 -5 6 -7 8 0 3 3 4 5 6 -7 1 Bài 12: Nén và giải nén Một chuỗi kí tự thuần nhất được định nghĩa là chuỗi chỉ bao gồm các kí tự ‘A’.. ‘Z’ hoặc ‘a’.. ‘z’. Một xâu thuần nhất có thể được viết thu gọn, bao gồm các ký tự kèm theo số lần xuất hiện liên tiếp của ký tự đó. Ví dụ: Chuỗi thuần nhất: AABBCDDEEF Chuỗi thu gọn: 2A2BC2D2EF Chuỗi thu gọn: A5B3D2E Chuỗi thuần nhất: ABBBBBDDDEE Yêu cầu: Viết chương trình xử lý chuỗi đọc được ‒ Nếu là chuỗi thuần nhất thì hãy chuyển đổi nó về dạng thu gọn. ‒ Nếu là chuỗi thuộc dạng thu gọn thì hãy chuyển đổi nó trở lại dạng thuần nhất tương ứng. Dữ liệu vào: từ tệp INPUT.TXT gồm nhiều dòng, mỗi dòng là một chuỗi ở dạng thuần nhất hoặc thu gọn. Kết quả: Lưu vào tập tin OUTPUT.TXT xâu đã chuyển đổi, mỗi xâu trên 1 dòng. Bài 13: CHỮ SỐ Xét dãy số tự nhiên {an} được xây dựng theo quy tắc sau: · Cho trước số a0 là một số tự nhiên có tối đa 10 chữ số. · Số ai (i>0) là một số tự nhiên nhận được từ số ai-1 bằng cách viết thêm vào sau số của ai-1 nhưng chư số cua số ai-1 nhưng theo thứ tự ngược lại. Ví dụ: Với a0 \= 246 thì a1 \= 246642, a2 \= 246642246642, a3 \= 246642246642246642246642 Với hai số N và M cho trước (1 £ N £ 25, 1 £ M £ 109), hãy tìm chữ số thứ M trong aN. Dữ liệu vào cho trong file văn bản với tên là CHUSO.INP trong đó dòng đầu chứa số a0, dòng thứ hai chứa hai số tự nhiên N và M. Kết quả ghi ra file văn bản với tên là CHUSO.OUT. Trong trường hợp có lời giải, file này sẽ chứa số tìm được, ngược lại file này chứa số -1. Ví du: CHUSO.INP CHUSO.OUT CHUSO.INP CHUSO.OUT 246 2 12 -1 3 7 3 17 Bài 14: TÌM NGHIỆM Cho phương trình có dạng sau: x + y + z = K trong đó K là một số nguyên dương. Với số K cho trước (K £ 5000), hay tim tât cả cac bộ số (x, y, z) vơi x, y, z là số nguyên tố và (x £ y £ z) là nghiệm của phương trình trên. Dữ liệu vào cho trong file văn bản EQUA.INP trong đó chứa duy nhất số K. Kết quả ghi ra file văn bản EQUA.OUT như sau: · Nêu phương trinh vô nghiêm ghi số 0. · Nêu phương trinh có nghiêm thi môi dong ghi 3 số x, y, z ; Dong cuối ghi số N là số bộ nghiêm cua phương trinh. |
