TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH



tải về 2.51 Mb.
trang1/21
Chuyển đổi dữ liệu24.07.2016
Kích2.51 Mb.
  1   2   3   4   5   6   7   8   9   ...   21
TỦ SÁCH TRI THỨC DUY TÂN



NGUYỄN XUÂN HUY

SÁNG TẠO

TRONG THUẬT TOÁN



LẬP TRÌNH

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



Lời nói đầu 3

Chương 1 Các thuật toán trên String 4

Chương 2 Xử lí dãy lệnh và biểu thức 22

Chương 3 Cặp ghép 50

Chương 4 Các phép lật và chuyển vị 74

74



Chương 5 Luyện tập từ các đề thi 110

Cho số tự nhiên x trong dạng thập phân có tối đa 200 chữ số. Tìm số tự nhiên y đầu tiên lớn hơn x và ở dạng nhị phân x và y có cùng số chữ số 1. 144

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


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.


Các tiền tố và hậu tố của xâu s = 'abcd'

Tiền tố

Hậu tố

1:s = s[1..1] = 'a'

2:s = s[1..2] = 'ab'

3:s = s[1..3] = 'abc'

4:s = s[1..4] = 'abcd'




s:1 = s[1..4] = 'abcd'

s:2 = s[2..4] = 'bcd'

s:3 = s[3..4] = 'cd'

s:4 = s[4..4] = 'd'



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 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ố.

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 lại cho kề nhau, ta sẽ thu được một xâu con của s.


1.2 Về tổ chức dữ liệu vào/ra


Trong hầu hết các bài ta giả thiết dữ liệu vào và ra được ghi 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.




data.inp
Tinh tong cua 12 so sau day:
1 -2 3 -4 5 6
7 8 9 10 -11 -12
data.out
Tong cua 12 so:
+1 -2 +3 -4 +5 +6 +7 +8 +9 +10 -11 -12 = 20
1.3 Data

Trong file văn bản data.inp chứa dòng dữ liệu đầu tiên có nội dung
"Tinh tong cua n so sau day:",
trong đó n là một số nguyên dương cho trước.
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');

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 << endl << endl << " Fini" << endl;

cin.get();

return 0;

}

bool LaChuSo(char c) { return (c >= '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;

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 << "Tong cua " << n << " so:" << endl;

for (i = 0; i < n; ++i) {

f >> x; // doc tung so x

if (x > 0) g << " +" << x; else g << " " << x;

t += x; // lay tong

}

g << " = " << t;

f.close(); // dong input file

g.close();

delete s; // thu hồi biến s, nếu cần

}

1.4 Xâu con chung


Hãy tìm chiều dài lớn nhất k trong số các xâu con chung của hai xâu x và y.
Thí dụ, x = "xaxxbxcxd", y = "ayybycdy", chiều dài của xâu con chung dài nhất là 4 ứng với xâu "abcd".

Thuật toán

Xét hàm 2 biến s(i,j) là đáp số khi giải bài toán với 2 tiền tố i:x và j:y. Ta có,



  • s(0,0) = s(i,0) = s(0,j) = 0: một trong hai xâu là rỗng thì xâu con chung là rỗng nên chiều dài là 0;

  • 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) = Max { s(i–1,j), s(i,j–1) }.

Để cài đặt, trước hết ta mường tượng là có thể sử dụng mảng hai chiều v với qui ước v[i][j] = s(i,j). Sau đó ta cải tiến bằng cách sứ dụng 2 mảng một chiều a và b, trong đó a là mảng đã tính ở bước thứ i–1, b là mảng tính ở bước thứ i, tức là ta qui ước a = v[i–1] (dòng i–1 của ma trận v), b = v[i] (dòng i của ma trận v). Ta có, tại bước i, ta xét kí tự x[i], với mỗi j = 0..len(y)–1,

  • Nếu x[i] = y[j] thì b[j] = a[j–1] + 1;

  • Nếu x[i] ≠ y[j] thì b[j] = Max { a[j], b[j–1] }.

