Minh muốn làm một thiếp chúc tết Quý Mùi có nền được tạo bởi 2n
dòng, mỗi dòng là một dãy kí tự gồm n chữ cái ‘Q’ và ‘M’ sao cho hai dòng kề
nhau khác nhau tại đúng một vị trí, dòng cuối cùng cũng được coi là kề với dòng
đầu tiên. Giả sử bạn có thể giúp Minh làm điều đó. Với mỗi giá trị n và k cho
trước bạn hãy hiển thị dòng thứ k trong tấm thiếp trên. Các dòng được mã số từ
1 trở đi, 1 £
n £
30.
Thuật toán
n = 1
|
n = 2
|
n = 3
|
||
Q
M
|
Q
M
|
QQ
QM
|
QQ
QM
MM
MQ
|
QQQ
QQM
QMM
QMQ
|
M
Q
|
MM
MQ
|
|||
MQ
MM
QM
QQ
|
MMQ
MMM
MQM
MQQ
|
|||
Thiết kế các
thiếp T(1), T(2) và T(3)
|
||||
Kí hiệu T(n) là
tấm thiếp được thiết kế với giá trị n cho trước. T(n) ở dạng đầy đủ sẽ chứa 2n
dòng. T(1) chứa hai dòng là ‘Q’ và ‘M’.
Giả sử ta đã thiết kế xong T(n-1), khi đó T(n) sẽ được thiết kế theo 3 bước sau.
Bước 1. Lật: Lật
T(n-1) xuống phía dưới, tức là lấy đối xứng
qua đường kẻ ngang cuối tấm thiếp. Ta kí hiệu phần đối xứng của T(n-1) là T*(n-1).
Bước 2. Thêm Q:
Viết thêm kí tự ‘Q’ vào mọi dãy của T(n-1).
Bước 3. Thêm M:
Viết thêm kí tự ‘M’ vào mọi dãy của T*(n-1).
Ta có thể viết
thêm kí tự vào đầu hoặc cuối dãy. Trong bài này ta chọn đầu dãy.
Dễ dàng chứng
minh rằng thuật toán trên sinh ra các tấm thiếp thỏa các yêu cầu của đầu bài.
Thật vậy, ta gọi P là tính chất “Hai dòng kề nhau khác nhau tại đúng một vị
trí”. Khi đó T(1) thỏa P là hiển nhiên vì nó chỉ chứa 2 dòng ‘Q’ và ‘M’. Giả
sử T(n-1) thỏa P.
Khi đó đương nhiên T*(n-1) cũng thỏa
P. Do phép đối xứng, dòng cuối cùng của T(n-1) và dòng đầu tiên của T*(n-1) giống nhau nên khi thêm ‘Q’ cho dòng
trên và ‘M’ cho dòng dưới chúng sẽ khác nhau tại vị trí thêm đó. Tương tự, dòng
đầu tiên của T(n-1) và dòng
cuối cùng của T*(n-1) giống nhau
nên khi thêm ‘Q’ cho dòng đầu và ‘M’ cho dòng cuối chúng sẽ khác nhau tại vị
trí thêm.
Dựa theo thuật
toán trên ta viết hàm Line(n,k) sinh ra dòng thứ k trên tấm thiếp T(n). Thí dụ,
Line(3,7) = ‘MQM’. Hàm sẽ lặp n lần, mỗi
lần sinh 1 kí tự theo chiều ngược lại với kiến thiết trên. Ta thấy, nếu k > 2n-1 thì chứng tỏ dòng k nằm trong T*(n-1), do đó kí tự đầu dòng của nó sẽ phải là
‘M’ và dòng từ T(n-1) lật xuống
dòng k sẽ có chỉ số 2n-k+1, ngược lại, nếu k £ 2n-1 thì dòng k nằm trong T(n-1), do đó kí tự đầu dòng của nó là
‘Q’.
(* Pascal *)
function Line(n:
integer; k: longint): string;
var s: string; m:
longint; i: integer;
begin
m := 1; m :=
m shl n; { m = 2^n }
for i := n
downto 1 do
begin
m := m
shr 1; { m div 2 }
if (k
<= m) then s := s + ‘Q’
else
begin
s := s + ‘M’; k
:= 2*m – k + 1;
end;
end;
Line := s;
end;
Mã Gray
Mã Gray của một số tự
nhiên k là số (k shr 1) xor k = (k div 2) xor k, trong đó xor là phép toán cộng
loại trừ theo bít: a xor b = 0 khi và chỉ khi a = b.
Các tính chất của mã
Gray
1. Mã Gray của hai số
tự nhiên khác nhau thì khác nhau: k1 ¹ k2 Þ Gray(k1) ¹ Gray(k2).
2. Mã Gray của hai số
tự nhiên liên tiếp khác nhau tại đúng 1 bit.
3. Gay(0) = 0; Gray(1)
= 1;
4. Nếu số x có n bit
thì Gray(2n-1) = 2n-1.
|
k
|
Gray(k)
|
GLine(4,k)
|
k
|
Gray(k)
|
GLine(4,k)
|
|
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
|
0: 0000
1: 0001
3: 0011
2: 0010
6: 0110
7: 0111
5: 0101
4: 0100
|
QQQQ
QQQM
QQMM
QQMQ
QMMQ
QMMM
QMQM
QMQQ
|
8: 1000
9: 1001
10: 1010
11: 1011
12: 1100
13: 1101
14: 1110
15: 1111
|
12: 1100
13: 1101
15: 1111
14: 1110
10: 1010
11: 1011
9: 1001
8: 1000
|
MMQQ
MMQM
MMMM
MMMQ
MQMQ
MQMM
MQQM
MQQQ
|
|
Mã Gray
và giá trị của hàm Gline của 16
số tự
nhiên đầu tiên k = 0..15.
|
|||||
Nhờ mã Gray ta có thể viết
hàm GLine(n,k) cho ra dòng k trong thiệp T(n)
một cách đơn giản như sau:
Bước 1. Tính x = Gray(k) = (k
shr 1) xor k = (k div 2) xor k.
Bước 2. Xét n bit thấp của x,
nếu là 1 thì viết ‘M’ nếu là 0 thì viết ‘Q’.
(* Pascal
*)
function Gray(k:
longint): longint;
begin Gray := (k
shr 1) xor k end;
function Gline(n:
integer; k: longint): string;
var s: string; i: integer;
const cc:
array[0..1] of char = ('Q','M');
begin
k := Gray(k);
s = ‘’;
for i := n-1 downto 0 do
s = s +
cc[(k shr i) and 1];
GLine := s;
end;
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét