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
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

3 1 6 4
1 2 4 6
2 3 5 5
3
4 1 6 3
2 2 5 5
1 4 3 6
3
3 3 4 4
1 1 2 2
5 5 6 6
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

3 2 1
Test3 Test 4 Test 5
windows.inp windows.inp windows.inp
30
6161 454 6798 948
4539 3570 6826 5162
270 3788 3767 7556
4102 3247 5928 5136
4107 2856 4277 4606
37 1189 7245 5495
525 4753 4052 5979
827 4678 8792 8965
4110 2513 6549 6935
40
7329 4383 8260 6535
3233 6621 7834 6684
2442 1447 6069 5693
1969 1711 4548 4876
4118 5086 7622 7372
1873 2693 2406 6751
1612 2159 7294 2491
2710 7092 7177 7224
3059 1666 5150 8767
50
7373 311 8578 2162
2705 4225 4836 5842
4755 899 7763 2333
3855 2099 8069 7507
152 1478 8506 4119
2551 435 7820 1722

4280 1949 6108 3702
917 684 2528 4737
1140 3896 6681 4220
4288 6452 4908 8843
118 5423 6189 8878
5673 4660 6538 8479
2326 5102 4277 6713
6070 37 8567 4804
8300 1964 8694 7524
6157 1128 8655 8198
1104 273 5378 1150
4391 2374 5620 8904
237 4299 2995 6515
2584 111 6852 8879
2841 53 7934 893
1351 1076 5105 8093
2795 3366 6997 6813
236 6972 8911 8773
3275 3781 8561 6584
7374 1019 8163 3709
5705 6290 5846 6881
3291 2907 8742 8178
1816 6428 2175 7602
4205 906 5392 8771
165 7249 8953 8664
506 1290 7887 2013
6703 621 8971 3745
1864 1894 4326 8273
623 379 4032 4965
1217 8310 4021 8921

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