Ph Thế
Bả
Ph
ạm
Thế

Bả
o
/>
T ờ Đ ih Kh h T hiê T HCM
T
rư
ờ
ng
Đ
ạ
i

h
ọc
Kh
oa
h
ọc
T
ự n
hiê
n
T
p.
HCM

N
Ộ
IDUNG
Ộ
1. Thiếtkế chương trình
M
ả
ộ
hi
ề

hi
hi
ề
à
hi
ề
hi
ề
2.
M
ả
ng m
ộ
tc
hi
ề
u,

h

a
i
c
hi
ề
uv
à
n
hi
ề
uc
hi
ề
u
3. Contrỏ
4. Chuỗik
ý
t
ự
5. Cấutrúc
6. Tậptin
7.
Đ
ệ
quy
7.
Đ
ệ
quy
8. Mộtsố thuật toán thông dụng

Cách tính điểm
y Điểmthựchành50%tổng điểm
y Điểmlýthuyết50%tổng đi ểm
y Điểmc
ộ
n
g
thêm 10

–20%

tổn
g
điểm
ộ
g
g
Tài li
ệ
uthamkhảo
ệ
1. Quách TuấnNgọc,Ng ôn Ngữ LậpTrìnhC.Nhà Xuất
Bả
n
Giáo Dục,1998.
2. MarkAllenWeiss,EfficientCprogramming

PrenticeHall,1998.
3
YaleN 

Patt
SanjayJ Patel
Introductionto 
3
.
YaleN
.

Patt
,SanjayJ
.
Patel
,
Introductionto 
ComputingSystem,fromBitsandGatesto Cand
Beyond McGrawHill,1999.
4
T ầ
Đ
Th
Giá
tìh
lậ
tìh
C(
Tậ
1&2
) NXB
4
.

T
r
ầ
n
Đ
an
Thư
,
Giá
o
t
r
ì
n
h
lậ
p
t
r
ì
n
h
C

(
Tậ
p
1

&


2
)
.
NXB

ĐH QG TPHCM –2003.
5. N
g
u
y
ễn Thanh Thu
ỷ
,
Nh
ập
môn l
ập
trình n
g
ôn n
gữ
C.
gy
ỷ
,
ập
ập
g
g

NXB KH-KT – 2005.
6. Phạm Văn Ất -Kỹ thuậtlậptrìnhC cơ sở và nâng cao.
NXB KH
-
KT
-
2006
NXB

KH
-
KT
-
2006
.
Ebook
1. Beginning C From Novice to Professional.
2
CPrimerPlus5
th
Edition
2
.
C

Primer

Plus

5

th
Edition
.
3. Mastering Algorithms with C.
4
Practical C Programming
4
.
Practical

C

Programming
.
5. Expert C Programming - Deep C Secrets.
6
The Complete Reference
6
.
The

Complete

Reference
.
7. C Reference Card (ANSI).
Website
1.
2
htt // i /

2
.
htt
p:
//
www.cprogramm
i
ng.com
/
3. />4
htt // d /
4
.
htt
p:
//
www.co
d
eguru.com
/
5. />6
htt // 4 i t
6
.
htt
p:
//
c
4
sw

i
mmers.ne
t
7.
8
h// l /
8
.
h
ttp:
//
www.goog
l
e.com.vn
/
Phạm Thế Bảo
Trường Đạihọc Khoa họcTự nhiên Tp HCM
Trường

Đại

học

Khoa

học

Tự

nhiên


Tp
.
HCM
Phân lọai
1. Phương pháp trựctiếp
2. Phương pháp gián tiếphoặc tìm kiếmlờigiải
Phương
pháp
trực
tiếp
Phương
pháp
trực
tiếp
• Xác định trựctiếp đượclờigiải qua mộtthủ tục tính toán (công
thức
hệ
thức
định
luật
)
hoặc
qua
các
bước
căn
bản
để
có

thức
,
hệ
thức
,
định
luật
, …
)

hoặc
qua

các
bước
căn
bản
để
có
đượclờigiải.
• Việc
g
iải
q
u
yế
tv
ấ
n đ
ề

