Thuật toán loang

6a00e5536ab239883301a73dd2b493970d

Trong tuyển tập các đề thi tin học của Cuộc thi Olympic truyền thống 30 tháng 4 những năm 1999-2000 có bài này làm tôi nhớ mãi:

Cho một địa hình có dạng chữ nhật kích thước MxN. Mỗi vị trí (i, j) là một cây cột có độ cao là một số tự nhiên h[i][j] (i=1..M, j=1..N). Sau một trận mưa to, hãy tính tổng thể tích nước đọng lại trên địa hình.

Đây rõ ràng là một bài áp dụng triệt để thuật toán loang (loang dầu ăn hoặc nước đều được nhé).

Continue reading “Thuật toán loang”

A view of dynamic programming

canvas-army-knapsack-vintage-canvas-backpacks-girls

Let P be a problem. To solve P, we have a set of resources R which contains n elements { R(1), R(2), … R(n) }. Each subset of R (even empty one) can or cannot solve P but in case it can, there’s a cost of the solving. We have to choose a subset so that the solving cost is best (min or max).

We’ll consider the issue in term of dynamic programming.

Continue reading “A view of dynamic programming”

Thuật toán đàn kiến giải bài toán người du lịch

Marco Dorigo
Marco Dorigo (born 26 August 1961, in Milan, Italy)

Bài toán Người du lịch (Travelling Salesman Problem) là một trong những bài toán kinh điển và khó trong tin học. Có rất nhiều cách tiếp cận giải bài toán này ngay từ khi nó mới ra đời, như sử dụng quy hoạch tuyến tính, nhánh và cận (đã được đăng trên Tin học và Nhà trường), nhưng mới chỉ dừng lại ở các bộ dữ liệu nhỏ. Gần đây các cách tiếp cận về tiến hóa, như thuật toán di truyền được áp dụng có những kết quả khả quan hơn.

Xem tiếp tại đây

Thuật toán của game Lines98 (P.3)

Phần 3. Kiểm tra các viên bi ăn điểm

Có 3 kiểu ăn điểm trong game này:

  1. Kiểu Line: các viên bi cùng màu với số lượng từ 5 trở lên, nằm liên tiếp nhau, thằng hàng hoặc cột hoặc đường chéo.
  2. Kiểu Square: các viên bi cùng màu nằm kề cạnh nhau tạo thành 1 hình chữ nhật đặc có kích thước 2×2 hoặc 2×3.
  3. Kiểu Block: các viên bi cùng màu nằm kề cạnh nhau với số lượng từ 7 trở lên, tạo thành hình dạng bất kì.

Chúng ta sẽ xem xét lần lượt cả 3 kiểu trên:

Continue reading “Thuật toán của game Lines98 (P.3)”

Thuật toán của game Lines98 (P.2)

Phần 2. Tìm đường đi ngắn nhất

Khi người chơi chọn 1 viên bi ở vị trí (i1, j1) và chọn tiếp 1 ô trống ở vị trí (i2, j2). Ta cần di chuyển viên bi đó từ (i1, j1) đến (i2, j2) nếu có đường đi (phải là ngắn nhất), hoặc nếu không có đường đi thì phát ra âm thanh thông báo.

Đường đi là 1 dãy liên tiếp các ô trống (trừ ô đầu tiên ko cần trống, dĩ nhiên) kề cạnh nhau. Chú ý: 2 ô kề cạnh tức là chúng có chung 1 cạnh (nôm na là nằm sát nhau), trường hợp 2 ô chỉ chung đỉnh (nằm chéo nhau) thì ko được tính là kề cạnh.

Continue reading “Thuật toán của game Lines98 (P.2)”

Thuật toán của game Lines98 (P.1)

Lines98 - Katatunix

Bảng trò chơi 9×9 được mô tả bằng mảng 2 chiều: int a[9][9]. Trong đó, a[i][j] = c (0 <= c <= 7) là màu của viên bi tại cột i, hàng j. Quy ước c = 0 tức là không có viên bi nào ở vị trí đó.

Đánh số các ô từ 0 đến 80 theo thứ tự từ trên xuống dưới, từ trái qua phải.

Continue reading “Thuật toán của game Lines98 (P.1)”