Hướng dẫn cho Ma trận "ảo diệu"
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:
Đầ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