trên má
y
tính chỉ là thao tác lậ
p
trình ha
y
ể
ổ
g
qy
y
p
y
là s
ự
chuy
ể
n đ
ổ
ilờigiảit
ừ
ngôn ng
ữ
t
ự
nhiên sang ngôn ngữ
máy tính Æ kỹ thuậtlập trình trên máy tính.
Có
ba
loại

cơ
bản
:
•
Có
ba
loại
cơ
bản
:
o Lọai thứ nhất, dùng để biểudiễn cho các bài toán đãcólờigiảichính
xác bằng một công thứctoánhọcnàođó.
(1)
12
nn
n
+
++ +=
ví dụ: tính tổng n số nguyên dương.
o Loạithứ hai, biểudiễn cho các bài toán có công thứcgiảigần đúng
(
công
thức
tính
sin
cos
giải
phương
trình
siêu

việt
)
12

2
n
++ +=
(
công
thức
tính
sin
,
cos
,
giải
phương
trình
siêu
việt
,…
)
.
ví dụ:giảiphương trình bậc2
o Loạicuối cùng, biểudiễn các lờigiải không tường minh bằng kỹ thuật
đệ quy.
Chuyển đổidữ liệu bài toán thành dữ liệuchương trình
Nguyên lý 1: Dữ liệucủabàitoánsẽđượcbiểudiễnlạidướidạng
các
biến

của
chương
trình
thông
qua
các
quy
tắc
xác
định
của
các
biến
của
chương
trình
thông
qua
các
quy
tắc
xác
định
của
ngôn ngữ lập trình cụ thể
1
Biến
phương
tiện
biểi

diễn
dữ
liệu
của
chương
trình
1
.
Biến
-
phương
tiện
biểi
diễn
dữ
liệu
của
chương
trình
2. Thay đổi giá trị củabiến-lệnh gán
3
Kiểu
dữ
liệu
3
.
Kiểu
dữ
liệu
4. Hằng số

5
Cấu
trúc
một
chương
trình
5
.
Cấu
trúc
một
chương
trình
Chuyển đổi quá trình tính toán của bài toán thành
các
cấu
trúc
của
chương
trình
các
cấu
trúc
của
chương
trình
y Nguyên lý 2 (Định lý Bohn-Jacopini): Mọi quá trình tính toán đều
có th
ể
mô t

ả
và thựchiệndự
a
trên
b
ac
ấ
utrúccơ
b
ản: tu
ầ
nt
ự
,rẽ
nhánh và lặp.
1. Cấutrúctuầntự
2
Cấ
tú
ẽ
há h
2
.
Cấ
u
t
r
ú
cr
ẽ

n
há
n
h
1. Rẽ nhánh có điềukiện: if (condition)
y rẽ nhánh đơn: if ()
ẽ
há h
đôi
if () l
y r
ẽ
n
há
n
h
đôi
:
if

()
e
l
se
2. Rẽ nhiều nhánh: case
3. Rẽ nhánh không có điềukiện: LABEL và GOTO
ấ
3. C
ấ
utrúclặp:

1. Lặpxácđịnh
2
Lặp
không
xác
định
2
.
Lặp
không
xác
định
Phân chia bài toán ban đầu thành những
bài
toán
nhỏ
hơn
bài
toán
nhỏ
hơn
y Nguyên lý 3: Mọi bài toán lớn đềucóthể giảiquyếtbằng
cách
phân
chia
thành
những
bài
toán
nhỏ

hơn
cách
phân
chia
thành
những
bài
toán
nhỏ
hơn
1. Thủ tụcvàhàm-phương pháp phân chia chương trình thành
những
chương
trình
con.
những
chương
trình
con.
2. Biếncụcbộ và biếntoàncục
3
Tham
số
-
dữ
liệu
đầu
vào
/
đầu

ra
của
hàm
3
.
Tham
số
dữ
liệu
đầu
vào
/
đầu
ra
của
hàm
Biểudiễn tính toán không tường minh bằng đệ quy
y
N
guyên lý 4: quá trình đệ quy trong máy tính không đơngiản
như các biểuthức quy nạp trong toán học
Sẽ
tì h
bà
à
y
Sẽ
t
r
ì

