01/10/2018, 10:11

Giúp đỡ giải thích code bài toán dãy ABC

giải thich giúp mình đoạn code

Dãy ABC:
Cho trước một số nguyên dương N ( N<= 100), hãy tìm một xâu chỉ gồm các ký tự A,B,C thỏa mãn các điều kiện sau:
*Có độ dài N
*Hai đoạn con bất kỳ liền nhau đều khác nhau. ( Đoạn con là 1 dãy các ký tự liên tiếp của xâu).
*Có ít ký tự C nhất.

CODE:

const
      InputFile = 'data1.inp';
      OutputFile = 'data1.out';
      max = 100;
var
      N,MinC : Integer;
      X,Best : array[1..max] of 'A'..'C';
      T      : array[0..max] of Integer;
      f      : Text;
function Same(i,l : Integer) : Boolean;
var
      j,k : Integer;
      begin
             j:= i - l; 
             for k:= 0 to l-1 do
                 if X[i-k] <> X[j-k] then
                    begin
                           Same := False; Exit;
                    end;
                  Same := True;
      end;
function Check( i: Integer) :boolean;
var
       l:Integer;
    begin
       for l:= 1 to i div 2 do 
           if Same (i,l) then
    begin
       Check := False; Exit;
    end;
       Check := True;
    end;    
procedure KeepResult;
begin
     MinC := T[N];
     Best := X;
end;
procedure Attempt( i: Integer); 
var
      j: 'A'..'C';
begin
      for j:= 'A' to 'C' do
      begin
      X[i] := j;
      if Check(i) then 
      begin
            if j = 'C' then T[i] := T[i-1] +1     
            else T[i] := T[i-1];
            if T[i] + (N-i) div 4 < MinC then 
                if i = N then KeepResult
                else Attempt(i+1);
      end;
      end;
end;
procedure PrintResult;
var
      i: Integer;
begin
      for i:= 1 to N do Write ( f,Best[i]);
      WriteLn(f);
      WriteLn(f,' " C " - Letter Count: ',MinC);
end;
begin
      Assign (f,InputFile);Reset(f);
      ReadLn (f,N);
      Close(f);
      Assign(f,OutputFile); Rewrite(f);
      T[0] := 0;
      MinC := N;
      Attempt (1);
      PrintResult;
      Close(f);
end.
vtrnnhlinh viết 12:21 ngày 01/10/2018

format code lại nhé, cái tiêu đề cũng nên rút gọn lại bạn nhé

HK boy viết 12:17 ngày 01/10/2018

Đề của bạn không rõ ràng lắm nhỉ :v

*Có ít ký tự C nhất.

Đáp án là không có kí tự C nào.

Hai đoạn con bất kỳ liền nhau đều khác nhau.

Tức là thế nào hả bạn? Kiểu như ABABC không thoả mãn ấy hả?

Cao Van Thanh Cgdt viết 12:26 ngày 01/10/2018

mình nhĩ thế này nè:
lọc ra các xâu chỉ gồm ABC dài N;
loại tất cả các xâu có hai đoạn con giống nhau;
đếm C xem xâu nào ít nhất;

nắng viết 12:23 ngày 01/10/2018

ko phải
vì ABABC có 2 đoạn AB liền kề giống nhau

nắng viết 12:18 ngày 01/10/2018

ukm
nhưng mà minh ko kiểu cái code trên lắm

Cao Van Thanh Cgdt viết 12:22 ngày 01/10/2018

Tóm tắc code:
Input: N;
Output: Chuỗi chỉ gồm kí tự A,B,C dài N và không có 2 chuỗi con bất kì giống nhau;
Thuật toán: BackTracking, đệ quy tại Attemp();

nắng viết 12:23 ngày 01/10/2018

đệ quy tại Attemp();

mình ko hiểu hàm same và hàm check
giải thích giúp mình

HK boy viết 12:17 ngày 01/10/2018

@mua_ta:
Hàm same(i, l) kiểm tra đoạn [i-2*l+1, i-l] và đoạn [i-l+1, i] có giống nhau không.
Hàm check(i) kiểm tra trong khoảng từ 1 đến i có đoạn nào giống nhau không.
Code này xấu thật, căn dòng bừa bãi. Bạn moi code ở đâu thế @@ Bạn cũng phải quen đọc code và tư duy đi chứ!

Cao Van Thanh Cgdt viết 12:25 ngày 01/10/2018

check chạy l từ 1 tới nửa độ dài của X (i),
gọi hàm same kiểm tra chuỗi con có độ dài l:
hàm same kiểm tra từng kí tự của chuỗi con này (từ i tới i-l) với chuỗi bên cạnh (từ i-l-1 tới 0)

Cao Van Thanh Cgdt viết 12:24 ngày 01/10/2018

code này nhức đầu, ai code cái này không thể nào tồn tại trong team

Nguyễn Đình Biển viết 12:21 ngày 01/10/2018

Bài này ở ví dụ nhánh cận trong DSAP của thầy Lê Minh Hoàng mà. Format code trong sách đẹp hơn =))

Bài liên quan
0