Luận văn tốt nghiệp Phan Thanh Long
Hình 1.3
Với thuật toán Huffman trờng hợp xấu nhất là thời gian hình thành cây nhị phân
là O(n) với n là số ký tự cần mã hoá.
Chơng trình viết bằng ngôn ngữ Pascal minh hoạ thuật toán tạo mã Huffman:
Const n = 6; {Số ký tự cần mã hoá a, b, c, }
Type Nod = record
S:integer; {tần suất}
Code:String; {mã nhị phân}
Name:char; {tên ký tự}
end;
Var a:array[1 n] of Nod;
i,m:integer;
Procedure InputData; {Khởi tạo bảng tần suất các ký tự}
Var i:integer;
begin
for i:=1 to n do with A[i] do
begin S:=Round(exp(n/5)/exp(i/5))+1;Name:=Char(64+i);Code:=''; end;
end;
Procedure FindCode(m:integer); {Sinh mã huffman}
Var y,z:nod;
k:integer;
Begin
if m=1 then exit;
y:=a[m-1];
a[m-1].s:=a[m-1].s+a[m].s;
5
a,e,f,d,b,c
a,e,f,d b,c
e,f,da
e,f
d
e
f
b
c
0
0
0
0
0
1
1
1
1
1
0,3
0,6
0,2
0,1
0,1
0,1
0,3
0,4
0,2 0,2
Luận văn tốt nghiệp Phan Thanh Long
k:=m-1;
While (k>1) and (a[k].s>a[k-1].s) do Begin
z:=a[k]; a[k]:=a[k-1]; a[k-1]:=z; k:=k-1;
End;
FindCode(m-1);
z:=a[k];
for i:=k to m-2 do a[i]:=a[i+1];
a[m-1]:=y;
a[m-1].code:=z.code+'1'; a[m].code:=z.code+'0';
End;
BEGIN
InputData; FindCode(n);
For i:=1 to n do writeln(a[i].code);
END.
4.2 Cây biểu diễn biểu thức
Một biểu thức toán học có thể biểu diễn bằng cây, đây cũng là vấn đề hữu ích
trong việc xử lý và lu trữ biểu thức toán học trong máy tính
Xét biểu thức đại số sau:
Có thể vẽ 1 cây nhị phân nh hình 1.4 biểu diễn biểu thức A, trong đó mỗi đỉnh
trong mang dấu của một phép tính, gốc của cây mang phép tính sau cùng của A, ở
đây là dấu nhân ký hiệu: *, mỗi lá mang 1 số hoặc một chữ đại diện cho số.
Hình 1.4
Một phép duyệt cây là tiền thứ tự nếu thăm gốc trớc rồi sau đó thăm con trái
nh là một cây con với phơng pháp thăm gốc trớc và cuối cùng thăm con phải nh là
một cây con với phơng pháp thăm gốc trớc. Duyệt cây nh vậy mang tính đệ quy.
6
( )
ì+=
2
d
cbaA
a
*
+
-
/
b
c
d
2
Luận văn tốt nghiệp Phan Thanh Long
Khi duyệt cây trên theo tiền thứ tự ta có: * + a b - c / d 2
Cách viết biểu thức theo tiền thứ tự là ký pháp Balan.
Bằng duyệt cây ta có thể tính đợc giá trị biểu thức, ngoài phơng pháp tiền thứ tự
còn có thể duyệt cây theo phơng pháp pháp khác để tính giá trị biểu thức tùy vào
yêu cầu và đặc điểm của từng bài toán.
4.3 Cây quyết định
Có những bài toán phụ thuộc vào các quyết định. Mỗi quyết định thì có thể có
nhiều kết cục và những kết cục cuối cùng chính là lời giải của bài toán. Để giải
những bài toán nh vậy, ngời ta biểu diễn mỗi quyết định bằng một đỉnh của đồ thị
và mỗi kết cục là 1 lá của quyết định. Một cây đợc xây dựng nh trên gọi là cây
quyết định. Trong nhiều bài toán Tin gặp phải, có thể dùng cây quyết định để mô
hình hoá từ đó việc cài đặt sẽ dễ dàng thuận tiện hơn.
Ví dụ:
hình 1.5 là cây quyết định biểu diễn việc sắp xếp 3 số khác nhau a, b, c
Hình 1.5
Đoạn chơng trình sau thể hiện cho cây trên:
Var a, b, c: Integer;
Function Can(x,y: Integer): Boolean;
Begin
if x > y then Can:=True
Else Can:=False;
End;
7
a ? b
a ? c b ? c
b ? c
a ? c
c<a<b
c<b<a
b<c<a
b<a<c
a<c<b
a<b<c
b<a a<b
c<a
a<c
c<b
b<c
c<b
b<c
c<a
a<c
Luận văn tốt nghiệp Phan Thanh Long
Begin
Readln(a,b,c);
If Can(a,b) then Begin
If Can(a,c) then Begin
if Can(b,c) then Writeln(c,' ',b,' ',a)
Else Writeln(b,' ',c,' ',a);
End
Else Writeln(b,' ',a,' ',c);
End
Else Begin
If Can(b,c) then Begin
if Can(a,c) then Writeln(c,' ',a,' ',b)
Else Writeln(a,' ',c,' ',b);
End
Else Writeln(a,' ',b,' ',c);
End;
End.
4.4 Cây sắp xếp và tìm kiếm
Sắp xếp và tìm kiếm là một trong những vấn đề cơ bản trong kỹ thuật lập trình,
cây nhị phân cũng có khá nhiều ứng dụng quan trọng trong vấn đề này. Ta có thể
mô hình hoá việc sắp xếp và tìm kiếm bằng cây từ đó ta có thể đánh giá các kỹ
thuật này từ góc độ về cây.
4.4.1 Sắp xếp chèn với tìm kiếm nhị phân
ý tởng đợc bắt đầu nh sau, cho 1 danh sách cha sắp xếp hãy tìm 1 phần tử x bất
kỳ nào đó trong danh sách, rõ ràng để tìm ta phải lần lợt xét từng phần tử cho tới
khi nào bắt gặp phần tử cần tìm, nếu danh sách lớn thì thời gian tìm rất lâu. Bây
giờ với một danh sách đã sắp xếp, chia đôi danh sách và lấy phần tử là t ở vị trí
chia đôi để so sánh. Nếu t = x thì dừng, nếu t < x vì danh sách đã sắp xếp nên x
chỉ có thể nằm bên nửa phải danh sách nên ta chỉ việc tìm kiếm trong 1 nửa danh
sách bên phải và giảm đi khá nhiều công việc tìm kiếm. Nếu x < t thì tơng tự, ta
chỉ việc tìm bên nửa trái, đối với việc tìm kiếm cho lần sau với các danh sách con
nửa trái hoặc nửa phải ta thực hiện tơng tự nh vậy một cách đệ quy.
a) Từ những ý tởng thuật toán ta xây dựng cây nhị phân tìm kiếm cho một danh
sách nh sau:
8
Luận văn tốt nghiệp Phan Thanh Long
- Chọn 1 phần tử bất kỳ làm gốc
- Tất cả các phần tử có giá trị gốc thì thuộc cây con trái
- Tất cả các phần tử có giá trị > gốc thì thuộc cây con phải
- Đối với các cây con thì cũng có tính chất tơng tự nh vậy
Ví dụ cây nhị phân tìm kiếm cho danh sách 12, 10, 6, 11, 15, 13, 16, 19, 18 nh
hình 1.6:
Hình 1.6
b) Sắp xếp chèn bằng việc tìm nhị phân vị trí đúng.
Có thể tạm gọi là phơng pháp sắp xếp chèn nhị phân. ý tởng nh sau: cho trớc
một danh sách đã sắp xếp A, cần chèn 1 phần tử mới x vào A sao cho danh sách
luôn đợc sắp xếp. Đầu tiên ta tìm vị trí đúng của x trong A sau đó chèn x vào
đúng vị trí này trong A, ta có danh sách A = A {x} luôn đợc sắp xếp. Để tìm đ-
ợc ví trí đúng cần chèn của x trong A ta sử dụng phơng pháp tìm kiếm nhị phân,
chèn theo cách này gọi là chèn nhị phân.
Ví dụ để sắp xếp B = x
1
, x
2
, x
3
, x
n
ta thực hiện nh sau:
A := ;
For i:=1 to n do Begin
- Tìm vị trí đúng của x
i
trong A theo phơng pháp tìm nhị phân
- Chèn x
i
vào A theo đúng vị trí vừa tìm đợc (A := A {x
i
})
End;
Kết quả A là danh sách sắp xếp của B.
Chơng trình Pascal sau sắp xếp tăng dần theo phơng pháp chèn nhị phân
Const n = 9;
Ds : Array[1 n] of Integer = (1,9,1,6,3,10,10,8,7);
{Ham tra lai vi tri dung cua Pt trong danh sach}
Function FindNp(l,r,Pt: Integer): Integer;
Var t: Integer;
Begin
9
12
15
18
10
6
11
13
16
19
Luận văn tốt nghiệp Phan Thanh Long
If Pt<=Ds[l] then FindNp:=l
Else If Pt>=Ds[r] then FindNp:= r + 1
Else Begin
Repeat
t:= (l + r) div 2;
If Pt = ds[t] then Begin FindNp:=t+1; Exit End
Else If Pt<ds[t] then r:=t
Else l:=t;
Until r=l+1;
FindNp:=l+1;
End;
End;
Var i, j, vt, s: Integer;
Begin
For i:=2 to n do Begin
vt:= FindNp(1,i-1,ds[i]);
{Chen dung vi tri sao cho ds luon duoc sap xep}
s:=ds[i];
For j:=i-1 Downto vt do ds[j+1]:=ds[j];
ds[vt]:=s;
End;
For i:=1 to n do Write(ds[i]:3);
End.
4.4.2 Thuật toán sắp xếp hoà nhập
Giả sử ta có danh sách cha đợc sắp 8, 2, 4, 6, 9, 7, 10, 1, 5 ,3 có thể dùng cây
nhị phân mô tả quá trình sắp xếp danh sách theo thứ tự tăng dần nh sau:
Cây nhị phân với gốc đợc gán là chính là danh sách đó. Các con của gốc đợc
gán theo nguyên tắc: Con bên trái gán nửa danh sách đầu, con bên phải gán nửa
danh sách còn lại (danh sách gán ở gốc cây con trái và cây con phải hoặc bằng
nhau về số lợng hoặc chênh lệch nhau 1 phần tử).
Cứ tiếp tục cho tới khi cây nhị phân có mỗi lá đợc gán 1 phần tử trong dãy. Đó là
cây nh hình 1.7
10
Luận văn tốt nghiệp Phan Thanh Long
Hình 1.7
Đây là cây nhị phân đầy đủ cha phải cây sắp xếp của dãy đã cho ở trên
Hình 1.8
Để có cây nhị phân sắp xếp của một dãy, trớc hết cây đợc xây dựng tơng tơng tự
nh vậy, mỗi lá tơng ứng với mỗi phần tử của dãy. Bớc đầu tiên 2 phần tử đợc hoà
nhập vào 1 danh sách theo thứ tự tăng dần, danh sách tơng ứng này nh một nút
cha, 2 phần tử đợc hoà nhập là nút con. Sau đó ta tiếp tục hoà nhập các cặp nút t-
ơng tự nh vậy cho tới toàn bộ danh sách đợc sắp xếp lại theo thứ tự tăng dần và
cây biểu diễn cho dãy là cây nhị phân cân đối đợc mô tả nh hình 1.8
11
8, 2, 4, 6, 9, 7, 10, 1, 5, 3
8, 2, 4, 6, 9 7, 10, 1, 5, 3
8, 2, 4
6, 9
7, 10, 1
5, 3
8, 2
4
6
9
8
2
7, 10 1
7 10
5
3
8 2
7
10
2, 8
4 6
9
7, 10 1
5 3
2, 4, 8
6, 9
1,7, 10
3, 5
2, 4, 6, 8,9
1, 3,5, 7, 10
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Luận văn tốt nghiệp Phan Thanh Long
Các bớc thuật toán trên đợc mô tả trên là đã vận dụng thuật toán hoà nhập hai
danh sách đã đợc sắp xếp thành một danh sách mới đợc sắp xếp, thuật toán này
theo nguyên tắc sau:
- So sánh phần tử bé nhất trong danh sách trong danh sách thứ nhất với phần tử
bé nhất trong danh sách thứ 2.
- Quá trình trên đợc lặp lại cho 2 danh sách nhận đợc ở bớc trên
- Sau một số bớc sẽ gặp hai trờng hợp sau:
a) Cả 2 danh sách trở thành rỗng. Trong trờng hợp này, các phần tử có mặt trong
danh sách hoà nhập chính là danh sách cần xác định
b) Một danh sách trở thành rỗng, còn danh sách kia khác rỗng. Trong trờng hợp
này đa các phần tử còn lại (trong danh sách không rỗng) nối vào cuối của danh
sách hoà nhập.
Độ phức tạp thuật toán của thuật toán trên là O(nlogn) trong đó n là số phần tử
hoà nhập
Chơng trình bằng ngôn ngữ Pascal thể hiện thuật toán hoà nhập nh sau:
Const n = 10;
Type Vec = Array[1 n] of Integer;
Const cm:Vec = (-3,3,-1,4,1,5,6,7,-8,-9);
Var x,y:Vec;
Procedure Viet;
Var i:byte;
Begin
For i:=1 to n do Write(x[i]:3); Writeln;
End;
Procedure Hoa_nhap2p(x:Vec; p,m,n:Integer; Var z:Vec);
Var i,j,k: Integer;
Begin
i:=p;j:=m+1;k:=p;
While (i<=m) and (j<=n) do Begin
If x[i]<x[j] Then Begin
z[k]:=x[i];inc(i);
End
Else Begin z[k]:=x[j];inc(j);End;
Inc(k);
End;
12
Luận văn tốt nghiệp Phan Thanh Long
If i>m Then
for K:=j to n Do z[k]:=x[k]
Else
for k:=i to m Do z[n+k-m]:=x[k];
End;
Procedure Merge(l,r:integer);
Var i,m:integer;
Begin
If l<r Then Begin
m:=(l+r) div 2;
Merge(l,m); Merge(m+1,r);
For i:=l to r do y[i]:=x[i];
Hoa_nhap2p(y,l,m,r,x);
End;
End;
BEGIN
X := cm; Viet;
Merge(1,n); Viet;
END.
4.4.3 Thuật toán sắp xếp nhanh
Sắp xếp 1 danh sách có nhiều thuật toán, mỗi thuật toán đều có những u nhợc
điểm. Trong các thuật toán sắp xếp thì thuật sắp xếp nhanh (Quick sort) tỏ ra có
nhiều u điểm đợc sử dụng phổ biến và rất hiệu quả. Nguyên tắc của thuật toán này
có tính đệ quy có thể sử dụng cây nhị phân để mô tả thuật toán này. Thuật toán có
thể đợc mô tả tóm tắt nh sau:
Ví dụ để sắp xếp danh sách a
1
, a
2
, , a
n
thuật toán bắt đầu bằng việc lấy ngẫu
nhiên 1 phần tử làm chốt nhng thờng thì phần tử đầu tiên đợc chọn làm chốt. Nh
danh sách trên ta chọn a
1
làm chốt khi đó danh sách đợc phân đoạn thành 2 danh
sách con, một danh sách con gồm các phần tử nhỏ hơn a
1
theo thứ tự xuất hiện,
còn danh sách con khác gồm các phần tử lớn hơn a
1
cũng theo thứ tự xuất hiện.
Sau khi đã có hai danh sách con thì a
1
đợc đặt vào sau cùng của danh sách con
gồm các phần tử nhỏ hơn a
1
, nh vậy sau a
1
là danh sách con gồm các phần tử lớn
hơn a
1
. Thủ tục này đợc lặp lại một cách đệ quy cho mỗi danh sách con cho tới
khi nào mỗi danh sách con chỉ chứa một phần tử theo thứ tự xuất hiện của nó. Với
kết quả này ta đợc một danh sách đã đợc sắp xếp.
13
Luận văn tốt nghiệp Phan Thanh Long
Ví dụ cho danh sách: 3, 5, 7, 8, 1, 9, 2, 6;
Có thể dùng cây nhị phân biểu diễn thuật toán sắp xếp nhanh để sắp xếp danh
sách này nh hình 1.9
Hình 1.9
Danh sách lúc cha sắp xếp là gốc, danh sách đợc sắp xếp là danh sách mà mỗi
phần tử của nó là lá của cây.
Chơng trình thể hiện thuật toán sắp xếp nhanh nh sau:
Uses Crt;
const
Max = 10;
type
List = array[1 Max] of Integer;
var
Data: List;
I: Integer;
procedure QuickSort(var A: List; Lo, Hi: Integer);
procedure Sort(l, r: Integer);
var
i, j, x, y: integer;
begin
i := l; j := r; x := a[(l+r) DIV 2];
repeat
while a[i] < x do i := i + 1;
while x < a[j] do j := j - 1;
14
3, 5, 7, 8, 1, 9, 2, 4, 6
1, 2, 3 5, 7, 8, 9, 4, 6
1 2, 3
4, 5
7, 8, 9, 6
2 3
4 5
6, 7
8, 9
9
8
6
7
Không có nhận xét nào:
Đăng nhận xét