n
h
bà
ysaun
à
y.
Phươn
g
p
há
p
g
ián ti
ếp
g
pp
g
p
y Đượcsử dụng khi chưa tìm ra lờigiải chính xác củavấn
đề
đề
.
y Đây là cách tiếpcậnchủ yếucủaloàingườitừ xưa đến
nay
nay
.
y Lờigiảitrựctiếpbaogiờ cũng tốthơn, nhưng không
hải
lú
à

ũ
ó
phải
lú
cn
à
oc
ũ
ng c
ó
Ph
â
nl
ọa
i
p
h
ươ
n
g
p
h
áp
g
i
á
n
t
i
ếp

â
ọa
p ươ g
páp
gá
t ếp
1. Phương pháp thử -sai
1
Thử
i
hệ
thố
1
.
Thử
-sa
i
hệ
thố
ng
2. Thử - sai phân lớp
Thử
i
ẫ
hiê
3.
Thử
-sa
i
ng

ẫ
un
hiê
n
2. Phương pháp Heuristic
3. Phương
p
háp trí tuệ nhân tạo
Ph
há
thử
i
Ph
ương p
há
p
thử
-sa
i
Thomas Edison
–
p
hát bi
ể
u cách tìm mộtcâ
y
kim tron
g
một đ
ố

n
g
p
y
g
g
rơm: “trong khi chưa nghĩ ra đượcmộtcáchthậthaythìcứ
việc rút từng cọng rơmchođến khi rút được cây kim”.
Ph
há
à
d
tê
3
ê
lý
Ph
ương
phá
pn
à
y
dự
t
r
ê
n
3
nguy
ê

