Kỹ thuật đánh dấu và ứng dụng

KỸ THUẬT ĐÁNH DẤU VÀ ỨNG DỤNG
I. Lý thuyết về kỹ thuật đánh dấu:
	Để các bạn dễ hình dung về kỷ thuật này, tôi xin được đi thẳng vào ví dụ sau: 
Ví dụ 1: Cho một danh sách n số nguyên dương khác nhau từng đôi một được lưu trữ trong tệp So.inp n≤109. Lập trình tìm số nguyên dương nhỏ nhất chưa có mặt trong danh sách trên.
	Bài này có nhiều cách làm. Ở đây tôi xin đề cập một kỷ thuật tuy đơn giản nhưng rất hay và có thể áp dụng cho nhiều bài tập.
	Ta sử dụng mảng một chiều A.
	Var A:array[1..100000000] of byte;
	Ta sẽ sử dụng mảng A này để đánh dấu sự xuất hiện của các phần tử trong danh sách N số nguyên. Ta đánh dấu: A[i] = 1 nếu số i xuất hiện trong danh sách, a[i]=0 nếu i không xuất hiện.
	Khi đó ta có đoạn chương trình đánh dấu đơn giản như sau:
While not EOF(f) do
	Begin
	Read(f,x);	{Đọc ra số nguyên x}
	A[x]:=1;	{Đánh dấu x đã xuất hiện}
	End;
	Sau khi đã đánh dấu thì việc tìm số nào chưa xuất hiện trở nên rất đơn giản. Ta đi từ đầu mảng đến cuối mảng: Gặp số nào mà a[i]=0 thì dừng lại; và i chính là số nguyên dương đầu tiên chưa xuất hiện trong mảng.
	i:=1;
	While a[i]=1 do inc(i);
	Minh họa từng bước quá trình đánh dấu.	
So.inp
Kết quả chạy từng bước quá trình đánh dấu
2 4 1 5
- Ban đầu A[i] = 0 với mọi i
0
0
0
0
0
- lần 1:
	+ Đọc ra x=2
	+ Đánh dấu a[2] = 1
0
1
0
0
0
- lần 2:
	+ Đọc ra x=4
	+ Đánh dấu a[4] = 1
0
1
0
1
0
- lần 3:
	+ Đọc ra x=1
	+ Đánh dấu a[1] = 1
1
1
0
1
0
- lần 4:
	+ Đọc ra x=5
	+ Đánh dấu a[5] = 1
1
1
0
1
1
- Sau khi đánh dấu thì ta thấy a[3] = 0 nên 3 là số chưa xuất hiện.
	Sau ví dụ trên thì các bạn phần nào đã hiểu được kỷ thuật đánh dấu. sau đây tôi sẽ chuyển sang một số bài tập có sử dụng kỷ thuật này.
II. Một số bài tập ứng dụng kỷ thuật đánh dấu.
1. Tần số.
	Cho một mảng số nguyên A gồm n phần tử (ai≤50000, n≤109). giá trị các phần tử có thể trùng nhau. Ta gọi số lần xuất hiện của một số x trong mảng A chính là tần số của x.
	Em hãy lập trình tìm số nguyên có tần số lớn nhất.
Tanso.inp
Tanso.out
Giải thích
1 1 3 2 3 3 2 5 4 6 4 2 3 3
3 5
Số 3 có tần số 5
	Bài tập này ta có thể áp dụng kỷ thuật đánh dấu. a[x] chính là số lần xuất hiện của x trong mảng A. Khi đó ta khi đọc ra số nguyên x ta đánh dấu a[x] = a[x] + 1.
	Ta khai báo mảng A gồm tối đa 50.000 phần tử. Ban đầu A[i] = 0 với mọi i. Sau đó đọc dữ liệu từ tệp và đánh dấu.
	While not eof(f) do
 	Begin
 	Read(f,x);
	A[x]:=a[x]+1;
	End;
	Ví dụ mảng A cho bài trên:
2
3
5
2
1
1
1
2
3
4
5
6
	Kết quả: tần số lớn nhất chính là Max của mảng A: Số 3 có tần số 5
2. Distribution counting: Sắp xếp đếm phân phối.
	Đây là một thuật toán sắp xếp có thời gian thực thi nhanh hơn thuật toán Quicksort trong trường hợp cần sắp xếp danh sách gồm các số nguyên.
	Ý tưởng của thuật toán là sử dụng kỷ thuật đánh dấu.
	Ví dụ: Cho n số nguyên dương được lưu trữ trong tệp Sort.inp (ai≤5000, n≤109). Hãy lập trình sắp xếp dãy số này và ghi kết quả vào tệp sort.out.
