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 - Chương 2: Xử lý dãy lệnh và biểu thứ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; 
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 
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 
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) 
(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ừ. 
6 10 
2 2 3 3 6 9 
3 3 
3 2 1 
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 Min := a else Min := b end; 
function Max(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]); 
 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 
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 << endl << h << " " << k << endl; 
 for (int i = k; i > 0; --i) cout << " " << sl[i]; 
 cout << endl << " Fini"; cin.get(); 
 return 0; 
} 
void Ghi() { 
 ofstream g(gn); 
 g << h << " " << k << endl; 
 for (int i = k; i > 0; --i) g << sl[i] << " "; 
 g.close(); 
} 
void Tinhd(int i) { 
 int h = m-v[i]; // cho hut 
 d[i] = max(h,d[i-1]); t[i] = i; 
 int hmax; 
 for (int j = i-1; h >= 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; ++i) Tinhd(i); 
 return d[n]; 
} 
void Doc() { 
 ifstream f(fn); f >> n >> m; 
 cout << n << " " << m; 
 for (int i = 1; i > 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ẻ