Từ chuẩn

Một từ loại M là một dãy các chữ số, mỗi chữ số nằm trong khoảng từ 1 đến M. Số lượng các chữ số có mặt trong một từ được gọi là chiều dài của từ đó. Từ loại M được gọi là từ chuẩn nếu nó không chứa hai khúc (từ con) liền nhau mà giống nhau.

               a) Với giá trị N cho trước, hiển thị trên màn hình một từ chuẩn loại 3 có chiều dài N.

               b) Với mỗi giá trị N cho trước, tìm và ghi vào tệp văn bản tên TUCHUAN.OUT mọi từ chuẩn loại 3  có chiều dài N.

 1 £ N £ 40000.

Thí dụ:

1213123 là từ chuẩn loại 3, chiều dài 7.

1213213 không phải là từ chuẩn vì nó chứa liên tiếp hai từ con giống nhau là 213.

Tương tự, 12332 không phải là từ chuẩn vì chứa liên tiếp hai từ con giống nhau là 3.

Bài giải

Ta dùng mảng v[1..n] để lưu từ cần tìm. Tại mỗi bước i ta xác định giá trị v[i] trong khoảng 1..m sao cho v[1..i] là từ chuẩn.

Điều kiện P: v[1..i] là từ chuẩn.

Điều kiện Q: Dừng thuật toán theo một trong hai tình huống sau đây:

s         nếu i = n thì bài toán có nghiệm v[1..n].

s         nếu i = 0 thì bài toán vô nghiệm.

TimTu1: Tìm một nghiệm.

{Khởi trị mọi vị trớ bằng 0 }

for i :=  1 to n do v[i] :=  0;

i :=  1;

repeat

if i > n then {co nghiem v[1..n]}

begin

KetQua1(n); {in nghiem v[1..n]}

exit;

end;

if i < 1 then  {vo nghiem}

begin

KetQua1(0);

exit;

end;

         j  :=  Tim(i);

if j > 0 then

 begin

            v[i]  :=   j;

   inc(i) {tiến}

 end

else     

   begin {Lựi}

             v[i] :=  0;

             dec(i);

            end;

until false;

Hàm Tim hoạt động như sau: duyệt các giá trị tại vị trí v[i] của từ v[1..i] kể từ v[i] + 1 đến m sao cho v[1..i] là từ chuẩn.

Tim = true nếu tồn tại một giá trị v[i] như vậy. Ngược lại, nếu với mọi v[i] = v[i] + 1..m từ v[1..i] đều không chuẩn thì Tim = false.

function Tim(i: integer): Boolean;

begin

Tim :=  true;

while v[i] < 3 do

begin

  inc(v[i]);

  if Chuan(i) {v[1..i] la tu chuan}

       then exit;

end;

Tim :=  false;

end;

Để kiểm tra tính chuẩn của từ v[1..i], ta lưu ý rằng từ v[1..i-1] đã chuẩn (tính chất P), do đó chỉ cần khảo sát các cặp từ có chứa v[i], cụ thể là khảo sát các cặp từ có chiều dài k đứng cuối từ v. Đó là các cặp từ v[(i–k–k+1)..(i–k)] và v[i–k+1..i] với k = 1..(i div 2). Nếu với mọi k như vậy hai từ đều khác nhau thì Chuan=true. Ngược lại, Chuan = false.

function Chuan(i: integer): Boolean;

var k: integer;

begin

Chuan :=  false;

for k :=  1 to (i div 2) do

if Bang(i,k) then exit;

Chuan :=  true;

end;

Hàm Bang(i,k) kiểm tra xem hai từ kề nhau chiều dài k tính từ i trở về trước có bằng nhau hay không.

Hai từ được xem là khác nhau nếu chúng khác nhau tại một vị trí nào đó.

function Bang(i,k: integer): Boolean;

var j: integer;

begin

Bang :=  false;

for j :=  0 to k-1 do

if v[i-j] <> v[i-k-j] then exit;

Bang :=  true;

end;

Thủ tục TimTu tìm mọi nghiệm của bài toán.

(*  Pascal  *)

(*------------------------

        Tu chuan

-----------------------*)

{$B- }

uses crt;

const

MN = 40; {Cho cau b: tim moi nghiem }

MN1 = 40000; {Cho cau a: tim 1 nghiem }

