Một số bài toán để ôn luyện tư duy khi ôn đội tuyển Olympic

– Bài toán hình xoắn ốc: Bài này dạng cơ bản là cho bình phương của một số nguyên n, tìm cách in ra màn hình vị trí các số bắt đầu từ 1 đến chính nó vào ma trận vuông n*n. Bài toán này luyện cho mình cách điều khiển vòng lặp for và while cho hợp lý và tối ưu. Có nhiều biến thế của bài này để ta có thể ôn luyện.

– Bài toán dò mìn, tìm miền liên thông…: một số bài toán cần sử dụng thuật toán loang để xử lý. Những bài toán như này liên quan đến việc xử lý các điểm lân cận nhau, cần lưu ý việc đánh dấu các điểm đã duyệt tránh bị lặp vô tận dẫn đến tràn bộ nhớ.

– Cộng, trừ, nhân số lớn: Với kiểu dữ liệu của ngôn ngữ lập trình thường bị giới hạn ở mức độ nhất định, để xử lý cộng, trừ, nhân với các con số có từ 10 chữ số trở lên là những số siêu siêu lớn thì kiểu dữ liệu của ngôn ngữ không thế xử lý được. Việc này buộc phải xử lý thủ công, chia để trị. Thực hiện phép tính như cách mà ta được học từ nhỏ. Đối với cộng-trừ ta dùng mảng để lưu từng chữ số sau đó xử lý cộng trừ từng số 1 theo đúng nguyên tắc từ hàng nhỏ hơn đến hàng lớn (từ hàng đơn vị, từ phải sang trái) và tuân thủ nguyên tắc cộng dồn (chính là nhớ). Đối với phép nhân thì tương tự nhưng lưu ý phép nhân chính là phép cộng nhiều số lại với nhau mà thôi.

– Số nguyên tố: Với số nguyên tố thì có muôn vàn kiểu bài toán liên quan, vì số nguyên tố có nhiều tính chất rất “đẹp”. Các bài toán đa phần là tìm số nguyên tố, check xem có phải số nguyên tố hay không, tìm số nguyên tố cùng nhau… Các bài toán này sẽ có 1 số thuật toán kinh điển để tìm, các bạn có thể tìm hiểu.

– Đệ quy: Bài toán kinh điển của đệ quy chính là bài toán Tháp Hà Nội. Cũng là một cách chia để trị, các bài toán đều quy về cùng 1 dạng, và chỉ cần xử lý được bài toán ở nhân thì sẽ giải được. Với đệ quy thường tốn bộ nhớ đệm để chờ từng lần lượt kết quả của từng lượt đệ quy nến có trường hợp tràn bộ nhớ đệm. Bài toán đệ quy thì có đệ quy quay lui nổi tiếng với bài toán 8 con hậu.

– Một số bài toán khác: tìm đường đi ngắn nhất, quy hoạch động… một số bài thuần toán như: số fibonaci, tính tích phân, tìm căn, tìm nghiệm gần đúng…

Hướng tiếp cận bài toán bằng cách vét cạn từng Số nguyên tố

Một bài học quý báu mà thầy Thắng có truyền lại cho đội O trong kỳ thi Olympic như sau:
Vào một năm nào đó, kỳ thi của đội anh Hinh hay anh Hùng dự ACM-ICPC có bài toán cần giải đại loại là cho 1 khoảng và in ra các số nguyên tố trong khoảng đó. Tất nhiên kết quả phải được đưa ra dưới x giây.
Xét về kỹ thuật thông thường ta buộc phải kiểm tra từng số trong khoảng đó và xác định xem đó là có phải số nguyên tố hay không? Với bài toán kinh điển kiểm tra có phải số nguyên tố hay không thì có nhiều thuật toán, nhưng số càng lớn thì càng cần nhiều thời gian hơn để kiểm tra. Và việc xử lý vấn đề thời gian là yếu tố quan trọng nhất vì với các thuật toán hiện tại thì không thể xử lý được trong khoảng thời gian mà ban tổ chức đưa ra…
Vì thi ACM-ICPC không chấm thuật toán mà tính pass hay không thông qua tập test của ban tổ chức. Tất nhiên nếu có danh sách tập test và kết quả của ban tổ chức thì chỉ cần IF ELSE cũng đạt điểm.
Một ý tưởng xử lý rất thông minh đó là ta tiến hành liệt kê ra 1 tập sẵn các số nguyên tố nằm trong phạm vi của đề của ban tổ chức trước, sau đó chương trình chỉ cần đọc file và lấy danh sách số nguyên tố trong khoảng mà đề bài yêu cầu. Độ phức tạp sẽ O(n).
Kết quả của đội là đã giải thành công bài toán, bài đã chấp nhận, file sinh danh sách số nguyên tố gần 1GB, mất gần hết thời gian cả cuộc thi.

Đây là bài toán kinh điển về kinh nghiệm xử lý vấn đề, nó thay đổi tư duy và cách tiếp cận bài toán. Cũng như là phải hiểu rõ phương thức và hoàn cảnh. Nó có thể ứng dụng trong nhiều trường hợp trong công việc và đời sống.

P/S: Tất nhiên cách này không thể áp dụng được trong cuộc thi Olympic vì cuộc thi Olympic là cuộc thi thuật toán, khi ta chưa thể code được chương trình nhưng ta đưa ra được quan điểm, giải thuật xử lý đúng đắn thì ban tổ chức vẫn có thể cộng điểm cho chúng ta.
Với bài toán trên nếu giới hạn dung lượng file thì cũng không thể đạt điểm cho bài toán này.