Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



Minh muốn làm một thiếp chúc tết Quý Mùi có nền được tạo bởi 2ndò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 2ndò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;


  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.

 
Frank Gray là nhà vật lý học Mỹ làm nghiên cứu viên tại hãng Bell Labs với hàng loạt phát minh có giá trị được ứng dụng trong truyền hình, cơ học, điện tử và toán học. Năm  1947 Gray đăng ký bằng phát minh về mã nhị phân phản hồi sau này được gọi là mã Gray.
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
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts