›
›

Sáng tạo trong Thuật toán và Lập trình với ngôn ngữ Pascal và C # - Tập 3

pdf 163 trang phuongnguyen 3870
Download
Bạn đang xem 20 trang mẫu của tài liệu "Sáng tạo trong Thuật toán và Lập trình với ngôn ngữ Pascal và C # - Tập 3", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfsang_tao_trong_thuat_toan_va_lap_trinh_voi_ngon_ngu_pascal_v.pdf

Nội dung text: Sáng tạo trong Thuật toán và Lập trình với ngôn ngữ Pascal và C # - Tập 3

  1. T Ủ SÁCH TRI THỨC DUY TÂN NGUYỄN XUÂN HUY S Á N G T Ạ O TRONG THUẬT TOÁN V À L Ậ P T R Ì N H với ngôn ngữ Pascal và C++ T ậ p 3 Tuyển các bài toán Tin nâng cao cho học sinh và sinh viên giỏi MỤC LỤC
  2. Lời nói đầu 4 Chương 1 Các thuật toán trên String 5 1.1 Xâu kí tự 5 1.2 Về tổ chức dữ liệu vào/ra 6 1.3 Data 6 1.4 Xâu con chung 8 1.5 Đoạn chung 9 1.6 Đoạn lặp 11 1.7 Từ điển 14 1.8 TEFI 17 1.9 E xiếc 20 Chương 2 Xử lí dãy lệnh và biểu thức 23 2.1 Val 23 2.2 Xâu thu gọn 26 2.3 Robot 29 2.4 Hàm nhiều biến 33 2.5 Files 38 2.6 Gen 44 2.7 Tối ưu hóa chương trình 44 2.8 Mức của biểu thức 45 2.9 Tháp 46 2.10 Mi trang 46 2.11 Xếp thẻ 49 2.12 Xếp xe 50 Chương 3 Cặp ghép 51 3.1 Chị Hằng 51 3.2 Domino 55 3.3 Thám hiểm 59 3.4 Show 64 3.5 Cặp ghép cực đại: Chị Hằng 2 70 Chương 4 Các phép lật và chuyển vị 75 4.1 Lật xâu 75 4.2 Lật số nguyên 76 4.3 Sân bay vũ trụ 77 4.4 Cân 81 4.5 Biprime 87 4.6 Chuyển bi 90
  3. 4.7 Lát nền 2 94 4.8 Test 103 4.9 Giải mã 105 Chương 5 Luyện tập từ các đề thi 110 5.1 Số nguyên tố cùng độ cao 110 5.2 Số nguyên tố cùng số bít 1 112 5.3 Cắt hình 112 5.4 Tổng nhỏ nhất 115 5.5 Lò cò 119 5.6 Chuyển tin 127 5.7 Mã BW 130 5.8 Tam giác Pascal 134 5.9 Sơn mô hình 138 5.10 Nhúng mô hình 141 5.11 Số sát sau nhị phân 144 5.12 Hàm f(n) 150 5.13 Hàm h(n) 151 5.14 Rhythm 151 5.15 Cóc 152 5.16 Trả tiền 154 5.17 Game 156 5.18 Robots 160
  4. Lời nói đầu Theo yêu cầu của bạn đọc, trong tập 3 này chúng tôi minh họa bằng hai ngôn ngữ lập trình là Pascal và Dev-C++. Pascal là ngôn ngữ lập trình mang tính sư phạm cao và được dùng để giảng dạy trong nhà trường phổ thông theo chương trình hiện hành. Dev-C++ là môi trường mã nguồn mở được các bạn sinh viên yêu thích và thường được chọn làm môi trường lập trình trong các cuộc đua tài quốc gia và quốc tế. Cả hai môi trường Free Pascal và Dev-C++ đều được cung cấp miễn phí trên Internet. Chúng tôi hy vọng rằng sẽ tiếp tục nhận được những ý kiến đóng góp quý báu của bạn đọc gần xa về nội dung và hình thức trình bày của bộ sách. Hà Nội, Mùa Xuân năm Dần 2010 Nguyễn Xuân Huy
  5. Chương 1 Các thuật toán trên String 1.1 Xâu kí tự Xâu kí tự là một dãy các kí tự viết liền nhau. Các kí tự được lấy từ một bảng chữ cái cho trước, thông thường là bảng mã ASCII. Trong các bài toán tin, kí tự thường được hiểu là chữ cái viết HOA hoặc viết thường theo trật tự bố trí trong bảng chữ cái tiếng Anh và các chữ số. Có thể hiểu xâu kí tự là một mảng một chiều chứa các kí tự. Đôi lúc ta gọi vắn tắt là xâu. Hiểu theo nghĩa này ta có thể khai báo xâu kí tự như sau: // Dev-C++ char x[1000]; char *y = new char[1000]; Cả hai khai báo trên là tương đương nhau và x, y đều có dung lượng hay sức chứa tới 1000 kí tự với các chỉ số từ 0 đên 999. Các xâu kí tự trong C++ được kết thúc bằng kí tự (dấu) kết xâu '\0'. Bạn cần chắc chắn rằng dấu kết xâu luôn luôn có mặt trong các xâu do bạn quản lý. Một số hàm hệ thống của C++ tự động dặt dấu kết xâu vào cuối xâu kí tự. Nếu bạn tự viết các hàm xử lí xâu thì bạn cần có thao tác tường minh đặt dấu kết xâu vào cuối xâu. Nếu bạn khai báo xâu kí tự x gồm 1000 kí tự như trên thì bạn chỉ được phép ghi vào xâu đó tối đa 999 kí tự (gọi là các kí tự có nghĩa). Vị trí cuối cùng x[999] phải dành để ghi dấu kết xâu '\0'. Trong Pascal với những xâu ngắn, có chiều dài không quá 255 kí, tự bạn nên sử dụng kiểu string, thí dụ (* Pas *) var x: string[100]; Khai báo trên cho phép bạn sử dụng xâu x như một mảng gồm 101 phần tử, x: array[0 100] of char; Tuy nhiên, bạn cần nhớ rằng phần tử x[0] được hệ thống dành riêng để ghi chiều dài hiện hành của xâu. Thí dụ, (* Pascal *) var x: string[100]; x := 'abc'; sẽ gán x[1] = 'a'; x[2] = 'b'; x[3] = 'c'; Riêng x[0] được gán kí tự có mã ASCII là 3: x[0] = #3. Như vậy bạn được sử dụng đúng 100 kí tự có nghĩa. Chièu dài hiện hành khác với sức chứa. Xâu x nói trên có sức chứa 100 bytes dành cho bạn, không tính byte đầu tiên x[0], còn chiều dài hiện hành là 3. Chiều dài hiện hành được tính trong C++ bằng hàm strlen, trong Pascal bằng hàm length. Với những xâu dài trên 255 kí tự bạn nên khai báo như một mảng, thí dụ (* Pascal *) var x: array[1 1000] of char; và xử lí x như một mảng. Trong C++ cũng có kiểu dữ liệu string dành riêng cho việc quản lý các xâu. Với kiểu này bạn có thể thực hiện một số hàm tiện ích như cộng hai xâu x+y, gán trị x = y, Thí dụ, // Dev-C++ int main(){ string x = "abc", y = x; cout << endl << x << " + " << y << " = " << (x+y); // abc + abc = abcabc cin.get(); return 0; } Các xâu trong đề bài đều được hiểu thống nhất với chỉ số tính từ 1 đến N. Khi lập trình bằng C++ bạn lưu ý chuyển đổi kết quả cuối cùng từ chỉ số i sang i+1. Bạn cũng có thể ghi dữ liệu từ chỉ số 1 trở đi, bỏ qua phần tử 0. Hằng xâu kí tự trong C++ được ghi giữa hai dấu nháy kép, thí dụ "string in CPP", trong Pascal được ghi giữa hai dấu nháy đơn, thí dụ, 'string in Pascal'. Nếu giữa hai dấu nháy đơn hoặc kép ta không ghi kí tự nào thì ta thu được một xâu rỗng là xâu có chiều dài 0.
  6. Cho xâu s[1 n]. Một đoạn của s là dãy liên tiếp các kí tự trong s. Ta kí hiệu s[d c] là đoạn của s tính từ chỉ số d đến chỉ số c. Thí dụ, nếu s = 'abcdegh' thì s[2 5] = 'bcde' là một đoạn. Đoạn s[1 i] được gọi là tiền tố i của s và được kí hiệu là i:s. Đoạn s[i n] Các tiền tố và hậu tố của xâu s = 'abcd' được gọi là hậu tố i của s và được kí hiệu là s:i. Xâu dài n kí tự có đúng n tiền tố và n hậu tố. Tiền tố Hậu tố Nếu xóa khỏi s một số kí tự và (tất nhiên) dồn các kí tự còn 1:s = s[1 1] = 'a' s:1 = s[1 4] = 'abcd' lại cho kề nhau, ta sẽ thu được một xâu con của s. 2:s = s[1 2] = 'ab' s:2 = s[2 4] = 'bcd' 1.2 Về tổ chức dữ liệu vào/ra 3:s = s[1 3] = 'abc' s:3 = s[3 4] = 'cd' Trong hầu hết các bài ta giả thiết dữ liệu vào và ra được ghi 4:s = s[1 4] = 'abcd' s:4 = s[4 4] = 'd' trong các text file *.INP và *.OUT. Tên và cách thức ghi dữ liệu trong các file được cho trong từng thí dụ cụ thể của mỗi bài. Theo giả thiết này trong các bài giải sẽ chỉ tập trung giới thiệu những thuật toán cơ bản, các bạn sẽ tự viết phần tổ chức vào/ra để thu được chương trình hoàn chỉnh. Turbo Pascal và Borland C++ bị hạn chế về miền nhớ. Các bạn nên sử dụng Free Pascal và DevC++ để có thể cấp phát những mảng dữ liệu đủ lớn với hàng tỷ bytes. Các mảng trong C++ được gán chỉ số 0, còn trong Pascal chỉ số mảng do người lập trình tự đặt. Trong DevC++, nếu f là input file dạng text thì dòng lệnh f >> x đọc dữ liệu vào đối tượng x đến khi gặp dấu cách. Muốn đọc đầy đủ một dòng dữ liệu chứa cả dấu cách từ input file f vào một biến mảng kí tự s ta có thể dùng phương thức getline như thí dụ sau đây char s[1001]; f.getline(s,1000,'\n'); Phương thức này đọc một dòng tối đa 1000 kí tự vào biến s, và thay dấu kết dòng '\n' trong input file bằng dấu kết xâu '/0' trong C. Lệnh memset(a,0,sizeof(a)) gán toàn 0 cho mọi byte của mảng a. Lệnh memmove(a,b,n) copy n byte từ mảng b sang mảng a. Lệnh strcpy(x,"abcd"); khởi trị "abcd" cho xâu x Để làm quen với các thao tác đọc/ghi dữ liệu bạn hãy thử giải bài toán dưới đây. 1.3 Data data.inp Tinh tong cua 12 so sau day: Trong file văn bản data.inp chứa 1 -2 3 -4 5 6 dòng dữ liệu đầu tiên có nội dung 7 8 9 10 -11 -12 "Tinh tong cua n so sau day:", data.out trong đó n là một số nguyên dương Tong cua 12 so: cho trước. +1 -2 +3 -4 +5 +6 +7 +8 +9 +10 -11 -12 = 20 Tiếp đến là n số nguyên ghi cách nhau qua dấu cách. Yêu cầu: xác định giá trị của n và tính tổng của n số trong file data.inp rồi ghi kết quả vào output file data.out theo định dạng cho trong bảng. Thuật toán Ta viết thủ tục Tong theo các bước: 1. Mở input file f tên "data.inp". 2. Cấp phát biến string s, đọc dòng đầu tiên vào s. 3. Duyệt s để tìm kí tự số đầu tiên, đọc tiếp số đó và ghi vào biến n. 4. Mở output file g tên "data.out". 5. Ghi dòng đầu tiên "Tong cua n so:" với n là giá trị cụ thể đọc được tại bước 3. 6. Đọc từng số trong n số từ file f, ghi vào file g kèm dấu +/– và cộng dồn vào biến tổng t. 7. Ghi giá trị tổng t vào file g. 8. Đóng các files f và g. 9. Thu hồi miền nhớ đã cấp cho s. Độ phức tạp: Cỡ n. (* Pascal: data.pas *) uses crt; const fn = 'data.inp'; gn = 'data.out'; bl = #32; { Dấu cách } nl = #13#10; { Xuống đầu dòng mới } var n: integer; function LaChuSo(c: char): Boolean; begin LaChuSo := (c >= '0') and (c <= '9');
  7. end; procedure Tong; var i,t,x : integer; s: string; f,g: text; begin { Mo input file f ten fn = "data.inp" doc dong dau tien vao s } assign(f,fn); reset(f); readln(f,s); i := 1; { Duyet s tim chu so dau tien } while Not LaChuSo(s[i]) do inc(i); n := 0; { Doc so trong s ghi vao n } while LaChuSo(s[i]) do begin n := n*10 + (ord(s[i]) - ord('0')); inc(i); end; assign(g,gn); rewrite(g); { Mo output file g ten gn="data.out" } writeln(g,'Tong cua ',n,' so:'); { Ghi dong thu nhat vao g } t := 0; { Khoi tri bien tich luy t } for i := 1 to n do { Doc lan luot tung so x trong n so } begin read(f,x); if x > 0 then write(g,' +',x) else write(g,' ',x); t := t + x; end; writeln(g,' = ',t); { Ghi ket qua } close(f); close(g); { Dong cac files } end; BEGIN Tong; writeln(nl,' Fini'); readln; END. // DevC++ Data #include #include #include #include using namespace std; // D A T A A N D V A R I A B L E const char * fn = "data.inp"; const char * gn = "data.out"; int n; // P R O T O T Y P E S void Tong(); bool LaChuSo(char c); // I M P L E M E N T A T I O N int main(){ Tong(); cout = '0' && c <= '9'); } void Tong() { const int mn = 100; int i, t, x; ifstream f(fn); // Mo input file f ten fn = "data.inp" char *s = new char [mn]; // cap phat s f.getline(s,mn,'\n'); // doc toan bo dong thu nhat for (i = 0; i < strlen(s); ++i) // duyet xau s tim chu so if (LaChuSo(s[i])) break;
  8. n = 0; // khoi tri so n while (LaChuSo(s[i])) { // doc so n n = n*10 + int(s[i]-'0'); ++i; } t = 0; // khoi tri bien tong t ofstream g(gn); // Mo output file g ten gn = "data.out" g > x; // doc tung so x if (x > 0) g b then Max := a else Max := b; end; function XauChung(var x,y: string): integer; var m,n,i,j: integer; a,b: array[0 255] of integer; begin m := length(x); n := length(y); fillchar(a,sizeof(a),0); for i := 1 to m do begin for j := 1 to n do if x[i] = y[j] then b[j] := a[j-1]+1 else b[j] := Max(a[j],b[j-1]); a := b; end; XauChung := a[n]; end; BEGIN writeln; writeln(XauChung('xabcxxxd','aybcydyy')); { 4 } readln; END. // Dev-C++: XauChung.cpp
  9. int Max(int a, int b) { rturn (a > b) ? a : b; } int XauChung(char *x, char *y) { int i,j; int m = strlen(x), n = strlen(y); int a[n], b[n]; for (j = 0; j < n; ++j) a[j] = (x[0] == y[j]) ? 1 : 0; for (i = 1; i < m; ++i) { b[0] = (x[i] == y[0]) ? 1 : 0; for (j = 1; j < n; ++j) if (x[i] == y[j]) b[j] = a[j-1] + 1; else b[j] = Max(a[j],b[j-1]); memmove(a,b,n*sizeof(int)); } return a[n-1]; } int main() { cout << endl << XauChung("xaxxbcxd","aybcyydy"); // 4 cin.get(); return 0; } Cách làm test Bạn hãy viết ra một xâu s nào đó làm đáp số, tức là xâu con chung, sau đó thêm vào s một số kí tự để nhận được xâu x, rồi lại thêm cho s một số kí tự khác để nhận được xâu y. Các bài tương tự 1. Xâu chung 2. Cho hai xâu x gồm m và y gồm n kí tự. Cần xóa đi từ xâu x dx kí tự và từ xâu y dy kí tự để thu được hai xâu giống nhau. Hãy xác định giá trị nhỏ nhất của tổng dx+dy. 2. Dãy con chung. Cho hai dãy số nguyên a gồm m và b gồm n phần tử. Cần xóa đi ít nhất là bao nhiêu phần tử từ mỗi dãy trên để thu được hai dãy giống nhau. Thuật toán cho bài Xâu chung 2 k = XauChung(x,y); dx = len(x) – k; dy = len(y) – k; 1.5 Đoạn chung Hãy tìm chiều dài lớn nhất k trong số các đoạn chung của hai xâu x và y. Thí dụ, x = "xabcxxabcdxd", y = "aybcyabcdydy" có chiều dài của đoạn chung dài nhất là 4 ứng với đoạn "abcd". Thuật toán Xét hàm 2 biến s(i,j) là chiều dài lớn nhất của hai đoạn giống nhau x[i k+1 i] và y[j k+1 j], k max. Ta có, Nếu x[i] = y[j] thì s(i,j) = s(i–1,j–1) + 1; Nếu x[i] ≠ y[j] thì s(i,j) = 0. Đáp số sẽ là Max { s(i,j) | 1 i len(x), 1 j len(y) }. Để cài đặt ta có thể sử dụng hai mảng một chiều như bài trước. Ta cũng có thể sử dụng một mảng một chiều a và hai biến phụ v và t. Biến t lưu tạm giá trị trước khi tính của a[j]. Biến v lấy lại giá trị t để tính cho bước sau. Độ phức tạp: Cỡ m.n, m = len(x), n = len(y). (* DChung.pas *) function Max(a,b: integer): tự viết; function DoanChung(x,y: string): integer; var m,n,i,j,v,t,kmax: integer; a: array[1 255] of integer; begin m := length(x); n := length(y); kmax := 0; fillchar(a,sizeof(a),0); for i := 1 to m do
  10. begin v := 0; for j := 1 to n do begin t := a[j]; if x[i] = y[j] then a[j] := v+1 else a[j] := 0; kmax := Max(kmax,a[j]); v := t; end; end; DoanChung := kmax; end; BEGIN writeln(DoanChung('xabcxxabcdxd','aybcyabcdydy')); {4} writeln(' Fini'); readln; END. // DevC++: DoanChung.cpp int Max(int a, int b); // tự viết int DoanChung(char *x, char *y) { int i, j, kmax = 0, v, t ; int m = strlen(x), n = strlen(y); int a[n]; memset(a,0,sizeof(a)); for (i = 0; i kmax ta ghi nhận imax = i; jmax = j; kmax = k. Cuối thủ tục ta tính cx = imax; dx = cx–kmax+1; cy = jmax; dy = cy–kmax+1.
  11. 1.6 Đoạn lặp Những viên ngọc lập trình (Bentley) Cho xâu s chứa n kí tự. Hãy xác định ba số nguyên i, j và k thỏa điều kiện 1 i < j n, k là giá trị max thỏa điều kiện s[i] = s[j], s[i+1] = s[j+1], , s[i+k–1] = s[j+k–1]. Hai đoạn bằng nhau gồm k kí tự trong s là s[i i+k–1] và s[j j+k–1], i < j, k max được gọi là hai đoạn lặp trong s. Thí dụ, s = 'xabababayyy' cho ta i = 2, j = 4, k = 5 ứng với đoạn lặp s[2 6] = 'ababa'. Thuật toán 1 Bài này khá giống bài đoạn chung. Xét hàm 2 biến s(i,j) là chiều dài lớn nhất của hai đoạn giống nhau x[i k+1 i] và y[j k+1 j], i < j, k max. Ta có, Nếu x[i] = x[j] thì s(i,j) = s(i–1,j–1) + 1; Nếu x[i] ≠ x[j] thì s(i,j) = 0. Đáp số sẽ là Max { s(i,j) | 1 i len(x), 1 j len(y), i < j }. Để cài đặt ta có thể sử dụng hai mảng một chiều như bài trước. Ta cũng có thể sử dụng một mảng một chiều a và hai biến phụ v và t. Biến t lưu tạm giá trị trước khi tính của a[j]. Biến v lấy lại giá trị t để tính cho bước sau. Độ phức tạp: Cỡ n2, n = len(s). (* Repeat.pas *) uses crt; var i,j,k: integer; procedure DoanLap(s: string; var imax, jmax, kmax: integer); var n,i,j,v,t: integer; a: array[1 255] of integer; begin n := length(s); kmax := 0; fillchar(a,sizeof(a),0); for i := 1 to n do begin v := 0; for j := i+1 to n do begin t := a[j]; if s[i] = s[j] then a[j] := v+1 else a[j] := 0; if kmax < a[j] then begin kmax := a[j]; imax := i-kmax+1; jmax := j-kmax+1; end; v := t; end; end; end; BEGIN DoanLap('xabababayy',i, j, k); writeln(i,' ', j, ' ',k); { i = 2, j = 4, k = 5 } readln; END. // DevC++: Repeat.cpp void DoanLap(char *s, int & imax, int & jmax, int & kmax) { int i, j , v, t ; int n = strlen(s); int a[n]; kmax = 0; memset(a,0,sizeof(a)); for (i = 0; i < n; ++i) { v = 0; for (j = i+1; j < n; ++j) { t = a[j]; if (s[i] == s[j]) a[j] = v + 1; else a[j] = 0;
  12. if (kmax 0) j; if (i j) ? -1 : 0); } Hàm ComLen(s, i, j) cho ra chiều dài lớn nhất của hai khúc đầu giống nhau của hai hậu tố s:i và s:j. int ComLen(char *s, int i, int j) { int k = Min(strlen(s)-i, strlen(s)-j); for (int v = 0; v < k; ++v, ++i, ++j) if (s[i] != s[j]) return v; return k; } Thuật toán Bentley khi đó sẽ được triển khai qua hàm sau, void DoanLap(char *s, int & imax, int & jmax, int & kmax) { int i, k; int n = strlen(s); int id[n]; for (i = 0; i < n; ++i) id[i] = i; IdSort(s,id,0,n-1); for (i = 1; i < n; ++i) {
  13. if ((k = ComLen(s, id[i], id[i-1])) > kmax) { kmax = k; imax = id[i]+1; jmax = id[i-1]+1; } } if (imax > jmax) { i = imax; imax = jmax; jmax = i; } } (* DoanLap2.pas *) uses crt; var i,j,k: integer; type mi1 = array[1 256] of integer; function Min(a,b: integer): integer; begin if a s[j+v] then begin if s[i+v] j then Sanh := -1 else Sanh := 0; end; procedure IdSort(var s: string; var id: mi1; d,c: integer); var i, j, m, t: integer; begin i := d; j := c; m := id[(i+j) div 2]; while (i 0 do dec(j); if (i s[j+v] then begin ComLen := v; exit end; ComLen := k+1; end; procedure DoanLap(s: string; var imax, jmax, kmax: integer); var n,i,j,k: integer; id: mi1; begin n := length(s); kmax := 0; for i := 1 to n do id[i] := i; IdSort(s,id,1,n); for i := 2 to n do begin k := ComLen(s,id[i],id[i-1]); if k > kmax then
  14. begin kmax := k; imax := id[i]; jmax := id[i-1]; end; end; if imax > jmax then begin i := imax; imax := jmax; jmax := i end; end; BEGIN DoanLap('xabababayy',i, j, k); writeln; writeln(i,' ', j, ' ',k); readln; END. Cách làm Test Xây dựng 4 xâu X, Y, A và B không có các kí tự chung. Ghép XABAB ABY một số lần. Đáp số: i = len(X) +1, j = len(X)+Len(A)+Len(B)+1, k = (v 1).(len(A)+len(b)) với v là số lần lặp các cặp AB. Thí dụ, với X = 'xy'; Y = 'zt'; A = 'abcde'; B = 'fghhik' ta có thể xây dựng các Test sau đây. Test 1. s = XABABY = 'xyabcdefghhikabcdefghhikzt'. Đáp số i = 3, j = 2 + 5 + 6 + 1 = 14, k = 5+6 = 11. Test 2. s = XABABABY = 'xyabcdefghhikabcdefghhikabcdefghhikabcdefghhikzt'. Đáp số i = 3, j = 14, k = 2*11 = 22. 1.7 Từ điển Olimpic Moscow Các từ trong bài được hiểu là một dãy liên tiếp các chữ cái a, b, , z. Một file văn bản chứa một từ điển T gồm tối đa n = 100 từ khác nhau đôi một. Mỗi từ dài không quá 50 kí tự và được viết trên một dòng. Cho một từ s dài không quá 200 kí tự. Hãy cho biết cần xóa đi khỏi s tối thiểu bao nhiêu chữ cái để phần còn lại tạo thành dãy liên tiếp các từ trong từ điển T, mỗi từ có thể xuất hiện nhiều lần. Thí dụ, dic.inp dic.out Giải thích 6 5 Sau khi xóa 5 chữ cái (gạch dưới) abba saintpavnamtranaisnotsaintabba not ta thu được dãy ghép của các từ 5, 6, 3, 2, 5, is 1 astra saintpanamaisnotsaintabba saint panama saintpavnamtranaisnotsaintabba Thuật toán Gỉa sử T là tập n từ trong từ điển, s là từ cần xử lí. Gọi d(i) là hàm cho đáp số khi giải bài toán với tiền tố i:s = s[1 i]. d(i) là số kí tự tối thiểu cần xóa khỏi s[1 i] để phần còn lại của s[1 i] tạo thành dãy liên tiếp các từ trong từ điển T. Với mỗi từ w dài m kí tự trong từ điển T ta xét hàm Nhung(w,i) có chức năng nhúng từ w vào tiền tố i:s như sau. Hàm cho ra chỉ số v thỏa hai điều kiện sau: 1. w là xâu con của s[v i], nghĩa là nếu xóa đi một số kí tự khỏi s[v i] ta sẽ thu được từ w, 2. s[v] = w[1], s[i] = w[m]. Nếu w được nhúng trong s[v i] thì số kí tự cần xóa khỏi s[v i] để thu được từ w sẽ là i–v+1–len(w). Nếu từ w được chọn thì tổng số kí tự cần xóa khỏi tiền tố i:s sẽ là d(v 1) + i–v+1–len(w). Ta cần chọn w sao cho giá trị này đạt min. Vậy, d(i) = min { d(v 1) + i–v+1–len(w) | w T, v = Nhung(w,i) } Khi w không thể nhúng được trong s[1 i] ta đặt v = Nhung(w,i) = 0 (pascal) hoặc 1 (C). (* TuDien.pas *) uses crt; const fn = 'dic.inp'; gn = 'dic.out'; nl = #13#10; bl = #32; type str = string[52]; var f,g: text; s: string[202]; w: array [1 102] of str; n: integer; d: array[0 202] of integer;
  15. kq: integer; procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n); for i := 1 to n do readln(f,w[i]); readln(f,s); close(f); end; procedure Ghi(v: integer); begin assign(g,gn); rewrite(g); writeln(g,v); close(g); end; function Nhung(var w: str; i: integer): integer; var j: integer; begin Nhung := 0; j := length(w); if j > i then exit; if w[j] 0 then d[i] := Min(d[i], d[v-1]+i-v+1-length(w[j])); end; end; function XuLi: integer; var m, i: integer; begin d[0] := 0; m := length(s); for i := 1 to m do Tinhd(i); XuLi := d[m]; end; BEGIN Doc; kq := XuLi; Ghi(kq); writeln(nl,nl,kq,nl,' Fini '); readln; END. // DevC++: TuDien.cpp #include #include #include #include using namespace std; // D A T A A N D V A R I A B L E const char * fn = "dic.inp"; const char * gn = "dic.out"; char w[102][52];
  16. char s[202]; int d[202]; int n, lens; // P R O T O T Y P E S void Doc(); void Xem(); int Nhung(char *, int i); int XuLi(); void Tinhd(int); int Min(int, int); void Ghi(int); // I M P L E M E N T A T I O N int main(){ Doc(); Xem(); int kq = XuLi(); Ghi(kq); cout > v; g.close(); } int Min(int a, int b) { return (a > n; for (int i = 0; i > w[i]; f >> s; lens = strlen(s); f.close(); } void Xem() { cout = 0; i) if (w[j] == s[i]) { j; if (j = 0) { k = (v == 0) ? 0 : d[v-1]; d[i] = Min(d[i], k+i-v+1-strlen(w[j])); } }
  17. Độ phức tạp. Cỡ p.n.m, trong đó p = len(s), n là số từ trong từ điển T, m là chiều dài của từ dài nhất trong T. Chú thích Bạn có thể cải tiến chương trình như sau. Khi đọc dữ liệu và tổ chức từ điển T bạn có thể loại trước khỏi T những từ w nào mà kí tự đầu tiên w[1] hoặc kí tự cuối cùng w[m] không xuất hiện trong s vì khi đó chắc chắn là hàm Nhung sẽ cho giá trị 1. Tốt hơn cả là bạn cho w trượt trong s để xác định xem w đặt lọt tại các chỉ số nào trong s. 1.8 TEFI TEFI.INP TEFI.OUT Trong text file tên TEFI.INP gồm n dòng và m cột 15 27 3 2 2 3 người ta dùng dấu chấm '.' tạo thành một bảng nền. Trên bảng nền đó người ta dùng dấu sao '*' * để viết các chữ IN HOA T, E, F và I theo các qui * * * tắc sau: - chân phương, không có chân * * - đơn nét * * * . - các nét song song không dính nhau * * * - các nét của hai chữ không dính nhau mà cách * * * * * nhau ít nhất một dấu chấm * * * * Hãy đếm số chữ cái mỗi loại. * * * * Thí dụ bên cho biết có 3 chữ T, 2 chữ E, 2 chữ F * * * và 3 chữ I. * * * * * * * * * * Thuật toán
  18. Ta xét hai dòng x và y liên tiếp nhau trong bảng nền và thử phát hiện đặc trưng của các chữ cái dựa trên 2 dòng này. Ta thấy, chữ T có đặc trưng duy nhất (không lẫn với các chữ cái khác) là đầu trên gồm 1 vach ngang (–) và 1 sổ đứng (|) dính nhau. Chữ I có đặc trưng duy nhất là một sổ đứng (|). Trong chữ E có 2 nét ngang trên và 2 nét ngang dưới, chữ F có 2 nét ngang trên và 1 nét ngang dưới. i i i i x * * . . * * . * dnt = số nét ngang trên. y * . * . . * . * * dnd = số nét ngang dưới. dx = đếm số chữ X; Đầu trên Đầu trên Nét ngang Nét ngang X = {T,E,F,I}. chữ T chữ I trên và dưới của Mỗi chữ E có 2 nét ngang trên và giữa của chữ E và F 2 nét ngang dưới. Mỗi chữ F có 2 chữ E và F nét ngang trên và 1 nét ngang dưới. de+df = dnt / 2; de = dnd – dnt/2. df = dnt/2 – de. Để tiện xử lý ta thêm vào đầu và cuối mỗi xâu một dấu chấm '.'. Các trường hợp cần xét được mô tả chi tiết dưới dạng bảng quyết định. Bảng quyết định cho bài toán TEFI Bảng quyết định gồm 2 phần: phần điều kiện và x[i] = '*' 1 0 1 1 phần quyết định.Các điều kiện được liệt kê độc x[i–1] = '*' 1 - 0 0 lập nhau. Điều kiện x[i+1] = '*' - - 1 - Giá trị 1 ứng với điều kiện đúng (true), 0 ứng với y[i] = '*' 1 1 1 1 điều kiện sai (false), dấu – cho biết điều kiện này y[i–1] = '*' - 0 0 0 không cần xét. y[i+1] = '*' - 0 - 1 Bảng được đọc theo cột: nếu các điều kiện trong cột thuộc phần điều kiện được thỏa thì quyết định T (chữ T) 1 tại cột đó được chọn. Quyết  (nét ngang trên) 1 x dòng trên; y dòng dưới. định L (nét ngang dưới) 1 I (chữ I) 1 Dựa vào bảng quyết định ta duyệt đồng thời dòng trên x và dòng dưới y để đếm các giá trị sau: dt là số lượng chữ T, di là số lượng chữ i, dnt là số lượng nét ngang trên  và dnd là số lượng nét ngang dưới L. Từ các giá trị dnt và dnd ta dễ dàng tính được số lượng chữ E và số lượng chữ F. Vì mỗi chữ E và mỗi chữ F đều có cùng 2 nét ngang trên nên de + df = dnt/2 (1). Mỗi chữ E có 2 nét ngang dưới, mỗi chữ F có 1 nét ngang dưới nên 2.de + df = dnd (2). Trừ từng vế của (2) cho (1) ta thu được de = dnd – dnt/2. Từ (1) ta suy ra df = dnt/2 – de. Độ phức tạp. cỡ m.n = dung lượng input file. (* TEFI.PAS *) uses crt; const fn = 'tefi.inp'; gn = 'tefi.out'; bl = #32; nl = #13#10; ss = '*'; cc = '.'; var x, y: string; dt, de, df, di: integer; n, m: integer; dnt, dnd: integer; f,g: text; procedure EF(i: integer); begin if (x[i+1] = ss) then inc(dnt) else if (y[i+1] = ss) then inc(dnd) end; procedure TEF(i: integer); begin if (y[i] = cc) then exit; if (x[i-1] = cc) then EF(i) else inc(dt); end; procedure II(i: integer); { x[i] = cc }
  19. begin if (y[i] = ss) and (y[i-1] = cc) and (y[i+1] = cc) then inc(di); end; procedure TEFI; var i,j: integer; begin dt := 0; di := 0; dnt := 0; dnd := 0; fillchar(x,sizeof(x),cc); assign(f,fn); reset(f); readln(f,n,m); for j := 1 to n do begin readln(f,y); y := cc + y + cc; for i := 2 to m do begin if (x[i] = ss) then TEF(i) else II(i); end; x := y; end; close(f); i := dnt div 2; { de + df } de := dnd - i; df := i - de; end; BEGIN TEFI; writeln('T = ',dt,' E = ',de,' F = ',df, ' I = ', di); readln; END. // DevC++: TEFI.CPP #include #include #include #include using namespace std; const char * fn = "tefi.inp"; const char * gn = "tefi.out"; string x, y; char ss = '*', cc = '.'; int n, m; int dt, de, df, di, dnt, dnd; // P R O T O T Y P E S void TEFI(); void TEF(int); void EF(int); void II(int); // I M P L E M E N T A T I O N int main(){ TEFI(); cout << endl << " T: " << dt << " E: " << de; cout << " F: " << df << " I: " << di; cout << endl << endl << " Fini "; // 3 cin.get(); return 0; } void TEF(int i) { if (y[i] == cc) return; if (x[i-1] == cc) EF(i); else ++dt; } void EF(int i){ if (x[i+1] == ss) ++dnt; else if (y[i+1] == ss) ++dnd; }
  20. void II(int i) { if (y[i] == ss && y[i-1] == cc && y[i+1] == cc) ++di; } void TEFI() { int i, j; dt = di = dnt = dnd = 0; ifstream f(fn); f >> n >> m; f.get(); x = cc; for (i = 0; i > y; y = cc + y + cc; for (i = 1; i <= m; ++i) if (x[i] == ss) TEF(i); else II(i); x = y; } f.close(); i = dnt / 2; // i = de + df de = dnd - i; df = i - de; } 1.9 E xiếc EXIEC.INP EXIEC.OUT Trong text file tên EXIEC.INP gồm n dòng và m 15 27 2 2 1 2 cột người ta dùng dấu chấm '.' tạo thành một bảng nền. Trên bảng nền đó người ta dùng dấu sao '*' để viết các chữ IN HOA E với nét ngang * * giữa hướng về phía Đông, Tây, Nam và Bắc. Qui tắc viết giống như trong bài TEFI. Hãy đếm * * số chữ cái mỗi loại. * * * * Thí dụ bên cho biết có 2 chữ E (nét ngang *.*.*.*.*.* hướng về phía Đông), 2 chữ  (nét ngang *.*.*.*.*.* hướng về phía Tây). 1 chữ E úp (nét ngang * *.* * hướng về phía Nam), và 2 chữ E ngửa (nét ngang hướng về phía Bắc). * * * * * * * * * Thuật toán x * * * * * * Hai E Nam và E Bắc được đặc trưng duy nhất qua hướng của nét ngang giữa y * * * * * * * * giống chữ T (E Nam) và  (E Bắc). Mỗi Đông Tây Nam Bắc E Đông có 2 nét dạng L và mỗi E Tây có dd L dt dn T db  2 nét dạng . Ngoài ra, mỗi chữ E Bắc còn có 1 nét L và 1 nét . Ta có Đặc trưng của các chữ E xiếc. Các biến dd, dt, dn, Số chữ E Đông = (dd – db)/2, db dùng để đếm số lần xuất hiện của các đặc trưng. Số chữ E Tây = (dt db)/2, Số chữ E Nam = dn, Số chữ E Bắc = db. Độ phức tạp. cỡ m.n = dung lượng input file. (* EXIEC.PAS *) uses crt;
  21. const fn = 'Exiec.inp'; gn = 'Exiec.out'; bl = #32; nl = #13#10; ss = '*'; cc = '.'; var x, y: string; dd, dt, dn , db: integer; n, m: integer; f,g: text; procedure TayNam(i: integer); begin if (y[i-1] = ss) then inc(dft) else if (x[i-1] = ss) and (x[i+1] = ss) then inc(dn) end; procedure DongBac(i: integer); begin if (y[i-1] = ss) then inc(db) else inc(dd); end; procedure DongTayNamBac(i: integer); begin if (y[i+1] = ss) then DongBac(i) else TayNam(i); end; procedure EXIEC; var i,j: integer; begin dd := 0; dt := 0; dn := 0; db := 0; assign(f,fn); reset(f); readln(f,n,m); fillchar(x,sizeof(x),cc); for j := 1 to n do begin readln(f,y); y := cc + y + cc; for i := 2 to m do if (x[i] = ss) and (y[i] = ss) then DongTayNamBac(i); x := y; end; close(f); dd := (dd-db) div 2; dt := (dt-db) div 2; end; BEGIN EXIEC; writeln(dd,' ',dt, ' ', dn, ' ', db); readln; END. // DevC++: EXIEC.CPP #include #include #include #include using namespace std; const char * fn = "exiec.inp"; const char * gn = "exiec.out"; string x, y; char ss = '*', cc = '.'; int n, m; int dd, dt, dn, db; // huong tro cua vach giua: Dong Tay Nam Bac // P R O T O T Y P E S void EXIEC(); void DongTayNamBac(int); void DongBac(int); void TayNam(int); // I M P L E M E N T A T I O N int main(){ EXIEC(); cout << endl << dd << " " << dt; cout << " " << dn << " " << db;
  22. cout > n >> m; x = cc; for (i = 0; i > y; y = cc + y + cc; for (i = 1; i <= m; ++i) if (x[i] == ss && y[i] == ss) DongTayNamBac(i); x = y; } f.close(); dd = (dd - db)/2; dt = (dt - db)/2; }
  23. Chương 2 Xử lí dãy lệnh và biểu thức 2.1 Val Cho các biến được gán trị a = 0, b = 1, c = 2, , z = 25. Tính trị của biểu thức số học được viết đúng cú pháp, chứa các tên biến, các phép toán +, –, *, và / (chia nguyên) và các cặp ngoặc (). Thí dụ, biểu thức, (b+c)*(e–b) + (y–x) sẽ có giá trị (1+2)*(4–1)+ (24–23) = 3*3+1 = 10. Thuật toán Do phải ưu tiên thực hiện các phép toán nhân (*) và chia (/) trước các phép toán cộng (+) và trừ ( ), ta qui ước các phép toán nhân và chia có bậc cao hơn bậc của các phép toán cộng và trừ. Gọi s là string chứa biểu thức, ta duyệt lần lượt từng kí tự s[i] của s và sử dụng hai ngăn xếp v và c để xử lí các tình huống sau: 1. Nếu s[i] là biến 'a', 'b', thì ta nạp trị tương ứng của biến đó vào ngăn xếp (stack) v. 2. Nếu s[i] là dấu mở ngoặc '(' thì ta nạp dấu đó vào ngăn xếp c. 3. Nếu s[i] là các phép toán '+', '–', '*', '/' thì ta so sánh bậc của các phép toán này với bậc của phép toán p trên ngọn ngăn xếp c. 3.1. Nếu Bac(s[i]) Bac(p) thì ta lấy phép toán p ra khỏi ngăn xếp c và thực hiện phép toán đó với 2 phần tử trên cùng của ngăn xếp v. Bước này được lặp đến khi Bac(s[i]) > Bac(p). Sau đó làm tiếp bước 3.2. 3.2 Nạp phép toán s[i] vào ngăn xếp c. 4. Nếu s[i] là dấu đóng ngoặc ')' thì ta dỡ dần và thực hiện các phép toán trên ngọn ngăn xếp c cho đến khi gặp dấu '(' đã nạp trước đó. Thuật toán được xây dựng trên giả thiết biểu thức s được viết đúng cú pháp. Về bản chất, thuật toán xử lý và tính toán đồng thời trị của biểu thức s theo nguyên tắc phép toán sau hay là kí pháp Ba Lan do nhà toán học Ba Lan Lucasievics đề xuất. Theo kí pháp này, biểu thức (b+c)*(e–b) + (y–x) sẽ được viết thành bc+eb–*yx–+ và được thực hiện trên ngăn xếp v như sau. Gọi iv là con trỏ ngọn của ngăn xếp v, iv được khởi trị 0: 1. Nạp trị của biến b vào ngăn xếp v: iv := iv + 1; v[iv] := (b); trong đó (b) là trị của biến b. 2. Nạp trị của biến c vào ngăn xếp v: iv := iv + 1; v[iv] := (c); 3. Thực hiện phép cộng hai phần tử trên ngọn ngăn xếp v, ghi kết quả vào ngăn dưới, bỏ ngăn trên: v[iv–1] := v[iv–1] + v[iv]; iv := iv –1; 4. Nạp trị của e vào ngăn xếp v: iv := iv + 1; v[iv] := (e); 5. Nạp trị của b vào ngăn xếp v: iv := iv + 1; v[iv] := (b); 6. Thực hiện phép trừ hai phần tử trên ngọn ngăn xếp v, ghi kết quả vào ngăn dưới, bỏ ngăn trên: v[iv–1] := v[iv–1] – v[iv]; iv := iv –1; 7. Thực hiện phép nhân hai phần tử trên ngọn ngăn xếp v, ghi kết quả vào ngăn dưới, bỏ ngăn trên: v[iv–1] := v[iv–1] * v[iv]; iv := iv –1; 8. Nạp trị của y vào ngăn xếp v: iv := iv + 1; v[iv] := (y); 9. Nạp trị của x vào ngăn xếp v: iv := iv + 1; v[iv] := (x); 10. Thực hiện phép trừ hai phần tử trên ngọn ngăn xếp v, ghi kết quả vào ngăn dưới, bỏ ngăn trên: v[iv–1] := v[iv–1] – v[iv]; iv := iv –1; 11. Thực hiện phép cộng hai phần tử trên ngọn ngăn xếp v, ghi kết quả vào ngăn dưới, bỏ ngăn trên: v[iv–1] := v[iv–1] + v[iv]; iv := iv –1; Kết quả cuối cùng có trong v[iv]. Bạn nhớ khởi trị ngăn xếp c bằng kí tự nào đó không có trong biểu thức, thí dụ '#'. Phép toán này sẽ có bậc 0 và dùng làm phần tử đệm để xử lý tình huống 3. Bạn cần đặt kí hiệu # vào đáy của ngăn xếp c để làm lính canh. Vì khi quyết định có nạp phép toán p nào đó vào ngăn xếp c ta cần so sánh bậc của p với bậc của phép toán trên ngọn của ngăn xếp c. Như vậy # sẽ có bậc 0. Bạn có thể thêm một phép kiểm tra để phát hiện lỗi "chia cho 0" khi thực hiện phép chia. Bạn cũng có thể phát triển thêm chương trình để có thể xử lí các biểu thức có chứa các phép toán một ngôi !, ++, – –. và các lời gọi hàm. Độ phức tạp. cỡ n, trong đó n là số kí hiệu trong biểu thức. (* Val.pas *)
  24. uses crt; const fn = 'val.inp'; gn = 'val.out'; nl = #13#10; bl = #32; mn = 500; var c: array[0 mn] of char; {Ngăn xếp c chứa các phép toán} ic: integer; v: array[0 mn] of integer; {Ngăn xếp v chứa trị của các biến} iv: integer; function LaBien(c: char): Boolean; begin LaBien := (c in ['a' 'z']); end; function LaPhepToan(c: char): Boolean; begin LaPhepToan := (c in ['+','-','*','/']) end; function Val(c: char): integer; { trị của biến c } begin Val := Ord(c)-ord('a'); end; function Bac(p: char): integer; { Bậc của phép toán p } begin if (p in ['+','-']) then Bac := 1 else if (p in ['*','/']) then Bac := 2 else Bac := 0; end; (* Thực hiện phép toán 2 ngôi trên ngọn ngăn xếp v *) procedure Tinh(p: char); begin case p of '+': begin v[iv-1] := v[iv-1] + v[iv]; dec(iv) end; '-': begin v[iv-1] := v[iv-1] - v[iv]; dec(iv) end; '*': begin v[iv-1] := v[iv-1] * v[iv]; dec(iv) end; '/': begin v[iv-1] := v[iv-1] div v[iv]; dec(iv) end; end end; procedure XuLiToan(p: char); begin while (Bac(c[ic]) >= Bac(p)) do begin Tinh(c[ic]); dec(ic) end; inc(ic); c[ic] := p; { nap phep toan p } end; procedure XuLiNgoac; begin while (c[ic] 0) do begin Tinh(c[ic]); dec(ic) end; XuLi := v[iv]; end; BEGIN writeln(nl,XuLi('(b+c)*(f-a+b-c+d)/(c*d+b)')); { 3 } readln; END. // DevC++: Val #include #include #include
  25. #include using namespace std; // Mo ta Dư lieu va bien const int mn = 500; char s[mn]; // bieu thuc char c[mn]; //ngan xep phep toan va dau ( int ic; // con trỏ ngăn xếp c int v[mn]; //ngan xep tinh toan int iv; // con trỏ ngăn xếp v int kq; // ket qua int n; // len – số ki tự trong biểu thức // Khai báo các hàm int XuLi(); bool LaBien(char c); // kiem tra c la bien ? bool LaPhepToan(char c); // kiem tra c la phep toan +, –, *, / ? void XuLiPhepToan(char pt); void XuLiNgoac(); int Bac(char pt); // Bac cua phep toan +, – (1), *, / (2) int Val(char c); // Tinh tri cua bien c void Tinh(char pt); // thuc hien phep toan pt // Cai dat int main() { strcpy(s,"(b+c)*(e-b) + (y-x)"); cout = 'a' && c = Bac(pt)) { Tinh(c[ic]); ic; } c[++ic] = pt; } void XuLiNgoac(){ while (c[ic] != '(') { Tinh(c[ic]); ic; } ic; // bo dau '(' } void Tinh(char pt) { // Thuc hien phép toan pt switch(pt) { case '+': v[iv-1] = v[iv-1]+v[iv]; iv; break;
  26. case '-': v[iv-1] = v[iv-1]-v[iv]; iv; break; case '*': v[iv-1] = v[iv-1]*v[iv]; iv; break; case '/': v[iv-1] = v[iv-1]/v[iv]; iv; break; } } 2.2 Xâu thu gọn Mộ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: Nếu s[v] là chữ cái C thì đọc tiếp số m sau C và tạo ra một dòng lệnh mới dạng (n, C, m), trong đó n là số hiệu riêng của dòng lệnh, C là chữ cái cần viết, m là số lần viết chữ cái C; Nếu s[v] là dấu mở ngoặc '(' thì ghi nhận vị trí dòng lệnh n+1 vào stack st; Nếu s[v] là dấu đóng ngoặc ')' thì đọc tiếp số m sau ngoặc, lấy giá trị t từ ngọn ngăn xếp và tạo ra một dòng lệnh mới dạng (n, #, m, t). Dòng lệnh này có ý nghĩa như sau: Cần thực hiện lặp m lần đoạn trình từ dòng lệnh t đến dòng lệnh n. Nếu số m = 0 thì ta xóa các dòng lệnh từ dòng t đến dòng hiện hành n. Nếu n = 1 thì ta không tạo dòng lệnh mới. 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: n c m t Ý nghĩa của dòng lệnh Chương trình P gồm 7 dòng lệnh thu 1 A 1 Viết A 1 lần được sau khi thực hiện Pha 1 với xâu 2 B 3 Viết B 3 lần (AB3(C2D)2(C5D)0)2A3. 3 C 2 Viết C 2 lần 4 D 1 Viết D 1 lần 5 # 2 3 Lặp 2 lần từ dòng lệnh 3 đến dòng lệnh 5 6 # 2 1 Lặp 2 lần từ dòng lệnh 1 đến dòng lệnh 6 7 A 3 Viết A 3 lần 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 }
  27. 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 '#') do begin if (s[v] in ChuCai) then LenhDon(s[v]) else if (s[v] = '(') then NapNgoac
  28. 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 = 'A') && (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;
  29. } 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; } } } 2.3 Robot Một Robot được lập trình để di chuyển trên mặt phẳng tọa độ xoy chia lưới đơn vị. Chương trình điều khiển Robot được viết dưới dạng xâu gọn như trong bài Xâu gọn và gồm dãy lệnh với ý nghĩa như sau: Gn – đi thẳng n bước qua các điểm nguyên, Rn – quay phải n lần 45 độ, Ln – quay trái n lần 45 độ. Robot được đặt tại vị trí xuất phát là gốc tọa độ, mặt hướng theo trục oy. Yêu cầu: Xác định tọa độ (x,y) nơi Robot dừng chân sau khi thực hiện chương trình ghi trong string s. Thí dụ, Sau khi thực hiện chương trình s = "(GR3(G2L)2(L5G)0)2G3" Robot sẽ dừng chân tại vị trí (10, 4) trên mặt phẳng tọa độ. Thuật toán Pha 1 hoàn toàn giống bài Xâu thu gọn. Riêng với pha 2 ta cần thay lệnh hiển thị bằng việc tính vị trí của Robot sau khi thực hiện mỗi dòng lệnh. 0 Ta mã số 8 hướng di chuyển trên mặt phẳng 7 (0,1) 1 tọa độ từ 0 đến 7. Với mỗi hướng ta xác định ( 1,1) (1,1) các giá trị dx và dy khi cho Robot đi 1 bước theo hướng đó. Thí dụ, theo hướng h = 0 thì Robot sẽ di chuyển từ tọa độ (x,y) sang tọa 6 2 ( 1,0) (1,0) độ (x, y + 1), như vậy dx = 0, dy = 1. Các giá trị này được khởi tạo sẵn trong một mảng hai chiều huong trong đó dx = 5 3 huong[h][0], dy = huong[h][1]. ( 1, 1) 4 (1, 1) (0, 1)
  30. Vì có 8 hướng nên nếu Robot đang hướng mặt về hướng h thì sau khi quay phải k lần hướng mặt của Robot sẽ là h = (h+k) mod 8, còn khi quay trái k lần ta sẽ có h = (h + n (k mod 8)) mod 8. Bạn để ý rằng phép trừ k đơn vị trên vòng tròn n điểm sẽ được đổi thành phép cộng với n k. Độ phức tạp Cỡ n, trong đó n là số kí tự trong xâu input. (* Robot.pas *) uses crt; const mn = 500; BL = #32; NL = #13#10; xx = 0; yy = 1; huong: array[0 7,0 1] of integer = ( (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1) ); 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 } x,y: integer; { Toa do Robot } h: integer; { huong di chuyen cua Robot } 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 ThucHien(i: integer); begin case C[i] of 'G': begin x:=x+M[i]*huong[h,xx];y:=y+M[i]*huong[h,yy] end; 'R': h := (h + M[i]) mod 8; 'L': h := (h + 8 - (M[i] mod 8)) mod 8;
  31. end; end; procedure Pha2; var i: integer; begin x := 0; y := 0; h := 0; 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 '#') 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 := '(GR3(G2L)2(L5G)0)2G3'; Go(s); writeln(NL,NL,'Ket qua (x,y) = ',x,BL,y); { (x,y) = (10,-4) } readln; END. // DevC++: Robot.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
  32. int p; // chi so ngon stack st int x, y; // Toa do (x,y) cua Robot const int xx = 0, yy = 1; int step[8][2] = {{0,1},{1,1},{1,0},{1,-1}, {0,-1},{-1,-1},{-1,0},{-1,1}}; int h; // huong di chuyen cua Robot // P R O T O T Y P E S void Go(char *); void LenhDon(char); void LenhLap(); int DocSo(); void Cach(); bool LaChuSo(char); bool LaChuCai(char); void Pha2(); void ThucHien(int); // I M P L E M E N T A T I O N int main(){ strcpy(s,"(GR3(G2L)2(L5G)0)2G3"); // (x,y) = (10,-4) Go(s); cout = 'A') && (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 Go(char *s ) { cout << endl << "input: " << s; // init p = 0; n = 0; 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(); }
  33. void ThucHien(int i) { switch(C[i]) { case 'G': x += M[i]*step[h][xx]; y += M[i]*step[h][yy]; break; case 'R': h = (h+M[i]) % 8; break; case 'L': h = (h+8-(M[i]%8)) % 8; break; } } void Pha2() { int i; cout << endl << s << " = "; x = y = 0; h = 0; i = 1; while (i <= n) { if (C[i] == '#') { R[i]; if (R[i] == 0) { R[i] = M[i]; ++i; } else i = T[i]; } else { ThucHien(i); // thuc hien dong lenh i ++i; } } } 2.4 Hàm nhiều biến Một số hàm có số tham biến không hạn chế, Thí dụ 1: Hàm ucln – tính ước chung lớn nhất của các số nguyên được định nghĩa như sau: ucln( ) = 0, không có tham biến, qui ước = 0 ucln(x) = |x|, ucln của số x là giá trị tuyệt đối của chính số đó ucln(a,b) = ucln(b,a), ucln(a,0) = a, ucln(a,b) = ucln(a mod b, b) ucln(x1, x2, ,xn) = ucln (ucln(x1, x2, ,xn-1), |xn|), n 2. Thí dụ 2: Hàm sum – tính tổng của các số nguyên: sum( ) = 0, sum(x) = x, sum(x1, x2, ,xn) = sum(sum(x1, x2, ,xn-1), xn), n 2. Ngoài ra còn các hàm lấy min, max của dãy phần tử Cho một biểu thức được viết đúng cú pháp, chứa các hằng nguyên, các biến a, b, được gán sẵn các trị a = 0, b = 1, , các phép toán số học +, –, *, / (chia nguyên), % (chia dư), các cặp ngoặc và các lời gọi hàm nhiều biến @. Hãy tính giá trị của biểu thức nếu @ là hàm ucln. Thí dụ, 16 sẽ là giá trị của biểu thức (10+@(12,30+@(6,8))+17*@( )+2)*@(1,3). Thật vậy, ta có @( ) = 0; @(6,8) = 2; @(12,30+@(6,8)) = @(12,30+2) = @(12,32) = 4; @(1,3) = 1; (10+@(12,30+@(6,8))+17*@( )+2)*@(1,3) = (10+4 + 17*0 +2)*1 = 16*1 = 16. Thuật toán Ta mở rộng thuật toán của bài Val để có thể xử lý thêm các trường hợp sau. Thứ nhất, chương trình phải nhận biết được phép toán đảo dấu. Đây là phép toán 1 ngôi khác với phép trừ là phép toán 2 ngôi. Thí dụ, biểu thức –a + b có phép toán đảo dấu. Phép này cũng khá dễ nhận biết. Nếu gặp dấu – và trong ngọn của ngăn xếp c không chứa phép toán nào thì phép – này sẽ là phép toán đổi dấu. Ta nạp vào ngăn xếp c kí hiệu ! cho phép đổi dấu nhằm phân biệt tường minh với với phép toán trừ. Kỹ thuật này có thể gây nhập nhằng, thí dụ, khi xử lí biểu thức a–b thì dấu – gặp đầu tiên nên trong ngăn xếp c không chứa phép toán nào. Hệ thống sẽ coi là phép toán đổi dấu. Ta khắc phục tình huống này bằng cách sau. Sau khi thực hiện hết các phép toán trong ngăn xếp c, nếu trong ngăn xếp tính toán t còn hơn 1 phần tử thì ta cộng dồn kết quả vào t[1]. Như vậy ta đã giả thiết a – b = a+(–b) trong đó – là phép đổi dấu. Thứ hai, chương trình phải xử li được các tình huống gọi hàm @ với các tham biến khác nhau. Khi gặp kí hiệu @ ta xác định xem giữa cặp ngoặc ( ) có đối tượng nào không. Nếu không có, ta ghi nhận một lời gọi hàm rỗng trong ngăn xếp c. Trong danh sách tham biến của lời gọi hàm có thể chứa dấu phảy dùng để ngăn cách các tham biến. Ta cũng nạp dần các dấu ngăn này vào ngăn xếp c. Thủ tục Cach bỏ qua các dấu cách trong xâu input s, tìm đến kí tự có nghĩa s[v] tiếp theo.
  34. Với hai ngăn xếp c dùng để ghi nhận các dấu phép toán và t dùng để chứa các giá trị cần tính toán ta tổ chức đọc duyệt xâu input s và xử lí như sau. 1. Khởi trị các ngăn xếp, 2. Với mỗi kí tự s[v] ta xét 2.1 s[v] = '@': Nạp @ vào c; đọc tiếp s để xác định xem giữa cặp ngoặc ( ) có kí hiệu nào không. Nếu không có: nạp thêm $ vào c để ghi nhận lời gọi hàm rỗng; 2.2 s[v] = '(': Nạp ( vào c; 2.3 s[v] là chữ số '0' '9': Đọc số này và nạp vào ngăn xếp t; 2.4 s[v] là tên biến (chữ cái 'a' 'z'): Nạp trị của các biến này vào ngăn xếp t. Trị của biến x được tính theo công thức x – 'a'; 2.5 s[v] là dấu phảy: Thực hiện các phép toán (nếu có) trên ngọn ngăn xếp c để tính trị của biểu thức ứng với tham số này. Thí dụ, s = "@(a+1, " thì ta phải tính trị của a + 1 trước khi gọi hàm; 2.5 s[v] = ')': Ta cần xác định xem dấu ')' đóng một biểu thức con hay đóng danh sách tham biến của một lời gọi hàm. Trước hết ta thực hiện các phép toán (nếu có) trên ngọn ngăn xếp c để tính trị của biểu thức kết thúc bằng dấu ')'. Kế đến ta duyệt ngược ngăn xếp c để xác định vị trí của dấu '('. Sát trước vị trí này có thể có dấu @ hoặc không. Nếu có ta tính hàm. Nếu sát sau '(' là kí hiệu '$' thì ta hiểu là hàm rỗng, ta sinh trị 0 cho ngăn xếp t. 2.6 s[v] là dấu các phép toán +, –, *, /, %: Ta thực hiện các phép toán bậc cao trên ngọn ngăn xếp c rồi nạp phép toán s[v] này vào c. Riêng với phép – ta cần xác định xem có phải là phép đảo dấu hay không. (* Func.pas *) uses crt; const bl = #13#10; nl = #32; mn = 500; var c: array[0 mn] of char; { ngan xep phep toan } ic: integer; { ngon ngan xep c } t: array[0 mn] of integer; { ngan xep tinh toan } it: integer; { ngon ngan xep t } s: string; { input } v: integer; { duyet s } function Ucln(a,b: integer): integer; var r: integer; begin a := abs(a); b := abs(b); while b > 0 do begin r := a mod b; a := b; b := r; end; Ucln := a; end; procedure Cach; begin while s[v] = bl do inc(v) end; function LaBien(c: char): Boolean; begin LaBien := (c in ['a' 'z']); end; function LaChuSo(c: char): Boolean; begin LaChuSo := (c in ['0' '9']); end; function LaPhepToan(c: char): Boolean; begin LaPhepToan := (c in ['+','-','*','/','%','!']) end; function Val(c: char): integer; begin Val := Ord(c)-ord('a'); end; function Bac(p: char): integer; begin if (p in ['+','-']) then Bac := 1 else if (p in ['*','/', '%']) then Bac := 2 else if (p = '!') then Bac := 3 else Bac := 0; end; function DocSo: integer; var so: integer; begin so := 0; while LaChuSo(s[v]) do
  35. begin so := so*10 + Ord(s[v])-ord('0'); inc(v); end; DocSo := so; end; procedure Tinh(p: char); begin case p of '+': begin t[it-1] := t[it-1] + t[it]; dec(it) end; '-': begin t[it-1] := t[it-1] - t[it]; dec(it) end; '*': begin t[it-1] := t[it-1] * t[it]; dec(it) end; '/': begin t[it-1] := t[it-1] div t[it]; dec(it) end; '%': begin t[it-1] := t[it-1] mod t[it]; dec(it) end; '!': begin t[it] := -t[it] end; { phép đảo dấu } end end; procedure Napc(ch: char); begin inc(ic); c[ic] := ch end; procedure NapBien(x: char); begin inc(v); inc(it); t[it] := Val(x); end; procedure NapSo; var so: integer; begin inc(it); t[it] := DocSo; end; procedure NapPhepToan(p: char); begin inc(v); if p = '-' then if Not LaPhepToan(c[ic]) then begin Napc('!'); exit end; while (Bac(c[ic]) >= Bac(p)) do begin Tinh(c[ic]); dec(ic) end; Napc(p); end; procedure NapPhay; begin inc(v); while LaPhepToan(c[ic]) do begin Tinh(c[ic]); dec(ic) end; Napc(','); end; procedure NapNgoac; begin inc(v); Napc('('); end; procedure NapHam; begin inc(v); Napc('@'); Cach; NapNgoac; { bo qua ( } Cach; if s[v] = ')' then { Ham rong } Napc('$'); end; procedure XuLiHam(i: integer); var j,kq: integer; begin if c[i+1] = '$' then begin inc(it); t[it] := 0; ic := i - 2; exit end; kq := 0; for j := it-ic+i to it do kq := Ucln(kq,t[j]); it := it-ic+i; t[it] := kq;
  36. ic := i - 2; end; procedure XuLiNgoac; { gap ) } var i: integer; begin inc(v); while LaPhepToan(c[ic]) do begin Tinh(c[ic]); dec(ic) end; i := ic; while (c[i] '#') do if LaBien(s[v]) then NapBien(s[v]) else if LaChuSo(s[v]) then NapSo else if LaPhepToan(s[v]) then NapPhepToan(s[v]) else if s[v] = ',' then NapPhay else if s[v] = '(' then NapNgoac else if s[v] = '@' then NapHam else if s[v] = ')' then XuLiNgoac else inc(v); while (LaPhepToan(c[ic])) do begin Tinh(c[ic]); dec(ic) end; for i := 2 to it do t[1] := t[1]+t[i]; BieuThuc := t[1]; end; BEGIN s := '@(-70,12+10-b,@(y+5,10)*c+12)'; writeln(nl,s, ' = ',BieuThuc(s)); { 7 } readln; END. // Dev-C++: Func #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]; // stack lenh int ic; // ngon stack c int t[mn]; // stack tinh toan int it; // ngon stac v int v; // duyet s char s[mn]; // xau input // P R O T O T Y P E S int BieuThuc(char *); int DocSo(); void Cach(); bool LaPhepToan(char); bool LaChuSo(char); bool LaBien(char); int Val(char); int Bac(char); void NapHam(); void NapNgoac(); void NapSo(); void NapPhay(); void XuLiNgoac();
  37. void XuLiHam(int); void Tinh(char); void XuLiToan(char); int Ucln(int , int); // I M P L E M E N T A T I O N int main(){ strcpy(s,"(10+@(12,30+@(6,8))+17*@()+2)*@(1,3)"); cout = '0') && (c = 'a') && (c <= 'z'); } int Val(char x) { return int(v-'0'); } 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 NapNgoac() { c[++ic] = '('; ++v; } void NapHam() { c[++ic] = '@'; ++v; // bo qua dau @ trong s Cach(); // tim dau ( c[++ic] = s[v]; // Nap ( ++v; // bo qua dau ( tring s Cach(); if (s[v]==')') c[++ic] = '$';// ham rong } void NapSo() { t[++it] = DocSo();} void NapVal(char x) { t[++it] = Val(x); ++v;} void Tinh(char p) { switch(p) { case '+': t[it-1] += t[it]; it; break; case '-': t[it-1] -= t[it]; it; break; case '*': t[it-1] *= t[it]; it; break; case '/': t[it-1] /= t[it]; it; break; case '%': t[it-1] %= t[it]; it; break; case '!': t[it] = -t[it]; break; } } void XuLiHam(int i) { // c[i-1 i] = @( int kq = 0 ; // ket qua
  38. if (c[i+1]=='$') { // ham rong ic = i-2; t[++it] = 0; return; } int k = ic - i + 1; // so tham bien int jj = it; it = it - k + 1; for(int j = it; j = Bac(p)) { Tinh(c[ic]); ic; } c[++ic] = p; } int BieuThuc(char *s ) { cout 1; it) t[1] += t[it]; return t[1]; } 2.5 Files files.inp files.out Người ta cần xử lí một số file trong số các file có tên 1, 2, ,48 hiện
  39. LOAD 3 LOAD 4 lưu trên đĩa cứng để tạo ra một file kết quả có tên 49. Qui trình xử lí MODI MODI được lập trình sẵn. Chương trình được viết bằng ngôn ngữ quản lý file SAVE 50 SAVE 51 gồm các lệnh LOAD 4 LOAD 3 LOAD i : đọc file i vào miền nhớ RAM MODI MODI MODI: sửa nội dung hiện có trên RAM SAVE 51 INS 51 INS j: xen file j vào file trên RAM LOAD 50 MODI SAVE j: ghi nội dung trên RAM vào file tên j. INS 51 SAVE 50 END: kết thúc chương trình. MODI LOAD 1 SAVE 52 INS 2 Trừ lệnh SAVE 49 cuối cùng, các lệnh SAVE đều được sử dụng để lưu LOAD 1 MODI tạm các kết quả trung gian với các tên file từ 50 trở đi. Với các file kích INS 2 INS 50 thước lớn, người ta muốn hạn chế số lần ghi đĩa bằng lệnh SAVE nhằm MODI SAVE 49 tiết kiệm thời gian xử lí. Hãy thay chương trình ghi trong files.inp bằng INS 52 END một chương trình tương đương ghi trong files.out với ít lệnh SAVE. Hai SAVE 49 chương trình được xem là tương đương nếu file 49 chứa kết quả cuối END cùng có nội dung giống nhau. Trước hết ta xét một thí dụ minh họa. Giả sử lúc đầu mỗi file có chỉ số i chứa một số nguyên dương i+10, i = 1, 2, , 48. Thao tác MODI lật các chữ số trong RAM, tức là viết dãy số theo thứ tự ngược lại. Thao tác INS i đọc số trong file i rồi xen vào sau chữ số đầu tiên của file hiện lưu trên RAM. CHƯƠNG NỘI RAM CHƯƠNG NỘI RAM TRÌNH TRONG DUNG TRÌNH DUNG FILES.INP TRONG TRONG TRONG FILE FILES.OUT FILE LOAD 3 13 13 LOAD 4 14 14 MODI 31 MODI 41 SAVE 50 31 31 SAVE 51 41 41 LOAD 4 14 14 LOAD 3 13 13 MODI 41 MODI 31 SAVE 51 41 41 INS 51 41 3411 LOAD 50 31 31 MODI 1143 INS 51 41 3411 SAVE 50 1143 1143 MODI 1143 LOAD 1 11 11 SAVE 52 1143 1143 INS 2 12 1121 LOAD 1 11 11 MODI 1211 INS 2 12 1121 INS 50 1143 11143211 MODI 1211 SAVE 49 11143211 11143211 INS 52 1143 11143211 END SAVE 49 11143211 11143211 END Khí đó trình tự thực hiện hai chương trình ghi trong input file FILES.INP và output file FILES.OUT được giải trình chi tiết trong bảng. Nội dung ghi trong 4 file mang mã số 1, 2, 3 và 4 đầu tiên lần lượt là 11, 12, 13 và 14. Kết quả cuối cùng của cả hai chương trình đều giống nhau và bằng 11143211. Chương trình ghi trên file inp chứa 4 lệnh SAVE trong khi chương trình ghi trên file out chứa 3 lệnh SAVE. Bạn cũng cần lưu ý rằng phép xen file INS nói chung không thỏa tính giao hoán và kết hợp. Để minh họa ta tạm qui ước nội dung ghi trong file được đặt giữa cặp ngoặc []. Khi đó, [12] INS [13] = [1132], trong khi [13] INS [12] = [1123], ngoài ra ([12] INS [13]) INS [14] = [1132] INS [14] = [114132], trong khi [12] INS ([13] INS [14]) = [12] INS [1143] = [111432].
  40. Thuật toán t S 49 I 52 M S 52 I M L 1 L 2 I Cây t tạo từ pha 1 Các từ viết tắt S 50 S 51 L – LOAD S – SAVE M – MODIFY M M I - INS L 3 L 4 Thuật toán được triển khai theo 2 pha: Pha Đọc và Pha Ghi. Pha thứ nhất, Pha Đọc sẽ đọc từng dòng lệnh của chương trình nguồn P từ input file và tạo thành một cây t. Pha thứ hai, Pha Ghi chỉ đơn thuần ghi lại cây t vào output file theo nguyên tắc ưu tiên lệnh SAVE cho cây con phải. Ta trình bày chi tiết các kỹ thuật tại hai pha. Mỗi nút của cây t có 4 thành phần (C, f , L, R) trong đó C là chữ cái đầu của lệnh LOAD, SAVE, MODI, END, f là số hiệu file (tên) trong dòng lệnh, L và R lần lượt là con trỏ trái và phải tới nút tiếp theo trên cây. Ta tạm kí hiệu 0 là con trỏ NULL trong C++ và NIL trong Pascal. 1. Pha Đọc sẽ đọc lần lượt từng dòng lệnh từ chương trình P vào biến string s và nhận biết lệnh qua chữ cái đầu tiên LOAD, SAVE, MODI, INS, END rồi xử lí theo từng trường hợp như sau: LOAD f : Nếu file f chưa xuất hiện thì tạo một nút mới v = (C, f, 0, 0) và đánh dấu f là file đã xuất hiện. Việc đánh dấu được thực hiện thông qua phép gán p[f] = v trong đó p là mảng các con trỏ tới các nút, f là số hiệu (tên) file, v là giá trị của con trỏ được cấp phát cho nút được khởi tạo cho file f, p[f] = 0 (NULL/nil) cho biết file f chưa xuất hiện trong chương trình P. Nếu f đã xuất hiện thì ta gán v là con trỏ tới nút đã khởi tạo cho file f, v = p[f]; SAVE f: Không tạo nút mới, chỉ ghi nhận f vào biến lastsave để biết phép SAVE cuối cùng của chương trình P sẽ ghi kết quả vào file nào. Đồng thời ta cũng cần đánh dấu p[f] = v để biết rằng file hiện có trên RAM là v đã được ghi vào file f; MODI: Tạo nút mới v = NewElem('M',–1,v,0) đặt trên nút v hiện hành. Giá trị của trường fnum được đặt là –1 cho biết lệnh này không quan tâm đến tên file vì nó chỉ MODIFY nội dung của file hiện có trên RAM; INS f: Nếu file f chưa xuất hiện thì tạo nút mới v = NewElem('I',f,v,0), ngược lại, nếu file f đã xuất hiện thì tạo nút mới v = NewElem('I',-1,v,p[f]). 2. Pha Ghi Giả sử t là cây tạo được sau pha 1. Ta viết thủ tục ToFile(t) duyệt cây t theo nguyên tắc ưu tiên cây con phải để ghi vào output file chương trình tối ưu số lệnh SAVE như sau. Cụ thể là ta duyệt cây con
  41. phải trước, sau đến cây con trái và cuối cùng là nút giữa. Thủ tục này có tên RNL. Ta xét các tình huống sau đây. 2.1 Cây t chỉ có cây con trái L, t = (L,0): Ta chỉ việc gọi thủ tục ToFile(L). 2.2 Cây t có cả hai cây con trái L và phải R, t = (L,R) và hai cây con này được gắn với nhau bằng lệnh INS: Trước hết phải gọi thủ tục ToFile(R) và ghi kết quả trung gian vào một file tạm m, sau đó gọi thủ tục ToFile(L) rồi thêm vào cuối dòng lệnh INS m. Độ phức tạp Cỡ n – số dòng lệnh trong input file. Bình luận Thuật toán trên cũng bỏ qua trường hợp dãy lệnh SAVE f giống nhau liên tiếp cũng như trường hợp hai lệnh liên tiếp là LOAD f và SAVE f với cùng một tên file. Bạn có thể cải tiến thêm bằng cách đọc input file một lần vào miền nhớ và loại bỏ các lệnh này trước khi tổ chức cây t. (* Files.pas *) uses crt; const fn = 'files.inp'; gn = 'files.out'; mn = 400; nl = #13#10; bl = #32; chuso = ['0' '9']; type pelem = ^elem; elem = record com: char; { lenh } fnum: integer; { so hieu file } L,R: pelem; { tro trai, phai } end; var f,g: text; { f: input file; g: output file } p: array[1 mn] of pelem; { danh dau cac file } s: string; { dong lenh } t: pelem; { cay nhi phan chuong trinh } lastSave: integer; tmp: integer; { file trung gian } function DocSo: integer; { doc so tu dong lenh s } var i, so: integer; begin so := 0; i := 1; while not (s[i] in chuso) do inc(i); while (s[i] in chuso) do begin so := so*10 + ord(s[i]) - ord('0'); inc(i); end; DocSo := so; end; function NewElem(c: char; fno: integer; Lp,Rp: pelem): pelem; var e: pelem; begin new(e); e^.com := c; e^.fnum := fno; e^.L := Lp; e^.R := Rp; NewElem := e; end; function Load(fno: integer): pelem; begin if p[fno] = nil then p[fno] := NewElem('L',fno,nil,nil); Load := p[fno]; end; procedure Save(v: pelem; fno: integer); begin lastSave := fno; p[fno] := v; end; function Ins(v: pelem; fno: integer): pelem; begin if p[fno] = nil then Ins := NewElem('I',fno,v,nil)
  42. else Ins := NewElem('I',-1,v,p[fno]); end; function Doc: pelem; var i: integer; v: pelem; { RAM } begin for i := 1 to mn do p[i] := nil; assign(f,fn); reset(f); while not seekeof(f) do begin readln(f,s); s := s + '#'; case s[1] of 'L': v := Load(DocSo); 'S': Save(v,DocSo); 'M': v := NewElem('M',-1,v,nil); 'I': v := Ins(v,DocSo); 'E': begin close(f); Doc := v; exit end; end; end; end; procedure ToFile(t: pelem); var sav: integer; begin sav := 0; if (t = nil) then exit; if (t^.R 0) then writeln(g,'INS',bl,sav); 'L': writeln(g,'LOAD',bl,t^.fnum); 'M': writeln(g,'MODI'); end; end; procedure Ghi(t: pelem); begin assign(g,gn); rewrite(g); tmp := 49; ToFile(t); writeln(g,'SAVE',bl,lastsave,nl,'END'); close(g); end; BEGIN t := Doc; Ghi(t); writeln(nl,' Fini');readln; END. // Dev-C++: Files #include #include #include using namespace std; // D A T A A N D V A R I A B L E const char * fn = "files.inp"; const char * gn = "files.out"; const char * LOAD = "LOAD"; const char * MODI = "MODI"; const char * INS = "INS";
  43. const char * SAVE = "SAVE"; const char * END = "END"; const char star = '*'; // Node const int mn = 400; struct elem { char com; int fnum; // com: lenh, fnum: file number elem * L; elem * R; // tro trai, tro phai }; elem* p[mn]; int tmp; int lastsave; // P R O T O T Y P E S elem * Doc(); elem * Load(int); elem *NewNode(char, int, elem*, elem*); elem * Ins(elem *, int); void Ghi(elem *t); void ToFile(elem*); ofstream g(gn); // I M P L E M E N T A T I O N int main() { elem * t = Doc(); Ghi(t); cout R != NULL) { ++tmp; sav = tmp; ToFile(t->R); g L); switch(t->com) { case 'I': if (t->R == NULL) g fnum 0) g fnum R = p[fno]; else e->fnum = fno; return e; } elem * Load(int fno) { // Tao node LOAD if (p[fno] == NULL) p[fno] = NewNode('L', fno, NULL, NULL); return p[fno]; }
  44. elem * NewNode(char cm, int i, elem * lp, elem * rp) { elem * pt = new elem; // Tao node moi pt->com = cm; pt->fnum = i; pt->L = lp; pt->R = rp; return pt; } elem * Doc() {// Doc vhuong trinh, tao cay char s[10]; ifstream f(fn); elem * v = NULL; // RAM int i, fno; for (i = 0; i > s; fno = 0; switch(s[0]) { case 'E': f.close(); return v; // END case 'L': f >> fno; v = Load(fno); break; // LOAD case 'S': f >> fno; lastsave = fno; p[fno]= v; break; // SAVE case 'I': f >> fno; v = Ins(v,fno); break; // INS case 'M': v = NewNode('M',-1,v,NULL); break; // MODIFY } } } 2.6 Gen (Bài tương tự) Trong phòng thí nghiệm sinh học phân tử người ta bảo quản các đoạn mã di truyền, tạm gọi là các đoạn gen trong các tủ chứa đặc biệt được mã số 1, 2, ,98. Các gen được chỉnh sửa và cấy ghép với nhau trên bàn thí nghiệm T để tạo ra một gen cuối cùng đặt trong tủ chứa số 99 theo một chương trình máy tính tự động bao gồm các thao tác sau: TAKE i : lấy một gen từ tủ chứa i đặt lên bàn thí nghiệm T, MODI: làm sạch, sửa chữa các thông tin di truyền trong gen hiện có trên bàn thí nghiệm T, INS j: cấy ghép gen hiện có trên T với gen trong tủ chứa j, kết quả thu đượ một gen trên T, STORE k: cất gen trên T vào tủ chứa k, END : kết thúc chương trình. Việc lấy và cất giữ gen đòi hỏi các thủ tục rất phức tạp nên người ta cần hạn chế đến mức tối đa các thao tác này. Ngoài ra, lưu ý rằng việc cấy ghép gen i vào gen j cho kết quả khác với việc cấy ghép gen j vào gen i. Hãy thay chương trình cho trước bằng một chương trình tương đương với ít lệnh STORE nhất theo nghĩa cho cùng kết quả thu được trong tủ chứa 99 như chương trình ban đầu. Trong quá trình thao tác được phép sử dụng các tủ chứa tạm từ 100 trở đi . 2.7 Tối ưu hóa chương trình (Bài tương tự) prog.inp prog.out Trong các bộ xử lí một địa chỉ các thao tác xử lí được thực hiện trên LOAD x LOAD x thanh ghi A, các hằng và biến được ghi trong miền nhớ RAM với các địa ADD y SUB y chỉ 0, 1, 2, Chương trình được viết dưới dạng một dãy tuần tự các lệnh SAVE 100 SAVE 100 mã máy bao gồm các lệnh sau LOAD x LOAD x LOAD i: đọc dữ liệu từ địa chỉ i vào thanh ghi A, SUB y ADD y ADD j: cộng số hiện có trên thanh ghi A với số có trong địa SAVE 101 MULT 100 chỉ j, kết quả để trên A, A := A+(j), trong đó (j) kí hiệu nội LOAD 100 SAVE z dung có trong địa chỉ j, MULT 101 END SUB j: A := A (j), SAVE z MULT j: A := A*(j), END DIV j: A := A/(j), SAVE j: ghi nội dung trển thanh ghi A vào địa chỉ j, END : kết thúc chương trình.
  45. Giả thiết rằng các kết quả tính toán trung gian được lưu tạm vào vùng nhớ tự do có địa chỉ qui ước từ 100 trở đi. các phép toán không thỏa các tính chất giao hoán và kết hợp. Hãy thay chương trình ghi trên text file tên prog.inp bằng một chương trình tương đương với ít lệnh SAVE nhất và ghi kết quả vào text file tên prog.out . Thí dụ, file prog.inp là chương trình tính z := (x+y)*(x-y) với 3 lệnh SAVE, file prog.out là chương trình tương đương với 2 lệnh SAVE. 2.8 Mức của biểu thức Trong các biểu thức tính toán người ta thường dùng các cặp ngoặc ( ) để nhóm thành các biểu thức con. Mức của biểu thức được hiểu là số lượng tối đa các cặp ngoặc lồng nhau trong biểu thức, thí dụ biểu thức (a+(b–c)*d)–(a–b) có mức 2. Cho trước k cặp ngoặc và mức h. Hãy cho biết có thể xây dựng được bao nhiêu biểu thức mức h và sử dụng đúng k cặp ngoặc. Thí dụ, ta có 3 biểu thức mức h = 2 sử dụng đúng k = 3 cặp ngoặc như sau: (()()) (())() ()(()) Dạng hàm: Level(k,h) Test 1. Level(3,2) = 3; Test 2. Level(19,18) = 35. Thuật toán Gọi s(k,h) là hàm 2 biến cho ra số lượng các biểu thức khác nhau có mức h và chứa đúng k cặp ngoặc. Xét cặp ngoặc thứ k. Ta thấy, - Nếu gọi A là biểu thức mức h–1 chứa đúng k–1 cặp ngoặc thì (A) sẽ là biểu thức độ sâu h và chứa đúng k cặp ngoặc. - Nếu gọi B là biểu thức mức h chứa đúng k–1 cặp ngoặc thì ( ) B và B ( ) sẽ là hai biểu thức mức h và chứa đúng k cặp ngoặc. Tuy nhiên trong trường hợp này ta phải loại đi tình huống ( ) B = B ( ). Tình huống này chỉ xảy ra duy nhất khi B có dạng dãy các cặp ngoặc mức 1: B = ( ) ( ). Khi đó ( ) B = ( ) ( ) ( ) = B ( ). Tóm lại, ta có s(k,h) = s(k–1,h–1) + 2s(k–1,h) với h > 1, và s(k,1) = 1, k = 1, 2, , với k 1cặp ngoặc chỉ có thể viết được 1 biểu thức mức 1 gồm dãy liên tiếp k cặp ngoặc ()() (). Ngoài ra ta có s(0,h) = 0, h > 0, với 0 cặp ngoặc không thể xây dựng được biểu thức mức h > 0; s(0,0) = 1, với 0 cặp ngoặc có duy nhất 1 biểu thức mức 0 (qui ước). Cài đặt: Ta có thể cài đặt hàm s(k,h) với k lần lặp và 2 mảng 1 chiều a và b, trong đó a[j] là giá trị của hàm s(k 1,j), b[j] là giá trị của hàm s(k,j), j = 1 h. Trước hết ta khởi trị ứng với k = 1: a[1] = b[1] = 1; a[i] = 0, i = 2 h với ý nghĩa sau: có 1 cặp ngoặc thì viết được 1 biểu thức mức 1, không có các biểu thức mức trên 1. Giả sử tại bước lặp thứ k 1 ta đã tính được các giá trị của hàm s(k 1,j) và lưu trong mảng a như sau: a[j] = s(k 1,j), j = 1 h. Khi đó các giá trị của hàm s(k,j) sẽ được tính và lưu trong mảng b như sau: b[1] = s(k,1) = 1 b[j] = s(k,j) = s(k–1,j–1) + 2s(k–1,j) = a[j 1] + 2a[j], j = 2 h Độ phức tạp: k.h. (* Level.pas *) uses crt; const bl = #32; nl = #13#10; mn = 1000; function Level(k,h: integer): longint; var a,b: array[0 mn] of longint; i,j: integer; begin fillchar(a, sizeof(a),0); a[1] := 1; b[1] := 1; for i := 2 to k do { i cap ngoac } begin for j := 2 to h do { i cap ngoac, muc j } b[j] := a[j-1] + 2*a[j]; a := b; end; Level := a[h]; end;
  46. BEGIN writeln(nl, level(3,2), nl, level(19,18)); readln; END. // Dev-C++: Level #include #include #include using namespace std; // P R O T O T Y P E S int Level(int, int); // I M P L E M E N T A T I O N int main() { cout << endl << endl << Level(19,18); // 35 cout << endl << endl << Level(3,2); // 3 cout << endl << endl << " Fini" << endl; cin.get(); return 0; } int Level(int k, int h){ int h1 = h+1; int *a = new int[h1]; int *b = new int[h1]; memset(a,0,d1*sizeof(int)); a[1] = b[1] = 1; for (int i = 2; i <= k; ++i) { a[1] = 1; for (int j = 2; j <= h; ++j) b[j] = a[j-1] + 2*a[j]; memmove(a,b,h1*sizeof(int)); } delete a; delete b; return a[h]; } 2.9 Tháp (Bài tương tự) Các em nhỏ dùng các khối gỗ hình chữ nhật to nhỏ khác nhau và có bề dày 1 đơn vị đặt chồng lên nhau để tạo thành một công trình kiến trúc gồm nhiều tòa tháp. Khối đặt trên phải nhỏ hơn khối dưới, số lượng khối các loại là không hạn chế. Độ cao của công trình được tính theo chiều cao của tháp cao nhất trong công trình. Với k khối gỗ có thể xây được bao nhiêu kiểu công trình độ cao h. 3 công trình độ cao 2 được xây bằng 3 khối gỗ 2.10 Mi trang
  47. Trong một file văn bản có n từ. Với mỗi từ thứ i ta biết chiều dài vi tính bằng số kí tự có trong từ đó. Người ta cần căn lề trái cho file với độ rộng m kí tự trên mỗi dòng. Mỗi từ cần được xếp trọn trên một dòng, mỗi dòng có thể chứa nhiều từ và trật tự các từ cần được tôn trọng. Hãy tìm một phương án căn lề sao cho phần hụt lớn nhất ở bên phải các dòng là nhỏ nhất. Giả thiết rằng mỗi từ đều có 1 dấu cách ở cuối, dĩ nhiên dấu cách này được tính vào chiều dài từ. Dữ liệu vào: file văn bản PAGES.INP. Dòng đầu tiên chứa hai số n và m. Tiếp đến là n chiều dài từ với các giá trị nằm trong khoảng từ 2 đến m. Dữ liệu ra: file văn bản PAGES.OUT. Dòng đầu tiên chứa hai số h và k, trong đó h là phần thừa lớn nhất (tính theo số kí tự) của phương án tìm được, k là số dòng của văn bản đã được căn lề. Tiếp đến là k số cho biết trên dòng đó phải xếp bao nhiêu từ. Các số trên cùng dòng cách nhau qua dấu cách. PAGES.INP PAGES.OUT Ý nghĩa: Cần xếp 6 từ chiều dài lần lượt là 2, 2, 3, 3, 6 và 9 trên 6 10 3 3 các dòng dài tối đa 10 kí tự. Nếu xếp thành 3 dòng là (2,2,3,3) 2 2 3 3 6 9 3 2 1 (6) (9) thì phần hụt tối đa là 4 (trên dòng 2). Nếu xếp thành 3 dòng là (2,2,3) (3,6) (9) thì phần hụt tối đa là 3 (trên dòng 1). Như vậy ta chọn cách xếp thứ hai với 3 dòng: Dòng 1: 3 từ; dòng 2: 2 từ; dòng 3: 1 từ. Thuật toán Gọi d(i) là đáp số của bài toán với i từ đầu tiên. Ta xét cách xếp từ w[i]. Đầu tiên ta xếp w[i] riêng 1 dòng, độ hụt khi đó sẽ là h = m v[i]. Nếu chỗ hụt còn đủ ta lại kéo từ i 1 từ dòng trên xuống, độ hụt khi đó sẽ là h = h v[i 1], Tiếp tục làm như vậy đến khi độ hụt h không đủ chứa thêm từ kéo từ dòng trên xuống. Mỗi lần kéo thêm một từ j từ dòng trên vào dòng mới này ta có một phương án. Độ hụt của phương án này sẽ là max (h v[j],d(j 1)). Ta sẽ chọn phương án nào đạt trị min trong số đó. Để cài đặt ta sử dụng mảng một chiều d chứa các giá trị của hàm d(i). Ta khởi trị cho v[0] = m+1 làm lính canh, d[1] = m v[1], vì khi chỉ có 1 từ thì ta xếp trên 1 dòng duy nhất và độ hụt là m v[1]. Để xác định sự phân bố số lượng từ trên mỗi dòng ta dùng mảng trỏ ngược t[1 n] trong đó t[i] = j cho ta biết các từ j, j+1, ,i cùng nằm trên một dòng theo phương án tối ưu. Sau đó ta gọi đệ qui muộn mảng t để tính ra số lượng các từ trên mỗi dòng, ghi vào mảng sl theo trật tự ngược. Độ phức tạp: Cỡ n2 vì với mỗi từ i ta phải duyệt ngược i lần. Tổng cộng có n từ nên số lần duyệt sẽ là n.n. (* Pages.pas *) uses crt; const mn = 200; bl = #32; nl = #13#10; fn = 'pages.inp'; gn = 'pages.out'; type mi1 = array[0 mn] of integer; var n,m,k,h: integer; f,g: text; v, d, t, sl: mi1; (* n - number of words; m - width of page; k - number of lines; h - maximum of white character of all lines; v[i] - length of i-th word; d[i] - solution result of input data v[1 i]; t[i] = j: all words j, j+1, ,i are in one line; sl[i] - number of words in i-th line *) procedure PP(var x: mi1; d,c: integer); var i: integer; begin for i := d to c do write(bl,x[i]); end; function Min(a,b: integer): integer; begin if a b then Max := a else Max := b end; procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n,m); writeln(n,bl,m); for i := 1 to n do read(f,v[i]);
  48. close(f); end; procedure Tinhd(i: integer); var j,h, hmax: integer; begin h := m; j := i; d[i] := m+1; while h >= v[j] do begin h := h - v[j]; hmax := Max(d[j-1],h); if d[i] > hmax then begin d[i] := hmax; t[i] := j; end; dec(j); end; end; function XuLi: integer; var i: integer; begin t[0] := 0; v[0] := m+1; d[0] := 0; for i := 1 to n do Tinhd(i); XuLi := d[n]; end; procedure Xep(i: integer); begin if (i = 0) then exit; inc(k); sl[k] := i-t[i]+1; Xep(t[i]-1); end; procedure Ghi; var i: integer; begin assign(g,gn); rewrite(g); writeln(g,h,bl,k); for i := k downto 1 do write(g,sl[i],bl); close(g); end; procedure Run; var i: integer; begin Doc; PP(v,1,n); h := XuLi; k := 0; Xep(n); writeln(nl, h, bl, k, nl); for i := k downto 1 do write(bl, sl[i]); Ghi; end; BEGIN Run; write(nl, ' Fini ');readln; END. // DevC++: Pages.cpp #include #include #include using namespace std; // Data and variables const char * fn = "pages.inp"; const char * gn = "pages.out"; const int mn = 200; int n; // so luong tu int m; // len dong int k; // so dong can viet
  49. int h; // do hut toi uu int v[mn]; // len cac tu int d[mn]; // int t[mn]; // con tro nguoc int sl[mn]; // Interface void Doc(); void PP(int [], int , int); int XuLi(); void Tinhd(int); void Xep(int); void Ghi(); // Implementation main () { Doc(); h = XuLi(); k = 0; Xep(n); Ghi(); cout 0; i) cout 0; i) g = v[j]; j) { h = h - v[j]; hmax = max(h,d[j-1]); if (d[i] > hmax) { d[i] = hmax; t[i] = j; } } } void Xep(int i) { // xep cac tu tren moi dong if (t[i] == 0) return; sl[++k] = i-t[i]+1; Xep(t[i]-1); } int XuLi() { v[0] = m+1; d[0] = 0; d[1] = m-v[1]; t[1] = 1; for (int i = 2; i > n >> m; cout > v[i]; f.close(); PP(v,1,n); } void PP(int a[], int d, int c) { cout << endl; for (int i = d; i <= c; ++i) cout << a[i] << " "; } 2.11 Xếp thẻ
  50. (Bài tương tự) 1 2 3 4 5 6 7 8 9 0 1 2 Dòng 1 1 2 3 O O O 2 2 Dòng 2 4 5 O 3 3 Dòng 3 6 O 4 3 Bài toán xếp thẻ Xếp n thẻ nhựa đồ chơi với chiều dài cho trước vào 5 6 tấm bảng rộng m đơn vị, giữ đúng trật tự trước sau sao cho số ô trống lớn nhất xét trên tất cả các dòng là nhỏ nhất. Ô trống là ô chứa O. 6 9 Số ghi cạnh mỗi thẻ là chiều dài của thẻ đó. Số ghi tại đầu mỗi thẻ là số hiệu của thẻ đó. 2.12 Xếp xe (Bài tương tự) Tại Hội thi Tin học trẻ có n đoàn học sinh đã xếp hàng đầy đủ tại địa điểm tập trung để chờ Ban tổ chức đưa xe ô tô đến chở các em đi tham quan thủ đô. Mỗi xe có m ghế dành cho mỗi em một ghế. Các đoàn được bố trí lên xe theo đúng trật tự từ đoàn số 1 đến đoàn số n. Mỗi xe có thể xếp vài đoàn liên tiếp nhau nhưng mỗi đoàn cần được xếp gọn trên 1 xe. Sau khi xếp đầy đủ các đoàn, người ta đếm số ghế trống trên mỗi xe và công bố số ghế trống lớn nhất h đã đếm được. Biết số học sinh trong mỗi đoàn, hãy tim một cách xếp xe để giá trị h là nhỏ nhất.
  51. Chương 3 Cặp ghép Lớp các bài toán xác định một tương ứng giữa hai tập phần tử A và B cho trước, thí dụ như tập A gồm các em thiếu nhi và tập B gồm các món quà như trong bài toán Chị Hằng dưới đây được gọi là các bài toán cặp ghép và thường được kí hiệu là f: A B với ý nghĩa là cần xác định một ánh xạ, tức là một phép đặt tương ứng mỗi phần tử i của tập A với duy nhất một phần tử j của tập B, f(i) = j. Một trong các thuật toán giải các bài toán này có tên là thuật toán Ghép cặp. Thuật toán đòi hỏi thời gian tính toán là n.m phép so sánh trong đó n là số phần tử (lực lượng) của tập A, m là số phần tử của tập B, n = ||A||, m = ||B||. Chương này trình bày thuật toán ghép cặp và các biến thể của nó. 3.1 Chị Hằng Nhân dịp Tết Trung Thu Chị Hằng rời Cung Trăng mang m món quà khác nhau mã số 1 m đến vui Trung Thu với n em nhỏ mã số 1 n tại một làng quê. Trước khi Chị Hằng phát quà, mỗi em nhỏ đã viết ra giấy những món quà mà em đó mơ ước. Yêu cầu: giúp Chị Hằng chia cho mỗi em đúng 1 món quà mà em đó yêu thích. Dữ liệu vào: file văn bản autum.inp Dòng đầu tiên: hai số n m Dòng thứ i trong số n dòng tiếp theo: k b1 b2 bk - k là số lượng quà em i yêu thích; b1 b2 bk là mã số các món quà em i yêu thích. Dữ liệu ra: file văn bản autum.out Dòng đầu tiên: v – số em nhỏ đã được nhận quà. v dòng tiếp theo: mỗi dòng 2 số i b cho biết em i được nhận món quà b. Thí dụ, autum.inp autum.out Ý nghĩa 5 5 5 Có 5 em và 5 món quà. Em 1 thích 2 món quà: 1 và 5; em 2 thích 2 2 1 5 1 1 món quà: 2 và 4; em 3 thích 2 món quà: 1 và 2; em 4 thích 3 món quà: 2 2 4 2 4 1, 4 và 5; em 5 thích 2 món quà: 1 và 3. 2 1 2 3 2 Một phương án xếp em nhỏ quà như sau: 1 1; 2 4; 3 2; 4 5; 3 1 4 5 4 5 5 3. 2 1 3 5 3 Thuật toán Giả sử các phần tử của tập nguồn A (các em nhỏ) được mã số từ 1 đến n và các phần tử của tập đích B (các gói quà) được mã số từ 1 đến m. Sau khi đọc dữ liệu và thiết lập được ma trận 0/1 hai chiều c với các phần tử c[i,j] = 1 cho biết em i thích món quà j và c[i,j] = 0 cho biết em i không thích quà j. Nhiệm vụ đặt ra là thiết lập một ánh xạ 1 1 f từ tập nguồn vào tập đich, f: A B. Ta sử dụng phương pháp chỉnh dần các cặp đã ghép để tăng thêm số cặp ghép như sau. Ta cũng sử dụng hai mảng một chiều A và B để ghi nhận tiến trình chia và nhận quà với ý nghĩa như sau: A[i] = j cho biết em i đã được nhận quà j; B[j] = i cho biết quà j đã được chia cho em i; A[i] = 0 cho biết em i chưa được chia quà và B[j] = 0 cho biết quà j trong túi quà B còn rỗi (chưa chia cho em nào). Giả sử ta đã chọn được quà cho các em 1, 2, , i 1. Ta cần xác định f(i) = j, tức chọn món quà j cho em i. Nếu ta tìm ngay được món quà j B thỏa đồng thời các điều kiện sau: B[j] = 0: j là món quà còn trong túi quà B, tức là quà j chưa được chia, c[i,j] = 1, tức là em i thích quà j thì ta đặt f(i) = j và việc chia quà cho em i đã xong. Trường hợp ngược lại, nếu với mọi quà j thỏa c[i,j] = 1 (em i thích quà j) đều đã được chia cho một em t nào đó (B[j] = t ≠ 0) thì ta phải tiến hành thủ tục thương lượng với toàn bộ các em đang giữ quà mà bạn i thích như sau: Tạm đề nghị các em dang giữ quà mà bạn i thích, đặt quà đó vào một túi riêng bên ngoài túi có đề chữ i với ý nghĩa "sẽ trao 1 món quà trong túi này cho bạn i"; Đưa những em vừa trả lại quà vào một danh sách st gồm các em cần được ưu tiên tìm quà ngay. Như vậy, em i sẽ có quà nếu như ta tiếp tục tìm được quà cho một trong số các em trong danh sách st nói trên. Với mỗi em trong danh sách st ta lại thực hiện các thủ tục như đã làm với em i nói trên.
  52. Ta cần đánh dấu các em trong danh sách để dảm bảo rằng không em nào xuất hiện quá hai lần và như vậy sẽ tránh được vòng lặp vô hạn. Sau một số bước lặp ta sẽ thu được dãy t1  t2  tk 1  tk với ý nghĩa là em t1 sẽ nhận quà từ em t2, em t2 sẽ nhận quà từ em t3, em tk-1 sẽ nhận quà từ em tk. và sẽ gặp một trong hai tình huống loại trừ nhau sau đây: Tình huống 1: Ta tìm được một món quà cho em tk, nghĩa là với em tk ta tìm được một món quà j còn rỗi (B[j] = 0) và tk yêu thích (c[tk,j] = 1). Ta gọi thủ tục Update(tk, j) thực hiện dãy các thao tác chuyển quà liên hoàn từ em này cho em kia như sau: em tk trao quà qk của mình cho bạn tk 1 để nhận quà mới j em tk 1 trao quà qk 1 của mình cho bạn tk-2 để nhận quà mới qk từ tay bạn tk; em t2 trao quà q2 của mình cho bạn t1 để nhận quà mới q3 từ tay bạn t3; em t1 nhận quà j. Đây chính là em i mà ta cần chia quà. Ta thu được: f(i) = f(t1) = q2; f(t2) = q3; ; f(tk) = j và hoàn thành việc chia quà cho em i trên cơ sở thương lượng các em trong dãy trên nhừơng quà cho nhau. Tình huống 2: Không gặp tình huống 1, nghĩa là, với mọi em trong dãy t1, t2, , tk mọi món quà các em yêu thích đều đã được chia cho em nào đó. Nói cách khác, chiến lược nhường quà cho nhau (để nhận quà khác) không mang lại kết quả. Ta kết luận: "không thể chia quà cho em i". Do không thể chia được quà cho em i ta tiếp tục chia quà cho các em khác. Tổ chức dữ liệu Mảng nguyên t[1 n], t[j] = i: em j sẽ nhường quà của mình cho bạn i; Mảng nguyên a[1 n], a[i] = j: em i đã được chia quà j; Mảng nguyên b[1 m], b[j] = i: quà j đang có trong tay em i. Để ý rằng a[b[j]] = j và b[a[i]] = i; Mảng nguyên st[1 n]: danh sách các em tạm trả lại quà và đang cần được ưu tiên nhận quà mới. Biến nguyên p: trỏ tới ngăn trên cùng của stack st. Mảng nguyên 2 chiều nhị phân c[1 n,1 m], c[i][j] = 1 khi và chỉ khi em i thích quà j; Hàm Xep(i): chia quà cho bạn i; Xep(i) = 1 nếu tìm được một cách chia, ngược lại, khi không tìm được Xep = 0. Hàm Par thực hiện ghép cặp cho các em theo thứ tự từ 1 đến n. (* Autum.pas *) uses crt; const fn = 'autum.inp'; gn = 'autum.out'; bl = #32; nl = #13#10; mn = 201; type mi1 = array[0 mn] of integer; mb2 = array[0 mn,0 mn] of byte; var n, m: integer; { n - so nguoi; m - so qua } a, b: mi1; t: mi1; st: mi1; p: integer; c: mb2; f,g: text; {f: input file; g: otput file } procedure Doc; var i,j,k,q: integer; begin assign(f,fn); reset(f); read(f,n,m); fillchar(c,sizeof(c),0); for i := 1 to n do begin read(f,k); for j := 1 to k do begin read(f,q); c[i][q] := 1 end; end; close(f); end; procedure Print; var i,j: integer;
  53. begin writeln(nl,n,bl,m); for i := 1 to n do begin for j := 1 to m do write(c[i,j]); writeln; end; end; procedure Update(i,j: integer); var q: integer; begin repeat q := a[i]; { i bỏ qùa q } a[i] := j; b[j] := i; { để nhận quà j } j := q; i := t[i]; { chuyển qua người trước } until q = 0; end; function Xep(i: integer): integer; var j: integer; begin Xep := 1; p := 0; inc(p); st[p] := i; { nạp st } fillchar(t, sizeof(t),0); t[i] := i; while p > 0 do begin i := st[p]; dec(p); { Lấy ngọn st } for j := 1 to m do if c[i,j] = 1 then { i thích qùa j } begin if b[j] = 0 then { qùa j chưa chia } begin Update(i,j); exit end else if t[b[j]] = 0 { b[j] chưa có trong st } then begin inc(p); st[p] := b[j]; t[b[j]] := i end; end; end; Xep := 0; end; procedure Ghi(v: integer); var i: integer; begin assign(g,gn); rewrite(g); writeln(g,v); for i := 1 to n do if a[i] > 0 then writeln(g,i,bl,a[i]); close(g); end; procedure Par; { Ghep cap } var i,v: integer; begin Doc; Print; v := 0; fillchar(a, sizeof(a),0); b := a; for i := 1 to n do v := v + Xep(i); Ghi(v); end; BEGIN Par; write(nl,' Fini '); readln; END. // DevC++: Autum.cpp #include
  54. #include using namespace std; // D A T A A N D V A R I A B L E S const char * fn = "autum.inp"; const char * gn = "autum.out"; const int mn = 201; // so nguoi va so qua toi da int a[mn]; // a[i] = j: em i nhan qua j int b[mn]; // b[j] = i: qua j trong tay em i int t[mn]; // t[j] = i : em j nhuong qua cho ban i int c[mn][mn]; // c[i][j] = 1: i thich qua j int n; // so em nho int m; // so qua int st[mn]; // stack int p; // con tro stack // P R O T O T Y P E S int main(); void Doc(); void Print(); int Par(); int Xep(int); void Update(int, int); void PrintArray(int [], int , int ); void Ghi(int); // I M P L E M E N T A T I O N int main() { Doc(); Print(); int v = Par(); Ghi(v); cout 0) g 0); } int Xep(int i) { // tim qua cho em i memset(t, 0, sizeof(t)); int j; p = 0; st[++p] = i; t[i] = i; while(p > 0) { i = st[p ]; // lay ngon stack for (j = 1; j 0) { // i thich qua j
  55. if (b[j] == 0) { // qua j chua chia Update(i,j); return 1; } if (t[b[j]] == 0) { //b[j] chua co trong danh sach st[++p] = b[j]; t[b[j]] = i; // nap } } } } return 0; // Khong chon duoc qua cho em i } int Par(){ // Cap ghep int v = 0, i; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for (i = 1; i > n >> m; int i,j,k,r; for (i = 1; i > k; for (r = 1; r > j ; c[i][j] = 1; } } f.close(); } Nhận xét Ta có thể dùng ngăn xếp hay hàng đợi trong bài này kết quả không phụ thuộc vào trật tự duyệt. 3.2 Domino
  56. Cho lưới đơn vị gồm n dòng và m cột. Các ô trong lưới được gán mã số 1, 2, , n m theo trật tự từ dòng trên xuống dòng dưới, trên mỗi dòng tính từ trái qua phải. Người ta đặt v vách ngăn giữa hai ô kề cạnh nhau. Hãy tìm cách đặt nhiều nhất k quân domino, mỗi quân gồm hai ô kề cạnh nhau trên lưới và không có vách ngăn ở giữa. domino.inp domino.out Dữ liệu 4 5 8 10 Input file: Text file domino.inp. 2 3 1 2 Dòng đầu tiê`n: 3 số n – số dòng, m – số cột, v – số vách 4 5 3 4 ngăn. 6 7 5 10 Tiếp đến là v dòng, mỗi dòng 2 số a b cho biết vách ngăn đặt 9 10 6 11 giữa hai ô này. 10 15 7 8 Output file: Text file domino.out. 7 12 9 14 Dòng đầu tiên k – số quân 1 2 3 4 5 19 20 12 13 domino tối đa đặt được trên lưới. 6 7 8 9 10 13 18 15 20 Tiếp đến là k dòng, mỗi dòng 2 16 17 số x y cho biết số hiệu của 2 ô kề 11 12 13 14 15 18 19 cạnh nhau tạo thành một quân 16 17 18 19 20 domino. Thuật toán Bài này có hai điểm khác với dạng bài cặp ghép truyền thống. Thứ nhất là ghép cặp được thực hiện từ một tập A với chính nó: f: A A. Thứ hai, mỗi số trong tập A chỉ có thể ghép tối đa với 4 số trong các ô kề cạnh nó mà ta tạm gọi là số kề. Thí dụ, 8 có 4 số kề theo thứ tự trái, phải và trên, dưới là 7, 9 và 3, 13. Các số ngoài rià và các số có vách ngăn còn có ít bạn hơn. Thí dụ, 20 có đúng 1 bạn. Khi đọc dữ liệu ta xác định ngay cho mỗi số i trong bảng bốn số kề và ghi vào mảng ke với ý nghĩa như sau ke[i][j] = 1 khi và chỉ khi i có số kề tại vị trí j; j = 1, 2, 3, 4. Nếu i có vách ngăn phải thì i sẽ mất bạn kề phải. Tương tự, nếu i có vách ngăn dưới thì i sẽ mất bạn kề dưới. Ngoài ra, dễ hiểu rằng các số trên dòng 1 thì không có số kề trên, các số trên dòng n thì không có số kề dưới. Tương tự, các số trên cột 1 thì không có số kề trái, các số trên cột m thì không có số kề phải. Nhắc lại rằng ta chỉ cần sử dụng một mảng a với ý nghĩa a[i] = j, đồng thời a[j] = i cho biết số i chọn số kề j để ghép thành 1 quân domino. Nói cách khác nếu ta xếp được f(i) = j thì ta phải gán a[i] = j và a[j] = i. Tiếp đến ta thực hiện thủ tục Xep(i) cho mọi số chưa được ghép cặp (a[i] = 0) và chưa là bạn của bất kì số nào (b[i] = 0). Khi ghi kết quả ra file ta lưu ý là hai cặp (i , a[i] = j) và (j, a[j] = i) thực ra chỉ tạo thành một quân domino duy nhất, do đó ta chỉ cần ghi một trong hai cặp đó. Ta chọn cặp i a[i]. (* Domino.pas *) uses crt; const maxmn = 201; fn = 'domino.inp'; gn = 'domino.out'; bl = #32; nl = #13#10; phai = 1; trai = 2; tren = 3; duoi = 4; type mi1 = array[0 maxmn] of integer; var n: integer; { so dong } m: integer; { so cot } nm: integer;{ nm = n.m } f,g: text; ke: array[0 maxmn,phai duoi] of Boolean; st: mi1; { stack } p: integer; { ngon st } a, t: mi1; procedure Doc; var i, j, k, v, t: integer; begin fillchar(ke,sizeof(ke),true); assign(f,fn); reset(f); readln(f,n,m,v); { v - so vach ngan } nm := n*m; { dong 1 va dong n } k := (n-1)*m; for j := 1 to m do begin ke[j, tren] := false; ke[j+k, duoi] := false; end;