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…

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *