Showing posts with label Đề thi học sinh giỏi Tỉnh. Show all posts
SỞ GIÁO DỤC VÀ ĐÀO TẠO
HÀ TĨNH
(Đề thi có 2 trang)
|
KỲ THI CHỌN HỌC SINH GIỎI TỈNH CẤP THPT
NĂM HỌC 2012 - 2013
MÔN THI: TIN HỌC - LỚP 10
Thời gian: 180 phút (Không kể thời gian giao đề)
|
|||||||||||||
Hãy trình bày
thuật toán giải các bài toán sau đây:
BÀI
1: SỐ THÂN THIỆN
Đang
tìm hiểu các thuật toán về số tự nhiên, Nguyên phát hiện ra số tự nhiên có rất
nhiều tính chất thú vị. Ví dụ số hoàn hảo có tính chất: tổng các ước bằng 2 lần
số đó, như số 6, số 24… Nhiều số tự nhiên khi tìm ước chung lớn nhất với số đảo
ngược của nó bằng 1, những số như thế được gọi là số thân thiện. Chẳng hạn số
23, số đảo ngược của nó là 32, hai số này có ước chung lớn nhất là 1 nên số 23
là số thân thiện và 32 cũng là số thân thiện.
Yêu cầu:
Cho 2 số tự nhiên a, b (10 ≤ a ≤ b ≤ 104). Hãy đếm xem trong đoạn từ
a đến b có bao nhiêu số thân thiện.
Ví dụ:
Dữ liệu vào
|
Kết quả
|
Giải thích
|
19 29
|
4
|
Đó là các số: 19, 23, 25, 29
|
BÀI
2: SỐ TỰ NHIÊN NHỎ NHẤT
Nam
một người bạn của Nguyên đang tìm cách giải một bài toán liên quan tới số tự
nhiên và cần sự giúp đỡ của Nguyên, nhưng thử thách lần này là một dãy gồm N số
tự nhiên bất kỳ nằm trong đoạn từ 0 tới 109, tìm số tự nhiên nhỏ
nhất không có trong dãy số đó. Vì số
lượng các số tự nhiên trong dãy số đã cho có thể lên tới 106 phần tử
nên việc tìm thủ công là không thể mà cần một thuật toán để cài đặt vào máy
tính và nhờ máy tính tìm giúp.
Yêu cầu: Cho một dãy A gồm N (1 ≤ N ≤ 106) số tự
nhiên. Hãy tìm số tự nhiên nhỏ nhất
không xuất hiện trong dãy A.
Ví dụ:
Dữ liệu vào
|
Kết quả
|
N= 5
Dãy số: 5
4 2 3 1
|
0
|
N= 9
Dãy số: 2 4
0 3 1
2 6 2 8
|
5
|
BÀI
3: SỐ LƯỢNG NHÓM ĐỀ TÀI
Nhà
trường phát động phong trào đăng ký làm sáng tạo khoa học kỹ thuật, tất cả các
bạn trong lớp của Nguyên đều tích cực tham gia và được phân công vào các nhóm
đề tài. Mỗi nhóm đề tài được ký hiệu: <Tên nhóm> <Số thành viên>,
ví dụ Nguyên được phân công vào nhóm TIN gồm 3 thành viên thì ký hiệu nhóm là
TIN 3. Danh sách được lập ra gồm ký hiệu nhóm và tên thành viên, nhưng trong
quá trình in ấn cột ký hiệu nhóm bị mờ <tên nhóm> và không đọc được chỉ
còn lại <số thành viên>.
Ví dụ:
Ký hiệu
|
Thành viên
|
hiệu
|
Thành viên
|
|
TIN 3
|
Việt
|
3
|
Việt
|
|
TOAN
2
|
Tuấn
|
2
|
Tuấn
|
|
TIN 3
|
Thái
|
Do lỗi in ấn →
|
3
|
Thái
|
TIN 3
|
Anh
|
3
|
Anh
|
|
TOAN
2
|
Chính
|
2
|
Chính
|
Yêu
cầu:
Cho danh sách gồm n học sinh và số
thành viên của nhóm tương ứng với từng học sinh. Hãy xác định số lượng nhóm đề
tài đã được phân công. Dữ liệu đảm bảo
bài toán có nghiệm.
Ví dụ:
Dữ liệu vào
|
Kết quả
|
N= 5
3 2
3 3 2
|
2
|
N= 10
5 1
2 5 5
2 5 5
2 2
|
4
|
---------------------------HẾT---------------------------
Ghi
chú:
-
Ngoài
cách trình bày bằng phương pháp liệt kê hoặc sơ đồ khối, thí sinh có thể sử
dụng ngôn ngữ mô phỏng PASCAL hoặc ngôn ngữ PASCAL để trình bày thuật toán với
dữ liệu vào/ra từ màn hình.
-
Thí
sinh không được sử dụng tài liệu.
-
Giám
thị không giải thích gì thêm.
-
SỞ GIÁO DỤC VÀ ĐÀO TẠO
 HÀ
