30/09/2018, 17:30
Giải thích thuật toán
Mình có một bài toán trong sách nhưng không hiểu thuật toán của nó.
Cho sâu s (độ dài không vượt quá 10^6) chỉ gồm 2 ký tự ‘A’ và ‘B’. Đếm số cách chọn cặp chỉ số (i, j) mà xâu con liên tiếp từ kí tự thứ i đến kí tự thứ j của xâu s có số lượng kí tự ‘A’ bằng số lượng kí tự ‘B’.
Input: Tệp AB.INP gồm 1 dòng duy nhất chứa xâu s
Output: Tệp AB.OUT một dòng duy nhất chứa 1 số là kết quả bài toán
Ví dụ:
AB.INP: ABAB
AB.OUT: 4
Đây là thuật toán của bài được viết bằng Pascal
const MAX = 1000000
fi = 'AB.INP';
fo = 'AB.OUT';
var s: ansistring
c: array[-MAX..MAX] of longint;
f: text;
i, sum: longint;
count: int64;
BEGIN
assign(f, fi); reset(f);
read(f, s);
close(f);
fillchar(c, sizeof(c), 0);
c[0] := 1;
sum := 0;
count := 0;
for i := 1 to length(s) do begin
if (s[i] = 'A') then sum := sum - 1;
else sum := sum + 1;
count := count + c[sum];
inc(c[sum]);
end;
assign(f, fo); rewrite(f);
write(f, count);
close(f);
END.
Mọi người có thể giải thích cho mình không? Mình xin cảm ơn
Bài liên quan
Mình thấy ý tưởng của thuật toán này rất hay
Giả sử các đoạn x là đoạn có số lượng A = B. Thì lúc đó tổng ở vị trí trước x và sau x là như nhau.
VD: AAB gia tri sum la -1 -2 -1
Do đó nếu các đoạn liên tiếp có AB bằng nhau thì các đoạn con kết thúc tại cuối x cũng băng c[sum] ( c[sum] sẽ đếm tất cả đoạn con kết thúc có giá trị = sum)
hay nói cách khác nếu s(x)= s(y) thì s(x-y) = 0 tức là đoạn con từ x-y có A=B
@pexea12: Chào bạn!
Thứ nhất, đây là 1 đoạn code trong sách thì ắt hẳn trong cuốn sách đó cũng phải có đề cập chút đỉnh về nó. Ví dụ như cái phần bạn đang đọc nói về cái gì, thuật toán gì, v.v. Tại sao bạn không bắt đầu từ quyển sách ấy?
Thứ hai, đây là 1 đoạn code khá đơn giản. ý tôi đơn giản ở đây là ý nghĩa của từng dòng code, sau khi dòng code chạy thì kết quả sẽ ra cái gì. Nên khó có khả năng đã hiểu thuật toán mà đọc lại không hiểu. Và ngược lại, đã không biết thuật toán nó như thế nào thì 1000 người chắc khó tìm được 1 người suy ngược lại được thuật toán với đoạn code trên.
Thứ ba, người ta lập trình thường đi từ ý tưởng, từ thuật toán đến việc thực hiện ý tưởng đó bằng ngôn ngữ lập trình. Và bạn đang làm điều ngươc lại.
Vài dòng suy nghĩ chia sẻ cùng bạn.
Thân!
Bài này ở trong “Tài liệu giáo khoa chuyên Tin quyển 1” bạn ạ, và chỉ có phần code.
Nếu đã có phần giải thích thuật toán thì mình cũng đã không đăng lên hỏi làm gì.
Bạn hiểu nhầm ý của câu hỏi mình rồi. Dù sao thì cũng cảm ơn lời khuyên của bạn.