Đề thi chọn HSG Tin học 12 cấp Tỉnh năm 2004 - 2005 - Bảng A

Chia sẻ: Lý Hoàng Duy | Ngày: | Loại File: DOC | Số trang:4

Thêm vào BST

Báo xấu

327
lượt xem 59
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo chuyên môn công nghệ thông tin - Đề thi chọn HSG Tin học 12 cấp Tỉnh năm 2004 - 2005 - Bảng A

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi chọn HSG Tin học 12 cấp Tỉnh năm 2004 - 2005 - Bảng A

SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI TỈNH – THPT QUẢNG NGÃI Năm học 2004-2005 Môn: Tin học - Bảng A ĐỀ CHÍNH THỨC Thời gian: 180 phút (không kể thời gian giao đề) Ngày thi: 05/12/2004 TỔNG QUAN BÀI THI NGÀY THỨ HAI - BẢNG A Tên bài Tên chương trình Dữ liệu vào Kết quả BÀI 3 Tháp Hà Nội TOWER.PAS Bàn phím Màn hình BÀI 4 C ửa s ổ WINDOWS.PAS WINDOWS.INP WINDOWS.OUT Hãy lập trình giải các bài toán sau: Bài 3 : Tháp Hà nội Tên chương trình: TOWER.PAS Có 3 cọc cắm tại 3 vị trí 1, 2, 3 như hình 1. Trên cọc thứ nhất có một chồng gồm n đĩa bằng gỗ hình tròn to nhỏ khác nhau được xuyên lỗ ở giữa tựa như những đồng xu và đặt chồng lên nhau để tạo ra một toà tháp. Người chơi phải chuyển được toà tháp từ cọc 1 sang cọc 3, tuân thủ quy tắc sau: (1) Người chơi được sử dụng vị trí thứ 2 để đặt tạm các tầng tháp. (2) Mỗi lần được chuyển 1 tầng tháp từ một vị trí sang một trong hai vị trí còn lại. (3) Không được đặt tầng tháp lớn trên tầng tháp nhỏ. Hãy tìm cách giải bài toán trên với số lần chuyển đĩa là ít nhất, theo hai cách a. Sử dụng phương pháp đệ quy. b. Sử dụng phương pháp khác (không dùng đệ quy). Dữ liệu:: Nhập vào từ bàn phím số nguyên N , N ≤ 64. Kết quả: Xuất ra màn hình • Các bước chuyển • Tổng số lần chuyển Ví dụ: N=3 Xuất ra màn hình : A --> C A --> B C --> B A --> C B --> A B --> C 1 2 3 A --> C (A) (B) (C) Số lần chuyển : 7 Hình 1. Bài toán tháp Hà Nội 1/2
Bài 4: Cửa sổ Tên chương trình: WINDOWS.PAS Trong khi sử dụng một số hệ điều hành phổ biến hiện nay, chúng ta thường mở một vài cửa sổ. Mỗi cửa sổ là một hình chữ nhật chứa các hình vuông nhỏ (có kích thước 1x1). Các cửa sổ đã mở phụ thuộc vào vị trí và kích thước của nó, có thể một phần hoặc toàn bộ bao trùm lên những cửa sổ đã được mở sớm hơn. Chúng ta có thể đóng cửa sổ bằng con chuột máy tính, nếu chúng ta kích chuột vào hình vuông nhỏ phía trên bên phải, trong giây lát cửa sổ sẽ được đóng. Hình vuông nhỏ của cửa sổ sẽ hiển thị rõ ràng nếu như không có hình vuông nào được mở sau nó mà chưa đóng. Viết chương xác định số lần kích chuột nhỏ nhất để đóng cửa sổ đã được mở đầu tiên. Dữ liệu: Vào từ tập tin văn bản Windows.inp - Dòng đầu tiên chứa số nguyên N, chính là số cửa sổ đã mở, 1 ≤ N ≤ 100. - Trong N dòng tiếp theo, mỗi dòng chứa 4 số nguyên R1, S1, R2 và S2, các số được viết cách nhau một dấu cách, 1 ≤ R1 ≤ R2 ≤ 10000, 1 ≤ S1 ≤ S2 ≤ 10000. R1, S1 là hàng, cột trên màn hình của hình vuông phía trên bên trái của cửa sổ. R2, S2 là hàng, cột trên màn hình của hình vuông phía dưới bên phải của cửa sổ. Các cửa sổ đã mở theo trật tự như đã xuất hiện trong tập tin dữ liệu vào. Chúng ta xem màn hình gồm các hàng, cột của các hình vuông nhỏ. Hàng được đánh số từ trên xuống dưới, cột được đánh số từ trái sang phải và hình vuông phía trên bên trái của màn hình ở hàng 1, cột 1. Kết quả: Ghi ra tập tin văn bản windows.out số lần kích chuột ít nhất để đóng cửa sổ đầu tiên. Ví dụ: windows.inp windows.inp windows.inp 3 3 3 3164 4163 3344 1246 2255 1122 2355 1436 5566 windows.out windows.out windows.out 3 2 1 Ghi chú: - Thí sinh không được sử dụng tài liệu - Giám thị không giải thích gì thêm. 2/2
SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI TỈNH – THPT QUẢNG NGÃI Năm học 2004-2005 HƯỚNG DẤN CHẤM ĐỀ CHÍNH THỨC Môn: Tin học - Bảng A Ngày thi: 05/12/2004 Bài 3: 10 điểm Giải thuật : Phải đảm cài đặt không dùng đệ quy. Dùng stack để khử đệ quy. Test chương trình với N = 5, N=7, N=9, N=11, N=15 Test 1 Test 2 Test 3 Test 4 Test 5 N=5 N=7 N=9 N=11 N=13 31 127 511 2047 8191 Cho điểm với các test Câu a Câu b Test 1 0,5 1,5 Test 2 0,5 1,5 Test 3 0,5 1,5 Test 4 0,5 1,5 Test 5 0,5 1,5 Bài 4: (10 điểm) Test 1: 0,5 điểm Test 2: 0,5 điểm Test 3: 1 điểm Test 4: 2 điểm Test 5: 3 điểm Test 6: 3 điểm Test1 Test 2 Test 3 windows.inp windows.inp windows.inp 3 3 3 3164 4163 3344 1246 2255 1122 2355 1436 5566 windows.out windows.out windows.out 3 2 1 Test3 Test 4 Test 5 windows.inp windows.inp windows.inp 30 40 50 6161 454 6798 948 7329 4383 8260 6535 7373 311 8578 2162 4539 3570 6826 5162 3233 6621 7834 6684 2705 4225 4836 5842 270 3788 3767 7556 2442 1447 6069 5693 4755 899 7763 2333 4102 3247 5928 5136 1969 1711 4548 4876 3855 2099 8069 7507 4107 2856 4277 4606 4118 5086 7622 7372 152 1478 8506 4119 37 1189 7245 5495 1873 2693 2406 6751 2551 435 7820 1722 525 4753 4052 5979 1612 2159 7294 2491 6780 354 8375 7338 827 4678 8792 8965 2710 7092 7177 7224 2403 4310 8480 5501 4110 2513 6549 6935 3059 1666 5150 8767 4399 2857 4631 5020 3/2
2292 850 3517 4988 489 5889 6279 7962 1864 1894 4326 8273 4873 1269 8506 4949 249 1997 3311 7619 623 379 4032 4965 367 2089 2926 2991 6175 3861 6983 8661 1217 8310 4021 8921 2746 2097 7138 6816 5911 7450 7306 8346 1108 2282 3796 2667 1930 1506 4184 7841 4280 1949 6108 3702 5326 606 8371 1752 3869 5203 8534 7039 917 684 2528 4737 832 294 8599 6546 1873 2013 8744 2749 1140 3896 6681 4220 5472 4369 8575 5540 2629 2499 8231 5444 4288 6452 4908 8843 3564 351 5635 7039 6282 2198 7000 4101 118 5423 6189 8878 5123 3832 6172 6872 5916 2686 6889 5680 5673 4660 6538 8479 4815 3619 6674 6358 3924 1215 7109 3245 2326 5102 4277 6713 1780 853 2983 3569 3097 2189 4570 8152 6070 37 8567 4804 629 3855 3482 8322 1048 7782 6274 8865 8300 1964 8694 7524 4400 1329 6310 2297 2038 1032 3942 8449 6157 1128 8655 8198 950 1948 3256 4020 1422 3777 3641 7859 1104 273 5378 1150 5138 2337 6043 4843 4808 639 7740 7569 4391 2374 5620 8904 4967 338 5484 8217 3600 723 5834 6541 237 4299 2995 6515 2819 934 3337 4315 5768 120 6663 5732 2584 111 6852 8879 4542 1585 5045 8947 1536 2658 2854 8927 2841 53 7934 893 4056 754 6391 1963 4516 7505 6802 8310 1351 1076 5105 8093 1948 3927 3053 5219 187 862 4252 3403 2795 3366 6997 6813 1064 1898 2810 2358 236 6972 8911 8773 3629 3359 4777 8958 3275 3781 8561 6584 1233 2724 7586 2867 7374 1019 8163 3709 4109 242 6481 4983 5705 6290 5846 6881 3816 6107 6291 8462 3291 2907 8742 8178 6482 2606 6544 7234 1816 6428 2175 7602 145 2694 5074 8981 4205 906 5392 8771 4521 4728 5580 8355 165 7249 8953 8664 1534 1704 8304 4779 506 1290 7887 2013 7540 7687 7802 8043 6703 621 8971 3745 2565 901 3892 8828 909 2027 6355 8788 4336 3338 7225 3506 965 3374 6937 4771 3302 2539 6870 8694 6017 4440 7094 6007 65 6975 217 8367 1856 785 6595 6410 996 8271 8222 8749 1066 5410 7247 7396 1232 860 3523 1430 windows.out windows.out windows.out 4 12 21 4/2