Link giải đề thi olympic tin học 2010 và 2011
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (55.57 KB, 4 trang )
Giải đề thi Olympic Tin học 2010 và 2011. Một số kỹ năng cần thiết.
Nội dung thi:
- Chuyên: Thuật toán.
- Không chuyên: Excel + Thuật toán.
- Cao đẳng (Thường có 1 bài chung giữa đôi một của ba nhóm này).
(Do mục đích sư phạm nên các link download trong bài viết được sắp xếp tuần tự,
từng link một. Đây là ý đồ của người viết. Còn không, bạn có thể vào thư mục để
download luôn một thể, link download ở cuối bài)
1. Về phần thi Excel
Đây là phần thi hay cho khối Cao đẳng và Không chuyên. Nguyên tắc để làm tốt phần thi này
là:
- Xác định phần thi này là khó. Nguyên nhân khó là vì thông thường khi ta làm bài thi Excel ở
Trường thì các Thầy Cô dường như đã giúp chúng ta định hướng được từng bước đi cụ thể như
thế nào trong đề thi rồi. Còn đối với Olympic hình như là không có điều đó. Vì vậy, thí sinh phải
tự xác định từng bước vấn đề của mình là gì. Nắm được vấn đề then chốt sẽ hóa giải được
toàn bộ phần thi này.
- Khi đọc đề phải đọc thật kỹ để phân tích mình sẽ cần phải thực hiện những bước trung gian
nào. Tránh hiện tượng: lạc giữa một rừng công thức của Excel, chẳng biết đi đâu và về đâu.
- Và đôi khi cần một chút thông minh (chỉ một chút thôi). Có thể rèn việc này bằng cách hiểu
thật ngọn ngành, chi tiết từng hàm thông dụng của Excel một.
Ví dụ: Bài 1 về Excel trong Đề thi Khối Cao đẳng
2010: />Lời giải: />
2. Về phần thi thuật toán
Đây là phần thi hay vì nó tổng hợp những kiến thức bạn học về thuật toán, cấu trúc dữ liệu, và
cả kinh nghiệm làm bài nữa.
Nguyên tắc để làm tốt phần thi này là:
- Thứ nhất: Một triết lý bất di bất dịch tồn tại từ lâu là:
Cấu trúc dữ liệu + Giải thuật = Chương trình
đây vẫn là nguyên lý thường trực.
- Thứ hai: Cần đọc kỹ đề, chỉ khi hiểu đề ta mới có thể phân tích bằng suy nghĩ tự nhiên xem
cần cài đặt cấu trúc dữ liệu nào thì phù hợp. Đồng thời chọn một thuật toán để có thể ăn điểm
qua từng test.
Việc đọc kỹ đề cũng giúp bạn không bị choáng ngợp khi mới đọc đề. Nếu bị choáng gần như
ta đã đánh mất một nửa thành công. Vì vậy, việc chuẩn bị tư tưởng thoải mái, tâm thế vững
vàng khi thi là cần thiết.
Trong thi Olympic thì việc làm đúng, cài đặt đúng không đồng nghĩa với việc ăn điểm mỗi test.
Nguyên nhân là mỗi test thường bị giới hạn thời gian chạy. Nếu quá thời gian chạy sẽ không
được tính điểm cho test đó.
Lời khuyên:
+ Máy tính làm việc với kiểu nguyên sẽ nhanh hơn.
+ Máy tính truy cập vào mảng cũng nhanh hơn.
+ Nhập/xuất file nên cẩn thận. Nhưng không nên cẩn thận quá vì việc nhập/xuất làm chậm việc
chạy chương trình. Tất nhiên, ta vẫn phải nhập/xuất file ít nhất 1 lần để đọc và ghi dữ liệu.
- Thứ ba: Nên học kỹ một số thuật toán thông dụng: Sắp xếp nhanh, Sắp xếp nhanh dựa
trên mảng chỉ dẫn [Tìm hiểu tại đây], Tìm kiếm nhị phân, Quy hoạch động, Thuật toán quay
lui, Các thuật toán về đồ thị: Thuật toán tìm đường đi ngắn nhất gồm Dijkstra và Floyd, Thuật
toán loang theo chiều rộng, Thuật toán loang theo chiều sâu và một số cấu trúc dữ liệu, thuật
toán khác không được học trong Đại học... Học được càng nhiều thuật toán, cấu trúc dữ liệu
bạn càng có cơ hội chọn ra một thuật toán phù hợp để giải bài toán. Và thực hành nhiều là cách
duy nhất để nhớ tất cả các thuật toán, cấu trúc dữ liệu này.
- Thứ tư: Nên vẽ, viết nháp ra giấy (bước này gọi là bước trực quan hóa) vì con người làm việc
với tư duy trực quan nhanh hơn với tư duy trừu tượng. Ta viết ra giấy xem giải quyết như thế
nào, cần làm những thao tác gì rồi tổng quát hóa (hay còn gọi là trừu tượng hóa) nên thành
chương trình.
- Thứ năm: Tìm hiểu đặc tính của ngôn ngữ lập trình mình sử dụng. Ví dụ như C và C++, tư
tưởng của chúng hầu hết dựa trên khái niệm con trỏ. Con trỏ của C/C++ rất linh hoạt, sử dụng
được nhuần nhuyễn con trỏ sẽ giúp sức cho bạn rất nhiều.
- Thứ sáu - Cuối cùng: ĐỌC NHIỀU và LÀM THẬT NHIỀU. Đồng thời biết cách so sánh với
những bài toán đã biết sẽ cho các bạn kinh nghiệm làm bài. Đây cũng là một bước quan
trọng trong tiến trình giải quyết bài toán.
Ví dụ 1: Bài 2 - Khối Cao đẳng 2010: Rèn luyện tư duy cho người lập trình. Với bài này, thao tác
thứ 4 (Trực quan hóa) rất quan trọng.
Lời giải: />
Ví dụ 2: Bài 3 - Đề thi Cao đẳng 2010. Rèn luyện suy nghĩ tự nhiên. Tức là: "nghĩ gì, làm
nấy". Bạn hãy nghĩ xem nếu gặp bài toán này thì bạn sẽ thực hiện bằng tay từng bước như
thế nào.
Riêng nội dung đề bài này đã nhấn mạnh rất rõ tầm quan trọng của cấu trúc dữ liệu và giải
thuật trong việc xây dựng chương trình tính toán.
Trong trường hợp bài toán yêu cầu thêm: Đưa ra thứ tự giải các bài toán (trong thực tế thì bình
thường vẫn phải đưa ra thứ tự này) thì cần phải giữ lại chỉ số của các bài toán nên thuật
toán phải là:
Thuật toán: Sắp xếp nhanh dựa trên mảng chỉ dẫn.
Lời giải: />Một lời giải khác dùng thuật toán sắp xếp bình thường và chậm hơn (nhưng dễ nhớ
hơn): />
Như vậy, ta thấy tính hai mặt của thuật toán: Thuật toán chạy càng nhanh thì càng phức
tạp và ngược lại, thuật toán càng đơn giản, càng dễ cài đặt thì chạy chậm hơn.
Ví dụ 3: Bài 4 - Khối Cao đẳng 2010. Bài này giúp ta biết cách so sánh với cấu trúc dữ liệu
ngăn xếp đã biết.
Thuật toán: Gần giống với ngăn xếp nhé.
Lời giải: />Đề thi khối không chuyên - 2010: />Ví dụ 4: Bài 2 - Khối không chuyên 2010 - Máy tính làm việc với số nguyên sẽ nhanh hơn.
Lời giải: Bạn hãy sửa lại Code của bài này. Bài này thực hiện chậm nhưng là Code này vẫn là
chuẩn mực cho lớp các bài toán khác: />3fu640d26cy3ej0
Ví dụ 5: Bài 4 - Khối không chuyên 2010
Thuật toán: Vẽ ra giấy sẽ hình dung ra.
Lời giải: />Đề thi khối chuyên Tin 2010: />Ví dụ 6: Bài 2 - Khối chuyên Tin 2010 - Máy tính làm việc với mảng sẽ nhanh hơn.
Lời giải: Mình cài đặt khác với ý tưởng đã nêu ở trên. Nhưng Code bài này vẫn rất chuẩn mực
cho lớp các bài toán tổng quát khác: />pm615d0pz90bhz4
Ví dụ 7: Bài 3 - Khối chuyên Tin 2010
Thuật toán: Sử dụng thuật toán Floyd trên đồ thị.
Lời giải: />Ví dụ 8: Bài 4 - Khối chuyên Tin 2010
Thuật toán: Đây là bài toán sử dụng thuật toán tìm kiếm trên xâu. Ở đây, ta sử dụng cấu trúc
dữ liệu: Suffix Array hoặc cấu trúc Trie. Mình chưa code bài này nên chỉ đề xuất vậy.
Qua đây, ta cũng nhận thấy tầm quan trọng của cấu trúc dữ liệu: Nếu ta sử dụng các cấu
trúc dữ liệu trước đây thì hoặc là không giải được, hoặc là giải được nhưng rất khó khăn khi cài
đặt (Ví dụ: cài đặt bảng băm cho bài này cũng được, nhưng không ăn hết được các test).
Xét đến đề thi năm 2011
Đề Khối Cao đẳng năm 2011: />Ví dụ 9: Bài 3 - Khối Cao đẳng 2011: Không khác gì Bài 3 - Đề thi Cao đẳng 2010 (Tất nhiên có
thay đổi chút xíu, nhưng không đáng kể).
Kết luận: Ta thấy được sự cần thiết khi so sánh để thấy sự tương đồng giữa bài toán cần giải
quyết với những bài toán đã biết trước đó.
Đề Khối không chuyên năm 2011: />Ví dụ 10: Bài 4 - Khối không chuyên 2011
Ở đây, mình in thêm cả những số thuộc vào tập số này.
Thuật toán: Quay lui (Duyệt toàn bộ).
Lời giải: />
- Các file .zip là file mình code năm 2010. Các bạn chạy file .dev.
- Các file .c là code năm 2012.
Một số bài giữa các khối trùng nhau, các bạn xem ở trong đề sẽ thấy.
Toàn bộ thư mục: />Xem thêm: Đạo lập trình - />
Sơn,
