TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH
tải về 2.51 Mb.
|
2.2 Xâu thu gọnMột xâu chỉ gồm các chữ cái A, B, C,...,Z có thể được viết gọn theo các quy tắc sau: 1. Xm – gồm m chữ cái X; 2. (S)m – gồm m lần viết xâu thu gọn S. Nếu m = 0 thì đoạn cần viết sẽ được bỏ qua, nếu m = 1 thì có thể không viết m. Thí dụ, (AB3 (C2D)2 (C5D)0)2A3 là xâu thu gọn của xâu ABBBCCDCCDABBBCCDCCDAAA. Cho xâu thu gọn s. Hãy viết dạng đầy đủ (còn gọi là dạng khai triển) của xâu nguồn sinh ra xâu thu gọn s. Trong xâu thu gọn có thể chứa các dấu cách nhưng các dấu cách này được coi là vô nghĩa và do đó không xuất hiện trong xâu nguồn. Thuật toán Ta triển khai theo kỹ thuật hai pha. Pha thứ nhất: Duyệt xâu s và tạo ra một chương trình P phục vụ cho việc viết dạng khai triển ở pha thứ hai. Pha thứ hai: Thực hiện chương trình P để tạo ra xâu nguồn. Pha thứ nhất: Duyệt từng kí tự s[v] và quyết định theo các tình huống sau:
Với thí dụ đã cho, sau pha 1 ta sẽ thu được chương trình P gồm các dòng lệnh như sau:
Pha thứ hai: Thực hiện chương trình P. Ta thực hiện từng dòng lệnh của chương trình từ dòng 1 đến dòng n. Với thí dụ đã cho, sau khi thực hiện 4 dòng lệnh đầu tiên ta thu được kết quả ABBBCCD. Tiếp đến dòng lệnh 5 cho ta biết cần thực hiện việc lặp 2 lần các lệnh từ dòng 3 đến dòng 5. Sau mỗi lần lặp ta giảm giá trị của cột m tương ứng. Khi m giảm đến 0 ta cần khôi phục lại giá trị cũ của m. Muốn vậy ta cần thêm một cột nữa cho bảng. Cột này chứa giá trị ban đầu của m để khi cần ta có thể khôi phục lại. Ta sẽ gọi cột này là R. Theo giải trình trên, sau khi thực hiện dòng 5 ta thu được xâu ABBBCCDABBBCCD. Với dòng lệnh 6, lập luận tương tự ta thu được xâu ABBBCCDABBBCCDABBBCCDABBBCCD Cuối cùng, sau khi thực hiện dòng lệnh 7 ta thu được kết quả ABBBCCDABBBCCDAAA Độ phức tạp Cỡ n, trong đó n là số kí tự trong xâu input. (* XauGon.pas *) uses crt; const mn = 500; BL = #32; NL = #13#10; ChuSo = ['0'..'9']; ChuCai = ['A'..'Z']; type mi1 = array[0..mn] of integer; mc1 = array[0..mn] of char; var M, T, R, st: mi1; { M: so lan lap; T: tu; R: luu, st: stack } c: mc1; { Lenh } p: integer; { ngon stack } s: string; v: integer; { chi dan cua s } n: integer; { so dong lenh } procedure Cach; begin while (s[v] = BL) do inc(v); end; function DocSo: integer; var so: integer; begin so := 0; Cach; if Not (s[v] in ChuSo) then begin DocSo := 1; exit; end; while (s[v] in ChuSo) do begin so := so*10 + (Ord(s[v]) - ord('0')); inc(v); end; DocSo := so; end; procedure LenhDon(ch: char); var so: integer; begin inc(v); so := DocSo; if so = 0 then exit; inc(n); C[n] := ch; M[n] := so; end; procedure NapNgoac; begin inc(v); inc(p); st[p] := n+1 end; procedure LenhLap; var tu, so: integer; begin inc(v); tu := st[p]; dec(p); so := DocSo; if (so = 0) then n := tu-1; if (so < 2) then exit; inc(n); C[n] := '#'; M[n] := so; T[n] := tu; R[n] := so; end; procedure Pha2; var i,j: integer; begin for i := 1 to n do begin write(NL,i,'. ',C[i],BL,M[i],BL); if C[i] = '#' then write(T[i],BL,R[i]); end; i := 1; while (i <= n) do begin if (C[i] = '#') then begin dec(R[i]); if (R[i] = 0) then begin R[i] := M[i]; inc(i) end else i := T[i]; end else begin for j := 1 to M[i] do write(C[i]); inc(i); end; end; end; procedure KhaiTrien(var s: string); var i: integer; begin s := s + '#'; v := 1; p := 0; while (s[v] <> '#') do begin if (s[v] in ChuCai) then LenhDon(s[v]) else if (s[v] = '(') then NapNgoac else if (s[v] = ')') then LenhLap else inc(v); end; write(NL,s , ' = '); Pha2; end; BEGIN s := ' (AB3(C2D)2(C5D)0)2A3'; KhaiTrien(s); readln; END. // DevC++: XauGon.cpp #include #include #include using namespace std; // D A T A A N D V A R I A B L E const int mn = 500; const char BL = 32; char C[mn]; // noi dung lenh int M[mn]; // so lan lap int T[mn]; // lap tu dong lenh nao int R[mn]; // luu gia tri M int n; // con dem dong lenh char s[mn]; // xau thu gon int v; // chi so duyet s int st[mn]; // stack int p; // chi so ngon stack st // P R O T O T Y P E S void KhaiTrien(char *); void LenhDon(char); void LenhLap(); int DocSo(); void Cach(); bool LaChuSo(char); bool LaChuCai(char); void Pha2(); // I M P L E M E N T A T I O N int main() { strcpy(s," (AB3(C2D)2(C5D)0)2A3"); KhaiTrien(s); cout << endl; system("PAUSE"); return EXIT_SUCCESS; } bool LaChuCai(char c) { return (c >= 'A') && (c <= 'Z'); } bool LaChuSo(char c) { return (c >= '0') && (c <= '9'); } void Cach() { while (s[v] == BL) ++v; } int DocSo() { int so = 0; Cach(); if (!LaChuSo(s[v])) return 1; while (LaChuSo(s[v])) { so = so*10 + int(s[v]-'0'); ++v; } return so; } void LenhDon(char ch) { int so; ++v; so = DocSo(); if (so == 0) return; ++n; C[n] = ch; M[n] = so; } void LenhLap() { int so; ++v; // bo qua dau ) so = DocSo(); int tu = st[p--]; if (so == 0) { n = tu-1; return; } if (so == 1) return; ++n; C[n] = '#'; M[n] = R[n] = so; T[n] = tu; } void KhaiTrien(char *s ) { // Pha1 p = 0; n = 0; // init for (v = 0; s[v];) { if (LaChuCai(s[v])) LenhDon(s[v]); else if (s[v] == '(') { st[++p] = n+1; ++v; } else if (s[v] == ')') LenhLap(); else ++v; } Pha2(); } void Pha2() { int i, j; cout << endl << s << " = "; i = 1; while (i <= n) { if (C[i] == '#') { --R[i]; if (R[i] == 0) { R[i] = M[i]; ++i; } else i = T[i]; } else { for (j = 1; j <= M[i]; ++j) cout << C[i]; ++i; } } } Каталог: tailieu tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1 tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam tải về 2.51 Mb. Chia sẻ với bạn bè của bạn:
|