Sau khi đọc dữ liệu vào hai xâu x và y ta gọi hàm XauChung để xác định chiều dài tối đa của xâu con chung của x và y. a,b là các mảng nguyên 1 chiều.

Độ phức tạp: Cỡ m.n, m = len(x), n = len(y).

(* XauChung.pas *)

function Max(a,b: integer): integer;

begin if a > 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

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

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 < m; ++i) {

v = 0;

for (j = 0; j < n; ++j) {

t = a[j];

if (x[i] == y[j]) a[j] = v + 1;

else a[j] = 0;

kmax = Max(kmax,a[j]);

v = t;

}

}

return kmax;

}

int main() {

cout << endl << DoanChung("xabcxxabcdxd","aybcyabcdydy");//4

cin.get();

return 0;

}

Cách làm test

Test 1. Trước hết viết một xâu s sau đó xây dựng 2 xâu x = y = s. Đáp số len(s). Thí dụ, x = y = s = 'abcaaabb'. Đáp số: 8

Test 2. Sửa lại Test 1 bằng cách thêm vào x và y một số kí tự khác nhau. Đáp số: len(s). Thí dụ, x = 'xy'+s+'uvz'; y = 'uv'+s+'xy'. Đáp số: 8.

Test 3. Sửa lại Test 2 bằng cách chèn thêm một đọan nhỏ của s vào x và y. Thí dụ, x = 'xy'+s+'uv'+s'; y = 'u' + s' + 'v'+ s +'xy' + s' với s' = 'abcaaab' (hụt 1 kí tự so với s. Đáp số: 8.



Các bài tương tự

1. Đoạn chung 2. Cho hai xâu x gồm m và y gồm n kí tự. Tìm đoạn chung dài nhất của hai xâu này. Kết quả cho ra 4 giá trị dx, cx, dy, cy, trong đó x[dx..cx] = y[dy..cy] là hai đoạn tìm được.

2. Đoạn chung 3. Cho hai dãy số nguyên a gồm m và b gồm n phần tử. Xác định chiều dài lớn nhất k để hai dãy cùng chứa k phần tử liên tiếp như nhau: a[i] = b[j], a[i+1] = b[j+1],…,a[i+k–1] = b[j+k–1].

Thuật toán cho bài Đoạn chung 2

Khi phát hiện a[j] > 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.


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;

if (kmax < a[j]) {

kmax = a[j]; imax = i-kmax+2; jmax = j-kmax+2;

}

v = t;

}

}

}

int main() {

int i, j, k;

DoanLap("xabababayy", i, j, k);

cout << endl << i << " " << j << " " << k;//i = 2, j = 4, k = 5

cin.get();

return 0;

}
Thuật toán 2 (Bentley, Những viên ngọc lập trình)

1. Sắp tăng theo chỉ dẫn các hậu tố của s theo trật tự từ điển. Gọi dãy được sắp theo chỉ dẫn này là id[1..n], n = len(s).

2. Duyệt dãy được sắp trong id, với mỗi cặp hậu tố đứng kề nhau s:id[i] và s:id[i1], i = 2..n ta gọi hàm ComLen(id[i], id[i-1]) để tính chiều dài của khúc đầu chung (hay tiền tố) dài nhất của chúng. Đáp số khi đó sẽ là

Max { ComLen(id[i], id[i-1]) | i = 2..len(s) }

Thủ tục sắp theo chỉ dẫn id xét các hậu tố s:id[i] được thực hiện theo giải thuật quicksort như sau:

void IdSort(char * s, int * id, int d, int c) {

int i = d, j = c, m = id[(i+j)/2], t;

while (i < j) {

while (Sanh(s,id[i],m) < 0) ++i;

while (Sanh(s,id[j],m) > 0) --j;

if (i <= j) {

t = id[i]; id[i] = id[j]; id[j] = t;

++i; --j;

}

}

if (d < j) IdSort(s,id,d,j);

if (i < c) IdSort(s,id,i,c);

}

