Giải Thích Thuật Toán - Programming - Dạy Nhau Học Trang chủ » độ Dài Xâu Không Vượt Quá » Giải Thích Thuật Toán - Programming - Dạy Nhau Học Có thể bạn quan tâm độ Dài Xâu Rỗng độ Dài Xâu Trong Pascal đổ đà Kiềng Nhà Cấp 4 đo đa Ký Giấc Ngủ Bao Nhiêu Tiền đo đa Ký Giấc Ngủ Là Gì Giải thích thuật toán programming pascal algorithm pexea12 (Dung Nguyen) July 26, 2022, 2:50am #1 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 xâ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 2 Likes Gio (Gió) July 7, 2015, 5:10pm #2 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 4 Likes Khai_Quach (Khải Quách) July 8, 2015, 1:12pm #3 @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! pexea12 (Dung Nguyen) July 26, 2015, 11:25am #4 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. 1 Like A_E (A E) July 26, 2022, 2:39am #5 tiền bối có thể giải thích rõ hơn với x,y -> i,j và chỗ inc(s[sum]) được khôn ạ ? DayNhauHoc's Discord Học C++ Free? Click Blog Dạy Nhau Học Tự Học Lập Trình 83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao? Từ khóa » độ Dài Xâu Không Vượt Quá Độ Dài Tối đa Của Xâu Kí Tự Trong PASCAL Là: Giải Bài Tập Tin Học 11 - Bài 12: Kiểu Xâu [PDF] Chuyên đề Xử Lý Xâu Chuyên đề Xâu Kí Tự - Tài Liệu Text - 123doc Câu Hỏi Trắc Nghiệm Kiểu Xâu | Computers - Quizizz Kiểu Xâu Ký Tự Với độ Dài Lớn Hơn 255 Ký Tự Trong Free Pascal Trong Các Phát Biểu Sau, Phát Biểu Nào Là Sai? A. Xâu Không Có Kí Tự ... Kiểu Dữ Liệu Xâu Kí Tự Trong Pascal - Ôn Thi HSG Cho Sâu S Có độ Dài Không Qúa 255 Kí Tự Chỉ Gồm Các Kí Tự Chữ Cái ... Giải Bài Tập Tin Học 11 - Bài 12: Kiểu Xâu - Nội Thất Hằng Phát Một Vài Bài Tập Về Palindrome - VNOI Một Số Bài Toán Quy Hoạch động điển Hình - VNOI