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.
Bài liên quan
format code lại nhé, cái tiêu đề cũng nên rút gọn lại bạn nhé
Đề của bạn không rõ ràng lắm nhỉ :v
Đáp án là không có kí tự C nào.
Tức là thế nào hả bạn? Kiểu như
ABABC
không thoả mãn ấy hả?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;
ko phải
vì ABABC có 2 đoạn AB liền kề giống nhau
ukm
nhưng mà minh ko kiểu cái code trên lắm
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();
mình ko hiểu hàm same và hàm check
giải thích giúp mình
@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ứ!
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)
code này nhức đầu, ai code cái này không thể nào tồn tại trong team
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 =))