gn = 'TuChuan.OUT';

var

v: array[0..MN1] of byte; {chua nghiem }

n: integer; {chieu dai tu: tinh chat Q }

g: text; {output file }

(*----------------------------------------

Kiem tra hai tu ke nhau, chieu dai k

tinh tu vi tri i tro ve truoc co bang nhau ?

----------------------------------------*)

function Bang(i,k: integer): Boolean; tự viết

(*-------------------------------------------

Kiem tra tu v[1..i] co la tu chuan ?

------------------------------------------*)   

function Chuan(i: integer): Boolean; tự viết

(*------------------------------------

Sua v[i] de thu duoc tu chuan

Tim = true: Thanh cong

Tim = false: That bai

-------------------------------------*)

function Tim(i: integer): Boolean; tự viết

(*-------------------------------------

Hien thi ket qua, tu v[1..n]

(Cau a: tim 1 nghiem)

-------------------------------------*)

procedure KetQua1(k: integer);

var i: integer;

begin

writeln;

if k = 0 then write('Vo nghiem')

else for i :=  1 to k do write(v[i]);

writeln;

end;

(*----------------------------------------

Quay lui: tim 1 nghiem cho bai toan

tu chuan chieu dai len, chi chua cac

chu so 1..lim

----------------------------------------*)

procedure TimTu1(len: integer); tự viết

(*--------------------------------

Test cau a: Tu chuan dai 200

chi chua cac chu so 1, 2, 3

--------------------------------*)

procedure Test1;

begin

clrscr;

TimTu1(200);

readln;

end;

(*---------------------------------

    Ghi mot nghiem vao file

---------------------------------*)

procedure KetQua(d: integer);

var i: integer;

begin

if d = 0 then write(g,'Vo nghiem')

else

begin

write(g,'Nghiem thu ',d,': ');

for i :=  1 to n do write(g,v[i]);

writeln(g);

end;

end;

(*--------------------------------------------

      Cau b: Liet ke toan bo cac tu chuan

chieu dai len, chi chua cac chu so 1, 2,3

---------------------------------------------*)

procedure TimTu(len: integer);

var

      i: integer;

      d: longint;

begin

if (len < 1) or (len > MN) then exit;

n :=  len;

for i :=  1 to n do v[i] :=  0;

assign(g,gn);

rewrite(g);

i :=  1;

d :=  0;

repeat

if i > n then {tim duoc 1 nghiem v[1..n]}

begin

    inc(d);

    KetQua(d);

    i :=  n;

end;

if i < 1 then {da vet het}

begin

    if d = 0 then KetQua(0);

    close(g);

    write('OK'); readln;

    exit;

end;

           

if Tim(i) then inc(i) {tiến }

else   {Lui }

begin

v[i] :=  0;

dec(i);

            end;

until false;

end;

(*------------------------------------------

Test cau b: Liet ke toan bo cac

tu dai 16, chi chua cac chu so 1, 2,3

Ket qua ghi trong tep TuChuan.out

------------------------------------------*)

procedure Test;

begin

clrscr;

TimTu(16);

end;

BEGIN

Test;

END.

Với N = 16, M = 3, có tổng cộng 798 nghiệm, tức là 798 từ chuẩn chiều dài 16 tạo từ các chữ số 1, 2 và 3. Dưới đây là 20 nghiệm đầu tiên tìm được theo thuật toán.

Nghiem thu 1:  1213123132123121

Nghiem thu 2:  1213123132123213

Nghiem thu 3:  1213123132131213

Nghiem thu 4:  1213123132131231

Nghiem thu 5:  1213123132131232

Nghiem thu 6:  1213123132312131

Nghiem thu 7:  1213123132312132

Nghiem thu 8:  1213123132312321

Nghiem thu 9:  1213123212312131

Nghiem thu 10: 1213123212312132

Nghiem thu 11: 1213123212313212

Nghiem thu 12: 1213123212313213

Nghiem thu 13: 1213123212313231

Nghiem thu 14: 1213123213121321

Nghiem thu 15: 1213123213121323

Nghiem thu 16: 1213123213231213

Nghiem thu 17: 1213123213231232

Nghiem thu 18: 1213123213231321

Nghiem thu 19: 1213212312131231

Nghiem thu 20: 1213212312131232