TĨNH |
KỲ THI CHỌN HỌC SINH GIỎI TỈNH CẤP THPT NĂM
HỌC 2012 - 2013
HƯỚNG DẪN CHẤM THI
Môn
thi: Tin học 10
|
Gợi ý đáp án
|
Thang điểm
|
|
Câu 1
|
6.0
|
|
- Xác định bài toán:
Input: Hai số a, b (10 ≤ a ≤ b ≤ 104)
Output: Số lượng số thân thiện thuộc đoạn [a,b]
|
0.5
|
|
- Ý tưởng: Dùng 1 biến dem để lưu số lượng số
thân thiện
Xét lần lượt các số tự nhiên i từ a
tới b
Với mỗi số i xác định số tự nhiên j là đảo ngược
của i
Nếu UCLN(i,j)= 1 thì tăng biến dem lên 1
Kết quả bài toán là dem
|
1.0
|
|
- Thuật toán:
Bước 1. Nhập hai số a và b;
Bước 2. i!a; dem ! 0;
Bước 3. Nếu i>b thì
chuyển đến bước 13;
Bước 4. k!i, Songuoc!0;
Bước 5. Nếu k = 0 thì chuyển đến
bước 8;
Bước 6. Songuoc!Songuoc*10+k mod 10;
Bước 7. k ! k div 10; rồi quay lại bước 5
Bước 8. k ! i;
Bước 9. Nếu k = Songuoc thì
chuyển đến bước 11;
Bước 10. Nếu k > Songuoc
thì k ! k - Songuoc
Ngược lại Songuoc ! Songuoc – k, rồi quay lại bước 9;
Bước 11. Nếu k=1 thì dem ! dem+1;
Bước 12. i!i+1 và quay lại bước 3;
Bước 13. Đưa ra kết quả dem rồi kết thúc.
|
4.5
|
|
Theo yêu cầu đề bài cho
thấy các bước giải rất rõ ràng nên trong thuật toán có thể chia nhỏ từng phần
để cho điểm.
Bước 1: Nhập dữ liệu: 0,5 điểm
Bước 2, bước 3, bước 12 thể hiện vòng lặp: 1 điểm
Bước 4 tới bước 7 tính số đảo ngược: 1 điểm
Bước 8 tới bước 11 xác định UCLN: 1,5 điểm
Bước 13: Đưa ra kết quả: 0,5 điểm
|
||
Câu 2.
|
7.0
|
|
- Xác định
bài toán:
Input: N và dãy A
gồm N số tự nhiên
Output: Số tự nhiên nhỏ
nhất không xuất hiện trong dãy A
|
0.5
|
|
- Ý tưởng:
Nhận xét: Số tự
nhiên nhỏ nhất luôn nằm trong đoạn từ 0 tới N.
Do vậy dùng dãy B[0..N] để đánh
dấu những số đã có trong dãy A nằm trong đoạn từ 0 tới N. Ban đầu đánh dấu
tất cả các phần tử của dãy B có giá trị là False. Tiếp theo đánh dấu trong
dãy B những phần tử có trong dãy A như sau:
Xét i: 1 tới N, nếu Ai<=N thì đánh
dấu B[Ai]ßTrue
Tìm số tự nhiên đầu tiên j trong dãy B
mà Bj=False, với j: 0 tới N
|
1.5
|
|
- Thuật toán:
Bước 1. Nhập N và dãy A1, A2,...,AN;
Bước 2. i!0;
Bước 3. Nếu i>N thì chuyển đến bước 6;
Bước 4. Bi!False;
Bước 5. i!i+1; rồi quay lại bước 3;
Bước 6. i!1;
Bước 7. Nếu i>N thì và chuyển đến bước 10;
Bước 8. Nếu Ai<=N thì B[Ai]!true;
Bước 9. i!i+1 và quay lại bước 7;
Bước 10. j!0;
Bước 11. Nếu Bj=false thì thông báo j, rồi kết thúc;
Bước 12. j!j+1 và quay lại bước 11;
|
5.0
|
|
Câu 3.
|
7.0
|
|
- Xác định bài toán:
Input: N và dãy A
gồm N số nguyên dương lưu số thành viên
Output: Số lượng
nhóm đề tài
|
0.5
|
|
- Ý tưởng:
Xét lần lượng từng học
sinh:1 .. N
Ứng với từng học sinh đánh dấu các học sinh
cùng nhóm, đồng thời tăng biến dem lên 1.
Kết quả bài toán là dem
|
1.5
|
|
- Thuật toán:
Bước 1. Nhập N và dãy A1,
A2,...,AN;
Bước 2. i!1; dem ! 0;
Bước 3. Nếu i>N thì chuyển đến bước 11;
Bước 4: Nếu Ai<=0 thì chuyển sang bước thứ 10;
Bước 5. dem ! dem+1;
Bước 6. K!Ai; j ! i; d ! 0;
Bước 7. Nếu (j>N) hoặc (d=K) thì và chuyển đến bước 10;
Bước 8. Nếu Aj=k thì Aj ! -K; d ! d+1;
Bước 9. j!j+1 và quay lại bước 7;
Bước 10. i!i+1 và quay lại bước 3
Bước 11. Đưa ra kết quả dem
rồi kết thúc.
|
5.0
|
|
-
Mỗi bài toán có nhiều thuật toán khác nhau để
giải, Tùy vào bài làm của học sinh và thang điểm trên để cho điểm phù hợp
-
Bài 3: Có thuật toán sắp xếp trước khi đánh
dấu với độ phức tạp thuật toán nhỏ hơn, nếu học sinh thể hiện được thuật toán
này có thể khuyến khích hơn
-
Tỉnh Hà Tĩnh ( 2012-2013 ).
Trang 1 / 2
SỞ GIÁO DỤC VÀ ĐÀO TẠO
BÌNH PHƯỚC
KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 CẤP TỈNH
NĂM HỌC 2012 – 2013
MÔN: TIN HỌC
(Đề thi gồm 02 trang) Thời gian làm bài: 180 phút
(Không kể thời gian phát đề)
Tổng quan bài thi
SỞ GIÁO DỤC VÀ ĐÀO TẠO
BÌNH PHƯỚC
KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 CẤP TỈNH
NĂM HỌC 2012 – 2013
MÔN: TIN HỌC
(Đề thi gồm 02 trang) Thời gian làm bài: 180 phút
(Không kể thời gian phát đề)
Tổng quan bài thi
Câu
|
Tên bài
|
Tên tệp chương trình
|
Tên tệp dữ liệu vào
|
Tên tệp dữ liệu ra
|
1
|
Tìm số
|
TIMSO.PAS
|
TIMSO.INP
|
TIMSO.OUT
|
2
|
Đếm số
lượng
|
SOLUONG.PAS
|
SOLUONG.INP
|
SOLUONG.OUT
|
3
|
Kết nối
|
KETNOI.PAS
|
KETNOI.INP
|
KETNOI.OUT
|
Câu 1: Tìm số (7 điểm)
Cho hai số nguyên dương A, X (1 < A < 100; 0 < X < 109). Hãy tìm số nguyên K
lớn nhất thỏa mãn AK ≤ X.
Dữ liệu vào từ tệp văn bản TIMSO.INP: Chứa hai số theo trình tự A, X trên một
dòng. Hai số cách nhau một khoảng trắng.
Dữ liệu ra ghi vào tệp văn bản TIMSO.OUT: Số nguyên K.
Ví dụ:
TIMSO.INP
|
TIMSO.OUT
|
3 10
|
2
|
Câu 2: Đếm số lượng (7 điểm)
Xét dãy gồm N số nguyên dương A1, A2, …, AN và số nguyên X cho trước. Hãy
đếm số cặp (Ai, Aj) thỏa mãn các điều kiện:
o Ai + Aj = X
o 1 £ i < j £ N
Dữ liệu vào từ tệp văn bản SOLUONG.INP:
o Dòng đầu tiên chứa số nguyên dương N với 1 < N ≤ 106.
o Dòng tiếp theo chứa N số nguyên A1, A2, ..., AN với 0 < Ai < 105, 1 ≤ i ≤ N.
Hai số kề nhau cách nhau một khoảng trắng.
o Dòng cuối cùng chứa số nguyên dương X < 106.
Dữ liệu ra ghi vào tệp văn bản SOLUONG.OUT: Số lượng cặp (Ai, Aj) thỏa mãn
điều kiện trên.
ĐỀ CHÍNH THỨC
Trang 2 / 2
Ví dụ:
SOLUONG.INP
|
SOLUONG.OUT
|
9
5 12 7 11 9 1 2 3 11 13 |
3
|
Câu 3: Kết nối (6 điểm)
Cho N số nguyên dương A1, A2, …, AN. Từ các số nguyên này, có thể tạo ra một
số nguyên mới bằng cách kết nối tất cả các số đã cho viết liên tiếp tiếp nhau.
Ví dụ: với N = 3, các số 50, 9, 80 ta có thể tạo ra các số mới như sau: 50980,
50809, 95080, 98050, 80509, 80950. Có tất cả N! số được tạo ra. Trong trường hợp
này, số lớn nhất là 98050.
Yêu cầu: cho N số nguyên dương A1, A2, …, AN. Hãy xác định số lớn nhất có thể
tạo thành theo nguyên tắc trên.
Dữ liệu vào từ tệp văn bản KETNOI.INP:
o Dòng đầu tiên chứa số nguyên N với 1 < N ≤ 106.
o Dòng thứ hai chứa N số nguyên A1, A2, …, AN với 0 < Ai < 100, 1 ≤ i ≤ N.
Hai số kề nhau cách nhau một khoảng trắng.
Dữ liệu ra ghi vào tệp văn bản KETNOI.OUT: Số lớn nhất có thể tạo ra từ dãy
số.
Ví dụ:
KETNOI.INP
|
KETNOI.OUT
|
3
50 9 80 |
98050
|
_____HẾT_____
Giám thị coi thi không giải thích gì thêm..