Hàm Sanh(s, i, j) so sánh hai hậu tố s:i và s:j theo trật tự từ điển hoạt động theo nguyên tắc sau: Lần lượt so sánh các cặp kí tự s[i] và s[j] cho đến cuối xâu, nếu gặp cặp kí tự khác nhau đầu tiên thì xét: kí tự nào nhỏ hơn thì xâu chứa nó sẽ nhỏ hơn xâu kia.



int Sanh(char *s, int i, int j) { //so sanh 2 hau to s:i, s:j

int k = Min(strlen(s)-i, strlen(s)-j), v;

for (v = 0; v < k; ++v,++i,++j)

if (s[i] != s[j]) return (s[i] < s[j]) ? -1 : 1;

return (i < j) ? 1 : ((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) {

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 < b then Min := a else Min := b; end;

function Sanh(var s: string; i,j: integer): integer;

var k, v: integer;

begin

k := Min(length(s)-i,length(s)-j);

for v := 0 to k do

if s[i+v] <> s[j+v] then

begin

if s[i+v] < s[j+v] then Sanh := -1 else Sanh := 1;

exit;

end;

if i < j then Sanh := 1

else if i > 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 <= j) do

begin

while Sanh(s,id[i],m) < 0 do inc(i);

while Sanh(s,id[j],m) > 0 do dec(j);

if (i <= j) then

begin

t := id[i]; id[i] := id[j]; id[j] := t;

inc(i); dec(j);

end;

end;

if d < j then IdSort(s,id,d,j);

if i < c then IdSort(s,id,i,c);

end;

function ComLen(var s: string; i, j: integer): integer;

var v,k: integer;

begin

k := Min(length(s)-i, length(s)-j);

for v := 0 to k do

if s[i+v] <> 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

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 = (v1).(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
abba
not
is
astra
saint
panama
saintpavnamtranaisnotsaintabba

5
Sau khi xóa 5 chữ cái (gạch dưới)
saintpavnamtranaisnotsaintabba
ta thu được dãy ghép của các từ 5, 6, 3, 2, 5, 1
saintpanamaisnotsaintabba


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;

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] <> s[i] then exit;

for i := i downto 1 do

if (s[i] = w[j]) then

begin

dec(j);

if j = 0 then begin Nhung := i; exit; end;

end;

end;

function Min(a,b: integer): integer;

begin if (a < b) then Min := a else Min := b; end;

procedure Tinhd(i: integer);

var j,v: integer;

begin

d[i] := d[i-1]+1;

for j := 1 to n do

begin

v := Nhung(w[j],i);

if v > 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];

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 << endl << kq;

cout << endl << endl << " Fini" << endl;

cin.get();

return 0;

}

void Ghi(int v) {

ofstream g(gn);

g >> v;

g.close();

}

int Min(int a, int b) { return (a < b) ? a : b; }

void Doc() {

ifstream f(fn);

f >> n;

for (int i = 0; i < n; ++i) f >> w[i];

f >> s; lens = strlen(s);

f.close();

}

void Xem() {

cout << endl << n << " " << s;

for (int i = 0; i < n; ++i) cout << endl << w[i];

}

// Nhung tu w vao tien to s:i

int Nhung(char *w, int i) {

int j = strlen(w)-1;

if (i < j) return -1;

if (w[j] != s[i]) return -1;

for (; i >= 0; --i)

if (w[j] == s[i]) {

--j;

if (j < 0) return i;

}

return -1;

}

int XuLi() {

for (int i = 0; i < lens; ++i) Tinhd(i);

return d[lens-1];

}

void Tinhd(int i) {

int j, k, v;

d[i] = (i == 0) ? 1 : (d[i-1]+1);

for (j = 0; j < n; ++j)

if ((v = Nhung(w[j],i)) >= 0) {

k = (v == 0) ? 0 : d[v-1];

d[i] = Min(d[i], k+i-v+1-strlen(w[j]));

}

}
Độ 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
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, FI 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.

