dathoc.com Bài giảng Giáo án đề thi tài liệu miễn phí Download, chia sẽ tài nguyên dạy và học miễn phí !
Tất cả Giáo án Bài giảng Bài viết Tài liệu
Nếu không xem dược hãy bấm Download về máy tính để xem
Download giao an Kỷ thuật Đánh dấu và ứng dụng mien phi,tai lieu Kỷ thuật Đánh dấu và ứng dụng mien phi,bai giang Kỷ thuật Đánh dấu và ứng dụng mien phi 100%, cac ban hay chia se cho ban be cung xem

Uploaded date: 3/23/2015 8:55:13 PM
Filesize: 0.02 M
Download count: 3
Bấm nút LIKE +1 để cảm ơn
SAU ĐÓ BẤM
Download
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
𝑛
10
9. 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ử (𝑎
𝑖≤50000, 𝑛
10
9). 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ử