Sort.inp
Sort.out
1 1 3 2 3 3 2 5 4 6 4 2 3 3
1 1 2 2 2 3 3 3 3 3 4 4 5 6
	Thuật toán sắp xếp này gồm 2 bước như sau:
Đọc qua một lượt từ a[1] đến a[n]: và đánh dấu số lần xuất hiện (như bài tần số)
B
2
3
5
2
1
1
1
2
3
4
5
6
Sau đó ta dựa trên mảng B này để viết ra các số thành một danh sách.
Giá trị i
Kết quả danh sách
Giải thích
i = 1
1 1
B[1] = 2: ta viết i ra 2 lần.
i = 2
1 1 2 2 2
B[2] = 3: ta viết i ra 3 lần.
i = 3
1 1 2 2 2 3 3 3 3 3
B[3] = 5: ta viết i ra 5 lần.
i = 4
1 1 2 2 2 3 3 3 3 3 4 4
B[4] = 2: ta viết i ra 2 lần.
i = 5
1 1 2 2 2 3 3 3 3 3 4 4 5
B[5] = 1: ta viết i ra 1 lần.
i = 6
1 1 2 2 2 3 3 3 3 3 4 4 5 6
B[6] = 1: ta viết i ra 1 lần.
Kết quả duyệt từ đầu đến cuối mảng B: Ta được DS đã sắp xếp.
	Đoạn Code thể hiện thuật toán sắp xếp này:
	Fillchar(B,sizeof(B),0);
	While not oef(f) do
 	Begin
 	Read(f,x);
	B[x] := B[x] + 1;
	End;
	n:=0;
	For i:=1 to 5000 do
 	For j:=1 to B[i] do
	Begin
 	n:=n+1;
	A[n]:=i;
	End;
	Trong ví dụ trên ta thấy số lượng phần tử của mảng B phụ thuộc vào giá trị lớn nhất của các phần tử là bao nhiêu. (ở ví dụ này là 5000).
3. Số lần xuất hiện của các kí tự :
	Cho một xâu S gồm các kí tự chữ cái hoa và thường (S có thể rất dài). Bạn hãy lập trình đếm số lần xuất hiện của từng kí tự có trong xâu S.
StringCount.inp
StringCount.out
abcacAAa
A 2
a 3
b 1
c 2
	Nhận xét: Ta biết 
kí tự ‘A’ có mã ASCII là 65, kí tự ‘Z’ có mã ASCII là 90
kí tự ‘a’ có mã ASCII là 97, kí tự ‘z’ có mã ASCII là 122.
Lúc này, để đơn giản ta có thể khai báo mảng T gồm 122 phần tử, đánh số từ 1 đến 122.
	Var T:array[1..122] of longint;
	Lúc này ta đánh dấu: T[65] chính là số lần xuất hiện của kí tự A, T[66] là số lần xuất hiện của kí tự B 
	Ta có đoạn Code thể hiện quá trình đánh dấu:
Fillchar(T,sizeof(T), 0);	
For i:=1 to length(s) do T[ord(s[i])] := T[ord(s[i])] + 1;
Lưu ý: Ord(s[i]) cho giá trị là mã ASCII của kí tự S[i]. Ví dụ T[ord(‘A’)] tức là T[65].
	Xử lý kết quả:
	For i:=65 to 122 do
 	If T[i]0 then Writeln(g, chr(i), ‘ ‘, T[i]);
Lưu ý: Chr(i) cho giá trị là kí tự tương ứng với mã ASCII i. Ví dụ Chr(97) = ‘a’
	Chương trình các em tự cài đặt. 
Bài tập mở rộng: s gồm cả kí tự số. (Ta chỉ cần thay đổi vòng lặp in kết quả For i:=1 to 122 vì kí tự số thì quá trình đánh dấu diễn ra bình thường).
Bài 4: (Bài 1 trang 156 – Olympic 30/04/2008 – Chuyên Lê Quý Đôn – Khánh Hòa)
	Một kho hàng chứa N mặt hàng (0<N<5000000), mỗi mặt hàng được đánh một mã số không trùng nhau từ 0 đến 109. Mã số của các mặt hàng được lưu trữ không tuần tự trong tệp. Qua thời gian mặt hàng nào được bán đi thì mã số được xóa bỏ.
	Hãy lập trình tìm một mã số nhỏ nhất thỏa mãn để đánh cho một mặt hàng mới nhập kho.
