0
K
KỸ
ỸTHU
THUẬ
ẬT L
T LẬ
ẬP TRÌNH
P TRÌNH
THUẬT TOÁN
VÀ CẤU TRÚC DỮLIỆU
1
N
NỘ
ỘI DUNG
I DUNG
Thuật toán
Kiểudữliệuvàcấutrúcdữliệu
Mối liên hệgiữathuậttoánvàcấutrúcdữliệu
Kiểu con trỏtrong C
Sửdụng kiểuarray trongC
Kiểu xâu kí tựtrong C
Sửdụng struct trong C
2
KH
KHÁ
ÁI NI
I NIỆ
ỆM THU
M THUẬ
ẬT TO
T TOÁ
ÁN
N
Thuật toán (giảithuật) là một quy tắcđể vớinhững dữ
liệu ban đầuđã cho, tìm đượclờigiảisaumộtkhoảng
thờigianhữuhạn
Bài toán
Thuật toán
Máy tính
Dữ liệu vào Kết quả ra
3
Tính kết thúc (tính dừng)
Tính xác định
Tính phổdụng
Tính hiệuquả
•Thựchiện nhanh
•Tiêu phí ít tài nguyên máy tính (bộnhớ)
C
CÁ
ÁC Đ
C ĐẶ
ẶC TRƯNG C
C TRƯNG CỦ
ỦA THU
A THUẬ
ẬT TO
T TOÁ
ÁN
N
4
C
CÁ
ÁC Đ
C ĐẶ
ẶC TRƯNG C
C TRƯNG CỦ
ỦA THU
A THUẬ
ẬT TO
T TOÁ
ÁN
N
Thuật toán tìm UCLN của hai sốnguyên dương
1. Nhậpvàohaisốnguyên dương a, b
2. So sánh hai số, chọnsốnhỏnhấtgắn cho UCLN
3. Nếumột trong hai sốa, b không chia hếtchoUCLN thìthực
hiệnbước4, ngượclạithìthựchiệnbước5
4. GiảmUCLN mộtđơnvịvà quay lạibước3
5. In UCLN. Kếtthúc
?Các đặctrưng củathuậttoántrên
5
TIÊU CHU
TIÊU CHUẨ
ẨN Đ
N ĐÁ
ÁNH GI
NH GIÁ
ÁTHU
THUẬ
ẬT TO
T TOÁ
ÁN
N
Lựachọnthuật toán nào cho bài toán?
Tiêu chuẩn1: Thuật toán đơngiản, dễhiểu, dễcài đặt
Tiêu chuẩn2: Thuậttoánsửdụng tiếtkiệm tài nguyên
máy tính (dung lượng không gian nhớ, thời gian)
6
NGÔN NG
NGÔN NGỮ
ỮTHU
THUẬ
ẬT TO
T TOÁ
ÁN
N
Ngôn ngữdùng để mô tảthuật toán
?Tại sao phải dùng ngôn ngữdiễnđạtthuật toán
?Đặcđiểmcủa ngôn ngữdiễnđạtthuật toán
•Ngôn ngữliệtkêtừng bước(Ngônngữtựnhiên)
•Sơđồkhối
•Ngôn ngữ“giảcode”: TựaPascal, tựaC, …
–Các bước trong chương trình nên đượcđánh sốthứtự
–Có thểbỏqua phần khai báo dữliệu, thay vào đólàđặctảcấutrúcdữliệu
trướckhiviếtgiảithuật
Mô tảthuật toán
•Thuật toán: <Tên thuật toán>
•Vào (Input): <Dữliệuvàocủathuật toán, mô tảrõ kiểudữliệu>
•Ra (Output): <Các dữliệura-Kếtquả>
7
NGÔN NG
NGÔN NGỮ
ỮTHU
THUẬ
ẬT TO
T TOÁ
ÁN
N
Ngôn ngữliệtkêtừng bước
•Thuật toán: Euclid
•Vào: m,n nguyên dương (m > n)
•Ra: gcd là ước chung lớnnhấtcủa m và n
r: sốnguyên dương
Bước1. Nhậpvàom, n
Bước2. Nếu m, n >0 thì chuyển sang bước3, ngượclại thì thông báo
“Dữliệu vào không hợplệ”vàkết thúc thuậttoán
Bước3. Nếu m > n thì chuyển sang bước4. Ngượclại, hoán chuyển
giá trịcủam, n
Bước4. Nếu n = 0 thì gcd = m, in giá trịcủa gcd và kếtthúc. Ngượclại,
chuyển sang bước5.
Bước 5. Tính r là phầndưcủaphépchiam chon
Bước 6. Gán giá trịcủa n cho m và củar chon. Quay lạibước4.
8
NGÔN NG
NGÔN NGỮ
ỮTHU
THUẬ
ẬT TO
T TOÁ
ÁN
N
Sơđồkhối
Đi
Điề
ều
uki
kiệ
ện
n
L
Lệ
ệnh
nh N
Nú
út
tthao
thao t
tá
ác
c
Ch
Chỉ
ỉhư
hướ
ớng
ng truy
truyề
ền
nthông
thông tin
tin
N
Nú
út
tđi
điề
ều
uki
kiệ
ện
n
N
Nú
út
tb
bắ
ắt
tđ
đấ
ấu
u,
, n
nú
út
tk
kế
ết
tth
thú
úc
c
9
NGÔN NG
NGÔN NGỮ
ỮTHU
THUẬ
ẬT TO
T TOÁ
ÁN
N
Thuật toán Euclid
Sai
Sai
Đúng
Đúng
Bắt đầu
Nhập m, n
m, n >0
m >= n
n = 0
gcd = m
In gcd
r = m mod n
m = n
n = r
r = m
m = n
n = r
Kết thúc
Thông báo
Dữ liệu vào
không hợp lệ
Sai Đúng
10
NGÔN NG
NGÔN NGỮ
ỮTHU
THUẬ
ẬT TO
T TOÁ
ÁN
N
Ngôn ngữTựa Pascal
•Khai báo: Program < Tên chương trình>
Begin …….
End.
•Chú thích {….}
•Phép toán sốhọc: +, - *, /, ↑(luỹthừa)
•Phép toán so sánh: >, >=, <, <=, =, ≠
•Giá trịlogic: true, false
•Phép toán logic: and, or, not
11
NGÔN NG
NGÔN NGỮ
ỮTHU
THUẬ
ẬT TO
T TOÁ
ÁN
N
Các câu lệnh
•Câu lệnh gán V := E;
–V: biến, E: biểuthức
–Phép gán chung: V1 := V2 := E;
•Câu lệnh điềukiện if B then S1 [else S2];
•Câu lệnh tuyển Case
B1: S1;
B2: S2;
….
Bn: Sn;
else Sn+1
end case;
12
NGÔN NG
NGÔN NGỮ
ỮTHU
THUẬ
ẬT TO
T TOÁ
ÁN
N
•Câu lệnh lặp
–Sốlầnlặpbiếttrước for i := m to n do ….
for i := n down to m do….
–Sốlầnlặp không biếttrước while B do S;
repeat S until B;
(B: biểuthức logic; S: dãy lệnh)
•Câu lệnh chuyển
go to n; (n:sốhiệucủamộtbướctrongchương trình)
•Câu lệnh vào ra
read(<danh sách biến>);
write(<danh sách biểuthức>)
13
NGÔN NG
NGÔN NGỮ
ỮTHU
THUẬ
ẬT TO
T TOÁ
ÁN
N
•Chương trình con
–Hàm
function <tên hàm>(<danh sách tham số>): <kiểudữliệu>
S
return <biểuthức>
–Thủtục Procedure: không có kếtquảra
–Sửdụng Var đặttrướcthamsốcầngiữlạisựthay đổigiátrịsau
khi kếtthúcthựchiện hàm/thủtục
–Lờigọi Hàm Tên_hàm(<danh sách tham sốthựcsự>)
–Lờigọithủtục Call <Tên thủtục>(<danh sách tham sốthựcsự>)
14
Đ
ĐỘ
ỘPH
PHỨ
ỨC T
C TẠ
ẠP THU
P THUẬ
ẬT TO
T TOÁ
ÁN
N
Giảithuật nào hiệuquảnhấtchomột bài toán?
•Độ phứctạpthờigian
•Độ phứctạp không gian
?Đánh giá giảithuậtkhichạychương trình ???
Các yếutốảnh hưởng đếnthờigianthựchiệnthuật toán
•Môi trường phầncứng: tốcđộ xửlý, bộnhớ,…
•Môi trường phầnmềm: kiểulệnh, ngôn ngữ, trình biên dịch
•Kích thướcdữliệuvào
Đánh giá độ phứctạpthờigianT(n) bằng tổng sốphép
tính cầnphảithựchiện.
15
Độ tăng củahàm
•Cho hai hàm f(x), g(x) xác định từtậpcácsốnguyên dương hoặctập
sốthựcvàotậpsốthực. Ta nói f(x) là O(g(x)) nếutồntại hai hằng số
C và k sao cho: |f(x)| ≤C.|g(x)|, vớimọix > k.
Ví dụ1
•f(x) = anxn+…. +a0, vớia
ilà các sốthực. Khi đóf(x) = O(x
n).
•với x > 1 ta có
•ĐặtC = |a
n| + |an−1| + … + |a0| và k = 1, suy ra f(x) = O(xn).
Ví dụ2.
•f(x) = 1+ 2+ 3 + … + n = n(n+1)/2 nên là O(n2).
Đ
ĐỘ
ỘPH
PHỨ
ỨC T
C TẠ
ẠP THU
P THUẬ
ẬT TO
T TOÁ
ÁN
N
)....(
...(
...)(
01
01
0
1
1
aaax
x
a
x
a
ax
axaxaxf
nn
n
n
n
n
n
n
n
n
n
+++≤
+++≤
+++≤
−
−
−
−
16
Đ
ĐỘ
ỘPH
PHỨ
ỨC T
C TẠ
ẠP THU
P THUẬ
ẬT TO
T TOÁ
ÁN
N
Các thuậtngữthường dùng
•Độ phứctạpO(1) gọilàđộ phứctạphằng số
•Độ phứctạp O(log(n)) gọilàđộ phứctạp logarit
•Độ phứctạpO(n) gọilàđộ phứctạptuyến tính
•Độ phứctạp O(nlogn) gọilàđộ phứctạpnlogn
•Độ phứctạpO(n
k) gọilàđộ phứctạpđathức
•Độ phứctạpO(b
n) , b>1, gọilàđộ phứctạp hàm mũ
•Độ phứctạpO(n!) gọilàđộ phứctạpgiaithừa
17
Đ
ĐỘ
ỘPH
PHỨ
ỨC T
C TẠ
ẠP THU
P THUẬ
ẬT TO
T TOÁ
ÁN
N
Ví dụ1
K:=0;
For i:=1 to n do
Begin
K:=K+i;
End;
Ví dụ2
K:=0;
For i:=1 to n do
For j:= 1 to n do
Begin
K := K + i * j ;
End;
18
Đ
ĐỘ
ỘPH
PHỨ
ỨC T
C TẠ
ẠP THU
P THUẬ
ẬT TO
T TOÁ
ÁN
N
Ví dụ3
i :=1; K:=0;
while i <= n do
begin
K:= K+ i*i;
i := i * 2;
end;
Sốphép toán cầnthựchiện:
(1 so sánh + 2 nhân + 1 cộng) * (1 + |log2n|) = 4 + 4 |log2n| là
O(log2n).
19
Ví dụ4
Searching(A[]: array of integer, n: integer, integer K): Boolean
Begin
i := 1; found := false;
while (i <=n and !found) do
begin
if A[i] = K then found:=true;
else i := i+1;
end;
return found;
end;
Đ
ĐỘ
ỘPH
PHỨ
ỨC T
C TẠ
ẠP THU
P THUẬ
ẬT TO
T TOÁ
ÁN
N