15 27

...........***.............

***.........*.....****.....

*...........*.....*........

***...............***......

*....***********..*........

*........*........*..*****.

***..*...*...***.....*.....

.....*...*....*..*...*.....

.....*...*....*..*...****..

.........*....*..*...*.....

..****...*.......*...*.....

..*......*..*....*...****..

..***....*..*..............

..*.........*..............

..*.........*..............

3 2 2 3


Thuật toán
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.
dnd = số nét ngang dưới.
dx = đếm số chữ X;
X = {T,E,F,I}.
Mỗi chữ E có 2 nét ngang trên và 2 nét ngang dưới. Mỗi chữ F có 2 nét ngang trên và 1 nét ngang dưới.
de+df = dnt / 2; de = dnd – dnt/2.
df = dnt/2 – de.
y

*


.
*
.

.
*


.
*
*

















Đầu trên chữ T


Đầu trên chữ I

Nét ngang trên và giữa của chữ E và F

Nét ngang dưới của chữ E và F

Để 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à
phần quyết định.Các điều kiện được liệt kê độc lập nhau.
Giá trị 1 ứng với điều kiện đúng (true), 0 ứng với
điều kiện sai (false), dấu – cho biết điều kiện này không cần xét.
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ại cột đó được chọn.
x  dòng trên; y  dòng dưới.


Điều kiện

x[i] = '*'
1
0
1
1
x[i–1] = '*'
1
-
0
0
x[i+1] = '*'
-
-
1
-
y[i] = '*'
1
1
1
1
y[i–1] = '*'
-
0
0
0
y[i+1] = '*'
-
0
-
1

Quyết định
T (chữ T)
1



 (nét ngang trên)


1

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 }

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;

}

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 < 8; ++i) x = x + x;

for (j = 0 ; j < n; ++j) {

f >> 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 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).

15 27

...........................

***...............****.....

*.................*........

***...............***......

*....***********..*........

*....*...*.....*..****.....

***..*.*.*.*.*.*...........

.....*.*.*.*.*.*..****.....

.......*...*.*.......*.....

.......*******....****.....

..****...............*.....

.....*............****.....

..****..*...*....*.........

.....*..*...*....*.........

..****..**********.........

2 2 1 2


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 giống chữ T (E Nam) và (E Bắc). Mỗi E Đông có 2 nét dạng L và mỗi E Tây có 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ó

Số chữ E Đông = (dd – db)/2,

Số chữ E Tây = (dtdb)/2,

Số chữ E Nam = dn,

Số chữ E Bắc = db.



y

*

*




*

*







*







*

*

*






Đông
dd L



Tây
dt

Nam
dn T

Bắc
db




Đặc trưng của các chữ E xiếc. Các biến dd, dt, dn, db dùng để đếm số lần xuất hiện của các đặc trưng.









Độ phức tạp. cỡ m.n = dung lượng input file.


(* EXIEC.PAS *)

uses crt;

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;

cout << endl << endl << " Fini "; // 3

cin.get();

return 0;

}

void DongTayNamBac(int i) {

if (y[i+1] == ss) DongBac(i);

else TayNam(i);

}

void DongBac(int i){

if (y[i-1] == ss) ++db;

else ++dd;

}

void TayNam(int i) {

if (y[i-1] == ss) ++dt;

else if (x[i-1] == ss && x[i+1] == ss) ++dn;

}

void EXIEC() {

int i, j;

dd = dt = dn = db = 0;

ifstream f(fn);

f >> n >> m; x = cc;

for (i = 0; i < 8; ++i) x = x + x;

for (j = 0 ; j < n; ++j) {

f >> 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;

}




: tailieu
tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning
tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm
tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc
tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI
tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1
tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng
tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp
tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc
tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam


  1   2   3   4   5   6   7   8   9   ...   21


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2019
được sử dụng cho việc quản lý

    Quê hương