Laäp trình C - Caáu truùc döõ Lieäu giaûi thuaät
Leâ Vaên Haïnh Oct11 1
TOÅNG QUAN 1
1. MÔÛ ÑAÀU:
1.1. Laäp trình: (Programming) laø moät quaù trình vieát chöông trình baèng moät ngoân ngöõ
naøo ñoù maø maùy tính coù theå thöïc hieän vaø nhöõng ngöôøi laäp trình khaùc coù theå hieåu.
1.2. Caùc böôùc trong giai ñoaïn laäp trình:
Böôùc 1 : GIAÛI THUAÄT
(i) Nghó ra caùch giaûi ( giaûi thuaät) .
(ii) Laøm roõ raøng giaûi thuaät : baèng caùch phaân ñoaïn giaûi thuaät thoâng qua caùc hình
veõ, sô ñoà. Thoâng thöôøng, ngöôøi ta duøng löu ñoà (Flow Chart) ñeå trình baøy
giaûi thuaät.
Böôùc 2 : VIEÁT CHÖÔNG TRÌNH
(i) Vieát phaàn loõi cuûa thaân chöông trình.
(ii) Theâm caùc phaàn nhaäp vaø xuaát.
(iii) Theâm caùc phaàn khai baùo.
Böôùc 3 : CHAÏY THÖÛ, SÖÛA CHÖÕA
(i) Chaïy thöû chöông trình trình nhieàu laàn, söûa chöõa nhöõng loãi nhoû.
(ii) Söûa chöõa, caûi tieán chöông trình.
Böôùc 4 : TOÅNG KEÁT
(i) Theâm nhöõng ghi chuù cho chöông trình nhö :
Muïc ñích cuûa caû chöông trình.
Muïc ñích cuûa 1 ñoaïn chöông trình hay 1 phaùt bieåu.
1.3. Thuaät toaùn (Algorithm):
1.3.1. Thuaät toaùn: laø moät daõy caùc böôùc chaët cheõ vaø roõ raøng, xaùc ñònh moät trình töï
caùc thao taùc treân moät soá ñoái töôïng naøo ñoù sao cho moät soá höõu haïn laàn
thöïc hieän ta thu ñöôïc keát quaû nhö mong ñôïi.
1.3.2.
Caùc ñaëc tröng cuûa thuaät toaùn
:
Tính döøng (tính keát thuùc): Moät thuaät toaùn bao giôø cuõng phaûi döøng sau moät
soá höõu haïn caùc böôùc thöïc hieän .
• Phaân bieät ñöôïc giöõa giaûi thuaät, thuaät toaùn, löu ñoà, maõ giaû vaø
chöông trình.
• Töø cuøng 1 chöông trình, hoïc sinh coù theå laàn löôït laäp giaûi thuaät,
thuaät toaùn, löu ñoà, maõ giaû vaø vieát chöông trình.
• Laøm quan vôùi caùc khaùi nieäm veà bieán, haèng soá, kieåu döõ lieäu, toaùn
töû, leänh gaùn, caùc ñoái töôïng nhaäp xuaát trong C.
MUÏC TIEÂU
Laäp trình C - Caáu truùc döõ Lieäu giaûi thuaät
Leâ Vaên Haïnh Oct11 2
Tính phoå duïng (tính chính xaùc): thuaät toaùn coù theå giaûi baát kyø baøi toaùn naøo
trong moät lôùp caùc baøi toaùn. Cuï theå laø thuaät toaùn coù theå laøm vieäc vôùi caùc döõ
lieäu khaùc nhau vaø luoân daãn ñeán moät keát quaû mong muoán.
Ví duï : chöông trình Giaûi phöông trình baäc hai phaûi cho keát quaû luoân ñuùng vôùi caùc döõ
lieäu soá nhaäp vaøo cho a,b,c laø baát kyø (soá nguyeân, soá thöïc, soá döông, soá aâm. . .)
Tính duy nhaát : nghóa laø vôùi nhieàu laàn chaïy chöông trình treân cuøng moat taäp
döõ lieäu ñaøu vaøo phaûi cho ra cuøng moät keát quaû.
Tính roõ raøng: giaûi thuaät phaûi ñöôïc theå hieän baèng caùc caâu leänh minh baïch;
caùc caâu leänh ñöôïc saép xeáp theo thöù töï nhaát ñònh.
Tính khaùch quan: Moät giaûi thuaät duø ñöôïc vieát bôûi nhieàu ngöôøi treân nhieàu
maùy tính vaãn phaûi cho keát quaû nhö nhau.
1.3.3. Moät thuaät toaùn khoâng phaûi laø moät chöông trình, thuaät toaùn coù theå ñöôïc moâ
taû bôûi moät trong ba caùch:
Maõ töï nhieân
Maõ giaû (pseudocode).
Duøng caùc bieåu töôïng ñöôïc quy ñònh ñeå bieåu dieãn giaûi thuaät (flowchart).
1.4. Giaûi thuaät:
Trong khi tìm kieám lôøi giaûi cho caùc baøi toaùn trong thöïc teá, ngöôøi ta nhaän ra
raèng:
(i) Coù nhöõng baøi toaùn ñeán nay vaãn chöa xaùc ñònh ñöôïc lieäu coù toàn taïi moät
thuaät toaùn ñeå giaûi quyeát hay khoâng?
(ii) Coù nhöõng baøi toaùn ñaõ coù thuaät toaùn ñeã giaûi nhöng, nhöng khoâng chaáp
nhaän ñöôïc do:
Thôøi gian ñeå giaûi baøi toaùn theo thuaät toaùn ñoù quaù lôùn.
Caùc ñieàu kieän kyõ thuaät cho thuaät toaùn khoù ñaùp öùng.
(iii) Coù nhöõng baøi toaùn coù theå giaûi ñöôïc moät caùch höõu hieäu baèng moät lôøi giaûi
naøo ñoù, nhöng lôøi giaûi naøy laïi vi phaïm moät soá tính chaát cuûa thuaät toaùn.
Trong thöïc tieãn, coù raát nhieàu tröôøng hôïp ngöôøi ta chaáp nhaän caùc caùch giaûi
thöôøng cho keát quaû toát (taát nhieân khoâng phaûi luùc naøo cuõng toát) nhöng ít
phöùc taïp, hieäu quaû vaø khaû thi.
Do ñoù, ngöôøi ta môû roäng khaùi nieäm thuaät toaùn (giuùp cho thuaät toaùn bôùt
“cöùng nhaéc”) baèng moät khaùi nieäm môùi laø giaûi thuaät. Giaûi thuaät laø nhöõng caùch
giaûi khoâng hoaøn toaøn ñaùp öùng ñaày ñuû caùc tính chaát cuûa moät thuaät toaùn nhöng
vaãn cho keát quaû gaàn ñuùng. Hieän nay ñaõ coù nhöõng giaûi thuaät ñeä quy, giaûi thuaät
ngaãu nhieân, giaûi thuaät Heuristic, .. .
Ñeå thuaän tieän, trong taøi lieäu naøy seõ söû duïng khaùi nieäm giaûi thuaät ñeå chæ
chung cho thuaät toaùn vaø giaûi thuaät.
Toùm laïi, Giaûi thuaät laø moät taäp hôïp höõu haïn cuûa caùc chæ thò hay phöông
caùch ñöôïc ñònh nghóa roõ raøng cho vieäc hoaøn taát moät soá söï vieäc töø moät traïng
thaùi ban ñaàu cho tröôùc; khi caùc chæ thò naøy ñöôïc aùp duïng trieät ñeå thì seõ daãn ñeán
keát quaû sau cuøng nhö ñaõ döï ñoaùn.
Laäp trình C - Caáu truùc döõ Lieäu giaûi thuaät
Leâ Vaên Haïnh Oct11 3
1.4.1. Maõ töï nhieân:
1.4.1.1. Khaùi nieäm:
Laø vieát noäi dung chöông trình baèng ngoân ngöõ töï nhieân giaûn löôïc.
1.4.1.2. Quy öôùc :
Phaûi deã hieåu, deã nhôù, nhaát quaùn vaø khoâng coù söï hieåu laàm.
1.4.1.3. Ví duï : vieát chöông trình cho ngöôøi duøng nhaäp 1 soá nguyeân döông
(n). Tính toång caùc soá töø 1 ñeán n.
B1: Nhaäp soá n
B2: Toång=0
B3: Soá ñang xeùt=1
B4: Thöïc hieän khi Soá ñang xeùt <=n
Coäng doàn Soá ñang xeùt vaøo bieán Toång
Taêng soá ñang xeùt leân 1 ñôn vò.
Quay laïi B4
B5: Xuaát giaù trò cuûa Toång
1.4.2. Maõ giaû (
pseudocode
):
1.4.2.1. Khaùi nieäm:
Duøng ngoân ngöõ ñaõ ñöôïc quy öôùc tröôùc ñeå dieãn ñaït thuaät toaùn.
1.4.2.2. Quy öôùc :
• Phaûi deã hieåu, khoâng caàn moâ taû chi tieát ñeán caùc kyõ thuaät duøng trong laäp
trình.
• Coù theå duøng caùc töø khoùa cuûa ngoân ngöõ ñang duøng, hoaëc coù theå söû duïng
moät soá töø khoùa ñaõ ñöôïc quy öôùc tröôùc nhö:
IF <Ñieàu kieän> THEN …ENDIF
IF < Ñieàu kieän > THEN ... ELSE ... ENDIF
WHILE < Ñieàu kieän > DO … ENDWHILE
DO … UNTIL < Ñieàu kieän >
WRITE …
RETURN …
1.4.2.3. Ví duï : vieát chöông trình cho ngöôøi duøng nhaäp 1 soá nguyeân döông
(n). Tính toång caùc soá töø 1 ñeán n.
Input: n
Process:
Tong=0
SoDangXet=1
WHILE (SoDangXet <=n) DO
Tong = Tong + SoDangXet
SoDangXet = SoDangXet +1.
ENDWHILE
Output: Tong
Laäp trình C - Caáu truùc döõ Lieäu giaûi thuaät
Leâ Vaên Haïnh Oct11 4
1.4.3. Löu ñoà chöông trình:
1.4.3.1. Khaùi nieäm : Coøn ñöôïc goïi laø sô ñoà khoái. Laø sô ñoà theå hieän caùc böôùc
cuûa giaûi thuaät lieân quan ñeán moät vaán ñeà naøo ñoù ñöôïc ñöa vaøo giaûi
quyeát baèng maùy tính.
1.4.3.2. Caùc kyù hieäu duøng trong löu ñoà:
KYÙ HIEÄ
U
YÙ NGHÓA
nhaäp
xuaát
Chöùc naêng cuûa coâng vieäc vaøo ra döõ lieäu.
xöû lyù Nhoùm leänh ñeå thöï hieän moät chöùc naêng naøo ñoù cuûa
chöông trình
chöông
trình con
chöông trình con ñaõ ñònh nghóa.
quyeát
ñònh
Quyeát ñònh reõ nhaùnh naøo caên cöù vaøo ñieàu kieän chæ
ñònh ñöôïc ghi trong khoái. Trong moät soá tröôøng hôïp,
hình thoi ñöôïc môû roäng thaønh 1 hình ña giaùc coù
nhieàu ñöôøng ra, öùng vôùi caùc giaù trò cuûa bieåu thöùc
beân trong.
Höôùng xöû lyù cuûa löu ñoà.
noái trang Ñieåm vaøo hay ñieåm ra cuûa töøng trang trong löu ñoà
chöông trình.
ñieåm
cuoái
Ñieåm ñaàu hay ñieåm cuoái cuûa löu ñoà.
Noái Ñieåm vaøo hay ñieåm ra cuûa töøng phaàn trong löu ñoà
chöông trình.
1.4.3.3. Moät soá ví duï bieåu dieãn thuaät toaùn baèng löu ñoà:
1.4.3.3.1 Thuaät toaùn khoâng phaân nhaùnh:
Ví duï: Tính a=b2+c2. Vôùi b vaø c ñöôïc nhaäp vaøo
töø baøn phím. (hình 1)
Begin
b, c
A=b2+c2
A
End
(Hình 1)
Laäp trình C - Caáu truùc döõ Lieäu giaûi thuaät
Leâ Vaên Haïnh Oct11 5
1.4.3.3.2 Thuaät toaùn coù phaân nhaùnh:
Ví duï 1: Cho nhaäp 3 soá, in ra giaù trò lôùn nhaát trong 3 soá.
Coù theå thöïc hieän baèng nhieàu caùch, trong phaàn naøy neâu leân 2
trong caùc caùch:
Caùch 1: hình 2 (duøng bieán trung gian)
Caùch 2: hình 3 (duøng pheùp AND/OR/NOT trong ñieàu kieän.
Ví duï 2: Giaûi phöông trình baäc 1 ax+b=0. Vôùi a,b ñöôïc nhaäp vaøo(hình 4)
Ví duï 3: Giaûi phöông trình baäc 2 ax2 + bx + c =0. Vôùi a, b, c ñöôïc nhaäp
vaøo. (hình 5)
Begin
a, b, c
Max
End
a > b Max = b
Max = a
Max < c
Max = c
S
S
Ñ
Ñ
(Hình 2)
Begin
a, b, c
a>=b
AND
a>=c
S
Ñ
(Hình 3
)
Soá lôùn nhaát laø a
b>=a
AND
b>=c
Soá lôùn nhaát laø b
S
Ñ
Soá lôùn nhaát laø c End