Kênh 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!
Wednesday, January 22, 2014



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.
1213213khô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–kk+1)..(i–k)] và v[ik+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

0 comments:

Post a Comment

Popular Posts