Code.inp
Code.out
0 8 10 3 2 1
4
Bài 5: Dự tiệc
Ông An đến dự tiệc, buổi tiệc có N người (0<N<50000). Mỗi người được cài lên áo mỗi bông hoa trên đó có ghi một con số nguyên X (X<106) cho biết người khách đó sẽ dự tiệc phòng X. Hầu hết tất cả các phòng đều có số lượng khách chẵn, duy nhất một phòng có lượng khách là lẽ. Để đảm bảo đủ cặp cho tiệc Khiêu vũ nên BTC quyết định tìm phòng khách có số lượng người là lẽ để ghi số cho Ông An. Em hãy giúp BTC giải quyết điều đó.
	Dữ liệu vào: Tệp Dutiec.inp gồm n+1 dòng, dòng đầu tiên là số N, n dòng tiếp theo mỗi dòng ghi một số nguyên dương cho biết con số ghi trên áo người khách thứ i.
	Kết quả: ghi vào tệp Dutiec.out gồm con số duy nhất là phòng có số lượng khách lẻ.
Dutiec.inp
Dutiec.out
5
1
2
2
3
1
3
Bài 6: Xóa số
	Các số nguyên từ 1 đến n được xếp theo thứ tự tăng dần trên một đường tròn theo chiều kim đồng hồ. Bắt đầu từ số 1, chuyển động theo chiều kim đồng hồ, cứ bước qua một số lại xoá đi một số. Công việc đó tiếp diễn cho đến khi trên vòng tròn còn lại đúng một số. Lập chương trình tìm số đó và lưu vào tệp Xoaso.out.
	Dữ liệu vào: Là số nguyên N trong tệp Xoaso.inp
Xoaso.inp
Xoaso.out
3000
Bài 7: SỐ LƯỢNG NHÓM ĐỀ TÀI (Khoahoc.pas)
Nhà trường phát động phong trào đăng ký làm sáng tạo khoa học kỹ thuật, tất cả các bạn trong lớp của Nguyên đều tích cực tham gia và được phân công vào các nhóm đề tài. Mỗi nhóm đề tài được ký hiệu: , ví dụ Nguyên được phân công vào nhóm TIN gồm 3 thành viên thì ký hiệu nhóm là TIN 3. Danh sách được lập ra gồm ký hiệu nhóm và tên thành viên, nhưng trong quá trình in ấn cột ký hiệu nhóm bị mờ và không đọc được chỉ còn lại .
Ví dụ:
 Ký hiệu
Thành viên
hiệu
Thành viên
TIN 3
Việt
3
Việt
TOAN 2
Tuấn
2
Tuấn
TIN 3
Thái
Do lỗi in ấn →
3
Thái
TIN 3
Anh
3
Anh
TOAN 2
Chính
2
Chính
Yêu cầu: Cho danh sách gồm n học sinh và số thành viên của nhóm tương ứng với từng học sinh. Hãy xác định số lượng nhóm đề tài đã được phân công. Dữ liệu đảm bảo bài toán có nghiệm. 
Ví dụ:
Khoahoc.inp
Khoahoc.out
5
3 2 3 3 2 
2
10
5 1 2 5 5 2 5 5 2 2
4
Bài 8: (5đ) Bình chọn qua điện thoại VNMODEL.pas
	Trong vòng chung kết cuộc thi “Vietnam Next Top Model” trên VTV3 các thí sinh được đánh số báo danh là một số nguyên dương có giá trị không vượt quá 1000. Khán giả xem truyền hình có thể bình chọn cho thí sinh mình yêu thích bằng cách nhắn tin qua điện thoại di động.
Ban tổ chức nhận được tin nhắn hợp lệ của N khán giả (các khán giả được đánh số từ 1 đến N), khán giả thứ i bình chọn cho thí sinh mang số báo danh ai.
Hãy liệt kê số báo danh của những thí sinh được nhiều khán giả bình chọn nhất theo thứ tự tăng dần.
Dữ liệu: Vào từ file văn bản VNMODEL.INP
Dòng đầu tiên ghi số nguyên dương N là số lượng khán giả có tin nhắn bình chọn hợp lệ (N≤106)
N dòng tiếp theo, dòng thứ i ghi số nguyên dương ai là số báo danh của thí sinh mà khán giả thứ i bình chọn.
Kết quả: Ghi ra file văn bản VNMODEL.OUT
Danh sách các thí sinh được nhiều khán giả bình chọn nhất theo thứ tự số báo danh tăng dần
Ví dụ:
VNMODEL.INP
VNMODEL.OUT
5
3
1
3
2
2
2
3
Ghi chú: Có ít nhất 50% số điểm của bài tương ứng với các test có N≤1000