Hướng dẫn cho Ma trận "ảo diệu"


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: cuom1999

Đầu tiên chúng ta cần xử lý trường hợp \(m = 1\) hoặc \(n = 1\). Giả sử \(n = 1\), cần tìm cách xếp các số từ \(0\) tới \(2^m - 1\) lên một hàng sao cho 2 số kề nhau thì khác nhau đúng một chữ số trong hệ nhị phân. Đây chính là dãy Gray Code. Cách dựng như sau:

Giả sử đã dựng được cho dãy \(m\), ta sẽ dựng cho dãy \(m + 1\) như sau:

Gọi \(A\) là dãy \(m\). Với mỗi số trong \(A\), thêm số \(0\) vào cuối tạo thành dãy \(A_0\), thêm số 1 vào cuối tạo thành \(A_1\). Dãy \(m + 1\) là: \(A_0 + rev(A_1)\), nói cách khác lật ngược dãy \(A_1\) rồi ghép vào đuôi của \(A_0\).

Ví dụ, giả sử ta có dãy \(A=[00, 01, 11, 10]\) cho \(m = 2\). Ta có thể dựng cho \(m = 3\) như sau:

\(A_0 = [000, 010, 110, 100]\)

\(A_1 = [001, 011, 111, 101] \Rightarrow rev(A_1) = [101, 111, 011, 001]\)

Khi đó \(A_0 + rev(A_1) = [000, 010, 110, 100, 101, 111, 011, 001]\) là một dãy thỏa mãn cho \(m = 3\).


Trường hợp cho hình chữ nhật hoàn toàn tương tự. Ta cần tìm cách tăng \(n\) lên \(n+1\). Ví dụ ta có bảng \((2, 2)\) là:

\(\begin{bmatrix} 00 & 10 \\ 01 & 11 \end{bmatrix}\)

Cần tạo bảng \((3, 2)\). Có thể làm như sau:

Thêm \(0\) vào cuối mỗi số, ta được:

\(A_0 = \begin{bmatrix} 000 & 100 \\ 010 & 110 \end{bmatrix}\)

Thêm \(1\) vào cuối mỗi số, ta được:

\(A_1 = \begin{bmatrix} 001 & 101 \\ 011 & 111 \end{bmatrix}\)

Lật ngược bảng \(A_1\) theo chiều ngang rồi ghép vào phía dưới \(A_0\), ta được bảng \((3, 2)\):

\(\begin{bmatrix} 000 & 100 \\ 010 & 110 \\ 011 & 111 \\ 001 & 101 \end{bmatrix}\)



Bình luận

Không có bình luận nào.