n
lý
:
1. Nguyên lý vét cạn(duyệttoànbộ): liệtkêtấtcả các trường hợp
xả
y
ra và xem xét chún
g
.
y
g
Ví dụ:liệtkêtấtcả số nguyên tố từ m đếnn.
2. Nguyên lý ngẫu nhiên: dựatrênviệcthử mộtsố khả năng được
chọn
một
cách
ngẫu
nhiên
trong
tập
khả
năng
(
thường
rất
lớn
chọn
một
cách
ngẫu

nhiên
trong
tập
khả
năng
(
thường
rất
lớn
,
nếuápdụng nguyên lý toàn bộ sẽ tốnnhiềuthờigian).Khả
năng tìm lờigiải đúng (hoặcgần đúng) sẽ phụ thuộcvàochiến
l
h
ẫ
hiê
à
ột
ố
điề
kiệ
thể
l
ượcc
h
ọnn
gẫ
un
hiê
nv

à
m
ột
s
ố
điề
u
kiệ
ncụ
thể
.
Ví dụ:kiểmtrachấtlượng trong quá trình sảnxuấtcủamột đoàn kiểmtra.
Một lô hàng có 1000 thùng, chọnngẫu nhiên 10 thùng, mỗi thùng có
24
ả
hN
h
ẫ
hiê
5
ả
hN
24
s
ả
n
phN
m, c
h
ọnng

ẫ
un
hiê
n
5
s
ả
n
phN
m,
N
g
u
y
ên l
ý
đư
ợ
c
p
hát triên thành
p
hươn
g
p
há
p
Monté-Carlos.
gy
ý

ợ
p
p g
pp
Càng ngày nguyên lý ngẫu nhiên càng phát triểnmạnh mẽ,
trong sốđócómộtphương pháp nổibậtlàphươn gpháp
Gti
G
ene
ti
c.
3. Nguyên lý mê cung: nguyên lý này đượcápdụng khi chúng ta
không
biết
chính
xác
"
hình
dạng
"
của
lời
giải
,
mà
phải
xây
không
biết
chính

xác
hình
dạng
của
lời
giải
,
mà
phải
xây
dựng lờigiảidầnquatừng bước, giống như tìm đượcrakhỏi
mê cung.
Thử sai - hệ thống
1. Nguyên lý vét cạntoànbộ:muốn tìm cây kim trong đống
rơm
hãy
lần
lượt
rút
từng
cọng
rơm
đến
khi
rút
được
cây
rơm
,
hãy

lần
lượt
rút
từng
cọng
rơm
đến
khi
rút
được
cây
kim.
Thuật
giải
:
gọi
D
là
không
gian
bài
toán
(
tập
tất
cả
khả
năng
Thuật
giải

:
gọi
D
là
không
gian
bài
toán
(
tập
tất
cả
khả
năng
xảyra),D={(x
1
,x
2
, ,x
n
)/x
i
∈D
i
vớiD
i
là tậphữuhạncóm
i
phầntử}.
gọi f: D {true, false} là quy tắcxácđịnh lờigiải.

Ví dụ:một đàn gà và mộtbầychócótổng cộng N chân, đàn
gà đông hơnbầy chó M con. Hỏi có bao nhiêu gà và chó?
2. Nguyên lý mắtlưới: lướibắtcáchỉ bắt đượcnhững con cá có
kích thướclớnhơnkíchthướcm
ắ
tlưới.
Ví dụ:
Tìm n
g
hi
ệ
m
p
hươn
g
trình tron
g
m
ộ
t đo
ạ
n
g ệ
p g
g
ộ
ạ
Khử nhiễu trong ảnh
3. Nguyên lý mê cung: Muốn thóat khỏi mê cung thì phảibiết
quay lui và biết đánh dấunhững nơi đã đi qua.

Ví dụ:
Tìm đường đingắnnhất
hử
i
hâ
lớ
T
hử
-sa
i
p
hâ
n
lớ
p
1
Nguyên
lý
chung
về
giảm
độ
phức
tạp
của
thử
-
sai
:
thu

hẹp
1
.
Nguyên
lý
chung
về
giảm
độ
phức
tạp
của
thử
sai
:
thu
hẹp
tậptrường hợptrước và trong khi duyệt, đồng thời đơngiản
hóa tối đa điềukiệnchấpnhậnmộttrường hợp.
2. Quy tắc:
1. đơngiản điềukiện:tránhtínhlại trong vòng lặpvàthừakế kếtquả
ổ
tính toán của
b
ướctrước: t
ổ
hợpchỉnh hợp, heap sort,
2. Kỹ thuậtcầm canh: mã đituần,
y
số

âm
đầu
tiên
trong
mảng
:
điều
kiện
while(x[
i
]
>
0
&&
i
<=
n)
do
cách
khác
số
âm
đầu
tiên
trong
mảng
:
điều
kiện
while(x[

i
]
0
&&
i
n)
do
cách
khác
a[n+1]=-1; while(x[i]>0) do
3. Nguyên lý thu gọn không gian tìm kiếm: loạibỏ những
t ờ
h
h ặ
hó
t ờ
h
hắ
hắ
khô
dẫ
đế
t
rư
ờ
ng
h
ợp
h
o

ặ
cn
hó
m
t
rư
ờ
ng
h
ợpc
hắ
cc
hắ
n
khô
ng
dẫ
n
đế
n
lờigiải.
y Quy tắc rút gọn:
1. Dựatrênđánh giá toàn cục: tìm điềukiện để rút gọntậpkhả năng đề
ầ
c
ử
trong một
b
ướcxâydựng một thành
p

h
ầ
n.
Ví dụ: tìm tổ hợpchặpncủak.
2
Dựa
trên
đánh
giá
cục
bộ
:
xây
dựng
phép
kiểm
tra
đơn
giản
để
nhanh
2
.
Dựa
trên
đánh
giá
cục
bộ
:

xây
dựng
phép
kiểm
tra
đơn
giản
để
nhanh
chóng loạibỏđượccáckhả năng cho thành phần x[i] mà không phải
xây dựng toàn bộ n-i thành phầncònlạicủalờigiải.
d
h
ố
hi
{
}
d
Ví
dụ
:c
h
osáus
ố
t
ự
n
hi
ên A=
{

1,7,2,9,3,5
}
.Tìm
d
ãy con củaAsao
cho tổng các phầntử trong dãy con bằng 8.
4
Nguyên
lý
đánh
giá
nhánh
cận
:
nhánh
có
chứa
quả
phải
nặng
4
.
Nguyên
lý
đánh
giá
nhánh
cận
:
nhánh

có
chứa
quả
phải
nặng
hơntrọng lượng củaquả.
Ví dụ: bài toán ngườidulịch.
5. Quay lui không dùng đệ quy
6. Phươn
g
p
há
p
sinh lời
g
iải
g
pp
g