De Cuong Ktlt-dh

Bé c«ng th¬ng Trêng §¹i häc c«ng nghiÖp hµ néi --- ---

®Ò c¬ng chi tiÕt m«n häc

kü thuËt lËp tr×nh (Tµi liÖu gi¶ng d¹y)

hÖ: §¹i häc (lu hµnh néi bé)

Hµ néi – 4/2007

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Tµi liÖu tham kh¶o 1. Kü thuËt lËp tr×nh C – GS.TS. Ph¹m V¨n Êt 2. Ng«n ng÷ lËp tr×nh C++ - GS. TS. Ph¹m v¨n Êt. 3. Kü thuËt lËp tr×nh - NguyÔn TiÕn Huy – TrÇn H¹nh Nhi. 4. Ng«n ng÷ lËp tr×nh C++ - Ng« Trung ViÖt. …. Néi dung Ch¬ng I. Tæng quan vÒ C++ Ch¬ng II. C¸c cÊu tróc ®iÒu khiÓn Ch¬ng III.

Kü thuËt lËp tr×nh ®¬n thÓ

Ch¬ng IV.

Kü thuËt lËp tr×nh dïng m¶ng

Ch¬ng V. Kü thuËt lËp tr×nh dïng con trá Ch¬ng VI. Kü thuËt lËp tr×nh víi tÖp Ch¬ng VII. D÷ liÖu kiÓu cÊu tróc Ph©n bæ thêi gian: 30 tiÕt lý thuyÕt + 60h thùc hµnh §iÒu kiÖn tiªn quyÕt: §· häc m«n NhËp m«n tin häc, Pascal Thang ®iÓm: 10 Sè bµi kiÓm tra: 02 bµi Sè bµi thi: 01 bµi thi gi÷a häc phÇn + 01 bµi thi hÕt häc phÇn. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

2

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Biªn so¹n: ThS. NguyÔn M¹nh Cêng

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

3

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü Ch¬ng I. tæng quan vÒ C++

I. Quy tr×nh lµm viÖc trong C++

I.1. C¸c bíc ®Ó lËp ch¬ng tr×nh b»ng C++ §Ó thùc hiÖn viÖc viÕt vµ thùc thi mét ch¬ng tr×nh ®¬n gi¶n trong C++, ngêi ta thêng lµm theo c¸c bíc sau: - Vµo m«i trêng so¹n th¶o m· lÖnh cña C++: ®Ó lµm ®îc viÖc nµy, trªn m¸y tÝnh ph¶i ®îc cµi ®Æt phÇn mÒm Turbo C 3.0 (hoÆc cao h¬n, hoÆc Booland C…). T×m file TC.exe trong th môc TC\BIN (hoÆc TC30\BIN) vµ thùc thi file nµy. - So¹n th¶o m· lÖnh cña ch¬ng tr×nh: M«i trêng so¹n th¶o cña TC lµ mét cöa sæ so¹n th¶o vµ hÖ thèng menu trî gióp qu¸ tr×nh so¹n th¶o còng nh dÞch vµ thùc thi ch¬ng tr×nh. Ta tiÕn hµnh so¹n th¶o m· lÖnh cña ch¬ng tr×nh trong cöa sæ nµy theo ®óng có ph¸p cña C++. - So¸t lçi, dÞch ch¬ng tr×nh: Sau khi so¹n th¶o m· lÖnh b»ng ng«n ng÷ C++, ta tiÕn hµnh dÞch ch¬ng tr×nh thµnh ng«n ng÷ m¸y. Qu¸ tr×nh dÞch chØ thµnh c«ng khi toµn bé m· lÖnh ta so¹n th¶o kh«ng cã lçi có ph¸p. V× vËy, trong qu¸ tr×nh dÞch, TC sÏ tiÕn hµnh so¸t lçi. Qu¸ tr×nh so¸t lçi ®îc tiÕn hµnh lÇn lît qua c¸c dßng lÖnh tõ trªn xuèng. Khi gÆp lçi, ch¬ng tr×nh dÞch sÏ b¸o lçi t¹i vÞ trÝ gÇn n¬i x¶y ra lçi. §Ó lµm c¸c c«ng viÖc dÞch – so¸t lçi, ta bÊm phÝm F9, nÕu ch¬ng tr×nh b¸o lçi, h·y tiÕn hµnh söa lçi. NÕu muèn qu¸ tr×nh dÞch cho ta mét file thùc thi ®îc cña ch¬ng tr×nh trªn ®Üa (file .exe) ta cÇn ®¶m b¶o trªn menu: Options\ Linker\ Settings\ Output\ Standard exe ®ang ®îc chän. - Thùc thi ch¬ng tr×nh: Khi ch¬ng tr×nh ®· hÕt lçi ta cã thÓ thùc thi ch¬ng tr×nh b»ng c¸ch bÊm tæ hîp phÝm Ctrl F9. KÕt thóc qu¸ tr×nh thùc thi sÏ quay vÒ m«i trêng so¹n th¶o m· lÖnh ban ®Çu. C¸c thao t¸c khi so¹n th¶o:

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

4

§Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh Më file míi: Chän File\ New hoÆc bÊm phÝm chøc n¨ng F3, gâ tªn file míi vµo vµ bÊm Enter. Më file cã s½n: Chän File\ Open hoÆc bÊm phÝm chøc n¨ng F2 råi chän file cÇn më vµ bÊm Enter. Lu file: Chän File\ Save hoÆc bÊm phÝm chøc n¨ng F2 råi ®Æt tªn file vµ bÊm Enter. Chó ý trong C++, phÇn më réng cña file m· nguån lµ .CPP. §ãng file: BÊm tæ hîp phÝm Alt F3. NÕu file cha lu, C++ sÏ yªu cÇu lu file hoÆc bá qua viÖc lu file, h·y bÊm Y hoÆc N nÕu muèn lu file hoÆc kh«ng lu file. Phãng to, thu nhá cña sæ so¹n th¶o: BÊm phÝm chøc n¨ng F5. ChuyÓn ®Õn cöa sæ so¹n th¶o bÞ Èn ®»ng sau cöa sæ hiÖn t¹i: bÊm phÝm chøc n¨ng F6. Tho¸t khái m«i trêng C++: BÊm tæ hîp phÝm Alt X. B«i ®en vïng m· lÖnh: kÝch, gi÷ vµ rª chuét lªn vïng cÇn b«i ®en hoÆc chuyÓn con trá vÒ ®Çu vïng cÇn b«i ®en råi gi÷ phÝm Shift trong lóc di chuyÓn con trá qua vïng cÇn b«i ®en. Sao chÐp vïng b«i ®en: Chän Edit\ Copy hoÆc bÊm tæ hîp phÝm Ctrl + Insert. D¸n vïng m· lÖnh ®· sao chÐp: Chän Edit\ Paste hoÆc bÊm tæ hîp phÝm Shift + Insert. Sao chÐp nhanh vïng b«i ®en: Di chuyÓn ®Õn vÞ trÝ míi vµ bÊm phÝm K råi C trong lóc gi÷ phÝm Ctrl. Di chuyÓn vïng b«i ®en: ChuyÓn ®Õn vÞ trÝ míi vµ bÊm phÝm K råi V trong lóc gi÷ phÝm Ctrl. Xo¸ vïng m· lÖnh ®· b«i ®en: BÊm phÝm K råi Y trong lóc gi÷ phÝm Ctrl. Bá b«i ®en: BÊm phÝm K råi K trong lóc gi÷ phÝm Ctrl hoÆc cã thÓ bÊm phÝm K råi H trong lóc ®ang gi÷ phÝm Ctrl. ChuyÓn con trá vÒ ®Çu dßng: BÊm phÝm Home. ChuyÓn con trá vÒ cuèi dßng: BÊm phÝm End.

I.2. CÊu tróc mét ch¬ng tr×nh ®¬n gi¶n trong C++ Mét ch¬ng tr×nh ®¬n gi¶n trong C++ thêng ®îc viÕt trong mét cöa sæ so¹n th¶o (®iÒu nµy kh«ng hoµn toµn ®óng trong c¸c ch¬ng tr×nh lín). Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

5

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Mét ch¬ng tr×nh bÊt kú trong C++ ®Òu ®îc t¹o nªn tõ rÊt nhiÒu hµm (t¹m gäi lµ nh÷ng ®¬n vÞ ch¬ng tr×nh), trong ®ã cã mét hµm ®Æc biÖt ®îc xem nh “ch¬ng tr×nh chÝnh” vµ ®îc gäi lµ hµm main. Th«ng thêng hµm main ®îc viÕt ra ®Ó gäi (sö dông) c¸c hµm kh¸c nh»m gi¶i quyÕt bµi to¸n. Tuy nhiªn, ë ®©y ta chØ xÐt mét ch¬ng tr×nh ®¬n gi¶n bao gåm duy nhÊt mét hµm main, ta viÕt theo cÊu tróc sau: 1#include 2void main() 3{ 4C¸c lÖnh trong th©n hµm main 5} Dßng 1: ®îc gäi lµ c¸c chØ thÞ tiÒn xö lý. Dßng nµy cã nhiÖm vô khai b¸o c¸c th viÖn sÏ sö dông trong ch¬ng tr×nh. Trong C++, c¸c lÖnh (hµm) thêng ®îc ®Æt trong c¸c th viÖn, lµ c¸c file .h (cã thÓ t×m thÊy chóng trong th môc Include cña bé TC). NÕu trong ch¬ng tr×nh muèn sö dông c¸c lÖnh nµy th× cÇn ph¶i khai b¸o sÏ sö dông c¸c th viÖn t¬ng øng t¹i ®©y. Cã rÊt nhiÒu th viÖn cã thÓ sö dông nhng nh÷ng th viÖn hay dïng lµ: conio.h, stdio.h, iostream.h, math.h, iomanip.h, string.h, ofstream.h, ifstream.h, fstream.h,… Dßng 2: lµ tõ kho¸ void main() khai b¸o b¾t ®Çu hµm main. Dßng 3 vµ 5: c¸c dÊu ‘{‘ vµ ‘}’ b¸o hiÖu b¾t ®Çu vµ kÕt thóc th©n hµm main hoÆc b¾t ®Çu vµ kÕt thóc mét khèi lÖnh. Dßng 4: lµ n¬i ta ®Æt c¸c lÖnh cña ch¬ng tr×nh chÝnh. VÝ dô: ch¬ng tr×nh in ra mµn h×nh dßng ch÷ “Hello wold !” #include “iostream.h” Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

6

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü void main() { cout<< “Hello wold !”; getch(); }

§Ó xem trong mét th viÖn cã chøa nh÷ng hµm nµo, trªn menu ta chän Help\ Index råi gâ tªn th viÖn vµ bÊm Enter. §Ó xem mét hµm ta ®ang sö dông thuéc vµo th viÖn nµo, ta còng chän help\ Index råi gâ tªn hµm vµ bÊm Enter. Trong C++ cã ph©n biÖt ch÷ hoa vµ ch÷ thêng. Sau mçi lÖnh ®Òu cã dÊu “;” ®Ó b¸o kÕt thóc lÖnh. §Æt l¹i ®êng dÉn tíi c¸c th viÖn: Trong mét ch¬ng tr×nh ta thêng sö dông c¸c hµm trong c¸c th viÖn kh¸c nhau ®îc khai b¸o t¹i dßng 1 (nh trªn). Th«ng thêng, c¸c th viÖn ®Æt trong c¸c th môc TC\INCLUDE. M«i trêng lËp tr×nh C++ tù thiÕt ®Æt ®êng dÉn tíi c¸c th viÖn nµy. Tuy nhiªn, trong trêng hîp ®êng dÉn bÞ thay ®æi, ch¬ng tr×nh dÞch sÏ kh«ng t×m thÊy chóng vµ b¸o lçi, khi ®ã ta cÇn ph¶i thiÕt ®Æt l¹i: B1: Trong Menu chÝnh, chän Option\ Directories. B2: Trong Include, ®Æt ®êng dÉn tíi c¸c th viÖn cã ®u«i .h(vÝ dô: C:\TC\INCLUDE). Trong Libraries, ®Æt ®êng dÉn tíi c¸c th viÖn ®u«i .lib (vÝ dô: C:\TC\LIB). II. BiÕn, biÓu thøc, c¸c lÖnh nhËp xuÊt

II.1. BiÕn §Ó hiÓu kh¸i niÖm vµ b¶n chÊt biÕn, ta xÐt ch¬ng tr×nh ®¬n gi¶n sau: NhËp vµo c¸c sè nguyªn a, b. Gäi P lµ tæng cña a vµ b, S lµ tÝch cña a vµ b. TÝnh K=S*P/(S+P). Ta dÔ dµng biÓu diÔn bµi to¸n b»ng m« h×nh sau: a b

P

S

K

Cã thÓ coi ®Çu vµo cña bµi to¸n lµ a, b vµ ®Çu ra lµ K. C¸c gi¸ trÞ P vµ S lµ c¸c gi¸ trÞ trung gian. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

7

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Khi ngêi dïng nhËp vµo c¸c gi¸ trÞ a vµ b, chóng cÇn ®îc lu tr÷ trong bé nhí. T¬ng tù nh vËy c¸c gi¸ trÞ P, S, K nÕu cÇn còng sÏ ®îc lu tr÷ trong bé nhí. VËy tèi ®a ta cÇn sö dông 5 « nhí ®Ó lu tr÷ chóng. C¸c « nhí nµy gäi lµ c¸c biÕn. BiÕn lµ mét vïng nhí ®îc ®Æt tªn. Mçi « nhí (biÕn) ®Òu ®îc ®Æt 1 tªn tu©n theo quy íc ®Æt tªn nh sau: - Tªn biÕn bao gåm ch÷ c¸i, ch÷ sè hoÆc dÊu g¹ch nèi ‘_’ - Ký tù ®Çu tiªn cña tªn biÕn kh«ng ®îc lµ mét ch÷ sè. - Kh«ng ®îc trïng víi tõ kho¸. - Trong cïng mét ph¹m vi kh«ng cã 2 biÕn trïng tªn. Trong ch¬ng tr×nh, ta sö dông tªn biÕn ®Ó truy cËp vµo « nhí cña biÕn. Khi ®ã tªn biÕn chÝnh lµ gi¸ trÞ ®ang chøa trong « nhí cña nã. TÊt c¶ c¸c biÕn khi sö dông ®Òu ph¶i khai b¸o. Có ph¸p nh sau: ;

Trong ®ã: : mçi biÕn dïng ®Ó chøa mét lo¹i gi¸ trÞ kh¸c nhau nh: sè nguyªn, sè thùc, ký tù .v.v.., do vËy chóng ph¶i cã kiÓu t¬ng øng. Mét sè kiÓu c¬ b¶n nh sau: KiÓu sè: bao gåm + Sè nguyªn int/ short int: lµ kiÓu d÷ liÖu cã ®é dµi 2 byte, dïng ®Ó khai b¸o c¸c biÕn nguyªn cã gi¸ trÞ trong kho¶ng –32768 -> 32767 + Sè nguyªn kh«ng dÊu: unsigned int: ®é dµi 2 byte, khai b¸o c¸c biÕn nguyªn cã gi¸ trÞ tõ 0 tíi 65535. + Sè nguyªn dµi long: lµ kiÓu d÷ liÖu cã ®é dµi 4 byte, dïng khai b¸o c¸c biÕn nguyªn cã gi¸ trÞ trong kho¶ng – 2.147.483.648 -> 2.147.483.647.

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

8

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

+ Sè nguyªn dµi kh«ng dÊu: unsigned long: ®é dµi 4 byte, khai b¸o c¸c biÕn cã gi¸ trÞ tõ 0 tíi 4.294.967.295. + Sè thùc (dÊu ph¶y ®éng) float: kÝch thíc 4 byte khai b¸o c¸c biÕn thùc tõ 3.4*10-38 -> 3.4*1038. + Sè thùc (dÊu ph¶y ®éng, ®é chÝnh x¸c kÐp) double: kÝch thíc 8 byte, cã ph¹m vi tõ 1.7*10-308 - > 1.7*10308 + Sè thùc (dÊu ph¶y ®éng, ®é chÝnh x¸c kÐp) dµi long double: kÝch thíc 10 byte, khai b¸o c¸c biÕn tõ 3.4 * 10-4932 tíi 1.1 * 104932. KiÓu ký tù: bao gåm + KiÓu ký tù char: khai b¸o biÕn chøa mét ký tù. + KiÓu con trá ký tù char *: t¬ng ®¬ng víi chuçi ký tù. : ®îc ®Æt tuú ý tu©n theo c¸c quy íc ®Æt tªn biÕn ë trªn. VÝ dô: int a, b;

float c;

ë ®©y, ta khai b¸o 2 biÕn a vµ b cã cïng kiÓu sè nguyªn vµ biÕn c cã kiÓu sè thùc. Khi ®ã ch¬ng tr×nh sÏ cÊp ph¸t 2 « nhí cã kÝch thíc 2 byte mçi « vµ ®Æt tªn lµ a, b; mét « nhí kÝch thíc 4 byte ®îc ®Æt tªn c. VÞ trÝ khai b¸o: Cã thÓ khai b¸o biÕn t¹i bÊt kú ®©u trong th©n ch¬ng tr×nh tríc khi sö dông. II.2. BiÓu thøc Mét biÓu thøc bao gåm 2 thµnh phÇn: c¸c to¸n tö (phÐp to¸n) vµ c¸c to¸n h¹ng (sè h¹ng). C¸c to¸n tö: Trong C++, c¸c to¸n tö ®îc t¹m ph©n chia lµm 4 lo¹i theo chøc n¨ng cña chóng. Sau ®©y lµ mét sè to¸n tö hay dïng: - C¸c to¸n tö sè häc: Stt 1 2 3

To¸n tö Céng Trõ Nh©n

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

C¸ch viÕt + *

9

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü 4 5 6 7

Chia §ång d T¨ng 1 ®¬n vÞ Gi¶m 1 ®¬n vÞ

/ % ++ --

- C¸c to¸n tö Logic: Stt 1 2 3

To¸n tö Vµ HoÆc Phñ ®Þnh

C¸ch viÕt && || !

- C¸c to¸n tö so s¸nh: Stt

To¸n tö

1 2 3 4

Lín h¬n Nhá h¬n Lín h¬n hoÆc b»ng Nhá h¬n hoÆc b»ng B»ng Kh«ng b»ng

5 6

C¸ch viÕt > < >= <= == !=

- To¸n tö g¸n: Stt 1

To¸n tö G¸n

C¸ch viÕt =

Mét b¶ng t¬ng ®èi ®Çy ®ñ c¸c to¸n tö trong C++ nh sau: [] () . -> ++ -& * + ~ ! sizeof / % << >> < > <= >= == != ^ | && || ?: = *= /= %= += -= <<= >>= &= ^= |= , # ##

C¸c to¸n h¹ng: Cã thÓ chia c¸c to¸n h¹ng lµm 3 lo¹i gåm: h»ng, biÕn vµ hµm. H»ng: gåm h»ng sè, h»ng x©u ký tù vµ h»ng ký tù. H»ng x©u ký tù khi viÕt cÇn ®îc ®Æt gi÷a hai dÊu nh¸y kÐp “”;

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 0

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

h»ng ký tù ®îc ®Æt gi÷a hai dÊu nh¸y ®¬n ‘’ cßn h»ng sè th× kh«ng. Hµm: gåm nh÷ng hµm tr¶ vÒ mét gi¸ trÞ nµo ®ã vµ gi¸ trÞ nµy ®îc sö dông trong biÓu thøc. Cã rÊt nhiÒu hµm cã s½n trong c¸c th viÖn mµ ta cã thÓ sö dông cho biÓu thøc. Sau ®©y lµ mét sè hµm to¸n häc (th viÖn math.h) thêng dïng: STT Tªn hµm 1. Sin(x) 2. 3.

Cos(x) x

C¸ch viÕt sin(x) cos(x) sqrt(x)

4.

ex

exp(x)

5.

Ln(x)

log(x)

6.

Log10(x)

log10(x)

7.

|x| (x nguyªn)

abs(x)

8.

|x| (x thùc)

fabs(x)

VÝ dô: xÐt biÓu thøc to¸n häc sau ((2ex + |x|.Ln(x)) >

x/

sin(x)) ∧ (x < 5)

BiÓu thøc ®îc viÕt díi d¹ng ng«n ng÷ C++ nh sau: (2*exp(x) + fabs(x)*log(x) > sqrt(x)/ sin(x)) && (x < 5) Trong biÓu thøc nµy, c¸c to¸n tö sè häc gåm: +, *; to¸n tö logic gåm: &&; c¸c to¸n tö so s¸nh gåm: >, <; c¸c to¸n h¹ng lµ h»ng sè gåm: 2, 5; to¸n h¹ng lµ biÕn gåm: x; c¸c to¸n h¹ng lµ hµm gåm: exp(x), fabs(x), log(x), sqrt(x), sin(x). II.3. C¸c lÖnh nhËp-xuÊt a. C¸c lÖnh nhËp xuÊt trong IOStream.h - LÖnh xuÊt: cout<< ; Trong ®ã: <<: ®îc gäi lµ to¸n tö xuÊt. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 1

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

: cã thÓ lµ H»ng ký tù, H»ng x©u ký tù, BiÕn, Hµm hoÆc ph¬ng thøc ®Þnh d¹ng. VÝ dô:

cout<<“Sin(x) =”; cout<<sin(x);

Cã thÓ sö dông liªn tiÕp nhiÒu to¸n tö xuÊt trªn mét dßng cout, ch¼ng h¹n: cout<<“Sin(x) =”<<sin(x); NÕu muèn xuÊt d÷ liÖu trªn nhiÒu dßng ta cã thÓ sö dông to¸n tö endl ®Ó xuèng dßng. VÝ dô: cout<<“Sin(x) =”<<endl<<sin(x); sÏ xuÊt d÷ liÖu trªn 2 dßng. • §Þnh d¹ng d÷ liÖu tríc khi xuÊt: Ta cã thÓ sö dông mét trong 2 c¸ch sau: C¸ch 1: sö dông to¸n tö ®Þnh d¹ng: cout.width(int n): chØ ®Þnh tèi thiÓu n vÞ trÝ dµnh cho viÖc xuÊt d÷ liÖu. NÕu gi¸ trÞ xuÊt chiÕm Ýt h¬n n vÞ trÝ th× mÆc ®Þnh lµ c¸c ký tù trèng sÏ chÌn vµo phÝa tríc. NÕu gi¸ trÞ xuÊt chiÕm nhiÒu h¬n n vÞ trÝ, sè vÞ trÝ dµnh cho gi¸ trÞ xuÊt ®ã sÏ ®îc t¨ng lªn sao võa ®ñ thÓ hiÖn gi¸ trÞ xuÊt. cout.fill(char ch): ChØ ®Þnh ký tù ch sÏ ®îc ®iÒn vµo nh÷ng vÞ trÝ trèng (nÕu cã). cout.precision(int n): chØ ®Þnh ®é chÝnh x¸c cña gi¸ trÞ sè khi xuÊt lµ n ký tù phÇn thËp ph©n. VÝ dô: gi¶ sö ta cã biÕn thùc a: float a = 123.4523; NÕu muèn xuÊt a ra mµn h×nh díi d¹ng: 000123.45 ta cã thÓ ®Þnh d¹ng nh sau: cout.width(9); cout.fill(‘0’); cout.precision(2); cout<
C¸ch 2: sö dông c¸c hµm ®Þnh d¹ng: T¬ng tù nh c¸c ph¬ng thøc ®Þnh d¹ng, c¸c hµm ®Þnh d¹ng t¬ng øng lµ: setw(int n) – t¬ng tù nh cout.width(int n). Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 2

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

setfill(char ch) – t¬ng tù nh cout.fill(char ch). setprecision(int n) – t¬ng tù nh cout.precision(int n). C¸ch dïng: sö dông c¸c hµm ®Þnh d¹ng ngay trªn c¸c dßng cout, tríc khi ®a ra gi¸ trÞ xuÊt. Víi vÝ dô trªn, ta cã thÓ viÕt: cout<<setw(9)<<setfill(‘0’)<<setprecision(2)<
- LÖnh nhËp:

cin rel="nofollow">> ;

Trong ®ã: >>: ®îc gäi lµ to¸n tö nhËp. Dßng cin dïng ®Ó nhËp c¸c gi¸ trÞ (th«ng thêng lµ) tõ bµn phÝm vµo c¸c biÕn. VÝ dô: ®Ó nhËp gi¸ trÞ cho biÕn a, ta viÕt: cout<< “a= ”; cin>>a;

Cã thÓ dïng liªn tiÕp nhiÒu to¸n tö nhËp trªn mét dßng cin ®Ó nhËp gi¸ trÞ cho nhiÒu biÕn, ch¼ng h¹n: cin>>a>>b>>c; LÖnh cin chØ thÝch hîp cho viÖc nhËp c¸c biÕn kiÓu sè. Víi c¸c biÕn kiÓu x©u ký tù th× x©u nhËp vµo ph¶i kh«ng chøa dÊu c¸ch v× lÖnh cin sÏ kÕt thóc khi ta nhËp vµo dÊu c¸ch hoÆc phÝm Enter.

VÝ dô: ViÕt ch¬ng tr×nh nhËp vµo mét sè thùc x, in ra mµn h×nh gi¸ trÞ cña F(x) = sin2(x) + |x| + eln(x) víi ®é chÝnh x¸c 2 ch÷ sè sau dÊu ph¶y. #include #include <math.h> #include void main() { clrscr(); float x, F; cout<<”nhËp sè thùc x “; cin>>x; cout.precision(2); cout<<”Gi¸ trÞ F(“<<x<<”) =”; cout<<sin(x)*sin(x) + fabs(x) + exp(log(x)); getch(); }

b. C¸c lÖnh nhËp xuÊt trong Stdio.h - LÖnh xuÊt: printf(“chuçi cÇn xuÊt” , , …); Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 3

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Trong ®ã: - “chuçi cÇn xuÊt” cã thÓ gåm: - H»ng ký tù, h»ng x©u ký tù: Lµ c¸c ký tù cÇn in lªn mµn h×nh. - C¸c ®Æc t¶ hay ký tù ®¹i diÖn, bao gåm: %d: ®¹i diÖn cho biÕn nguyªn. %f: ®¹i diÖn cho biÕn thùc. %c: ®¹i diÖn cho biÕn kiÓu ký tù (mÆc ®Þnh). …

- Mçi biÕn cÇn ®a ra mµn h×nh cÇn cã mét ®Æc t¶ t¬ng øng t¹i vÞ trÝ muèn ®a ra, nh vËy sè lîng biÕn b»ng sè lîng c¸c ®Æc t¶. VÝ dô: CÇn ®a ra c¸c gi¸ trÞ cña c¸c biÕn a, b, c kiÓu nguyªn, ta viÕt: printf (“Gi¸ trÞ cña a b c la %d %d %d”, a, b, c);

- LÖnh nhËp: scanf(“chuçi c¸c ®Æc t¶”, &, &…);

Trong ®ã, mçi biÕn cÇn ph¶i cã mét ®Æc t¶ t¬ng øng. LÖnh scanf nhËp gi¸ trÞ vµo c¸c biÕn th«ng qua ®Þa chØ cña biÕn. To¸n tö & ®îc ®Æt tríc tªn biÕn ®Ó lÊy ®Þa chØ cña biÕn. c. C¸c lÖnh nhËp xuÊt trong Conio.h - LÖnh xuÊt: puts(p); Trong ®ã p lµ mét con trá x©u ký tù, tøc p cã kiÓu char* hoÆc lµ mét m¶ng kiÓu char. LÖnh puts(p) sÏ ®a c¸c ký tù ®îc con trá p trá tíi lªn mµn h×nh. - LÖnh nhËp: gets(p); Trong ®ã p lµ mét con trá x©u ký tù, tøc p cã kiÓu char* hoÆc lµ mét m¶ng kiÓu char. LÖnh gets(p) cã chøc n¨ng cho phÐp ngêi sö dông nhËp vµo mét x©u ký tù vµ chøa x©u võa nhËp vµo biÕn p.

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 4

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

NÕu sö dông liªn tiÕp nhiÒu lÖnh gets th× xen gi÷a c¸c lÖnh gets ta cÇn lµm s¹ch bé ®Öm bµn phÝm b»ng lÖnh : fflush(stdin); C¸c lÖnh gets, puts thÝch hîp cho viÖc nhËp xuÊt c¸c biÕn kiÓu x©u ký tù.

VÝ dô sau ®©y minh ho¹ c¸c sö dông c¸c lÖnh nhËp xuÊt mét c¸ch phï hîp cho tõng lo¹i biÕn: NhËp vµo Hä tªn, quª qu¸n, sè ngµy c«ng cña mét c«ng nh©n. In c¸c th«ng tin võa nhËp lªn mµn h×nh kÌm theo tiÒn c«ng, biÕt r»ng mçi ngµy c«ng ®îc tr¶ 50.000§. #include "iostream.h" #include "stdio.h" #include "conio.h" void main() { char HoTen[30]; char Que[50]; int NgayCong; cout<<"Nhap ho ten: "; gets(HoTen); fflush(stdin); cout<<"Nhap que quan: "; gets(Que); cout<<"Nhap ngay cong: "; cin>>NgayCong; long Luong = (long) NgayCong*50000; cout<<"Thong tin vua nhap la: "<<endl; cout<<"Ho ten:"<
getch(); }

V× NgayCong lµ biÕn kiÓu int nªn khi ta nh©n víi 50000 sÏ ®îc mét con sè thuéc kiÓu int. Tuy nhiªn con sè nµy qu¸ lín so víi d÷ liÖu kiÓu int nªn khi g¸n sang biÕn long Luong ta cÇn chuyÓn nã vÒ kiÓu long b»ng c¸ch viÕt: (long) NgayCong*50000; C¸ch viÕt nµy gäi lµ Ðp kiÓu. §Ó Ðp kiÓu mét biÓu thøc ta viÕt: () ; §Æc biÖt trong C++ lu«n quy ®Þnh phÐp chia mét sè nguyªn cho mét sè nguyªn sÏ thu ®îc th¬ng còng lµ mét sè nguyªn. V× vËy muèn thu ®îc th¬ng lµ sè thùc ta cÇn Ðp kiÓu th¬ng sè nµy. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 5

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

VÝ dô: níi n nguyªn d¬ng, phÐp chia 1/n sÏ cho ta kÕt qu¶ lµ 1 sè nguyªn (lÊy phÇn nguyªn cña th¬ng). §Ó lÊy kÕt qu¶ lµ sè thùc ta viÕt: (float) 1/n.

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 6

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Ch¬ng II. C¸c cÊu tróc ®iÒu khiÓn trong C++

I. CÊu tróc rÏ nh¸nh vµ cÊu tróc chän I.1. CÊu tróc rÏ nh¸nh Trong thùc tÕ, khi gi¶i quyÕt mét c«ng viÖc thêng ta ph¶i lùa chän nhiÒu ph¬ng ¸n gi¶i quyÕt kh¸c nhau. Ngêi ta thêng biÓu diÔn vÊn ®Ò nµy b»ng 2 mÖnh ®Ò logic sau: -

[1]. NÕu … th× …;

-

[2]. NÕu … th× … ngîc l¹i th×…

§Ó m« pháng hai mÖnh ®Ò ®ã, trong ng«n ng÷ lËp tr×nh C++ ®a ra cÊu tróc rÏ nh¸nh. Có ph¸p: if () [else ;]

;

ý nghÜa: NÕu nhËn gi¸ trÞ ®óng (TRUE), sÏ thùc hiÖn , ngîc l¹i, nÕu nhËn gi¸ trÞ sai (FALSE) sÏ thùc hiÖn ; (nÕu cã thµnh phÇn [else ;]). - vµ cã thÓ lµ mét lÖnh, mét khèi lÖnh hoÆc mét, mét khèi c¸c cÊu tróc ®iÒu khiÓn. C¸c khèi lÖnh hoÆc khèi cÊu tróc ®iÒu khiÓn ®îc ®Æt trong hai dÊu { }. CÊu tróc rÏ nh¸nh cã hai d¹ng (tuú thuéc vµo sù cã hay kh«ng cã thµnh phÇn [else ;]) nh trong s¬ ®å khèi díi ®©y.



TRUE

TRUE



FALSE

FALSE







Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 7

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

a). M« t¶ mÖnh ®Ò [1] ®Ò [2]

b) M« t¶ mÖnh

VÝ dô: LËp ch¬ng tr×nh nhËp vµo mét sè nguyªn. KiÓm tra tÝnh ch½n lÎ cña sè ®ã vµ th«ng b¸o ra mµn h×nh. #include #include <stdio.h> #include void main() { clrscr(); int a; cout<< “nhËp sè nguyªn a ”; cin>>a; if (a%2 = = 0) cout<<”sè “<
C¸c lÖnh if cã thÓ lång nhau theo nghÜa: C¸c c©u lÖnh bªn trong mét mÖnh ®Ò if l¹i cã thÓ lµ c¸c mÖnh ®Ò if. Mçi lÖnh if ®Çy ®ñ sÏ cho phÐp lùa chän 2 kh¶ n¨ng ®Ó thùc hiÖn. Trong trêng hîp cã n kh¶ n¨ng lùa chän vµ c¸c kh¶ n¨ng lo¹i trõ nhau, ta cã thÓ sö dông n-1 lÖnh if ®Çy ®ñ lång nhau. VÝ dô: ViÕt ch¬ng tr×nh thùc hiÖn viÖc nhËp vµo sè tiÒn ph¶i tr¶ cña kh¸ch hµng. NÕu sè tiÒn nhËp vµo tõ 300 tíi 400, khuyÕn m¹i 20% sè tiÒn ph¶i tr¶. NÕu sè tiÒn tõ 400 trë lªn, khuyÕn m¹i 30%. C¸c trêng hîp kh¸c kh«ng ®îc khuyÕn m¹i. TÝnh vµ in sè tiÒn khuyÕn m¹i cña kh¸ch lªn mµn h×nh. #include #include <stdio.h> #include void main() { clrscr(); int T, km; cout<<”NhËp sè tiÒn “; cin>>T; if (T>=300 && T <=400) km = T*0.2; else if (T>400) km = T*0.3; Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 8

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü else km = 0; cout<<”Sè tiÒn khuyÕn m¹i “<
NÕu n kh¶ n¨ng lµ lo¹i trõ nhau th× khi ®ã cã thÓ sö dông n-1 lÖnh if lång nhau hoÆc cã thÓ sö dông n lÖnh if rêi nhau cho n kh¶ n¨ng lùa chän. Trêng hîp ngîc l¹i, ta nªn sö dông c¸c lÖnh if rêi nhau. VÝ dô: ViÕt ch¬ng tr×nh nhËp vµo ®iÓm tæng kÕt vµ xÕp lo¹i ®¹o ®øc cña mét sinh viªn. Sau ®ã tÝnh sè tiÒn häc bæng cho sinh viªn ®ã nh sau: NÕu tæng kÕt >=7.00 th× ®îc 300000. NÕu ®iÓm tæng kÕt >=9.00 vµ ®¹o ®øc = “T” th× ®îc céng thªm 100000.

XÐt ®o¹n tr×nh sau: #include #include <stdio.h> #include void main() { clrscr(); float tk; char hk; long T; cout<<”Nhap ®iÓm tong ket”; cin>>tk; cout<<”Nhap hanh kiem”; cin>>hk; T=0; if (tk >= 7) T = 300000; else if (tk>=9 && hk = = ‘T’) T += 100000; cout<<”Häc bæng ” <
§o¹n tr×nh trªn sÏ cho kÕt qu¶ sai trong trêng hîp sinh viªn tæng kÕt >=9.0 vµ ®¹o ®øc tèt. Lý do lµ sö dông hai lÖnh if lång nhau khi c¸c kh¶ n¨ng kh«ng lo¹i trõ nhau. §o¹n tr×nh trªn cã thÓ ®îc viÕt l¹i nh sau: #include #include <stdio.h> #include void main() { clrscr(); float tk; char hk; long T; Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 9

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü cout<<”Nhap ®iÓm tong ket”; cin>>tk; cout<<”Nhap hanh kiem”; cin>>hk; T=0; if (tk >= 7) T = 300000; if (tk>=9 && hk = = ‘T’) T += 100000; cout<<”Häc bæng ” <
I.2. CÊu tróc chän Trong trêng hîp cã qu¸ nhiÒu kh¶ n¨ng lùa chän vµ c¸c kh¶ n¨ng lo¹i trõ nhau, nÕu sö dông nhiÒu lÖnh if lång nhau sÏ lµm cho ch¬ng tr×nh phøc t¹p, khã kiÓm so¸t. V× vËy C++ cung cÊp mét cÊu tróc ®iÒu khiÓn kh¸c sö dông trong trêng hîp nµy, ®ã lµ cÊu tróc chän. Có ph¸p:

switch () { case : break; case : break; … case : break; [default: ;] }

ý nghÜa: KiÓm tra gi¸ trÞ cña : NÕu nhËn gi¸ trÞ , thùc hiÖn NÕu BiÕn = nhËn gi¸ trÞ , thùc hiÖn GT1 … NÕu nhËn gi¸ trÞ , thùc hiÖn BiÕn = GT2 NÕu cã thµnh phÇn [default: …], thùc hiÖn khi biÕn nguyªn kh«ng nhËn gi¸ trÞ nµo trong n gi¸ trÞ ë trªn.… S¬ ®å khèi: BiÕn = GTn Tµi liÖu gi¶ng d¹y- Lu hµnh néimÆc bé LÖnh Trang ®Þnh



2 0

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

- LÖnh switch chØ thùc hiÖn trªn biÕn nguyªn. C¸c c©u lÖnh , … cã thÓ lµ mét khèi lÖnh hoÆc khèi c¸c cÊu tróc ®iÒu khiÓn (tøc nhiÒu lÖnh, nhiÒu cÊu tróc ®iÒu khiÓn ®Æt gi÷a hai ký tù { vµ }). Sau ®ã ph¶i cã lÖnh break; nÕu kh«ng lÖnh switch sÏ ch¹y sai ý nghÜa cña nã. - Thµnh phÇn [default: …] lµ kh«ng b¾t buéc. NÕu cã thµnh phÇn nµy, sÏ ®îc ®îc thùc hiÖn sau khi tÊt c¶ c¸c trêng hîp case ®Òu kh«ng tháa m·n. VÝ dô 1: ViÕt ch¬ng tr×nh nhËp vµo m· häc vÞ (lµ mét sè nguyªn) cña mét nh©n viªn. In ra häc vÞ t¬ng øng víi quy ®Þnh: M· =1: Cö nh©n. M· =2: Kü s. M· =3: Th¹c sü. M· =4: TiÕn sü. C¸c m· kh¸c: Kh«ng xÕp lo¹i häc vÞ. void main() { clrscr(); int M; cout<<”NhËp m· häc vÞ”; cin>>M; switch (M) { case 1: cout<<”Cö nh©n”; break; case 2: cout<<”Kü s”; break; case 3: cout<<”Th¹c sü”; break; case 4: cout<<”TiÕn sü”; break; Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

2 1

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü default: } getch(); }

cout<<”Kh«ng xÕp lo¹i häc vÞ”;

VÝ dô 2: ViÕt ch¬ng tr×nh nhËp vµo mét th¸ng cña mét n¨m nµo ®ã. In sè ngµy cña th¸ng ®ã ra mµn h×nh. #include #include <stdio.h> #include void main(void) { clrscr(); int T, N; cout<<”NhËp th¸ng”; cin>>T; cout<<”NhËp n¨m “; cin>>N; switch (T) { case 1: case 3: case 5: case 7: case 8: case 10: case 12: cout<<”Th¸ng cã 31 ngµy”; break; case 4: case 6: case 9: case 11: cout<<”Th¸ng cã 30 ngµy”; break; case 2: if (N%4 = = 0) cout<<”Th¸ng cã 28 ngµy”; else cout<<”Th¸ng cã 29 ngµy”; break; } getch(); }

ChuyÓn ®æi gi÷a cÊu tróc chän vµ rÏ nh¸nh: Víi cÊu tróc rÏ nh¸nh, c¸c biÕn trong biÓu thøc ®iÒu kiÖn cã thÓ cã kiÓu bÊt kú. Ngîc l¹i, víi cÊu tróc chän, chØ lùa chän c¸c trêng hîp cña biÕn nguyªn. Do vËy, viÖc chuyÓn ®æi tõ cÊu tróc chän sang cÊu tróc rÏ nh¸nh bao giê còng thùc hiÖn ®îc mét c¸ch dÔ dµng, ®iÒu ngîc l¹i kh«ng ®óng. §Ó chuyÓn ®æi mét cÊu tróc rÏ nh¸nh mµ biÓu thøc ®iÒu kiÖn cã c¸c biÕn kh«ng ph¶i kiÓu nguyªn sang cÊu tróc chän cÇn sö dông thªm mét biÕn nguyªn ®Ó m· ho¸ c¸c trêng hîp cña nã, sau ®ã ta ¸p dông cÊu tróc chän trªn biÕn nguyªn nµy. II. CÊu tróc lÆp Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

2 2

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

II.1. Vßng lÆp víi sè lÇn lÆp x¸c ®Þnh Gi¶ sö cÇn thùc hiÖn mét vßng lÆp víi n lÇn lÆp. Trong Pascal ta thêng viÕt: For i:=1 to n do ; Khi thùc hiÖn lÖnh lÆp nµy, m¸y tÝnh ph¶i thùc hiÖn tuÇn tù c¸c c«ng viÖc sau: (1) G¸n i:=1; (2) KiÓm tra xem i ®· vît qu¸ n cha, tøc kiÓm tra gi¸ trÞ cña biÓu thøc: i<=n; vµ (3) T¨ng gi¸ trÞ cña i lªn 1 ®¬n vÞ sau mçi lÇn lÆp: i:=i+1; Nh vËy, dÔ thÊy m¸y tÝnh cÇn thùc hiÖn 3 biÓu thøc cña vßng lÆp: i:=1; i<=n; i:=i+1;. Mçi vßng lÆp, bao giê còng ph¶i x¸c ®Þnh cho ®îc 3 biÓu thøc nµy. Ta t¹m gäi chóng lµ c¸c biÓu thøc , , . Trong C++, vßng lÆp x¸c ®Þnh còng ®îc x¸c ®Þnh b»ng 3 biÓu thøc d¹ng nh trªn. Có ph¸p nh sau: for (; ; ;

Trong ®ã, thêng nhËn nhiÖm vô khëi g¸n gi¸ trÞ ban ®Çu cho biÕn ch¹y; lµ mét biÓu thøc logic ®îc dïng lµm ®iÒu kiÖn dõng cho vßng lÆp. Vßng lÆp sÏ dõng khi nhËn gi¸ trÞ sai (FALSE); ®îc dïng ®Ó thay ®æi gi¸ trÞ cña biÕn ch¹y sau mçi lÇn lÆp. cã thÓ lµ mét lÖnh, mét khèi lÖnh hoÆc mét, mét khèi c¸c cÊu tróc ®iÒu khiÓn. ý nghÜa: B1: Thùc hiÖn B2: KiÓm tra . NÕu sai, tho¸t khái vßng for. Ngîc l¹i, sang B3. B3: Thùc hiÖn , thùc hiÖn , quay l¹i B2.

S¬ ®å khèi:



Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé FALSE Trang

TRUE



2 3

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

C¸c trêng hîp ®Æc biÖt cña vßng lÆp for • Trêng hîp 1: C¸c biÓu thøc , , cã thÓ khuyÕt nhng c¸c dÊu “;” ph¶i ®îc gi÷ nguyªn.

VÝ dô: ViÕt ch¬ng tr×nh tÝnh n! (n nguyªn) C¸ch 1: Sö dông vßng lÆp for th«ng thêng void main() { clrscr(); int n; long GT=1; cout<<”Nhap n “; cin>>n; for (int i=2;i<=n; i++) GT*=i; cout<
C¸ch 2: Vßng for khuyÕt . void main() { clrscr(); int n; long GT=1; cout<<”Nhap n “; cin>>n; int i=2; for (;i<=n; i++) GT*=i; cout<
C¸ch 3: Vßng for khuyÕt vµ void main() { clrscr(); int n; long GT=1; cout<<”Nhap n “; cin>>n; int i=2; for (;i<=n; ) { GT*=i; i++; } cout<
2 4

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü getch(); }

C¸ch 4: Vßng for khuyÕt c¶ 3 biÓu thøc. Trong trêng hîp nµy, vßng for kh«ng thÓ dõng mét c¸ch tù nhiªn ®îc (do thiÕu ®iÒu kiÖn dõng lµ ). Khi ®ã ta cÇn tho¸t khái vßng lÆp mét c¸ch cã chñ ®Þnh. C¸c c¸ch tho¸t khái vßng lÆp for khi thiÕu + C¸ch 1: sö dông lÖnh break; Khi gÆp lÖnh break; trong th©n vßng for, ch¬ng tr×nh sÏ lËp tøc tho¸t khái vßng lÆp for vµ chuyÓn tíi lÖnh tiÕp theo bÊt kÓ vÉn nhËn gi¸ trÞ ®óng hoÆc khuyÕt . + C¸ch 2: sö dông lÖnh goto; LÖnh goto cã d¹ng: goto ; . Trong ®ã, cã d¹ng: :

tuú ý ®Æt theo quy íc ®Æt tªn trong C. Khi gÆp lÖnh goto ;, ch¬ng tr×nh sÏ nh¶y tíi vÞ trÝ ®Æt nh·n. NÕu nh·n ®Æt ngoµi vßng for, ch¬ng tr×nh sÏ tho¸t khái vßng for. CÇn chó ý trong trêng hîp 2 lÖnh for lång nhau, khi ®ã lÖnh break chØ lµm cho ch¬ng tr×nh tho¸t khái vßng for gÇn nhÊt chøa lÖnh break. Do vËy, ®Ó tho¸t khái c¶ 2 vßng for lång nhau, ta cã thÓ sö dông lÖnh goto. Tho¸t khái for sö dông break: void main() { clrscr(); int n; long GT=1; cout<<”Nhap n “; cin>>n; int i=2; for (;;) { if (i==n) break; GT*=i; i++; } Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

2 5

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü cout<
Tho¸t khái for, sö dông goto: void main() { clrscr(); int n; long GT=1; cout<<”Nhap n “; cin>>n; int i=2; for (;;) { if (i==n) goto Ex; // nh·n lµ Ex, tªn tù ®Æt. GT*=i; i++; } Ex: cout<
V× ®é “r¾c rèi” cña ch¬ng tr×nh (®èi víi ch¬ng tr×nh dÞch) tû lÖ thuËn víi sè lÖnh goto sö dông trong ch¬ng tr×nh, v× vËy nªn h¹n chÕ sö dông goto. • Trêng hîp 2: C¸c , cã thÓ lµ c¸c biÓu thøc phøc hîp (tøc lµ gåm nhiÒu biÓu thøc con). Khi ®ã, c¸c biÓu thøc con ®îc ®Æt c¸ch nhau bëi dÊu ph¶y.

VÝ dô 2: Cho d·y sè nguyªn x[] = { 1, 4, 5, 7, 3, 2}. ViÕt ch¬ng tr×nh ®¶o ngîc d·y sè trªn vµ in kÕt qu¶ lªn mµn h×nh. §Ó gi¶i quyÕt bµi to¸n trªn, cã thÓ cã nhiÒu c¸ch. C¸ch gi¶i sau minh ho¹ c¸ch viÕt kh¸c cña vßng for víi vµ lµ c¸c biÓu thøc phøc hîp. #include "conio.h" #include "iostream.h" #include "stdio.h" void main() { clrscr(); int x[ ] = {1, 4, 5, 7, 3, 2}, n; n=sizeof(x)/ sizeof(int); //n lµ sè phÇn tö cña x (6) Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

2 6

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü for (int i=0, j=n-1; i
ThËm chÝ, cã thÓ viÕt l¹i lêi gi¶i trªn b»ng c¸ch sö dông vßng for víi c¸c lÖnh th©n vßng for ®îc ®a vµo nh sau: void main() { clrscr(); int x[ ] = {1, 4, 5, 7, 3, 2}, n; n=sizeof(x)/ sizeof(int); int tg; for (int i=0, j=n-1; i
II.2. Vßng lÆp víi sè lÇn lÆp kh«ng x¸c ®Þnh Trong C++, ta chia vßng lÆp víi sè lÇn lÆp kh«ng x¸c ®Þnh ra lµm hai lo¹i: a. LÆp kiÓm tra ®iÒu kiÖn tríc: Tríc tiªn, kiÓm tra biÓu thøc ®iÒu kiÖn. NÕu biÓu thøc ®iÒu kiÖn cßn ®óng, sÏ thùc hiÖn lÖnh lÆp. NÕu biÓu thøc ®iÒu kiÖn sai, ra khái vßng lÆp. S¬ ®å khèi:



TRUE

;

FALSE

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

2 7

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Nh vËy: LÖnh lÆp cã thÓ kh«ng ®îc thùc hiÖn lÇn nµo nÕu sai ngay tõ ®Çu hoÆc còng cã thÓ lÆp v« h¹n nÕu lu«n ®óng. Có ph¸p: while () ;

- cã thÓ lµ mét lÖnh, mét khèi lÖnh hoÆc mét, mét khèi cÊu tróc ®iÒu khiÓn. ý nghÜa: B1: KiÓm tra biÓu thøc ®iÒu kiÖn . NÕu biÓu thøc ®iÒu kiÖn sai, tho¸t ra khái vßng lÆp. NÕu biÓu thøc ®iÒu kiÖn ®óng, chuyÓn qua bíc 2. B2: Thùc hiÖn . Quay l¹i B1. VÝ dô 1. ViÕt ch¬ng tr×nh t×m sè lòy thõa 2 ®Çu tiªn lín h¬n 1000. #include #include <stdio.h> #include void main() { clrscr(); int So=2; while (So <=1000) So *=2; cout<<”Sè cÇn t×m lµ ”<<So; getch(); }

VÝ dô 2. ViÕt ch¬ng tr×nh nhËp vµo ®iÓm ®¹o ®øc cña mét häc sinh (thang ®iÓm 100, nguyªn) vµ sè ngµy ®i häc muén cña häc sinh ®ã. NÕu häc sinh ®i häc muén 1 ngµy, trõ 1 ®iÓm. TÝnh vµ in sè ®iÓm cßn l¹i cña häc sinh. #include #include <stdio.h> #include void main() { clrscr(); int D, HM; cout<<”NhËp ®iÓm ®¹o ®øc”;

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

cin>>D;

2 8

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü cout<<”NhËp

sè

ngµy

®i

häc

muén”;

cin>>HM; while (HM>0) { D - -; HM - -; } cout<<”§iÓm cßn l¹i “<
b. LÆp kiÓm tra ®iÒu kiÖn sau: T¬ng tù nh vßng lÆp kiÓm tra ®iÒu kiÖn tríc, chØ kh¸c ë chç biÓu thøc ®iÒu kiÖn ®îc kiÓm tra mçi khi ®· thùc hiÖn lÖnh lÆp. Nh vËy, lÖnh lÆp lu«n ®îc thùc hiÖn Ýt nhÊt mét lÇn. S¬ ®å khèi:

;



TRUE

FALSE

Có ph¸p: do ; while ();

- cã thÓ lµ mét lÖnh, mét khèi lÖnh hoÆc mét, mét khèi cÊu tróc ®iÒu khiÓn. ý nghÜa: B1: Thùc hiÖn ; B2: KiÓm tra biÓu thøc ®iÒu kiÖn . NÕu biÓu thøc ®iÒu kiÖn sai, tho¸t ra khái vßng lÆp. NÕu biÓu thøc ®iÒu kiÖn ®óng, chuyÓn qua bíc 1. VÝ dô 1: ViÕt ch¬ng tr×nh t×m sè nguyªn x ®Çu tiªn lín h¬n 5 mµ tháa m·n sin(x) = 1 Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

2 9

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

void main() { clrscr(); int x=0; do x +=1; while (x <=5 | | sin(x) !=1); cout<<”Sè cÇn t×m lµ ”<<x; getch(); }

VÝ dô 2: ViÕt ch¬ng tr×nh nhËp vµo mét sè nguyªn x. KiÓm tra xem sè ®ã ®· lín h¬n 10 hay cha. NÕu cha, yªu cÇu nhËp l¹i cho tíi khi sè nhËp vµo lín h¬n 10. KiÓm tra xem sè ®ã cã ph¶i lµ sè nguyªn tè kh«ng, in kÕt luËn lªn mµn h×nh. void main() { clrscr(); int So; do { cout<<”NhËp mét sè nguyªn “; cin>>So; if (So <=10) cout<<”Sè kh«ng tháa m·n. NhËp l¹i : “; } while (So <=10); //KiÓm tra xem So cã ph¶i lµ sè nguyªn tè kh«ng

int kt=0; int d =2; do { if (So % d ==0) kt = 1; d++; } while (d<So); if (kt==0) cout<<”Sè “<<So<<” Lµ sè nguyªn tè”; else cout<<”Sè “<<So<<” Kh«ng lµ sè nguyªn tè”; getch(); }

§Ó tho¸t khái vßng lÆp kh«ng x¸c ®Þnh, ta còng cã thÓ sö dông break hoÆc goto. Tuy nhiªn, c¸c trêng hîp nµy Ýt x¶y ra do ®Æc thï cña vßng lÆp. ChuyÓn ®æi gi÷a c¸c cÊu tróc lÆp: Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

3 0

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Tõ vßng lÆp x¸c ®Þnh (for), ta cã thÓ chuyÓn sang vßng lÆp kh«ng x¸c ®Þnh (while hoÆc do/ while) b»ng c¸ch sö dông thªm mét biÕn ®Õm kiÓu nguyªn trong th©n vßng lÆp kh«ng x¸c ®Þnh. Tríc khi lÆp ta khëi g¸n gi¸ trÞ cña biÕn ®Õm nµy b»ng 0. Mçi khi thùc hiÖn mét lÇn lÆp, ta t¨ng gi¸ trÞ cña biÕn ®Õm nµy lªn 1. §iÒu kiÖn dõng lµ khi sè lÇn lÆp ®· ®ñ. §Ó chuyÓn ®æi ngîc l¹i (tõ cÊu tróc lÆp kh«ng x¸c ®Þnh sang cÊu tróc lÆp x¸c ®Þnh) th× nãi chung, ta ph¶i sö dông c¸c vßng for khuyÕt biÓu thøc 2, díi d¹ng: for ( ; ; )

bëi v× ta kh«ng biÕt ch¾c sè lÇn lÆp cña cÊu tróc. Khi ®ã ta ph¶i sö dông lÖnh break hoÆc goto trong th©n vßng for ®Ó tho¸t cìng bøc. II.3. C¸c vÝ dô minh ho¹ sö dông vßng lÆp VÝ dô 1. ViÕt ch¬ng tr×nh nhËp vµo mét sè nguyªn n, sau ®ã tÝnh tæng c¸c sè nguyªn tè thuéc ®o¹n [1..n]. Cho biÕt cã bao nhiªu sè nguyªn tè thuéc ®o¹n trªn? void main() { clrscr(); int n, Tong, Dem; cout<<”NhËp sè nguyªn”; cin>>n; Tong =Dem=0; for (int i=1; i<=n; i++) { int Check = 0; for (int j=2; j< i; j++) if (i%j==0) Check = 1; if (Check ==0) { Tong +=i; Dem++; } } cout<<”Tæng c¸c sè nguyªn tè “<
Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

3 1

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

VÝ dô 2. ViÕt ch¬ng tr×nh nhËp vµo mét sè nguyªn n vµ mét sè thùc x, sau ®ã tÝnh gi¸ trÞ biÓu thøc: 2 3 n  x + x + x2 + .. + xn−1 NÕunch½n F=  3 3 3  0 NÕu nlÎ

void main() { clrscr(); int n; float x, F, ts, ms; cout<<”NhËp x”; cin>>x; cout<<”NhËp n”; cin>>n; F=0; if (n%2==0) { F=x; ts=x; ms=1; for(int i=1; i<=n; i++) { ts*=x; ms*=3; F+=ts/ms; } } cout<<”Gi¸ trÞ cña biÓu thøc “<
Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

3 2

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Ch¬ng III. Kü thuËt lËp tr×nh ®¬n thÓ I. §¬n thÓ vµ lËp tr×nh ®¬n thÓ

I.1. Kh¸i niÖm vµ ph©n lo¹i ®¬n thÓ Khi viÕt mét ch¬ng tr×nh, chóng ta cã thÓ triÓn khai theo hai c¸ch: C¸ch 1: Toµn bé c¸c lÖnh cña ch¬ng tr×nh ®îc viÕt trong hµm main. C¸c lÖnh ®îc viÕt theo tr×nh tù ®Ó gi¶i quyÕt bµi to¸n ®Æt ra. C¸ch 2: Ch¬ng tr×nh ®îc chia nhá thµnh c¸c ®¬n vÞ ch¬ng tr×nh t¬ng ®èi ®éc lËp gäi lµ ®¬n thÓ. C¸c ®¬n thÓ thùc hiÖn nh÷ng nhiÖm vô nhÊt ®Þnh vµ ®îc sö dông trong ch¬ng tr×nh th«ng qua nh÷ng lêi gäi ®¬n thÓ trong hµm main. u nhîc ®iÓm: - Víi c¸ch 1: sÏ thÝch hîp khi viÕt nh÷ng ch¬ng tr×nh cã kÝch thíc nhá. Toµn bé bµi to¸n, thuËt to¸n ®îc thÓ hiÖn trong mét ®o¹n m· tuÇn tù tõ trªn xuèng. Tuy nhiªn, c¸ch nµy kh«ng phï hîp víi c¸c ch¬ng tr×nh lín do: + KÝch thíc ch¬ng tr×nh cång kÒnh, khã kiÓm so¸t, chØnh söa. + C¸c ®o¹n m· cã thÓ lÆp ®i lÆp l¹i, kh«ng sö dông l¹i m· lÖnh. + Khã kh¨n trong viÖc tæ chøc lµm viÖc nhãm…

- Víi c¸ch 2: Ch¬ng tr×nh ®îc chia nhá thµnh c¸c ®¬n thÓ kh¾c phôc ®îc hai nhîc ®iÓm c¬ b¶n trªn. §Æc biÖt phï hîp víi c¸c ch¬ng tr×nh cã kÝch thíc lín vµ phøc t¹p. Ph©n lo¹i ®¬n thÓ: Trong C++, ®¬n thÓ cã thÓ lµ: [1]. C¸c líp ®èi tîng: Ch¬ng tr×nh bao gåm mét sè ®o¹n m· m« t¶ c¸c líp c¸c ®èi tîng nµo ®ã sÏ sö dông trong ch¬ng tr×nh chÝnh. Lo¹i ®¬n thÓ nµy ®îc nghiªn cøu trong néi dung m«n häc “LËp tr×nh híng ®èi tîng”. [2]. C¸c hµm: Ch¬ng tr×nh ®îc cÊu t¹o tõ c¸c hµm. Mçi hµm thùc thi mét nhiÖm vô t¬ng ®èi ®éc lËp, trong ®ã cã mét hµm main ®ãng vai trß nh ch¬ng tr×nh chÝnh ®Ó sö dông c¸c hµm kh¸c. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

3 3

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Trong ph¹m vi m«n häc, ta chØ xem xÐt c¸c ®¬n thÓ díi d¹ng c¸c hµm. C¸c ®Æc trng cña hµm: - Tªn hµm: do ngêi lËp tr×nh tù ®Æt vµ cã nh÷ng ®Æc ®iÓm sau: + Tªn hµm thêng mang tÝnh ®¹i diÖn cho c«ng viÖc mµ hµm sÏ ®¶m nhiÖm. + Tªn hµm ®îc ®Æt theo quy íc ®Æt tªn trong C++ (xem quy íc ®Æt tªn biÕn).

- KiÓu gi¸ trÞ tr¶ vÒ cña hµm: NÕu hµm tr¶ vÒ mét gi¸ trÞ th× gi¸ trÞ ®ã ®îc g¸n vµo tªn hµm vµ nã ph¶i thuéc mét kiÓu d÷ liÖu nµo ®ã mµ ta gäi lµ kiÓu gi¸ trÞ tr¶ vÒ cña hµm. KiÓu gi¸ trÞ tr¶ vÒ cña hµm cã thÓ lµ c¸c kiÓu d÷ liÖu chuÈn hoÆc mét kiÓu do ngêi lËp tr×nh tù ®Þnh nghÜa. - KiÓu vµ tªn c¸c ®èi cña hµm: NÕu hµm sö dông c¸c ®èi (c¸c gi¸ trÞ ®Çu vµo) th× c¸c ®èi ph¶i thuéc mét kiÓu d÷ liÖu nµo ®ã. Khi thiÕt lËp mét hµm, ta cÇn chØ ra danh s¸ch c¸c ®èi cña hµm vµ kiÓu d÷ liÖu cña mçi ®èi. - Th©n hµm: lµ néi dung chÝnh cña hµm, chøa toµn bé c¸c lÖnh cña hµm. Ph©n lo¹i hµm Trong pascal, ta cã hai lo¹i ch¬ng tr×nh con: thñ tôc (procedure) vµ hµm (function). Trong C++, chóng ta cã duy nhÊt mét lo¹i “ch¬ng tr×nh con” (mµ ta gäi lµ ®¬n thÓ), ®ã lµ hµm. Mét ch¬ng tr×nh trong C++ ®îc cÊu t¹o tõ c¸c hµm, trong ®ã hµm main lµ hµm b¾t buéc ph¶i cã, ®ãng vai trß nh ch¬ng tr×nh chÝnh. NÕu trong Pascal, tÊt c¶ c¸c hµm ®Òu tr¶ vÒ mét gi¸ trÞ nµo ®ã th× trong C++ c¸c hµm ®îc chia lµm hai lo¹i: - Hµm kh«ng cã gi¸ trÞ tr¶ vÒ: Lµ hµm chØ cã chøc n¨ng thùc hiÖn mét c«ng viÖc nµo ®ã mµ ta kh«ng quan t©m tíi gi¸ trÞ tr¶ vÒ cña hµm. Nã t¬ng ®íng víi thñ tôc trong Pascal. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

3 4

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

- Hµm cã gi¸ trÞ tr¶ vÒ: Ngoµi viÖc thùc hiÖn mét c«ng viÖc nµo ®ã, ta cßn quan t©m tíi gi¸ trÞ thu ®îc sau khi hµm thùc thi ®Ó dïng trong nh÷ng ®o¹n tr×nh tiÕp theo. Tïy theo nguån gèc cña hµm ngêi ta ph©n ra: - C¸c hµm cã s½n: Lµ c¸c hµm chøa trong c¸c th viÖn cña C++, lµ c¸c file cã phÇn më réng lµ .h, ®· ®îc ®Þnh nghÜa tõ tríc. Ngêi lËp tr×nh chØ viÖc sö dông th«ng qua c¸c chØ thÞ: #include . - C¸c hµm tù ®Þnh nghÜa: Lµ c¸c hµm do ngêi lËp tr×nh tù ®Þnh nghÜa. C¸c hµm nµy còng cã thÓ ®îc tËp hîp l¹i trong mét file .h ®Ó dïng nh mét th viÖn cã s½n. I.2. §Þnh nghÜa vµ sö dông hµm • §Þnh nghÜa hµm Mét hµm thêng cã cÊu tróc nh sau: ([kiÓu ®èi] [tªn ®èi]) { C¸c lÖnh trong th©n hµm; }

Trong ®ã: - : lµ kiÓu cña gi¸ trÞ tr¶ vÒ cña hµm. NÕu hµm kh«ng cã gi¸ trÞ tr¶ vÒ, ta dïng kiÓu tr¶ vÒ lµ void. Ngîc l¹i, ta thêng sö dông c¸c kiÓu chuÈn nh int, float, double, char… - : do ngêi dïng tù ®Þnh nghÜa theo quy íc ®Æt tªn biÕn. - ([kiÓu ®èi] [tªn ®èi]): liÖt kª danh s¸ch c¸c ®èi cña hµm vµ kiÓu d÷ liÖu cña ®èi (nÕu cã). NÕu hµm cã nhiÒu ®èi th× c¸c ®èi c¸ch nhau bëi dÊu ph¶y. Mét nguyªn t¾c trong C+ + lµ mçi ®èi ®Òu ph¶i cã mét kiÓu ®i kÌm tríc tªn ®èi. VÝ dô 1: Hµm tÝnh n! ®¬n gi¶n ®îc viÕt nh sau: long GT(int n) { long kq=1; Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

3 5

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü for (int i=1; i<=n; i++) kq *=i; return kq; }

- NÕu hµm cã gi¸ trÞ tr¶ vÒ th× cÇn cã c©u lÖnh return ; ®Ó g¸n gi¸ trÞ nµy vµo tªn hµm. TuyÖt ®èi kh«ng ®îc g¸n = ;. cã thÓ lµ mét biÓu thøc, mét biÕn hoÆc mét h»ng. NÕu kh«ng cã lÖnh return nµy, ch¬ng tr×nh sÏ b¸o lçi. return.

Nh vËy, riªng hµm void (kiÓu tr¶ vÒ lµ void) sÏ kh«ng cã lÖnh

VÝ dô 2. ViÕt hµm gi¶i ph¬ng tr×nh bËc nhÊt víi ®èi vµo lµ hai hÖ sè a, b. void PTBN(float a, float b) { if (a==0 && b==0) cout<<”Ph¬ng tr×nh v« sè nghiÖm”; else if (a==0 && b!=0) cout<<”ph¬ng tr×nh v« nghiÖm”; else cout<<”Ph¬ng tr×nh cã nghiÖm “<<-b/a; }

•

Sö dông hµm

Hµm ®îc sö dông th«ng qua lêi gäi cña nã. Th«ng thêng, chóng ®îc sö dông trong hµm main ®Ó gi¶i quyÕt bµi to¸n ®Æt ra. Tuy nhiªn, vÒ nguyªn t¾c mét hµm bÊt kú ®Òu cã thÓ gäi tíi c¸c hµm kh¸c, miÔn lµ c¸c hµm ®ã ®· ®îc ®Þnh nghÜa tríc. Khi gäi hµm, ta gäi tíi tªn hµm. NÕu hµm cã ®èi sè, ta ph¶i truyÒn c¸c tham sè phï hîp vÒ kiÓu vµo vÞ trÝ c¸c ®èi sè nµy. Sè lîng tham sè truyÒn vµo khi gäi hµm ph¶i b»ng sè lîng c¸c ®èi sè vµ theo ®óng thø tù khi ta ®Þnh nghÜa hµm. C¸ch viÕt mét lêi gäi hµm nh sau: <([danh s¸ch c¸c tham sè thùc sù])>

Nh vËy: Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

3 6

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

- C¸c tham sè ph¶i cã kiÓu trïng víi kiÓu cña ®èi sè t¬ng øng. - NÕu hµm kh«ng cã ®èi sè th× lêi gäi hµm vÉn ph¶i sö dông dÊu () kÌm tªn hµm: (). Tuy nhiªn, v× hµm cã 2 lo¹i: cã vµ kh«ng cã gi¸ trÞ tr¶ vÒ nªn c¸ch sö dông hai lo¹i hµm nµy còng kh¸c nhau. - NÕu hµm cã gi¸ trÞ tr¶ vÒ th× tªn hµm ®îc sö dông nh mét biÕn, tøc lµ ta kh«ng thÓ sö dông hµm mét c¸ch ®éc lËp mµ lêi gäi hµm cã thÓ ®îc ®Æt ë vÕ ph¶i cña phÐp g¸n, trong biÓu thøc hoÆc kÌm víi mét lÖnh kh¸c.

- Ngîc l¹i, nÕu hµm kh«ng cã gi¸ trÞ tr¶ vÒ, tªn hµm ®îc sö dông nh mét lÖnh, tøc lµ lêi gäi hµm ®îc viÕt ®éc lËp, kh«ng viÕt trong phÐp g¸n, trong biÓu thøc hay kÌm víi mét c©u lÖnh kh¸c.

VÝ dô: Hµm tÝnh n! ®îc viÕt ë 2 d¹ng: cã vµ kh«ng cã gi¸ trÞ tr¶ vÒ: long GT(int n) { long kq=1; for (int i=1; i<=n; i+ +) kq *=i; return kq; }

void GT(int n) { long kq=1; for (int i=1; i<=n; i+ +) kq *=i; cout<< “KÕt qu¶:”<
Cã thÓ nhËn thÊy 2 ®iÓm kh¸c biÖt cña hai c¸ch viÕt cho cïng mét hµm. Tuy nhiªn, ta quan t©m tíi sù kh¸c nhau trong c¸ch gäi (sö dông) hai hµm trªn. ë hµm thø nhÊt, do lµ hµm cã gi¸ trÞ tr¶ vÒ nªn nã ®îc sö dông nh mét biÕn. Gi¶ sö ta cÇn tÝnh 5!, vËy ta cã thÓ gäi hµm nµy theo c¸c c¸ch nh b¶ng sau: C¸ch gäi sai GT(5);

C¸ch gäi ®óng

ý nghÜa

b = GT(5);

T¹i vÕ ph¶i cña phÐp g¸n

cout<< GT(5);

Dïng kÌm víi lÖnh cout

b = GT(5) + 1;

Dïng trong biÓu thøc

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

3 7

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Tuy nhiªn, ë hµm thø 2 th× c¸ch sö dông ngîc l¹i

C¸ch gäi sai b = GT(5);

C¸ch gäi ®óng GT(5);

cout<< GT(5); b = GT(5) + 1;

I.3. Tæ chøc c¸c hµm Khi mét ch¬ng tr×nh cã nhiÒu hµm, ta quan t©m tíi viÖc tæ chøc chóng nh thÕ nµo cho khoa häc. Th«ng thêng cã 2 c¸ch tæ chøc c¸c hµm: C¸ch 1: c¸c hµm ®Æt trong cïng mét tÖp víi ch¬ng tr×nh chÝnh. Ch¬ng tr×nh ngoµi hµm main cßn cã c¸c hµm kh¸c th× c¸c hµm cã thÓ ®Æt tríc hoÆc sau hµm main ®Òu ®îc: C¸c hµm ®Æt tríc hµm main: #include… … … void main() { Th©n hµm main; }

C¸c hµm ®Æt sau hµm main: #include… … ; ; … void main() { Th©n hµm main; } … Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

3 8

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Trong ®ã, chÝnh lµ dßng ®Çu tiªn cña hµm cã kÌm theo dÊu chÊm ph¶y ‘;’. Nguyªn mÉu cña hµm cã d¹ng: ([KiÓu ®èi] [Tªn ®èi]);

Nh vËy, nÕu hµm ®îc ®Æt sau hµm main th× cÇn khai b¸o nguyªn mÉu cña hµm tríc hµm main ®Ó ch¬ng tr×nh dÞch cã thÓ biÕt tríc sù tån t¹i cña chóng khi dÞch hµm main. C¸c hµm lu«n ®Æt rêi nhau. Mét hµm kh«ng bao giê ®îc phÐp ®Æt trong mét hµm kh¸c. VÝ dô 1. ViÕt ch¬ng tr×nh kiÓm tra mét sè nguyªn n cã ph¶i lµ sè nguyªn tè kh«ng, nÕu n lµ sè nguyªn tè, h·y tÝnh n!. Ch¬ng tr×nh ®îc chia lµm hai hµm: hµm kiÓm tra xem n cã ph¶i sè nguyªn tè kh«ng vµ hµm tÝnh n!. Mét hµm main sö dông hai hµm trªn ®Ó gi¶i quyÕt bµi to¸n. Hai hµm ®Æt tríc hµm main: int NT(int n) { if (n ==1 | | n ==2) return =1; else {Check =0; for (int i=2; i>a; if (NT(a) == 0) cout<<”Sè “<
3 9

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü cout<<”Sè “<
lµ

“<
Hai hµm ®Æt sau hµm main: //Khai b¸o nguyªn mÉu cña hµm: int NT(int n); long GT(int n); //hµm main---------------------------void main() { int a; cout<<”NhËp a”; cin rel="nofollow">>a; if (NT(a) == 0) cout<<”Sè “<
lµ

“<
C¸ch 2: C¸c hµm ®Æt trong tÖp th viÖn:

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

4 0

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

B1: ViÕt c¸c hµm (trõ hµm main() )trong mét file sau ®ã lu díi ®Þnh d¹ng .h. File nµy thêng ®îc gäi lµ file th viÖn (hoÆc header file). (®Ó thuËn tiÖn cho viÖc so¸t lçi, tèt nhÊt tríc tiªn nªn tæ chøc c¸c hµm nh c¸ch 1, sau khi ®¶m b¶o c¸c hµm ch¹y tèt, di chuyÓn toµn bé c¸c hµm (trõ hµm main()) sang mét file míi vµ lu l¹i víi ®u«i .h) B2: ViÕt hµm main() trong mét tÖp riªng. §Ó hµm main() cã thÓ sö dông c¸c hµm viÕt trong file th viÖn ®· t¹o trong B1, cÇn thªm chØ thÞ: #include <[ ®êng dÉn] “Tªn th viÖn.h” rel="nofollow">

NÕu ®Æt th viÖn trªn trong th môc TC\ Include th× trong chØ thÞ #include kh«ng cÇn thªm ®êng dÉn. Ngîc l¹i, cÇn thªm ®Çy ®ñ ®êng dÉn tíi file th viÖn nãi trªn. VÝ dô: T¹o file .h víi néi dông sau, (vÝ dô file “TV.h”): int NT(int n) { if (n ==1 | | n ==2) return =1; else {Check =0; for (int i=2; i
Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

4 1

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Gi¶ sö file TV.h nµy ®îc ®Æt trong th môc C:\TC\BIN. Ta më mét file míi vµ viÕt hµm main() nh sau: #include #include <stdio.h> #include #include “C:\TC\BIN\ TV.h” void main() { int a; cout<<”NhËp a”; cin>>a; if (NT(a) == 0) cout<<”Sè “<
lµ

“<
- C¸c file th viÖn .h kh«ng cÇn ph¶i cã c¸c chØ thÞ tiÒn xö lý #include … - Kh«ng thÓ so¸t lçi b»ng c¸ch bÊm F9 trong file th viÖn .h. I. 4. Ph¹m vi ho¹t ®éng cña biÕn Theo ph¹m vi ho¹t ®éng cña biÕn, ta chia ra: - BiÕn toµn côc: (global) Lµ c¸c biÕn cã ph¹m vi ho¹t ®éng trong toµn bé ch¬ng tr×nh, kÓ tõ vÞ trÝ khai b¸o biÕn. BiÕn toµn côc cã vÞ trÝ khai b¸o n»m ngoµi c¸c hµm (kÓ c¶ hµm main). Th«ng thêng nã ®îc khai b¸o ngay tõ nh÷ng dßng ®Çu tiªn cña ch¬ng tr×nh (sau c¸c chØ thÞ tiÒn xö lý). NÕu ch¬ng tr×nh ®îc viÕt trªn nhiÒu tÖp, ®Ó ph¹m vi ho¹t ®éng cña biÕn bao gåm c¶ c¸c tÖp kh¸c, ta cÇn thªm chØ danh extern vµo tríc khai b¸o biÕn toµn côc. Trong trêng hîp nµy, tõ kho¸ extern cßn ®îc ®Æt tríc c¸c nguyªn mÉu cña hµm víi ý nghÜa t¬ng tù.

- BiÕn côc bé: (private) lµ c¸c biÕn ®îc khai b¸o trong th©n mét hµm, thËm trÝ trong mét khèi lÖnh nµo ®ã cña th©n hµm. Ph¹m vi ho¹t ®éng: NÕu biÕn ®îc khai b¸o trong th©n mét khèi nµo ®ã sÏ cã ph¹m vi ho¹t ®éng chØ trong khèi, kÓ Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé 4 Trang 2

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

c¶ c¸c khèi con n»m bªn trong khèi ®ã. KÕt thóc khèi, biÕn côc bé sÏ ®îc gi¶i phãng. Muèn biÕn nµy tån t¹i trong suèt thêi gian ch¬ng tr×nh lµm viÖc, ta cÇn thªm tõ khãa static tríc khai b¸o biÕn ®Ó khai b¸o biÕn díi d¹ng biÕn tÜnh.

VÝ dô: int x; void Ham(int a) { cout<<”BiÕn x trong hµm “<<x; if (a%2==0) { int x=5; x+=a; cout<<”BiÕn x trong hµm “<< x;} } void main() { x=1; int a = 2; Ham(a); cout<< “BiÕn x trong hµm main “<<x; int x = 3; cout<<”BiÕn x trong hµm main “<<x; getch(); }

- BiÕn x díi d¹ng toµn côc cã ph¹m vi ho¹t ®éng trong toµn bé ch¬ng tr×nh, kÓ tõ khi khai b¸o. - NÕu trong mét khèi cã khai b¸o biÕn côc bé trïng tªn víi biÕn toµn côc th× kÓ tõ khi khai b¸o, khèi ®ã sÏ sö dông biÕn côc bé mµ kh«ng sö dông biÕn toµn côc. II. Kü thuËt ®Ö quy

II.1. Kh¸i niÖm vÒ ®Ö quy Trong C++, mét hµm cã thÓ gäi ®Õn chÝnh nã, tÝnh chÊt nµy cña hµm gäi lµ tÝnh ®Ö quy. Khi mét hµm thÓ hiÖn tÝnh ®Ö quy, ta gäi hµm ®ã lµ hµm ®Ö quy. VÝ dô: XÐt hµm tÝnh n!. Ngoµi c¸ch viÕt sö dông vßng lÆp nh trªn, ta cã thÓ cã c¸ch tiÕp cËn kh¸c ®Ó gi¶i quyÕt bµi to¸n: Ta ®Þnh nghÜa: n! = (n-1)! * n. Víi ®Þnh nghÜa nµy, gi¶ sö n=5 th× n! ®îc tÝnh nh sau: Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

4 3

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

5!

Kü

= = = =

4! 3! 2! 1!

* * * *

5 4 * 5. 3 * 4 * 5. 2 * 3 * 4 * 5.

Víi 1! = 1, ta hoµn toµn cã thÓ tÝnh ®îc 5! b»ng c¸ch tÝnh c¸c gi¸ trÞ 2!, 3!, 4! ®Ó råi thay vµo c«ng thøc 5!= 4! *5. Mét c¸ch tæng qu¸t, nÕu ta cã hµm GT(n) ®Ó tÝnh n! th× GT(n) = GT(n-1) * n. §©y chÝnh lµ c«ng thøc thÓ hiÖn tÝnh ®Ö quy. Tõ c«ng thøc nµy, hµm ®Ö quy tÝnh n! cã thÓ viÕt nh sau: long GT(int n) { if (n==1) return 1; else return GT(n-1) * n; }

§Ó hiÓu b¶n chÊt cña ®Ö quy, ta xÐt qu¸ tr×nh tÝnh 3!. Qu¸ tr×nh nµy ®îc thÓ hiÖn qua s¬ ®å sau: B¾t ®Çu : tÝnh 3!

GT(2) * 3

KÕt thóc Return 1*2*3

TiÕn tr×nh GT(2)

TiÕn tr×nh GT(1)

GT(1) * 2

GT(0) * 1

Return 1*2

Bá qua lÖnh gäi ®Ö quy

Return 1

Khi gÆp lêi gäi GT(3) ®Ó tÝnh 3!, m¸y tÝnh t¹o ra mét tiÕn tr×nh (process) víi ®Çu vµo lµ 3. Tuy nhiªn, khi thùc hiÖn, ®Ó tÝnh 3!, tiÕn tr×nh nµy gÆp ph¶i lêi gäi ®Ö quy 3*GT(2). Khi ®ã, toµn bé tiÕn tr×nh nµy ph¶i dõng l¹i vµ chê ®Ó m¸y tÝnh t¹o ra mét tiÕn tr×nh míi (qu¸ tr×nh thùc thi hµm míi) víi ®èi vµo lµ 2. Khi tiÕn tr×nh míi nµy thùc hiÖn xong (tøc lµ tÝnh xong 2!) nã sÏ quay vÒ tiÕn tr×nh ban ®Çu víi kÕt qu¶ Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

4 4

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

2! tÝnh ®îc vµ tiÕp tôc thùc thi tiÕn tr×nh ban ®Çu víi kÕt qu¶ lµ 2!*3. Tuy nhiªn, tiÕn tr×nh tÝnh 2! l¹i gÆp lêi gäi ®Ö quy tÝnh 1! Nªn nã còng ph¶i t¹m dõng vµ chê 1 tiÕn tr×nh thø 3 ®îc t¹o ra ®Ó tÝnh 1!. RÊt may lµ trong tiÕn tr×nh tÝnh 1! kh«ng cã lêi gäi ®Ö quy (v× if(n==1) return 1;) nªn qu¸ tr×nh dõng-chêt¹o tiÕn tr×nh míi kh«ng x¶y ra. Do vËy c¸c tiÕn tr×nh ®ang chê tríc ®ã lÇn lît ®îc kh«i phôc vµ tr¶ vÒ kÕt qu¶ mong muèn. Nh vËy, khi gÆp mét lêi gäi ®Ö quy, m¸y tÝnh sÏ: - T¹m dõng tiÕn tr×nh hiÖn t¹i, lu ®Þa chØ cña dßng lÖnh gäi ®Ö quy vµo ng¨n xÕp. - T¹o mét tiÕn tr×nh hoµn toµn míi, cÊp ph¸t c¸c vïng nhí míi cho c¸c biÕn côc bé, thùc hiÖn tiÕn tr×nh míi nµy. - Khi viÖc thùc thi tiÕn tr×nh míi hoµn thµnh, ch¬ng tr×nh quay vÒ ng¨n xÕp, lÊy ®Þa chØ cña dßng lÖnh gäi ®Ö quy vµ quay vÒ tiÕn tr×nh ban ®Çu.

Mét c¸ch tæng qu¸t ta cã s¬ ®å qu¸ tr×nh thùc thi hµm ®Ö quy nh sau: B¾t ®Çu

Gäi ®Ö quy

B¶n sao 1

Gäi ®Ö quy

B¶n sao n

…

Gäi ®Ö quy

Bá qua lÖnh gäi ®Ö quy

KÕt thóc

Nãi chung, mét hµm ®îc viÕt theo kiÓu ®Ö quy sÏ tèn bé nhí h¬n, thùc thi phøc t¹p h¬n vµ do vËy ngêi ta thêng t×m c¸ch khö ®Ö quy (tøc viÕt ch¬ng tr×nh kh«ng theo kiÓu ®Ö quy). Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

4 5

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Tuy nhiªn, c¸ch tiÕp cËn ®Ö quy l¹i tá ra rÊt cã hiÖu qu¶ víi c¸c bµi to¸n liªn quan tíi duyÖt c©y, ®å thÞ, danh s¸ch tuyÕn tÝnh .v.v… II.2. ThiÕt kÕ hµm ®Ö quy. C¸c bµi to¸n ¸p dông gi¶i thuËt ®Ö quy thêng cã ®Æc ®iÓm sau: - Bµi to¸n dÔ dµng gi¶i quyÕt trong mét sè trêng hîp riªng øng víi c¸c gi¸ trÞ ®Æc biÖt cña tham sè. Trong trêng hîp nµy, ta cã thÓ gi¶i quyÕt bµi to¸n mµ kh«ng cÇn gäi ®Ö quy. Ta gäi trêng hîp nµy lµ trêng hîp suy biÕn.

- Trong trêng hîp tæng qu¸t, bµi to¸n cã thÓ quy vÒ bµi to¸n cïng d¹ng nhng gi¸ trÞ cña tham sè thay ®æi. Vµ sau mét sè h÷u h¹n bíc biÕn ®æi ®Ö quy, sÏ dÉn tíi trêng hîp suy biÕn.

Trêng hîp suy biÕn rÊt quan träng trong bµi to¸n ®Ö quy. NÕu kh«ng cã trêng hîp nµy, qu¸ tr×nh t¹o tiÕn tr×nh míi sÏ kh«ng thÓ dõng l¹i vµ ta gÆp ph¶i trêng hîp ®Ö quy v« h¹n. NÕu trêng hîp tæng qu¸t mµ sau mét sè h÷u h¹n lÇn gäi ®Ö quy kh«ng thÓ quy vÒ trêng hîp suy biÕn th× còng kh«ng thÓ tho¸t khái qu¸ tr×nh gäi ®Ö quy v« h¹n nµy. Gi¶ sö bµi to¸n tÝnh n!, dÔ dµng thÊy: - Víi n = 0 hoÆc n = 1 th× n! = 1. Khi ®ã ta kh«ng cÇn gäi ®Ö quy vÉn cã thÓ tÝnh ®îc n!. §©y lµ trêng hîp suy biÕn. - Trêng hîp tæng qu¸t, n! = n* (n-1)!. Tøc lµ ®Ó tÝnh n!, ta cã thÓ quy vÒ bµi to¸n tÝnh (n-1)!. Sau mét sè h÷u h¹n bíc biÕn ®æi, ta cã thÓ quy vÒ bµi to¸n tÝnh 1!. Nh vËy: - Trêng hîp suy biÕn: n=0 hoÆc n=1. C«ng thøc trong trêng hîp nµy : n! = 1; - Trêng hîp tæng qu¸t: lµ c¸c trêng hîp cßn l¹i (n rel="nofollow">1) khi ®ã: n! = n* (n-1)!.

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

4 6

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Tõ ph¸t hiÖn trªn, ta cã thÓ t¹m chÊp nhËn ph¬ng ph¸p thiÕt kÕ hµm ®Ö quy theo 3 bíc nh sau: Bíc 1: - X¸c ®Þnh trêng hîp suy biÕn, gi¸ trÞ cña tham sè, c«ng thøc ®Ó tÝnh to¸n trong trêng hîp nµy. - X¸c ®Þnh trêng hîp tæng qu¸t, gi¸ trÞ cña tham sè, c«ng thøc ®Ó tÝnh to¸n trong trêng hîp nµy. Bíc 2: ViÕt néi dung ®Ö quy d¹ng: if (suy biÕn) return ; else return ; Bíc 3: Hoµn thiÖn hµm ®Ö quy.

VÝ dô 1: thiÕt kÕ hµm ®Ö quy tÝnh n!. Bíc 1:

- Suy biÕn : n=0 hoÆc n = 1; C«ng thøc n! = 1; - Tæng qu¸t: n kh¸c 0 vµ n kh¸c 1; C«ng thøc n! = n* (n-1)!. Bíc 2: if (n= = 0 || n= = 1) return 1; else return n * GT(n-1); Bíc 3: Hoµn thiÖn ®Ó thu ®îc hµm ®Ö quy tÝnh n!.

VÝ dô 2: D·y sè Catalan ®îc ph¸t biÓu ®Ö quy nh sau: C1 = 1; Cn =

n −1

∑C C i =1

i

n −i

H·y x©y dùng hµm ®Ö quy t×m sè CataLan thø n. Hµm ®Ö quy ®îc thiÕt kÕ nh sau: Bíc 1:

- Suy biÕn: n = 1; C«ng thøc suy biÕn: Cn = 1; - Kh«ng suy biÕn: n kh¸c 1; c«ng thøc tæng qu¸t: Cn =

n −1

∑C C i =1

i

n −i

Bíc 2: if (n = = 1) return 1; else Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

4 7

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü {

int C =0; for (int i=1; i
}

Víi phÇn thiÕt kÕ trªn, hµm ®Ö quy tÝnh sè CataLan thø n ®îc viÕt nh sau (bíc 3): int CataLan(int n) { if (n==1) return 1; else { int C=0; for (int i=1; i
II.3. §Ö quy vµ c¸c d·y truy håi Kh¸i niÖm: Mét d·y truy håi lµ d·y mµ c¸c sè h¹ng ®øng sau ®îc ®Þnh nghÜa dùa trªn c¸c sè h¹ng ®øng tríc cña d·y.

VÝ dô: cho d·y sau: a[1] = 1; a[n] = a[n-1] * n; DÔ dµng thÊy ®©y chÝnh lµ d·y c¸c giai thõa cña c¸c sè tù nhiªn: 1!, 2!, 3!, 4!…Víi sè h¹ng thø n ®îc ®Þnh nghÜa tõ sè h¹ng thø n-1. HoÆc d·y c¸c sè Fibonacci: F[1] = 1; F[2] = 1; F[n] = F[n-1] + F[n-2] (víi n>2). §Æc ®iÓm cña c¸c d·y truy håi: - Lu«n tån t¹i mét hoÆc mét sè sè h¹ng ®øng ®Çu d·y. C¸c sè h¹ng nµy dÔ dµng ®îc x¸c ®Þnh hoÆc ®îc cho tríc. §©y chÝnh lµ trêng hîp suy biÕn cho bµi to¸n ®Ö quy t×m sè h¹ng thø n.

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

4 8

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

- Lu«n tån t¹i mét c«ng thøc truy håi mµ sè h¹ng sau ®îc x¸c ®Þnh dùa vµo sè h¹ng ®øng tríc. VËy theo c«ng thøc truy håi ta lu«n x¸c ®Þnh ®îc sè h¹ng thø n tõ c¸c sè h¹ng ®Çu d·y (sau mét sè h÷u h¹n lÇn truy håi). VËy c«ng thøc truy håi chÝnh lµ c«ng thøc trong trêng hîp tæng qu¸t cho bµi to¸n ®Ö quy t×m sè h¹ng thø n. Do vËy, víi c¸c d·y truy håi, ngêi ta thêng sö dông c¸c gi¶i thuËt ®Ö quy ®Ó x¸c ®Þnh chóng. II.4. Mét sè vÝ dô vÒ ®Ö quy VÝ dô 1: USCLN cña hai sè nguyªn a, b ®îc ®Þnh nghÜa nh sau: USCLN(a, b)

= a nÕu b =0

= USCLN(b, a%b) nÕu b kh¸c 0. ViÕt hµm lÆp vµ ®Ö quy ®Ó tÝnh USCLN cña hai sè nguyªn a, b.

Hµm lÆp: int USCLN_Lap(int a, int b) { int Sodu; while (y !=0) { Sodu = a%b; a = b; b = Sodu; } return a; }

Hµm ®Ö quy: Bíc 1: - Suy biÕn : b=0; c«ng thøc suy biÕn: USCLN(a, b) = b; - Kh«ng suy biÕn: b kh¸c 0; c«ng thøc tæng qu¸t: USCLN(a, b) = USCLN(b, a%b); Bíc 2: if(b==0) return a; else return USCLN(b, a%b) Bíc 3: int USCLN_DQ(int a, int b) { if (b==0) return a; Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

4 9

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü else return USCLN_DQ(b, a%b); }

VÝ dô 2: C¸c sè Fibonacci ®îc ®Þnh nghÜa ®Ö quy nh sau: F[0] = F[1] = 1; F[i] = F[i-1] + F[i-2];

VD: 1, 1, 2, 3, 5, 8, 13… ViÕt hµm ®Ö quy t×m sè Fibonacci thø n. Bíc 1: Suy biÕn: n <=1; c«ng thøc suy biÕn: Fibo(n) = 1; Kh«ng suy biÕn: n >1; c«ng thøc tæng qu¸t: Fibo(n) = Fibo(n-1) + Fibo(n-2). Bíc 2: if(n<=1) return 1; else return Fibo(n-1) + Fibo(n-2); Bíc 3: int Fibo(int n) { if(n<=1) return 1; else return Fibo(n-1) + Fibo(n-2); } III. Kü thuËt truyÒn tham sè

III.1. Kh¸i niÖm vµ ph©n lo¹i tham sè Khi ®Þnh nghÜa hµm, th«ng thêng c¸c gi¸ trÞ ®Çu vµo ®îc ®Þnh nghÜa mét c¸ch h×nh thøc (gi¶ ®Þnh) vµ chóng ®îc gäi lµ c¸c ®èi sè (hay tham sè h×nh thøc). Khi sö dông hµm, nÕu hµm cã ®èi sè (tham sè h×nh thøc), khi gäi hµm ta ph¶i truyÒn c¸c tham sè (®èi sè thùc sù) t¬ng øng cho hµm. C¸c tham sè lµ c¸c gi¸ trÞ cô thÓ vµ t¬ng øng vÒ kiÓu víi c¸c ®èi sè cña hµm, chóng cã thÓ lµ c¸c biÕn hoÆc c¸c h»ng gi¸ trÞ. ë ®©y ta chØ xÐt c¸c tham sè lµ biÕn. Tham sè lµ biÕn ®îc chia lµm 2 lo¹i: [1]. Tham trÞ: Lµ c¸c biÕn th«ng thêng ®îc truyÒn vµo hµm. Khi truyÒn tham sè díi d¹ng tham trÞ, tham sè sÏ kh«ng Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé 5 Trang 0

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

®îc truy cËp trùc tiÕp. Hµm sÏ cÊp ph¸t mét vïng nhí míi vµ sao chÐp gi¸ trÞ cña tham sè vµo ®ã. C¸c lÖnh trong th©n hµm sÏ thao t¸c trªn vïng nhí míi nµy. Nh vËy, mét tham sè khi truyÒn vµo mét hµm sÏ kh«ng bÞ thay ®æi gi¸ trÞ cña nã khi ra khái hµm. [2]. Tham chiÕu: Lµ ®Þa chØ cña c¸c biÕn th«ng thêng hoÆc c¸c biÕn con trá (v× b¶n th©n con trá ®ang chøa ®Þa chØ cña c¸c biÕn thêng). Khi truyÒn tham sè díi d¹ng tham chiÕu, tham sè lµ c¸c biÕn vµ tham sè sÏ ®îc truy cËp trùc tiÕp. Nh vËy, c¸c mét tham sè khi truyÒn vµo mét hµm cã thÓ bÞ biÕn ®æi gi¸ trÞ cña nã.

BiÕn

Vïng nhí cña biÕn

BiÕn

Vïng nhí cña biÕn Vïng nhí míi

Gäi hµm

Thùc thi hµm

Gäi hµm

a) truyÒn tham chiÕu

Thùc thi hµm

b) TruyÒn tham trÞ

III.2. TruyÒn tham sè Khi ta truyÒn mét biÕn th«ng thêng vµo hµm tøc lµ ta ®· truyÒn díi d¹ng tham trÞ. Hµm sÏ cÊp ph¸t vïng nhí míi vµ sao chÐp gi¸ trÞ cña biÕn vµo « nhí nµy ®Ó sö dông. Nh vËy, ra khái th©n hµm, « nhí míi ®îc cÊp ph¸t bÞ xãa ngay vµ gi¸ trÞ cña biÕn kh«ng hÒ thay ®æi. VÝ dô 1. XÐt hµm sau: int tang(int a) { a++; } void main() { int n=1; cout<<”Gi¸ trÞ tríc khi gäi hµm “<
5 1

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü tang(n); cout<<”Gi¸ trÞ sau khi gäi hµm “<
BiÕn n lµ mét biÕn th«ng thêng vµ ®ang mang mét gi¸ trÞ cô thÓ (n=1;), ®îc truyÒn vµo hµm díi d¹ng tham trÞ nªn sau khi ra khái hµm, gi¸ trÞ cña nã kh«ng hÒ thay ®æi (vÉn lµ 1) mÆc dï trong th©n hµm int tang(int a) th× gi¸ trÞ cña ®èi sè bÞ thay ®æi (a++). VÝ dô 2. XÐt hµm sau int Ham(int a, int b) { a+=1; b+=a; cout<<”Gi¸ trÞ a trong th©n hµm “<
V× a, b ®îc truyÒn vµo hµm díi d¹ng tham trÞ nªn mÆc dï trong th©n hµm c¸c gi¸ trÞ nµy ®· bÞ thay ®æi nhng khi ra khái hµm nã l¹i gi÷ nguyªn gi¸ trÞ ban ®Çu. Nguyªn nh©n lµ do trong th©n hµm, chØ thay ®æi gi¸ trÞ trªn c¸c b¶n sao cña biÕn truyÒn vµo. NÕu ta chØ truyÒn ®Þa chØ cña biÕn vµo hµm th× viÖc truyÒn nh vËy gäi lµ truyÒn tham chiÕu. Khi ®ã hµm sÏ tham chiÕu trùc tiÕp tíi biÕn vµ thao t¸c trªn vïng nhí Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

5 2

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

cña biÕn truyÒn vµo. KÕt qu¶ lµ gi¸ trÞ cña biÕn cã thÓ bÞ thay ®æi do t¸c ®éng cña hµm. int tang(int * a) { (*a)++; } void main() { int n=1; cout<<”Gi¸ trÞ tríc khi gäi hµm “<
DÔ thÊy khi gäi hµm ta chØ truyÒn ®Þa chØ cña n vµo hµm (tang(&n)). Do vËy hµm int tang(int *a) sÏ sö dông biÕn n (cho ®èi sè *a) ®Ó thao t¸c. KÕt qu¶ sau khi ra khái hµm, biÕn n bÞ thay ®æi gi¸ trÞ (t¨ng lªn 1 ®¬n vÞ). Nh vËy, nÕu muèn truyÒn tham chiÕu th× ®èi sè t¬ng øng cña hµm ®îc ®Þnh nghÜa tríc ®ã ph¶i lµ con trá.

NÕu trong hµm main, biÕn n lµ con trá th× b¶n th©n con trá ®· chøa ®Þa chØ cña biÕn kh¸c nªn khi truyÒn n vµo ®· lµ truyÒn tham chiÕu. §©y lµ ®iÒu dÔ g©y nhÇm lÉn cÇn ph¶i ®îc chó ý. VÝ dô: víi hµm int tang(int *a) nh trªn, ta cã hµm main sau: void main() { int *n; int a=1; n=&a; // n ®ang trá tíi a – chøa ®Þa chØ cña a cout<<”Gi¸ trÞ tríc khi gäi hµm “<<(*n); tang(n); // truyÒn tham chiÕu cout<<”Gi¸ trÞ sau khi gäi hµm “<<(*n); getch(); }

Trong lêi gäi tang(n); ta truyÒn tham sè n vµo díi d¹ng tham chiÕu bëi v× n ®ang chøa ®Þa chØ cña biÕn a.

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

5 3

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Ch¬ng IV. Kü thuËt lËp tr×nh dïng m¶ng I.

M¶ng mét chiÒu

I.1. Khai niÖm vµ c¸ch khai b¸o Bµi to¸n: h·y lu tr÷ mét d·y sè gåm 5 phÇn tö: {2, 5, 3, 6, 7} C¸ch 1: Sö dông 5 « nhí (5 biÕn) cïng kiÓu. C¸c biÕn ®îc ®Æt tªn lÇn lît lµ: a, b, c, d, e. Khi ®ã, c¸c phÇn tö ®îc chøa trong 5 « nhí nµy nh sau: 2 a

5

3

b

c

6

7 d

e V× cÇn lu tr÷ 5 gi¸ trÞ kh¸c nhau nªn viÖc dïng 5 « nhí kh¸c nhau lµ cÇn thiÕt. Tuy nhiªn, ph¬ng ph¸p nµy tá kh«ng kh¶ thi do sö dông qu¸ nhiÒu tªn biÕn, dÉn tíi khã kiÓm so¸t c¸c biÕn, ®Æc biÖt trong trêng hîp sè phÇn tö cña d·y qu¸ lín. C¸ch 2: VÉn sö dông 5 « nhí cïng kiÓu nhng tÊt c¶ c¸c « ®îc ®Æt chung mét tªn (a ch¼ng h¹n). §Ó ph©n biÖt c¸c « víi nhau, ngêi ta ®¸nh chØ sè cho tõng «. ChØ sè lµ c¸c sè nguyªn liªn tiÕp, tÝnh tõ 0. Nh vËy ta thu ®îc: 2

a[0] a[4]

5

a[1]

3

6

a[2]

7

a[3]

KÕt qu¶ ta cã ®îc mét cÊu tróc d÷ liÖu kh¾c phôc ®îc nhîc ®iÓm cña c¸ch 1. CÊu tróc d÷ liÖu nµy gäi lµ m¶ng mét chiÒu. M¶ng lµ mét cÊu tróc bé nhí bao gåm mét d·y liªn tiÕp c¸c « nhí cïng tªn, cïng kiÓu nhng kh¸c nhau vÒ chØ sè, dïng ®Ó lu tr÷ mét d·y c¸c phÇn tö cïng kiÓu.

Có ph¸p khai b¸o m¶ng: [<Sè phÇn tö tèi ®a>];

Trong ®ã: : Lµ kiÓu d÷ liÖu cña mçi phÇn tö trong m¶ng, cã thÓ lµ mét kiÓu d÷ liÖu chuÈn hoÆc kiÓu d÷ liÖu tù ®Þnh nghÜa. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

5 4

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

: §îc ®Æt tuú ý tu©n theo quy íc ®Æt tªn biÕn trong C++. <Sè phÇn tö tèi ®a>: Lµ mét h»ng sè chØ ra sè « nhí tèi ®a ®îc dµnh cho m¶ng còng nh sè phÇn tö tèi ®a mµ m¶ng cã thÓ chøa ®îc. VÝ dô: Khai b¸o int a[3]; sÏ cÊp ph¸t 3 « nhí liªn tiÕp cïng kiÓu nguyªn (2 byte) dµnh cho m¶ng a. M¶ng nµy cã thÓ chøa ®îc tèi ®a 3 sè nguyªn. I.2. C¸c thao t¸c c¬ b¶n trªn m¶ng mét chiÒu - NhËp m¶ng: Gi¶ sö ta cÇn nhËp m¶ng a gåm n phÇn tö. C¸ch duy nhÊt lµ nhËp tõng phÇn tö cho m¶ng. Do vËy, ta cÇn sö dông mét vßng lÆp for duyÖt qua tõng phÇn tö vµ nhËp d÷ liÖu cho chóng. Nhng tríc tiªn, cÇn nhËp sè phÇn tö thùc tÕ cña m¶ng (n). for(int i=0; i>a[i]; }

- XuÊt m¶ng: t¬ng tù nh nhËp m¶ng, ta còng cÇn sö dông vßng lÆp for ®Ó xuÊt tõng phÇn tö cña m¶ng lªn mµn h×nh. for(i = 0; i
DuyÖt m¶ng: lµ thao t¸c th¨m lÇn lît tõng phÇn tö cña m¶ng. Thao t¸c duyÖt m¶ng cã trong hÇu hÕt c¸c bµi to¸n sö dông m¶ng. for(i = 0; i
I.3. C¸c bµi to¸n c¬ b¶n a. Bµi to¸n s¾p xÕp m¶ng Bµi to¸n: cho mét d·y gåm n phÇn tö. H·y s¾p xÕp d·y theo chiÒu t¨ng dÇn. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

5 5

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

§Ó gi¶i quyÕt bµi to¸n nµy, tríc tiªn ta cÇn lu tr÷ d·y c¸c phÇn tö ®· cho vµo bé nhí, nh vËy ta cÇn sö dông mét m¶ng mét chiÒu. Sau ®ã, cã rÊt nhiÒu ph¬ng ph¸p ®Ó s¾p mét m¶ng theo chiÒu t¨ng dÇn. Sau ®©y ta xem xÐt mét sè c¸ch phæ biÕn: • Ph¬ng ph¸p 1: S¾p xÕp næi bät – bubble sort ý tëng cña ph¬ng ph¸p nh sau: - S¾p lÇn lît tõng phÇn tö cña d·y, b¾t ®Çy tõ phÇn tö ®Çu tiªn. - Gi¶ sö cÇn s¾p phÇn tö thø i, ta tiÕn hµnh duyÖt lÇn lît qua tÊt c¶ c¸c phÇn tö ®øng sau nã trong d·y, nÕu gÆp phÇn tö nµo nhá h¬n phÇn tö ®ang s¾p th× ®æi chç. Gi¶ sö ta s¾p m¶ng a gåm n phÇn tö, gi¶i thuËt ®îc m« t¶ chi tiÕt nh sau: for(i = 0; i < n; i++)// víi mçi phÇn tö a[i] for(j = i+1; j
§Ó ®æi chç a[i] cho a[j], ta sö dông mét biÕn tg cã cïng kiÓu vµ g¸n mét trong 2 gi¸ trÞ (a[i] hoÆc a[j]) vµo ®ã. Sau ®ã g¸n gi¸ trÞ cßn l¹i sang gi¸ « nhí võa g¸n vµo tg. Cuèi cïng ta g¸n gi¸ trÞ ®ang chøa trong tg vµo « nhí nµy. for(i = 0; i < n; i++) for(j = i+1; j
Gi¶ sö ta cã m¶ng a = {3, 5, 2, 7, 4, 8}. H×nh ¶nh cña a sau c¸c lÇn lÆp s¾p xÕp næi bät nh sau: B¾t ®Çu s¾p i = 0

3

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

5

2

7

4

8 5 6

§Ò c¬ng chi tiÕt thuËt lËp tr×nh HÕt 1 vßng = 1; HÕt mét i=2; HÕt mét i=3; HÕt mét i=4;

Kü lÆp j;

i

2

5

3

7

4

8

vßng

j;

2

3

5

7

4

8

vßng

j;

2

3

4

7

5

8

vßng

j;

2

3

4

5

7

8

• Ph¬ng ph¸p s¾p xÕp chän – Selection sort Trong ph¬ng ph¸p s¾p sÕp næi bät, ®Ó s¾p mét phÇn tö nhiÒu khi ta ph¶i ®æi chç nhiÒu lÇn phÇn tö ®ang s¾p víi c¸c phÇn tö ®øng sau nã. Mét ý tëng rÊt hay lµ lµm sao chØ ®æi chç 1 lÇn duy nhÊt khi s¾p mét phÇn tö trong d·y. §©y chÝnh lµ ý tëng cña ph¬ng ph¸p s¾p xÕp chän. §Ó lµm ®îc ®iÒu nµy, khi s¾p phÇn tö thø i, ngêi ta tiÕn hµnh t×m phÇn tö nhá nhÊt trong sè c¸c phÇn tö ®øng sau nã kÓ c¶ phÇn tö ®ang s¾p råi tiÕn hµnh ®æi chç phÇn tö nhá nhÊt t×m ®îc víi phÇn tö ®ang s¾p. VÝ dô: Víi d·y a = {1, 6, 4, 2, 5, 7}, ®Ó s¾p phÇn tö thø 2 (6) ngêi ta tiÕn hµnh t×m phÇn tö nhá nhÊt trong sè c¸c phÇn tö {6, 4, 2, 5, 7}. Khi ®ã Min(6, 4, 2, 5, 7) = 2 vµ phÇn tö 2 ®îc ®¶o chç cho phÇn tö 6. KÕt qu¶ thu ®îc: 1

2

4

6

5

7

Tríc tiªn ta xem xÐt bµi to¸n t×m phÇn tö nhá nhÊt cña mét d·y c¸c phÇn tö: - LÊy mét phÇn tö ngÉu nhiªn trong d·y lµm phÇn tö nhá nhÊt (Min) (thêng lÊy phÇn tö ®Çu tiªn). - DuyÖt qua tÊt c¶ c¸c phÇn tö cña d·y, nÕu gÆp phÇn tö nµo nhá h¬n Min th× g¸n Min b»ng phÇn tö ®ã. VÝ dô: T×m sè nhá nhÊt trong m¶ng a gåm n phÇn tö: Min = a[0]; for(i = 0; i
Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

5 7

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Khi kÕt thóc vßng lÆp, ta thu ®îc gi¸ trÞ nhá nhÊt cña d·y ®ang chøa trong biÕn Min. Tuy nhiªn, ¸p dông gi¶i thuËt nµy vµo ph¬ng ph¸p s¾p xÕp chän ta cÇn ph¶i lu ý mét sè ®iÓm. Ch¼ng h¹n ta cÇn biÕt chÝnh x¸c vÞ trÝ cña phÇn tö Min n»m ë ®©u ®Ó tiÕn hµnh ®æi chç chø kh«ng quan t©m tíi gi¸ trÞ Min lµ bao nhiªu. Tuy nhiªn gi¶i thuËt t×m Min l¹i chØ cho biÕt gi¸ trÞ Min mµ kh«ng cho biÕt vÞ trÝ. NÕu muèn biÕt, ta l¹i ph¶i sö dông 1 vßng lÆp duyÖt l¹i tõ ®Çu ®Ó t×m vÞ trÝ Min. Do vËy, khi cµi ®Æt ph¬ng ph¸p s¾p xÕp chän, ®Ó tr¸nh trêng hîp sö dông nhiÒu vßng lÆp sÏ lµm t¨ng ®é phøc t¹p cña gi¶i thuËt, ta chØ chó ý tíi viÖc t×m vÞ trÝ phÇn tö Min. - S¾p xÕp tõng phÇn tö cña d·y, b¾t ®Çu tõ phÇn tö ®Çu tiªn.

- Gi¶ sö s¾p phÇn tö a[i], ta g¸n Min = i råi duyÖt qua c¸c phÇn tö ®øng sau nã (i+1 trë ®i). NÕu phÇn tö a[j] nµo nhá h¬n phÇn tö a[Min] th× g¸n Min b»ng vÞ trÝ cña a[j] (tøc Min=j). Cuèi cïng ta ®æi chç a[i] cho a[Min]. for(i = 0; i < n; i++) { Min = i; for(j = i+1; j
Gi¶ sö ta cã m¶ng a = {3, 5, 2, 7, qua c¸c lÇn lÆp s¾p xÕp chän nh sau: 3 5 2 7 4 2 5 3 7 4 2 3 5 7 4 2 3 4 7 5 2 3 4 5 7 2 3 4 5 7

4, 8}. H×nh ¶nh cña a 8 8 8 8 8 8

Min Min Min Min Min Min

= = = = = =

2 3 4 5 7 8

Sau ®©y lµ hµm s¾p xÕp chän víi ®èi vµo lµ m¶ng a gåm n phÈn tö: Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

5 8

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

void SapChon(int a[100], int n) { for (int i=0; i
• Ph¬ng ph¸p s¾p xÕp chÌn Mét thuËt to¸n gÇn nh ®¬n gi¶n ngang víi thuËt to¸n s¾p xÕp chän nhng cã lÏ mÒm dÎo h¬n, ®ã lµ s¾p xÕp chÌn. §©y lµ ph¬ng ph¸p ngêi ta dïng ®Ó s¾p xÕp c¸c thanh ngang cho mét chiÕc thang. §Çu tiªn, ngêi ta rót ngÉu nhiªn 1 thanh ngang vµ ®Æt vµo 2 thanh däc ®Ó lµm thang. TiÕp ®ã, ngêi ta lÇn lît chÌn tõng thanh ngang vµo sao cho kh«ng ph¸ vì tÝnh ®îc s¾p cña c¸c thanh ®· ®îc ®Æt trªn 2 thanh däc. Gi¶ sö víi m¶ng a = {3, 5, 2, 7, 4, 8}. Gi¶ sö c¸c phÇn tö 3 vµ 5 ®· ®îc chÌn vµo ®óng vÞ trÝ (®· ®îc s¾p): 3

5

Ta xem xÐt qu¸ tr×nh chÌn phÇn tö tiÕp theo vµo m¶ng (gi¶ sö chÌn 2 vµo). Khi ®ã, qu¸ tr×nh diÔn ra nh sau: 2 Tg

3527483574835748235748 - §Æt phÇn tö 2 vµo biÕn tg. - DuyÖt qua c¸c phÇn tö ®øng tríc phÇn tö 2 (c¸c phÇn tö ®· ®îc s¾p). NÕu gÆp phÇn tö nµo lín h¬n 2 th× ®Èy phÇn tö ®ã sang ph¶i 1 vÞ trÝ. Ngîc l¹i, nÕu gÆp phÇn tö nhá h¬n 2 Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé 5 Trang 9

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

th× chÌn 2 vµo ngay sau phÇn tö nhá h¬n nµy. NÕu ®· duyÖt hÕt c¸c phÇn tö ®øng tríc mµ vÉn cha t×m thÊy phÇn tö nhá h¬n 2 th× chÌn 2 vµo ®Çu m¶ng. KÕt thóc qu¸ tr×nh nµy, phÇn tö 2 ®· ®îc chÌn ®óng vÞ trÝ vµ 3 phÇn tö ®· ®îc s¾p lµ: 2

3

5

Toµn bé qu¸ tr×nh s¾p m¶ng a ®îc biÓu diÔn trong b¶ng sau: 3

5

2

7

4

8

3 3 2 2 2 2

5 3 3 3 3

5 5 4 4

7 5 5

7 7

8

Nh vËy trong qu¸ tr×nh thùc hiÖn, ®Ó chÌn 1 phÇn tö vµo ®óng vÞ trÝ cña nã, ta lu«n thùc hiÖn 2 c«ng viÖc: §Èy mét phÇn tö sang ph¶i 1 vÞ trÝ hoÆc chÌn phÇn tö cÇn chÌn vµo vÞ trÝ cña nã. NÕu gäi phÇn tö cÇn chÌn lµ a[i] ®ang chøa trong biÕn tg vµ j lµ biÕn duyÖt qua c¸c phÇn tö ®øng tríc a[i] th×: - Khi cha hÕt m¶ng vµ gÆp mét phÇn tö lín h¬n phÇn tö cÇn chÌn th× ®Èy nã sang ph¶i 1 vÞ trÝ: while ( j rel="nofollow">= 0 && a[j] > tg) a[j+1] = a[j];

- Ngîc l¹i th× chÌn tg vµo sau j: a[j+1] = tg; void SapChen(int a[100], int n) { for (int i=1; i< n; i++) { int Tg = a[i]; int j = i-1; while (j > = 0 && a[j] > Tg) { a[j+1] = a[j]; j--; } a[j+1]=Tg; } } Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

6 0

§Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh S¾p xÕp b»ng ph¬ng ph¸p chÌn trong trêng hîp trung b×nh cÇn n2/ 4 lÇn so s¸nh vµ n2/ 8 lÇn ho¸n vÞ. Trêng hîp tåi nhÊt gÊp ®«i sè lÇn nµy.

• Ph¬ng ph¸p s¾p xÕp trén: Merge sort Bµi to¸n trén: Cho m¶ng a gåm n phÇn tö vµ m¶ng b gåm m phÇn tö ®· s¾p t¨ng. H·y trén hai m¶ng ®Ó thu ®îc mét m¶ng thø 3 còng ®îc s¾p t¨ng. Tríc tiªn, ta xÐt hai m¶ng a vµ b nh vÝ dô nh sau: a

2

3

5

b

1

4

6

7

9

M¶ng c sau thu ®îc sau khi trén a vµ b lµ:

1 0

c 1 2 3 4 5 6 7 9 1 0

§Ó cã ®îc m¶ng c, ta lµm nh sau:

B1. Cho biÕn i xuÊt ph¸t tõ ®Çu m¶ng a (i=0) vµ biÕn j xuÊt ph¸t tõ ®Çu m¶ng b (j=0). B2. Ta so s¸nh a[i] vµ a[j] råi lÊy phÇn tö nhá h¬n trong hai phÇn tö ®ã ®Æt vµo m¶ng c. NÕu lÊy a[i], ta ph¶i t¨ng i lªn 1 ®¬n vÞ (i++) vµ t¬ng tù, nÕu lÊy b[j], ta t¨ng j lªn 1 ®¬n vÞ (j++). LÆp l¹i B2 cho tíi khi 1 trong 2 m¶ng ®· ®îc lÊy hÕt.

Víi m¶ng a,b ë trªn, dÔ thÊy gi¶i thuËt trªn sÏ dõng l¹i khi m¶ng a ®· ®îc lÊy hÕt. Tuy nhiªn, khi ®ã, m¶ng b vÉn cßn c¸c phÇn tö 6, 7, 9, 10 cha ®îc lÊy. C«ng viÖc tiÕp theo lµ chuyÓn toµn bé c¸c phÇn tö “cßn thõa” nµy tõ b sang c. Hµm sau thùc hiÖn trén 2 m¶ng a, b theo thuËt to¸n trªn. int c[100]; void Tron(int a[50],int n, int b[50], int m) { int i=0, j=0, k=0; while(i
6 1

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

DÔ thÊy qu¸ tr×nh cho i ch¹y trªn a vµ j ch¹y trªn b sÏ buéc ph¶i dõng l¹i khi 1 trong 2 m¶ng ®· ®îc duyÖt hÕt. NÕu kh«ng, biÕn i hoÆc j sÏ ch¹y qu¸ giíi h¹n cña m¶ng a hoÆc b. Khi dõng l¹i, mét trong 2 m¶ng cã thÓ cha ®îc duyÖt hÕt vµ cßn thõa mét sè phÇn tö vµ qu¸ tr×nh chuyÓn c¸c phÇn tö nµy sang c ®îc diÔn ra. Mét c¶i tiÕn nhá gióp cho i vµ j kh«ng bao giê ch¹y vît qu¸ giíi h¹n cña 2 m¶ng a vµ b cho tíi khi ta lÊy xong tÊt c¶ c¸c phÇn tö cña a vµ b ®Æt sang c. Muèn vËy, tríc khi thùc hiÖn gi¶i thuËt trªn, ta lµm nh sau: - Gäi Max lµ phÇn tö lín nhÊt trong sè c¸c phÇn tö cña c¶ a vµ b. - ChÌn gi¸ trÞ Max + 1 vµo vÞ trÝ cuèi cïng cña m¶ng a vµ m¶ng b.

Víi m¶ng trªn, gi¸ trÞ Max = 10 vµ hai m¶ng sau khi chÌn Max+1 vµo cuèi sÏ cã d¹ng: a

2

3

5

1 1

b

1

4

6

7

9

1 0

1 1

Khi i hoÆc j ch¹y tíi cuèi m¶ng, ta gÆp ph¶i gi¸ trÞ 11 lµ gi¸ trÞ lín h¬n bÊt kú gi¸ trÞ mµo cña hai m¶ng a vµ b ban ®Çu, do ®ã, theo gi¶i thuËt th× i vµ j sÏ bÞ dõng l¹i t¹i ®ã vµ kh«ng thÓ ch¹y vît ra khái giíi h¹n cña m¶ng. int c[100]; void Tron2(int a[50],int n, int b[50], int m) { int Max=a[n-1]; if(Max
ý tëng cña gi¶i thuËt s¾p xÕp trén nh sau: - Gi¶ sö cã m¶ng a cha s¾p:

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

6 2

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Chia m¶ng a lµm hai phÇn b»ng nhau vµ s¾p trªn 2 nöa cña a.

-

Trén 2 nöa ®· s¾p ®Ó thu ®îc m¶ng a còng ®îc s¾p:

ViÖc s¾p trªn 2 nöa cña a còng ®îc ¸p dông ph¬ng ph¸p s¾p xÕp trén nµy, do ®ã 2 nöa l¹i tiÕp tôc ®îc chia ®«i, trén… Nh vËy ta cã mét gi¶i thuËt ®Ö quy. Gi¶i thuËt sau sö dông m¶ng b lµm m¶ng trung gian. Mçi khi cÇn trén 2 nöa cña m¶ng a ta sao mét nöa ®Çu cña a sang b, mét nöa cßn l¹i còng ®Æt vµo cuèi cña b nhng theo thø tù ngîc l¹i vµ tiÕn hµnh trén víi i ch¹y tõ ®Çu m¶ng b cßn j ch¹y tõ cuèi m¶ng b. ViÖc trén 2 nöa sau khi 2 nöa ®· ®îc ®Æt chung vµo 1 m¶ng b nh vËy sÏ kh«ng cÇn ph¶i sö dông phÇn tö chÆn Max+1 nh trªn n÷a. int a[100], b[100]; void MergeSort(int l, int r) { if(r>l) { int m=(l+r)/2; MergeSort(l,m); MergeSort(m+1, r); //Sao chep nua dau cua a sang b

for(int i=m; i>=l; i--) b[i]=a[i];

//Sao chep nua con lai cua a sang b theo thu tu nguoc lai

for(int j=m+1; j<=r;j++) b[r+m+1-j]=a[j]; //i chay tu dau mang b, j chay tu cuoi mang b va tron

i=l; j=r; for(int k=l; k<=r; k++) if(b[i]
S¾p xÕp b»ng trén còng sö dông thªm mét m¶ng b phô trî cã kÝch thíc n. Ngêi ta ®· chøng minh s¾p xÕp b»ng trén lµ Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

6 3

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

æn ®Þnh vµ kh«ng bÞ ¶nh hëng bëi thø tù ban ®Çu cña d÷ liÖu. b. Bµi to¸n t×m kiÕm Cho mét m¶ng a gåm n phÇn tö vµ mét phÇn tö c cïng kiÓu. Hái c cã xuÊt hiÖn trong a kh«ng? • Ph¬ng ph¸p t×m kiÕm tuÇn tù: Mét ph¬ng ph¸p ®¬n gi¶n ®Ó gi¶i quyÕt bµi to¸n trªn lµ duyÖt m¶ng. Gi¶i thuËt ®îc tr×nh bµy nh sau: -

Sö dông mét biÕn ®Õm d = 0;

DuyÖt qua c¸c phÇn tö cña m¶ng, nÕu gÆp c ta t¨ng biÕn ®Õm: d++; KÕt thóc qu¸ tr×nh duyÖt m¶ng, nÕu d b»ng 0 chøng tá c kh«ng xuÊt hiÖn trong m¶ng vµ ngîc l¹i. Ph¬ng ph¸p trªn cÇn thiÕt ph¶i quyÖt qua tÊt c¶ c¸c phÇn tö cña m¶ng mét c¸ch tuÇn tù, do vËy, ®é phøc t¹p cña gi¶i thuËt lµ O(n) víi n lµ kÝch thíc cña m¶ng.

NÕu m¶ng a ®· ®îc s¾p (t¨ng hoÆc gi¶m) th× do tÝnh chÊt ®Æc biÖt nµy, ta cã thÓ gi¶i quyÕt bµi to¸n mµ kh«ng cÇn duyÖt qua tÊt c¶ c¸c phÇn tö cña m¶ng. Ph¬ng ph¸p ®ã gäi lµ t×m kiÕm nhÞ ph©n. • Ph¬ng ph¸p t×m kiÕm nhÞ ph©n: Gi¶ sö ta cÇn t×m kiÕm c trong mét ®o¹n tõ vÞ trÝ L tíi vÞ trÝ R trong m¶ng a (trêng hîp t×m kiÕm trªn toµn bé m¶ng th× L=0 vµ R=n-1). Ta lµm nh sau: - Gäi M lµ vÞ trÝ gi÷a cña ®o¹n m¶ng ta ®ang t×m kiÕm (M = (L+R)/2). Tríc tiªn ta tiÕn hµnh kiÓm tra a[M]. Khi ®ã, chØ cã thÓ x¶y ra mét trong 3 trêng hîp sau: a[M] = c: kÕt luËn c cã trong m¶ng a vµ ta cã thÓ dõng qu¸ tr×nh t×m kiÕm. a[M] > c: v× m¶ng ®îc s¾p (gi¶ sö s¾p t¨ng) nªn râ rµng c (nÕu cã) chØ n»m trong ®o¹n bªn ph¶i tøc [M+1, R]. Ta tiÕn hµnh lÆp l¹i qu¸ tr×nh t×m kiÕm trªn ®o¹n [M+1, R], tøc cËn tr¸i L=M+1. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

6 4

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

a[M] < c: khi ®ã c (nÕu cã) chØ n»m trong ®o¹n bªn tr¸i cña m¶ng tøc [L, M-1]. Ta tiÕn hµnh lÆp l¹i qu¸ tr×nh t×m kiÕm trªn ®o¹n [L, M-1], tøc cËn ph¶i R = M-1. KÕt thóc qu¸ tr×nh t×m kiÕm lµ khi x¶y ra mét trong hai trêng hîp: [1]. NÕu L > R chøng tá C kh«ng xuÊt hiÖn trong a. [2]. NÕu a[M] = c chøng tá c xuÊt hiÖn trong a t¹i vÞ trÝ M.

VËy qu¸ tr×nh chia ®«i-t×m kiÕm sÏ ®îc lÆp l¹i nÕu: (a[M] !=c && L<=R). Hµm sau thùc hiÖn viÖc t×m kiÕm nhÞ ph©n trªn mét m¶ng a cã kÝch thíc n víi mét kho¸ c cÇn t×m, sö dông vßng lÆp: void TKNP_Lap(int a[100], int n, int c) { int L=0, R=n-1, M; do { M = (L+R)/2; if (a[M]>c) R=M-1; if (a[M]
ViÖc chia ®«i vµ t×m kiÕm trªn mét nöa cña m¶ng ®îc lÆp ®i lÆp l¹i cho tíi khi x¶y ra 1 trong 2 trêng hîp : t×m thÊy vµ kh«ng t×m thÊy gîi ý cho ta mét cµi ®Æt ®Ö quy cho hµm nµy: - Trêng hîp suy biÕn: lµ trêng hîp a[M] = c hoÆc L > R. Khi ®ã, nÕu a[M]=c hµm tr¶ vÒ gi¸ trÞ M lµ vÞ trÝ cuÊt hiÖn cña c trong m¶ng; nÕu L > R th× c kh«ng xuÊt hiÖn trong m¶ng vµ hµm tr¶ vÒ gi¸ trÞ -1. - Trêng hîp tæng qu¸t: lµ trêng hîp a[M] > c hoÆc a[M] < c. Khi ®ã viÖc gäi ®Ö quy lµ cÇn thiÕt víi c¸c cËn L hoÆc R ®îc thay ®æi cho phï hîp. int TKNP_DQ(int a[100], int c, int L, int R) {

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

6 5

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

int M=(L+R)/2; if(a[M]==c) return M; else if(L>R) return -1; else //trêng hîp tæng qu¸t if(a[M]>c) return TKNP_DQ(a,c,L,M-1); else return TKNP_DQ(a,c,M+1,R); }

Gi¶i thuËt trªn gièng nh viÖc ta th¨m phÇn tö chÝnh gi÷a cña ®o¹n m¶ng ®ang t×m kiÕm, nÕu kh«ng gÆp c ta cã thÓ “rÏ” sang bªn tr¸i hoÆc bªn ph¶i ®Ó t×m tiÕp tuú thuéc vµo gi¸ trÞ cña phÇn tö chÝnh gi÷a nµy. ViÖc nµy gièng nh viÖc t×m kiÕm trªn c©y nhÞ ph©n (c©y mµ mçi nót cã 2 con sao cho c¸c gi¸ trÞ thuéc nh¸nh tr¸i nhá h¬n gi¸ trÞ cña nót vµ c¸c gi¸ trÞ cña nh¸nh bªn ph¶i lín h¬n gi¸ trÞ cña nót). Gi¶ sö ta cã m¶ng a nh sau: a

1

4

6

7

9

1 0

1 1

C¸c gi¸ trÞ cña a cã thÓ biÓu diÔn trªn c©y nhÞ ph©n t×m kiÕm nh sau: 7

4

1

10

6

9

11

NÕu ta cÇn t×m mét gi¸ trÞ c bÊt kú, gi¶ sö c = 9, ta chØ cÇn ®i hÕt chiÒu cao cña c©y. (§êng ®i trong trêng hîp nµy ®îc t« ®Ëm). Gi¶ sö m¶ng cã n phÇn tö, khi ®ã ta lu«n cã thÓ sö dông mét c©y cã chiÒu cao kh«ng qu¸ lg2(n) ®Ó biÓu diÔn c¸c gi¸ trÞ cña m¶ng trªn c©y. Do vËy, ®é phøc t¹p trong trêng cña gi¶i thuËt nµy lµ O(lg2(n)) II. M¶ng hai chiÒu

II.1. C¸c thao t¸c c¬ b¶n trªn m¶ng hai chiÒu

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

6 6

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

M¶ng 2 chiÒu lµ mét cÊu tróc bé nhí gåm nhiÒu « nhí cïng tªn, cïng kiÓu nhng kh¸c nhau vÒ chØ sè dïng ®Ó lu tr÷ mét b¶ng c¸c phÇn tö cïng kiÓu. Mçi b¶ng c¸c phÇn tö bao gåm nhiÒu dßng vµ nhiÒu cét, do vËy, chØ sè cña mét phÇn tö cña m¶ng ®îc x¸c ®Þnh bëi chØ sè cña dßng vµ cña cét t¬ng øng. Gi¶i sö b¶ng c¸c phÇn tö cã n dßng vµ m cét. C¸c dßng ®îc ®¸nh chØ sè b¾t ®Çu tõ 0: 0, 1, 2,…, n-1 vµ c¸c cét còng ®îc ®¸nh chØ sè tõ 0: 0, 1, 2, …, m-1. PhÇn tö t¹i dßng i, cét j cã chØ sè lµ [i][j]. Mét m¶ng a gåm 3 dßng, 4 cét cã d¹ng nh sau:

a0123012

a[1][2]

Khai b¸o m¶ng 2 chiÒu: [<Sè dßng tèi ®a>] [<Sè cét tèi ®a>];

VÝ dô: int a[5][10]; khai b¸o mét m¶ng a cã tèi ®a 5 dßng vµ 10 cét. M¶ng a cã thÓ chøa ®îc tèi ®a 50 phÇn tö kiÓu nguyªn. VÊn ®Ò t¹o d¸ng ma trËn: Khi thÓ hiÖn m¶ng hai chiÒu lªn mµn h×nh, ta thêng sö dông c©u lÖnh gotoxy ®Ó t¹o d¸ng ma trËn cho m¶ng. C©u lÖnh nµy cã t¸c dông ®a con trá mµn h×nh tíi täa ®é (x,y) ®· chØ ra trªn mµn h×nh ®Ó nhËp hoÆc xuÊt c¸c phÇn tö cña m¶ng. Có ph¸p: gotoxy(x, y); Víi x lµ täa ®é theo ph¬ng X (cét x) cña mµn h×nh, cã gi¸ trÞ tõ 1 tíi 80, y lµ täa ®é theo ph¬ng Y (dßng y) cña mµn h×nh, cã gi¸ trÞ tõ 1 tíi 25. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

6 7

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü 1

x

8 0

X

y

Y

2 5

To¹ ®é mµn h×nh trong chÕ ®é text mode Nh vËy, ®Ó t¹o d¸ng ma trËn cho m¶ng khi nhËp, xuÊt ta sö dông c©u lÖnh sau: gotoxy( x + k*j, x + i); Víi (x, y) lµ to¹ ®é ®Ønh tr¸i trªn cña ma trËn vµ k lµ bíc nh¶y theo trôc x (hay kho¶ng c¸ch gi÷a c¸c cét cña m¶ng - thêng chän k=3). Th«ng thêng ta hay nhËp xuÊt m¶ng t¹i 4 vÞ trÝ cña mµn h×nh t¬ng øng víi c¸c lÖnh gotoxy sau: gotoxy(5 + 3 *j, 5 + i); gotoxy(5 + 3 *j, 15 + i);

gotoxy(35 + 3 *j, 5 + i); gotoxy(35 + 3 *j, 15 + i);

NhËp m¶ng: - Ta sö dông hai vßng lÆp for lång nhau ®Ó nhËp tõng phÇn tö cho m¶ng. §o¹n tr×nh sau nhËp gi¸ trÞ cho mét m¶ng sè a gåm n dßng, m cét t¹o d¸ng t¹i vÞ trÝ cã to¹ ®é (5,5) : for(i=0; i>a[i][j]; }

XuÊt m¶ng: Ta còng sö dông hai vßng for lång nhau vµ t¹o d¸ng ma trËn cho m¶ng khi xuÊt. §o¹n tr×nh sau xuÊt m¶ng a gåm n dßng, m cét t¹o d¸ng t¹i to¹ ®é (35, 5): for(i=0; i
6 8

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü cout<
}

DuyÖt m¶ng: ViÖc th¨m lÇn lît tÊt c¶ c¸c phÇn tö cña m¶ng cÇn ph¶i sö dông 2 vßng lÆp for lång nhau: for(i=0; i
Thao t¸c duyÖt m¶ng lµ thao t¸c thêng xuyªn sö dông trong c¸c bµi tËp vÒ m¶ng. Ngay viÖc nhËp, xuÊt m¶ng vÒ b¶n chÊt còng lµ thao t¸c duyÖt m¶ng. II.2. C¸c bµi to¸n c¬ b¶n trªn m¶ng 2 chiÒu • C¸c bµi to¸n trªn ma trËn: VÒ mÆt h×nh thøc, m¶ng cã d¹ng ma trËn. Do vËy, mét d¹ng bµi tËp phæ biÕn vÒ m¶ng lµ thùc hiÖn c¸c bµi to¸n trªn ma trËn. Thuéc d¹ng nµy cã c¸c bµi nh: Céng, trõ, nh©n hai ma trËn; chuyÓn vÞ ma trËn, ®æi dÊu ma trËn, nghÞch ®¶o ma trËn… VÝ dô 1: NhËp vµo mét ma trËn a (n x k) vµ b (k x m) c¸c phÇn tö thùc. TÝnh ma trËn c = a * b. Víi hai ma trËn a, b ®· cho, tÝch cña chóng lµ ma trËn c cã kÝch thíc n x m víi: k −1

c[i][j] =

∑a[i][t ] * b[t ][ j ] t =0

void main() { int a[50][50], b[50][50], c[50][50]; int n, m, k; clrscr(); cout<<"n="; cin rel="nofollow">>n; cout<<"m="; cin>>m; cout<<"k="; cin>>k; for(int i=0; i>a[i][j]; } Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

6 9

§Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh for(i=0; i>b[i][j]; } for(i=0; i
• Thèng kª trªn ma trËn Mét d¹ng bµi to¸n kh¸ phæ biÕn trªn m¶ng hai chiÒu lµ thèng kª trªn ma trËn. ViÖc thèng kª mét ®¹i lîng nµo ®ã nh»m môc ®Ých kiÓm tra mét tÝnh chÊt nµo ®ã cña m¶ng. Mét vÊn ®Ò khã kh¨n ®Æt ra lµ x¸c ®Þnh chÝnh x¸c xem cÇn thèng kª ®¹i lîng nµo nÕu ®Ò bµi cha nãi râ. VÝ dô 1: NhËp vµo mét ma trËn vu«ng a (n x n) c¸c phÇn tö thùc. Ma trËn a ®îc gäi lµ “hîp lÖ” nÕu tÊt c¶ c¸c phÇn tö trªn dêng chÐo chÝnh ®Òu b»ng 0; c¸c phÇn tö phÝa trªn ®êng chÐo chÝnh ®Òu d¬ng vµ c¸c phÇn tö cßn l¹i ®Òu ©m. H·y kiÓm tra xem ma trËn võa nhËp cã hîp lÖ kh«ng? Ta biÓu diÔn ®iÒu kiÖn ®Ó ma trËn vu«ng a lµ “hîp lÖ” nh sau: ∀i = j, a[i ][ j ] = 0  ∀i < j, a[i ][ j ] > 0 ∀i > j, a[i ][ j ] < 0 

(IV.1)

LÊy phñ ®Þnh cña ®iÒu kiÖn nµy ta thu ®îc ®iÒu kiÖn ®Ó mét ma trËn vu«ng lµ “kh«ng hîp lÖ” nh sau: ∃i = j,a[i ][ j ] ≠ 0 ∃i < j,a[i ][ j ] ≤ 0 ∃i > j,a[i ][ j ] ≥ 0

(IV.2)

Nh vËy viÖc gi¶i bµi to¸n sÏ trë nªn dÔ dµng. Theo ®ã, ta thèng kª c¸c phÇn tö a[i][j] tho¶ m·n ®iÒu kiÖn IV.2. NÕu kh«ng tån t¹i phÇn tö nµo tho¶ m·n IV.2 th× ma trËn lµ hîp lÖ. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

7 0

§Ò c¬ng chi tiÕt thuËt lËp tr×nh void main() { int a[50][50];int n; clrscr(); cout<<"n="; cin>>n; for(int i=0; i>a[i][j]; } int d=0; for(i=0; ij && a[i][j]>=0) d++; } if(d==0) cout<<"Ma tran la hop le !"; else cout<<"Ma tran la khong hop le !"; getch(); }

Kü

VÝ dô 2: Cã n cöa hµng kinh doanh trong m th¸ng. Doanh thu cña mçi cöa hµng trong mçi th¸ng ®Òu ®îc lu tr÷ trong mét ma trËn cã n dßng, m cét. Mét cöa hµng sÏ bÞ ®ãng cöa nÕu doanh thu cña nã gi¶m liªn tiÕp trong m-1 th¸ng (trõ th¸ng ®Çu tiªn). H·y cho biÕt cöa hµng nµo trong sè n cöa hµng trªn sÏ bÞ ®ãng cöa? Bµi to¸n ®îc gi¶i quyÕt b»ng c¸ch duyÖt qua tõng cöa hµng (0 -> n-1). Víi mçi cña hµng i, ta ®Õm sè lÇn gi¶m doanh thu cña nã. NÕu cöa hµng nµo cã ®óng m-1 lÇn gi¶m doanh thu, cöa hµng ®ã sÏ bÞ ®ãng cöa. void main() { int a[50][50];int n,m; clrscr(); cout<<"Nhap so cua hang n="; cin>>n; cout<<"Nhap so thang m="; cin>>m; cout<<"Nhap dt cua tung cua hang-tung thang:"; for(int i=0; i>a[i][j]; } for(i=0; i
7 1

§Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh int d=0; for(j=0; j<m-1; j++) if(a[i][j]>a[i][j+1]) d++; if (d==m-1) cout<<"Cua hang "<
III.1. Mét sè lu ý khi sö dông x©u ký tù X©u ký tù (hay chuçi ký tù) lµ mét d·y liªn tiÕp c¸c ký tù. Nh vËy, vÒ b¶n chÊt x©u ký tù gièng víi mét m¶ng mét chiÒu mµ mçi phÇn tö cña m¶ng lµ mét ký tù. Tuy nhiªn, ngoµi c¸c ®Æc ®iÓm nh m¶ng, x©u ký tù cßn cã ®Æc thï riªng. • Khai b¸o biÕn kiÓu x©u ký tù: Cã hai c¸ch ®Ó khai b¸o biÕn x©u ký tù: - Khai b¸o nh m¶ng: char [<sè ký tù tèi ®a trong x©u>];

(1)

- Khai b¸o nh con trá x©u: char * ; (2)

Víi c¸ch khai b¸o (1), ta cÇn chØ ra ®é dµi tèi ®a cña x©u. §é dµi nµy kh«ng vît qu¸ 256. Víi c¸ch khai b¸o (2), ®é dµi x©u cha x¸c ®Þnh. Nh vËy x©u cã thÓ chøa tèi ®a 256 ký tù. VÝ dô: ta khai b¸o:

char S[30]; char * T;

Ta thu ®îc hai biÕn x©u. BiÕn x©u S chØ chøa ®îc c¸c x©u cã ®é dµi kh«ng qu¸ 30 ký tù. BiÕn x©u T cã ®é dµi cha x¸c ®Þnh vµ nã cã thÓ chøa ®îc x©u cã ®é dµi bÊt kú kh«ng qu¸ 256 ký tù. • NhËp x©u: MÆc dï x©u cã b¶n chÊt gièng m¶ng nh viÖc nhËp x©u kh«ng phøc t¹p nh nhËp m¶ng (kh«ng cÇn sö dông vßng lÆp). Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

7 2

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Th«ng thêng ngêi ta hay sö dông lÖnh gets cho viÖc nhËp x©u: gets( );

VÝ dô: ®Ó nhËp x©u S, ta viÕt: gets(S); Ta còng cã thÓ sö dông lÖnh scanf cho viÖc nhËp x©u hoÆc thËm chÝ lÖnh cin ®Ó nhËp c¸c x©u kh«ng chøa dÊu c¸ch. NÕu sö dông liªn tiÕp nhiÒu lÖnh gets ®Ó nhËp nhiÒu x©u th× gi÷a c¸c lÖnh gets ph¶i xo¸ bé ®Öm b»ng lÖnh fflush(stdin); • XuÊt x©u: T¬ng tù nhËp x©u, viÖc xuÊt x©u còng trë nªn rÊt ®¬n gi¶n b»ng c¸ch sö dông mét trong c¸c lÖnh xuÊt puts, printf, cout. VÝ dô: XuÊt x©u S lªn mµn h×nh, ta viÕt: cout<<S; hoÆc puts(S); … • DuyÖt x©u: ViÖc duyÖt x©u còng t¬ng tù nh duyÖt m¶ng. Tuy nhiªn, ta cÇn sö dông hµm strlen() tr¶ vÒ ®é dµi cña x©u cÇn duyÖt (hµm nµy cã s½n trong th viÖn string.h). Gi¶ sö duyÖt x©u S, ta viÕt: for(i=0; i < strlen(S); i++) { //Th¨m ký tù S[i]; }

• PhÐp g¸n x©u: NÕu a vµ b lµ hai biÕn kh«ng ph¶i kiÓu x©u, ta dÔ dµng g¸n a sang b vµ ngîc l¹i b»ng c¸ch viÕt: a=b; hoÆc b = a; Tuy nhiªn, nÕu a vµ b lµ hai biÕn kiÓu x©u, viÖc sö dông phÐp g¸n trªn lµ kh«ng hîp lÖ. §Ó g¸n x©u b sang x©u a, ta ph¶i sö dông hµm copy x©u: strcpy(a, b);

Mét c¸ch tæng qu¸t, hµm copy x©u ®îc viÕt nh sau: strcpy(S1, S2); Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

7 3

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Trong ®ã, S1 lµ mét biÕn x©u cßn S2 cã thÓ lµ mét biÕn x©u hoÆc mét h»ng x©u. Khi ®ã, x©u ký tù S2 sÏ ®îc g¸n sang S1. VÝ dô: char S1[30], S2[30]; strcpy(S1, “Ha Noi”); //G¸n “Ha Noi” vµo S1 strcpy(S2, S1); //G¸n S1 vµo S2, S1 vµ S2 cã cïng néi dung lµ Ha Noi

• PhÐp so s¸nh x©u: §Ó so s¸nh 2 biÕn x©u, ta còng kh«ng ®îc phÐp sö dông to¸n tö so s¸nh (==) mµ sö dông hµm so s¸nh x©u: int strcmp(S1, S2); Hµm nµy sÏ tr¶ vÒ gi¸ trÞ b»ng 0 nÕu hai x©u b»ng nhau; gi¸ trÞ d¬ng nÕu S1 > S2 vµ gi¸ trÞ ©m nÕu S1 <S2. VÝ dô: char S1[30], S2[30]; gets(S1); fflush(stdin); gets(S2); if (strcmp(S1, S2)==0) cout<< “ Xau S1 bang xau S2”; else cout<< “Xau S1 khac xau S2”;

Hai hµm strcpy vµ strcmp cã s½n trong th viÖn string.h. • LÊy m· ASCII cña mét ký tù trong x©u: Mét sè bµi to¸n ta cÇn lÊy m· ASCII cña c¸c ký tù. C«ng viÖc nµy trong C++ ®îc thùc hiÖn mét c¸ch dÔ dµng mµ kh«ng cÇn sö dông tíi hµm lÊy m· ASCII. §Ó lÊy m· ASCII cña mét ký tù S[i], ta chØ cÇn ®Æt to¸n tö Ðp kiÓu (int) ngay tríc ký tù ®ã: VÝ dô: Víi S lµ mét x©u, ®¬ng nhiªn S[i] lµ mét ký tù cña x©u. Hai c©u lÖnh sau sÏ cho kÕt qu¶ kh¸c nhau: cout<<S[i];

(1)

cout<<(int) S[i];

(2)

C©u lÖnh (1) in ra mµn h×nh ký tù S[i], cßn c©u lÖnh (2) chØ in ra m· ASCII cña ký tù ®ã. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

7 4

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

• ChuyÓn m· ASCII thµnh ký tù: T¬ng tù nh trªn, viÖc chuyÓn m· ASCII thµnh ký tù còng ®îc thùc hiÖn dÔ dµng b»ng to¸n tö Ðp kiÓu (char). Gi¶ sö muèn in ra mµn h×nh ký tù cã m· 65 (ch÷ A), ta chØ cÇn viÕt: cout<<(char) 65;

Khi ®ã ký tù ‘A’ sÏ ®îc in ra mµn h×nh do nã cã m· ASCII lµ 65. III.2. Mét sè bµi to¸n ®Æc thï trªn x©u Ngoµi c¸c bµi to¸n t×m kiÕm, s¾p xÕp nh trªn mét m¶ng th«ng thêng, c¸c bµi to¸n trªn x©u cßn ®îc më réng do tÝnh ®Æc thï cña x©u. Sau ®©y lµ mét sè d¹ng phæ biÕn: - Thèng kª trªn x©u: ch¼ng h¹n thèng kª sè ký tù, sè tõ, sè c©u, sè dÊu chÊm,…. - ChuÈn ho¸ x©u: C¾t c¸c ký tù trèng ë hai ®Çu x©u, xo¸ bít dÊu c¸ch nÕu cã 2 dÊu c¸ch liÒn nhau trong th©n x©u. Tríc dÊu chÊm c©u kh«ng cã dÊu c¸ch, sau dÊu chÊm c©u cã 1 dÊu c¸ch; ký tù ®Çu c©u viÕt hoa… VÝ dô 1: NhËp vµo mét x©u ký tù bÊt kú. Mét tõ trong x©u lµ mét d·y liªn tiÕp, dµi nhÊt c¸c ký tù kh¸c ký tù trèng. H·y cho biÕt x©u võa nhËp cã bao nhiªu tõ. DÔ thÊy víi mét x©u cha chuÈn th× sè tõ kh«ng tû lÖ thuËn víi sè dÊu c¸ch. Do vËy viÖc ®Õm sè dÊu c¸ch lµ kh«ng phï hîp. Thay vµo ®ã, ta ®i ®Õm sè lÇn b¾t ®Çu cña mét tõ, ®ã lµ sè lÇn S[i] b»ng dÊu c¸ch vµ S[i+1] kh¸c dÊu c¸ch. Tuy nhiªn, trong trêng hîp S[0] kh¸c dÊu c¸ch th× ta vÉn ®Õm thiÕu 1 tõ ®Çu tiªn nªn ph¶i t¨ng biÕn ®Õm lªn 1. void main() { char S[30]; cout<<"S="; gets(S); int d=0; for(int i=0; i<strlen(S)-1; i++) Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

7 5

§Ò c¬ng chi tiÕt thuËt lËp tr×nh if(S[i]==' ' && S[i+1] !=' ') d++;

Kü

if(S[0]!=' ') d++; cout<<"Xau co: "<
VÝ dô 2: NhËp mét x©u ký tù S bÊt kú. H·y ®Õm sè lÇn xuÊt hiÖn cña tÊt c¶ c¸c ch÷ c¸i cã trong S. NÕu kh«ng ph©n biÖt ch÷ hoa vµ ch÷ thêng th× b¶ng m· ASCII cã tæng céng 26 ch÷ c¸i. Trêng hîp tåi nhÊt lµ c¶ 26 ch÷ c¸i nµy ®Òu xuÊt hiÖn trong S. Do vËy ta sö dông 26 biÕn ®Õm (m¶ng d gåm 26 phÇn tö nguyªn). NÕu ta gÆp mét ký tù nµo ®ã trong S th× biÕn ®Õm t¬ng øng cña nã sÏ ®îc t¨ng lªn 1. B¶ng sau chØ ra sù t¬ng øng gi÷a biÕn ®Õm vµ ký tù: Ch÷ c¸i hoa (m· ASCII) A (65) B (66) C (67) … S[i] ((int) S[i])

BiÕn ®Õm t¬ng øng d[0] = d[65-65] d[1] = d[66-65] d[2] = d[67-65] … d[(int) S[i]-65]

Ch÷ c¸i thêng (m· ASCII) a (97) b (98) c (99) … S[i] ((int) S[i])

BiÕn ®Õm t¬ng øng d[0] = d[97- 97] d[1] = d[98-97] d[2] = d[99-97] … d[(int) S[i]-97]

Nh vËy ta cÇn chia hai trêng hîp: Trêng hîp thø nhÊt: nÕu ch÷ c¸i S[i] cã m· ASCII nhá h¬n 97 th× S[i] sÏ lµ ch÷ c¸i hoa. M· ASCII cña nã lµ k = (int) S[i]. Khi ®ã ta cÇn t¨ng biÕn ®Õm d[k-65]. Trêng hîp thø 2: nÕu ch÷ c¸i S[i] cã m· ASCII lín h¬n hoÆc b»ng 97 th× S[i] sÏ lµ ch÷ c¸i thêng. M· ASCII cña nã lµ k = (int) S[i]. Khi ®ã ta cÇn t¨ng biÕn ®Õm d[k-97].

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

7 6

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

KÕt thóc qu¸ tr×nh ®Õm, ta duyÖt l¹i m¶ng d. NÕu thÊy d[i] kh¸c 0 th× ®ã chÝnh lµ sè lÇn xuÊt hiÖn cña ch÷ c¸i (char) (i+65) hoÆc (char) (i+97). void main() { char S[30]; cout<<"S="; gets(S); int d[26]; for(int i=0; i<26; i++) d[i]=0; for(i=0; i<strlen(S); i++) { if((int)S[i] <97) d[(int)S[i]-65]++; else d[(int)S[i]-97]++; } for(i=0; i<26; i++) if(d[i]>0) cout<<"ky tu "<<(char)(i+97)<<" xuat hien "<
getch(); }

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

7 7

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Ch¬ng V. Kü thuËt lËp tr×nh dïng con trá I. Tæng quan vÒ con trá

I.1. Kh¸i niÖm vµ c¸ch khai b¸o - Mçi byte trong bé nhí ®Òu ®îc ®¸nh ®Þa chØ, lµ mét con sè hÖ thËp lôc ph©n. §Þa chØ cña biÕn lµ ®Þa chØ cña byte ®Çu tiªn trong vïng nhí dµnh cho biÕn. Th«ng thêng, khi ta khai b¸o mét biÕn, m¸y tÝnh sÏ cÊp ph¸t mét « nhí víi kÝch thíc t¬ng øng trong vïng 64Kb dµnh cho viÖc khai b¸o biÕn (m« h×nh tiny). ¤ nhí nµy cã thÓ dïng ®Ó lu tr÷ c¸c gi¸ trÞ kh¸c nhau, gäi lµ “gi¸ trÞ cña biÕn”. Bªn c¹nh ®ã, mçi biÕn cßn cã mét ®Þa chØ lµ mét con sè hÖ thËp lôc ph©n. Con trá (hay biÕn con trá) lµ mét biÕn ®Æc biÖt dïng ®Ó chøa ®Þa chØ cña c¸c biÕn kh¸c.

Nh vËy, con trá còng gièng nh biÕn thêng (tøc còng lµ mét « nhí trong bé nhí) nhng ®iÓm kh¸c biÖt lµ nã kh«ng thÓ chøa c¸c gi¸ trÞ th«ng thêng mµ chØ dïng ®Ó chøa ®Þa chØ cña biÕn. Con trá còng cã nhiÒu kiÓu (nguyªn, thùc, ký tù…). Con trá thuéc kiÓu nµo chØ chøa ®Þa chØ cña biÕn thuéc kiÓu ®ã.

Có ph¸p khai b¸o: * ;

Trong ®ã: cã thÓ lµ mét trong c¸c kiÓu chuÈn cña C++ hoÆc kiÓu tù ®Þnh nghÜa. ®îc ®Æt tuú ý theo quy íc ®Æt tªn trong C++. VÝ dô: dßng khai b¸o int a, *p; float b, *q; khai b¸o a vµ p kiÓu nguyªn, b vµ q kiÓu thùc, trong ®ã, p vµ q lµ hai con trá. Khi ®ã, p cã thÓ chøa ®Þa chØ cña a vµ q cã thÓ chøa ®Þa chØ cña b. I.2. Mét sè thao t¸c c¬ b¶n trªn con trá • LÊy ®Þa chØ cña biÕn ®Æt vµo con trá: Gi¶ sö a lµ mét biÕn nguyªn vµ p lµ mét con trá cïng kiÓu víi a. §Ó lÊy ®Þa chØ cña a ®Æt vµo p ta viÕt: Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

7 8

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

P = &a; To¸n tö & cho phÐp lÊy ®Þa chØ cña mét biÕn bÊt kú. Khi ®ã, ta nãi p ®ang trá tíi a. Mét c¸ch tæng qu¸t, ®Ó lÊy ®Þa chØ cña mét biÕn ®Æt vµo con trá cïng kiÓu, ta viÕt: = & ;

• PhÐp g¸n con trá cho con trá: NÕu p vµ q lµ hai con trá cïng kiÓu, ta cã thÓ g¸n p sang q vµ ngîc l¹i, ta viÕt: p = q; hoÆc q = p; Khi ®ã, ®Þa chØ ®ang chøa trong con trá ë vÕ ph¶i sÏ ®îc ®Æt vµo con trá ë vÕ tr¸i vµ ta nãi hai con trá cïng trá tíi mét biÕn. VÝ dô: int a, *p, *q; p=&a; //cho p trá tíi a q = p; //p vµ q cïng trá tíi a

• Sö dông con trá trong biÓu thøc: Khi sö dông biÕn con trá trong biÎu thøc th× ®Þa chØ ®ang chøa trong con trá sÏ ®îc sö dông ®Ó tÝnh to¸n gi¸ trÞ cña biÓu thøc. NÕu muèn lÊy gi¸ trÞ cña biÕn mµ con trá ®ang trá tíi ®Ó sö dông trong biÓu thøc th× ta thªm dÊu * vµo ®»ng tríc tªn biÕn con trá. VÝ dô: int a=5, b=3, *p, *q; p=&a; q=&b; int k = p + q; int t = *p + *q;

Khi ®ã, hai biÕn k vµ t cã gi¸ trÞ kh¸c nhau. Trong biÓu thøc k, ®Þa chØ ®ang chøa trong con trá p vµ q sÏ ®îc céng l¹i vµ ®Æt vµo k; ngîc l¹i t sÏ cã gi¸ trÞ = a + b = 8. II. Con trá - m¶ng vµ hµm

II.1. Con trá vµ m¶ng • Con trá lµ m¶ng Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

7 9

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Khi khai b¸o m¶ng, ta ®îc cÊp ph¸t mét d·y c¸c « nhí liªn tiÕp, cïng kiÓu ®îc gäi lµ c¸c phÇn tö cña m¶ng. §iÒu ®Æc biÖt lµ tªn m¶ng chÝnh lµ mét con trá trá tíi phÇn tö ®Çu tiªn cña m¶ng. Nh vËy tªn m¶ng n¾m gi÷ ®Þa chØ cña « nhí ®Çu tiªn trong m¶ng vµ do vËy, ta cã thÓ sö dông tªn m¶ng ®Ó qu¶n lý toµn bé c¸c phÇn tö cña m¶ng. VÝ dô: gi¶ sö ta khai b¸o: int a[10]; Khi ®ã, 10 « nhí ®îc cÊp ph¸t cho m¶ng a nh sau: C¸c phÇn tö lÇn lît lµ a[0], a[1], a[2],….a[9]. Tuy nhiªn, a lµ mét « nhí riªng biÖt vµ « nhí nµy ®ang chøa ®Þa chØ cña a[0] (a trá tíi a[0]): a

DÔ thÊy cã sù t¬ng øng sau: a a+1 a+2 … a+i

lµ ®Þa chØ cña a[0] lµ ®Þa chØ cña a[1] lµ ®Þa chØ cña a[2] lµ ®Þa chØ cña a[i]

Nh vËy th× *a *(a+1) *(a+2) … *(a+i)

lµ a[0] lµ a[1] lµ a[2] lµ a[i]

VËy ta cã thÓ sö dông c¸ch viÕt thø hai cho c¸c phÇn tö cña m¶ng. Thay v× viÕt a[i], ta cã thÓ viÕt *(a+i) • Con trá lµ m¶ng Mét con trá p bÊt kú còng t¬ng ®¬ng víi mét m¶ng mét chiÒu. ThËt vËy, gi¶ sö con trá p ®ang chøa ®Þa chØ cña mét « nhí a nµo ®ã, khi ®ã ta cã thÓ sö dông p ®Ó qu¶n lý mét d·y c¸c « nhí liªn tiÕp b¾t ®Çu tõ a. Nh vËy: p p+1

lµ ®Þa chØ cña a lµ ®Þa chØ cña « nhí ngay sau a

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

8 0

§Ò c¬ng chi tiÕt thuËt lËp tr×nh … p+i

Kü

lµ ®Þa chØ cña « nhí thø i kÓ tõ a. pap+1p+2

VËy, víi p lµ con trá th× ta cã thÓ coi nã nh m¶ng mét chiÒu vµ ®Ó truy cËp tíi phÇn tö thø i cña p ta cã thÓ viÕt *(p+i) hoÆc thËm chÝ viÕt p[i]. II.2. Con trá vµ hµm • Ph©n lo¹i ®èi sè Mét hµm trong C++ cã thÓ kh«ng tr¶ vÒ gi¸ trÞ nµo mµ ®¬n gi¶n chØ thùc hiÖn mét c«ng viÖc nµo ®ã (hµm void). Tuy nhiªn, víi nh÷ng hµm cã gi¸ trÞ tr¶ vÒ, gi¸ trÞ ®ã sÏ ®îc ®Æt vµo tªn hµm (tr¶ vÒ th«ng qua tªn hµm) b»ng lÖnh return ;. LÖnh return nµy t¬ng tù nh viÖc ta g¸n = ; Víi mét hµm, tªn hµm chØ cã mét nªn hµm chØ cã thÓ tr¶ vÒ duy nhÊt mét gi¸ trÞ th«ng qua tªn hµm. Tuy nhiªn, cã nh÷ng hµm ®ßi hái ph¶i tr¶ vÒ nhiÒu h¬n mét gi¸ trÞ, ch¼ng h¹n hµm gi¶i ph¬ng tr×nh bËc hai. Hµm nµy cã c¸c ®èi vµo lµ c¸c hÖ sè a, b, c cña ph¬ng tr×nh bËc hai vµ nÕu cã nghiÖm th× hµm sÏ tr¶ vÒ 2 nghiÖm x1 vµ x2. a b c

GPTB 2

x1 x2

NÕu viÕt hµm theo kiÓu cã gi¸ trÞ tr¶ vÒ nh c¸ch th«ng thêng (tr¶ vÒ qua tªn hµm) ta sÏ gÆp khã kh¨n do mét tªn hµm kh«ng thÓ chøa cïng lóc hai gi¸ trÞ x1 vµ x2. §Ó gi¶i quyÕt khã kh¨n ®ã, ta sö dông kü thuËt “®èi ra” cho hµm. Theo ®ã, c¸c ®èi cña hµm ®îc chia lµm hai lo¹i: - §èi vµo: lµ c¸c biÕn mang gi¸ trÞ ®Çu vµo cho hµm - §èi ra: lµ c¸c biÕn chøa gi¸ trÞ ®Çu ra cña hµm.

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

8 1

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

NÕu hµm tr¶ vÒ nhiÒu gi¸ trÞ th× c¸c gi¸ trÞ ®ã thêng kh«ng ®îc ®Æt vµo tªn hµm (qua lÖnh return) mµ ®îc tr¶ vÒ qua ®èi ra. NÕu ®èi ra lµ biÕn thêng th× khi sö dông hµm, ta chØ cã thÓ truyÒn tham sè díi d¹ng tham trÞ. §iÒu ®ã cã nghÜa lµ sau khi ra khái hµm, c¸c tham sè nµy l¹i quay trë vÒ gi¸ trÞ ban ®Çu nh tríc khi nã ®îc truyÒn vµo hµm. Nh vËy chóng kh«ng thùc hiÖn ®îc “phËn sù” cña m×nh lµ mang c¸c gi¸ trÞ ®Çu ra ra khái hµm. Do vËy, chØ cã thÓ sö dông c¸ch truyÒn tham sè theo kiÓu tham chiÕu, tøc lµ: C¸c ®èi ra b¾t buéc ph¶i lµ con trá.

VÝ dô 1: viÕt hµm tr¶ vÒ c¸c nghiÖm (nÕu cã) cña ph¬ng tr×nh bËc hai. Hµm sau sÏ tr¶ vÒ gi¸ trÞ -1 qua tªn hµm nÕu ph¬ng tr×nh bËc hai v« nghiÖm. Ngîc l¹i, nã tr¶ vÒ gi¸ trÞ +1. Khi ®ã, hai nghiÖm ®îc ®Æt vµo hai ®èi ra. Nh vËy hµm cã 3 ®èi vµo vµ 2 ®èi ra ®ång thêi hµm tr¶ vÒ gi¸ trÞ nguyªn qua tªn hµm (hµm int): int GPTB2(float a,float b,float c,float *x1,float *x2) { float DT=b*b-4*a*c; if(DT<0) return -1; else { *x1=(-b+sqrt(DT))/(2*a); *x2=(-b-sqrt(DT))/(2*a); return 1; } } void main() { float a,b,c; cout<<"a="; cin>>a; cout<<"b="; cin>>b; cout<<"c="; cin>>c; float x1, x2; int k=GPTB2(a,b,c,&x1,&x2); if(k==-1) cout<<"Phuong trinh vo nghiem"; else cout<<"Pt co 2 nghiem x1="<<x1<<" x2="<<x2; getch(); Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

8 2

§Ò c¬ng chi tiÕt thuËt lËp tr×nh }

Kü

VÝ dô 2: ViÕt hµm tr¶ vÒ ®ång thêi 3 gi¸ trÞ lµ tæng c¸c sè ch½n, tæng c¸c sè lÎ vµ tæng c¸c sè chia hÕt cho 3 trong mét m¶ng n phÇn tö nguyªn. C¸c ®èi vµo: m¶ng nguyªn a, kÝch thíc thùc tÕ cña m¶ng n. C¸c ®èi ra: T1- tæng c¸c sè ch½n trong m¶ng; T2- tæng c¸c sè lÎ trong m¶ng; T3- tæng c¸c sè chia hÕt 3 trong m¶ng. void TinhTong(int *a, int n, int *T1, int *T2, int *T3) { *T1=*T2=*T3=0; for(int i=0; i
• Gi¶i phãng bé nhí ®ang chiÕm gi÷ bëi con trá Khi kh«ng sö dông tíi con trá n÷a, nÕu ta kh«ng gi¶i phãng vïng nhí ®· cÊp ph¸t cho con trá th× hiÓn nhiªn vïng nhí nµy vÉn bÞ nã chiÕm gi÷ vµ kh«ng thÓ cÊp ph¸t cho c¸c con trá kh¸c (nÕu cã). §Æc biÖt trong c¸c hµm cã cÊp ph¸t bé nhí ®éng cho con trá, khi mµ viÖc gäi hµm x¶y ra thêng xuyªn nh-

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

8 7

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

ng khi kÕt thóc hµm ta kh«ng gi¶i phãng vïng nhí ®· cÊp ph¸t th× bé nhí sÏ bÞ chiÕm dông mét c¸ch nhanh chãng. Gi¶i phãng vïng nhí ®ang bÞ con trá chiÕm gi÷ ®¬n gi¶n lµ xo¸ ®Þa chØ ®ang lu tr÷ trong con trá ®ã. ViÖc nµy sÏ “c¾t ®øt” mèi liªn hÖ gi÷a con trá vµ vïng nhí mµ nã qu¶n lý. §Ó lµm nh vËy, h·y sö dông lÖnh free. Có ph¸p: free();

VÝ dô: Gi¶ sö con tro p ®· ®îc cÊp ph¸t bé nhí. Muèn gi¶i phãng nã, ta viÕt: free(p);

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

8 8

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Mét sè Bµi tËp thùc hµnh m«n kü thuËt lËp tr×nh HÖ: §¹i häc Ch¬ng I: më ®Çu 1. NhËp hai sè nguyªn, tÝnh tæng, hiÖu, tÝch, th¬ng, ®ång d. 2. NhËp mét sè nguyªn <= 9999, in ra mµn h×nh c¸ch ®äc sè nguyªn ®ã (VD: sè 1523 ®äc lµ: 1 ngµn 5 tr¨n 2 chôc 3 ®¬n vÞ). NhËn xÐt vÒ c¸ch lµm võa ¸p dông nÕu sè nguyªn nhËp vµo kh«ng ®îc giíi h¹n? Thö ®a ra ph¬ng ¸n ®äc sè hoµn toµn? (VÝ dô: víi sè 1304 ®äc lµ: mét ngh×n ba tr¨m linh t?) 3. ViÕt ch¬ng tr×nh tÝnh gi¸ trÞ biÓu thøc: F(x) = (x2+e|x|+sin2(x))/ 5

x 2 +1

Ch¬ng II: c¸c cÊu tróc ®iÒu khiÓn 1. ViÕt ch¬ng tr×nh nhËp vµo mét sè nguyªn n. KiÓm tra xem n ch½n hay lÎ. 2. ViÕt ch¬ng tr×nh gi¶i vµ biÖn luËn ph¬ng tr×nh bËc nhÊt theo hai hÖ sè a, b nhËp tõ bµn phÝm. 3. ViÕt ch¬ng tr×nh gi¶i vµ biÖn luËn ph¬ng tr×nh bËc hai víi c¸c hÖ sè a, b, c nhËp tõ bµn phÝm. 4. ViÕt ch¬ng tr×nh gi¶i vµ biÖn luËn hÖ ph¬ng tr×nh bËc nhÊt 2 Èn b»ng ph¬ng ph¸p ®Þnh thøc? 5. ViÕt ch¬ng tr×nh nhËp vµo sè tiÒn ph¶i tr¶ cña kh¸ch hµng. In ra sè tiÒn khuyÕn m¹i víi quy ®Þnh: nÕu sè tiÒn ph¶i tr¶ thuéc [200.000, 300.000) th× khuyÕn m¹i 20%. NÕu sè tiÒn ph¶i tr¶ tõ 300.000 trë lªn th× khuyÕn m¹i 30%. Cßn l¹i th× kh«ng khuyÕn m¹i. 6. ViÕt ch¬ng tr×nh nhËp vµo ®iÓm tæng kÕt cña mét häc sinh vµ in ra xÕp lo¹i cho häc sinh ®ã víi quy ®Þnh: - XÕp lo¹i giái nÕu tæng ®iÒm tõ 8.00 trë lªn. - XÕp lo¹i kh¸ nÕu tæng ®iÓm tõ 7.00 tíi cËn 8.00. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

8 9

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

- XÕp lo¹i trung b×nh nÕu tæng ®iÓm tõ 5.00 tíi cËn 7.00. - Cßn l¹i, xÕp lo¹i yÕu. ------------------7. ViÕt ch¬ng tr×nh nhËp vµo mét th¸ng cña mét n¨m bÊt kú (d¬ng lÞch), sau ®ã in ra sè ngµy cã trong th¸ng. ------------------8. ViÕt ch¬ng tr×nh tÝnh n!. H·y t×m c¸c c¸ch kh¸c nhau ®Ó gi¶i quyÕt bµi to¸n. 9. NhËp vµo mét sè nguyªn n. TÝnh tæng c¸c sè nguyªn tè trong ®o¹n [n, 2n]. §¸nh gi¸ ®é phøc t¹p cña gi¶i thuËt trong trêng hîp tåi nhÊt? 10. ViÕt ch¬ng tr×nh nhËp vµo mét sè nguyªn n, sau ®ã tÝnh gi¸ trÞ biÓu thøc: S=

1+

1 1 1 + + ... + 2 3 n

11. ViÕt ch¬ng tr×nh nhËp vµo mét sè nguyªn n, sau ®ã tÝnh gi¸ trÞ biÓu thøc 1 1  1 1 1 + + 2 + 3 + ... + n nÕun ch½n 2 F=  2 2 2 2  n +1 nÕun lÎ 

12. ViÕt ch¬ng tr×nh nhËp vµo mét sè thùc x vµ sè nguyªn n, sau ®ã tÝnh gi¸ trÞ biÓu thøc:   S=   

x 2 x3 xn x+ + + ... + n −1 3 32 3 0 nÕu nlÎ

nÕunch½n

13. ViÕt ch¬ng tr×nh nhËp vµo mét sè nguyªn n trong kho¶ng [10, 20] (nÕu sè nhËp vµo kh«ng thuéc kho¶ng ®ã th× yªu cÇu nhËp l¹i tíi khi tho¶ m·n). Sau ®ã tÝnh tæng c¸c sè liªn tiÕp tõ 1 tíi n. 14. ViÕt ch¬ng tr×nh nhËp vµo mét sè nguyªn d¬ng n, sau ®ã tÝnh tæng c¸c gi¸ trÞ ch½n, lÎ thuéc ®o¹n [1, n]. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

9 0

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

15. ViÕt ch¬ng tr×nh nhËp vµo c¸c sè nguyªn d¬ng n, m, sau ®ã in ra: - Tæng c¸c sè ch½n d¬ng trong kho¶ng [- n, m]. - Tæng c¸c sè ch½n ©m trong kho¶ng [- n, m]. - Tæng c¸c sè lÎ d¬ng trong kho¶ng [- n, m]. - Tæng c¸c sè lÎ ©m trong kho¶ng [- n, m]. H·y thùc hiÖn ch¬ng tr×nh b»ng hai c¸ch vµ ®¸nh gi¸ mçi c¸ch. 16. ViÕt ch¬ng tr×nh nhËp vµo mét sè nguyªn n, sau ®ã tÝnh tæng c¸c sè nguyªn tè thuéc ®o¹n [1..n]. Cho biÕt cã bao nhiªu sè nguyªn tè thuéc ®o¹n ®ã. 17. Dïng while (sau ®ã viÕt l¹i, dïng do/ while) ®Ó viÕt ch¬ng tr×nh in ra sè lµ luü thõa 2 bÐ nhÊt lín h¬n 1000. 18. Cho d·y sè x[] = { 12.3, -45.4, 12, 15, 10.1, 12.5}. ViÕt ch¬ng tr×nh ®¶o ngîc d·y sè trªn. §¸nh gi¸ ®é phøc t¹p cña gi¶i thuËt ®¶o ngîc d·y sè bÊt kú cã n phÇn tö trong trêng hîp tåi nhÊt? 19. ViÕt ch¬ng tr×nh t×m sè nguyªn d¬ng n nhá nhÊt tho¶ m·n: 1 + 2 + 3 + … + n > 1000. 20. §Ó tÝnh c¨n bËc hai cña mét sè d¬ng a, ta sö dông c«ng thøc lÆp sau: x(0) = a; x(n+1) = (x(n) * x(n) + a)/ (2* x(n)) víi n >=0. Qu¸ tr×nh lÆp kÕt thóc khi abs((x(n+1) – x(n))/x(n)) < ε . vµ khi ®ã x(n+1) ®îc xem lµ gi¸ trÞ gÇn ®óng cña sqrt(a). ViÕt ch¬ng tr×nh tÝnh c¨n bËc hai cña a víi ®é chÝnh x¸c ε = 0.00001. 21. LËp tr×nh ®Ó tÝnh sin(x) víi ®é chÝnh x¸c ε = 0.00001 theo c«ng thøc : sin(x) = x – x3/3! + x5/ 5! + …+ (-1)nx(2n+1)/ (2n+1)!. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

9 1

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

22.

Kü

LËp tr×nh ®Ó tÝnh tæ hîp chËp m cña n theo c«ng thøc: C(m, n) = (n(n-1)…(n-m+1))/ m!. Ch¬ng III: kü thuËt lËp tr×nh ®¬n thÓ

1. ViÕt hµm kiÓm tra xem mét sè nguyªn n cã ph¶i lµ sè nguyªn tè kh«ng. Sau ®ã, trong ch¬ng tr×nh chÝnh, nhËp vµo mét sè nguyªn n, kiÓm tra tÝnh nguyªn tè cña sè n vµ th«ng b¸o ra mµn h×nh? Më réng bµi to¸n b»ng c¸ch sö dông hµm trªn ®Ó tÝnh tæng c¸c sè nguyªn tè trong ®o¹n [1, n]? 2. ViÕt hµm tÝnh n! sau ®ã, trong ch¬ng tr×nh chÝnh, nhËp vµo mét sè nguyªn n vµ tÝnh, in ra kÕt qu¶ cña biÓu thøc: S=

n!+1 ( n +1)!

3. ViÕt hµm tÝnh gi¸ trÞ biÓu thøc F (trong bµi sè 10 ch¬ng II) víi ®èi vµo lµ n. Sau ®ã, trong ch¬ng tr×nh chÝnh, nhËp vµo hai sè a, b, tÝnh vµ in ra mµn h×nh kÕt qu¶ cña biÓu thøc: S=

F ( a ) − F (b) F ( a − b)

4. ViÕt hµm s¾p xÕp mét chuçi ký tù (tõ A->Z). Sau ®ã, trong ch¬ng tr×nh chÝnh, nhËp vµo mét x©u ký tù bÊt kú, in x©u ®· ®îc s¾p lªn mµn h×nh. 5. ViÕt ch¬ng tr×nh gi¶i ph¬ng tr×nh trïng ph¬ng : ax4 + bx2 + c = 0. 6. USCLN cña hai sè a, b ®îc ®Þnh nghÜa nh sau: USCLN(a, b) = a nÕu b = 0 = USCLN(b, a%b) nÕu b <> 0 ViÕt hµm ®Ö quy t×m USCLN cña hai sè nguyªn a, b. Trong ch¬ng tr×nh chÝnh, nhËp vµo hai sè nguyªn a, b. T×m vµ in USCLN cña hai sè ®ã lªn mµn h×nh. 7. ViÕt hµm t×m kiÕm ®Ö quy trªn mét d·y sè nguyªn ®· ®îc s¾p. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

9 2

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

8. C¸c sè Fibonacci F[i] ®îc ®Þnh nghÜa ®Ö quy nh sau: F[0] =1; F[1] =1; F[i] = F[i-1] + F[i-2] (víi i > 1); (VD: 1, 1, 2, 3, 5, 8, 13…) ViÕt hµm ®Ö quy t×m sè Fibonacci thø n trong d·y. (Bµi to¸n nµy cã thÓ ph¸t biÓu c¸ch kh¸c nh sau: cã mét cÆp thá con gåm 1 thá ®ùc vµ mét thá c¸i. Thá con b¾t ®Çu ®Î sau khi nu«i ®îc hai th¸ng. Mçi lÇn ®Î chØ ®îc 1 cÆp (còng gåm mét thá ®ùc vµ mét thá c¸i). Mçi th¸ng thá ®Ó mét lÇn. Hái sau 7 (hoÆc 8, hoÆc 9…) th¸ng ta cã mÊy ®«i thá – gi¶ ®Þnh trêng hîp lý tëng thá kh«ng bÞ chÕt vµ ®«i nµo còng ®Î). 9. ViÕt hµm ®Ö quy tÝnh n!. 10. ViÕt hµm ®Ö quy tÝnh f(x, n) = xn. 11. ViÕt hµm ®Ö quy tÝnh gi¸ trÞ cña biÓu thøc: F(x, n) = 2xn/ n! 12. ViÕt hµm ®Ö quy tÝnh sè ch÷ sè trong 1 sè nguyªn? (vÝ dô sè 1423 cã 4 ch÷ sè) 13. ViÕt hµm ®Ö quy t×m sè lín nhÊt trong mét d·y sè n phÇn tö? Ch¬ng IV: kü thuËt lËp tr×nh dïng m¶ng. 1. ViÕt ch¬ng tr×nh nhËp vµo mét m¶ng n sè nguyªn, s¾p xÕp m¶ng theo chiÒu t¨ng dÇn, in kÕt qu¶ lªn mµn h×nh. 2. ViÕt ch¬ng tr×nh nhËp vµo mét m¶ng n sè nguyªn, tÝnh tæng c¸c phÇn tö ch½n, c¸c phÇn tö lÎ, c¸c phÇn tö chia hÕt cho 3 vµ in kÕt qu¶ ra mµn h×nh. 3. ViÕt ch¬ng tr×nh nhËp vµo mét d·y sè thùc, t×m phÇn tö lín nhÊt (t¬ng tù, t×m phÇn tö nhá nhÊt) cña d·y vµ in kÕt qu¶ ra mµn h×nh. 4. ViÕt ch¬ng tr×nh nhËp vµo mét d·y sè nguyªn. TÝnh tæng cña c¸c sè nguyªn tè trong d·y vµ in kÕt qu¶ ra mµn h×nh. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

9 3

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

5. ViÕt ch¬ng tr×nh nhËp vµo mét d·y sè nguyªn vµ mét sè nguyªn c. §Õm sè lÇn xuÊt hiÖn vµ vÞ trÝ xuÊt hiÖn cña c trong d·y. In c¸c kÕt qu¶ ra mµn h×nh. 6. ViÕt ch¬ng tr×nh nhËp vµo mét d·y n sè nguyªn. TÝnh trung b×nh céng cña d·y vµ in kÕt qu¶ tÝnh ®îc ra mµn h×nh. 7. Mét d·y sè a gäi lµ ®îc s¾p t¨ng nÕu a[i] <= a[i+1] víi mäi i; D·y gäi lµ ®îc s¾p gi¶m nÕu a[i] >= a[i+1] víi mäi i; D·y gäi lµ ®îc s¾p t¨ng ngÆt nÕu a[i] < a[i+1] víi mäi i; D·y gäi lµ ®îc s¾p gi¶m ngÆt nÕu a[i] > a[i+1] víi mäi i; ViÕt ch¬ng tr×nh nhËp mét d·y n sè thùc, kiÓm tra xem d·y ®· ®îc s¾p hay cha. NÕu ®· ®îc s¾p th× s¾p theo trËt tù nµo (t¨ng, t¨ng ngÆt, gi¶m, gi¶m ngÆt?). NÕu cha th× s¾p xÕp d·y theo chiÒu t¨ng dÇn. In c¸c kÕt qu¶ lªn mµn h×nh. 8. Cho hai vector x(x1, x2…xn) vµ y(y1, y2…yn). ViÕt ch¬ng tr×nh in ra TÝch v« híng cña hai vector trªn. 9. Cho hai m¶ng a vµ b cã c¸c phÇn tö ®Òu ®· ®îc s¾p t¨ng. LËp ch¬ng tr×nh trén hai m¶ng trªn ®Ó thu ®îc mét m¶ng thø 3 còng s¾p theo thø tù t¨ng (b»ng 2 c¸ch). H·y ®a ra ph¬ng ¸n c¶i tiÕn 2 c¸ch trªn? 10. Cho mét m¶ng a gåm n phÇn tö nguyªn sao cho a[i] thuéc [1, n] vµ kh«ng cã gi¸ trÞ nµo xuÊt hiÖn qu¸ 1 lÇn trong m¶ng. ChØ b»ng 1 vßng lÆp (For(int i=0; i
9 4

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

lÖ, biÓu thøc )( )) hoÆc ((( ))…lµ kh«ng hîp lÖ. H·y cho biÕt biÓu thøc võa nhËp cã hîp lÖ kh«ng? 13. Mét m¶ng a gåm n phÇn tö nguyªn ®îc gäi lµ hîp lÖ nÕu tÊt c¶ c¸c phÇn tö cã chØ sè lÎ ®Òu nguyªn tè. H·y kiÓm tra tÝnh hîp lÖ cña m¶ng a? 14. NhËp vµo mét m¶ng a chØ gåm c¸c phÇn tö 0 hoÆc 1. Mét ®êng ®i trªn a lµ mét d·y liªn tiÕp c¸c phÇn tö 1. §é dµi cña ®êng ®i lµ sè phÇn tö trªn ®êng ®i ®ã. H·y cho biÕt: - M¶ng võa nhËp cã bao nhiªu ®êng ®i? - M¶ng võa nhËp cã ®êng ®i dµi nhÊt xuÊt ph¸t tõ vÞ trÝ nµo? - §é dµi cña ®êng ®i dµi nhÊt trong m¶ng? - §é dµi trung b×nh cña c¸c ®êng ®i trong m¶ng? 12. ViÕt ch¬ng tr×nh nhËp vµo mét ma trËn m x n sè nguyªn. T×m c¸c phÇn tö lín nhÊt vµ bÐ nhÊt trªn c¸c dßng (t¬ng tù c¸c cét) cña ma trËn. (sö dông for sau ®ã dïng while, do/ while). 15. ViÕt ch¬ng tr×nh t×m phÇn tö ©m ®Çu tiªn trong ma trËn (theo chiÒu tõ tr¸i qua ph¶i, tõ trªn xuèng díi). 16. ViÕt ch¬ng tr×nh nhËp vµo mét ma trËn m x n sè nguyªn. T×m phÇn tö lín nhÊt (t¬ng tù t×m phÇn tö nhá nhÊt) cña ma trËn võa nhËp. In kÕt qu¶ ra mµn h×nh. 17. ViÕt ch¬ng tr×nh nhËp vµo hai ma trËn A, B cã n hµng, m cét. TÝnh ma trËn C = A + B vµ in kÕt qu¶ ra mµn h×nh. 18. ViÕt ch¬ng tr×nh nhËp vµo hai ma trËn A, B, tÝnh vµ in ra mµn h×nh tÝch cña hai ma trËn ®ã. 19. ViÕt ch¬ng tr×nh nhËp vµo mét ma trËn A cã n dßng, m cét. In ra mµn h×nh ma trËn chuyÓn vÞ cña A. (A’ ®îc gäi lµ ma trËn chuyÓn vÞ cña A nÕu A’[i, j] = A[j, i] víi mäi i, j). 20. Ma trËn A ®îc gäi lµ ®èi xøng qua ®êng chÐo chÝnh nÕu A[i, j] = A[j, i] víi mäi i kh¸c j. ViÕt ch¬ng tr×nh nhËp vµo mét ma trËn A, kiÓm tra xem A cã ®èi xøng qua ®êng chÐo chÝnh kh«ng. In kÕt luËn lªn mµn h×nh. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

9 5

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

21. Mét ma trËn sè, vu«ng a ®îc gäi lµ hîp lÖ nÕu tÊt c¶ c¸c phÇn tö n»m trªn ®êng chÐo chÝnh b»ng 1, tÊt c¶ c¸c phÇn tö n»m phÝa trªn ®êng chÐp chÝnh ®Òu d¬ng, tÊt c¶ c¸c phÇn tö n»m phÝa díi ®êng chÐo chÝnh ®Òu ©m. H·y kiÓm tra xem a cã hîp lÖ kh«ng? Ch¬ng V: Kü thuËt lËp tr×nh dïng con trá 1. ViÕt ch¬ng tr×nh nhËp vµo mét m¶ng a gåm n phÇn tö nguyªn. S¾p xÕp m¶ng theo chiÒu gi¶m dÇn (lu ý sö dông tªn m¶ng nh con trá vµ sö dông con trá). 2. H·y dïng mét vßng for ®Ó nhËp vµo mét ma trËn vu«ng cÊp n víi c¸c phÇn tö thùc vµ t×m phÇn tö Max cña ma trËn nµy. 3. ViÕt hµm ho¸n vÞ hai biÕn thùc a, b b»ng c¸ch sö dông con trá (®èi vµo lµ hai con trá). ViÕt ch¬ng tr×nh chÝnh nhËp hai sè thùc a, b. Sö dông hµm trªn ®Ó ®æi chç a vµ b. 4. ViÕt hµm gi¶i hÖ ph¬ng tr×nh bËc nhÊt víi s¸u ®èi vµo lµ a, b, c, d, e, f vµ 2 ®èi ra lµ x vµ y. 5. ViÕt hµm tÝnh gi¸ trÞ ®a thøc: f(x) = a0xn + … + an-1x + an. víi ®èi vµo lµ biÕn nguyªn n vµ m¶ng thùc a. 6. ViÕt hµm céng hai ma trËn vu«ng a vµ b cÊp n (sö dông con trá). 7. ViÕt hµm tr¶ vÒ ®ång thêi 3 gi¸ trÞ lµ tæng ch¾n, tæng lÎ vµ tæng c¸c sè chia hÕt cho 3 cã trong m¶ng a gåm n phÇn tö nguyªn. Sö dông hµm trªn trong ch¬ng tr×nh chÝnh. 8. ViÕt ch¬ng tr×nh tÝnh tÝch ph©n cña f(x) trªn ®o¹n [a, b] b»ng c«ng thøc h×nh thang. Theo ®ã, tÝch ph©n cña f(x) trªn [a, b] b»ng: h * s. Trong ®ã: h lµ ®é dµi kho¶ng ph©n ho¹ch ®o¹n [a, b] thµnh n kho¶ng. s lµ tæng tÊt c¶ c¸c f(a+i*h) víi i tõ 1 tíi n. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

9 6

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Sö dông hµm trªn ®Ó tÝnh tÝch ph©n trong ®o¹n [-1, 4] cña: f(x) = (ex-2sin(x2))/ (1+x4). (nghiªn cøu c¸ch ®a con trá vµo gi¶i quyÕt bµi to¸n).

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

9 7

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü Mét sè c©u hái vÒ m¶ng

§Ò 1. NhËp vµo mét m¶ng a gåm n phÇn tö nguyªn. In ra mµn h×nh phÇn tö ©m ®Çu tiªn trong d·y (tÝnh tõ tr¸i qua ph¶i) vµ vÞ trÝ cña phÇn tö ©m ®ã (nÕu cã). NÕu m¶ng kh«ng cã phÇn tö ©m nµo, h·y tÝnh trung b×nh céng c¸c phÇn tö d¬ng trong m¶ng vµ in kÕt qu¶ ra mµn h×nh. §Ò 2. ViÕt ch¬ng tr×nh nhËp vµo mét d·y sè nguyªn. TÝnh tæng cña c¸c sè nguyªn tè trong d·y vµ in kÕt qu¶ ra mµn h×nh. NÕu m¶ng kh«ng cã sè nguyªn tè nµo, h·y s¾p m¶ng t¨ng dÇn b»ng ph¬ng ph¸p næi bät. §Ò 3. ViÕt ch¬ng tr×nh nhËp vµo mét d·y sè nguyªn vµ mét sè nguyªn c. §Õm sè lÇn xuÊt hiÖn vµ vÞ trÝ xuÊt hiÖn cña c trong d·y. In c¸c kÕt qu¶ ra mµn h×nh. NÕu c kh«ng xuÊt hiÖn trong m¶ng, h·y chÌn c vµo gi÷a m¶ng. §Ò 4. NhËp mét ma trËn vu«ng n x n phÇn tö thùc. Gäi P[i] lµ trung b×nh céng cña c¸c phÇn tö trong dßng thø i cña ma trËn vµ K lµ trung b×nh céng cña tÊt c¶ c¸c phÇn tö trong ma trËn. H·y tÝnh vµ in ra P[i] vµ K. §Ò 5. NhËp mét ma trËn vu«ng n x n phÇn tö nguyªn. KiÓm tra xem ma trËn võa nhËp cã ®èi xøng kh«ng? nÕu ®èi xøng, h·y in ra c¸c phÇn tö trªn ®êng chÐo chÝnh cña ma trËn ra mµn h×nh ®ång thêi tÝnh vµ in ra tæng c¸c phÇn tö n»m phÝa trªn ®êng chÐo chÝnh. §Ò 6. m¶ng m¶ng m¶ng

NhËp mét m¶ng a gåm n phÇn tö nguyªn, h·y ®¶o ngîc a vµ in m¶ng ®· ®¶o ngîc ra mµn h×nh. S¾p sÕp l¹i a theo chiÒu t¨ng dÇn vµ in ra phÇn tö lín nhÊt trong a.

§Ò 7. NhËp mét m¶ng a gåm n phÇn tö nguyªn. h·y s¾p xÕp m¶ng a sao cho: c¸c phÇn tö lín nhÊt ë ®Çu m¶ng, c¸c phÇn tö bÐ nhÊt ë cuèi m¶ng, c¸c phÇn tö cßn l¹i s¾p t¨ng dÇn. In m¶ng ®· s¾p ra mµn h×nh. §Ò 8. NhËp mét m¶ng a gåm n phÇn tö nguyªn. M¶ng a ®îc gäi lµ hîp lÖ nÕu tån t¹i 3 phÇn tö liªn tiÕp ®Òu lµ c¸c phÇn tö lÎ. H·y kiÓm tra xem a cã hîp lÖ kh«ng? nÕu kh«ng hîp lÖ h·y dån tÊt c¶ c¸c phÇn tö lÎ cña a lªn ®Çu m¶ng. §Ò 9. NhËp mét m¶ng a gåm n phÇn tö nguyªn. S¾p a theo chiÒu t¨ng dÇn b»ng ph¬ng ph¸p chän. Xo¸ mäi phÇn tö lÎ trong m¶ng a vµ in m¶ng kÕt qu¶ lªn mµn h×nh. Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

9 8

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

§Ò 10. NhËp mét m¶ng a gåm n phÇn tö nguyªn. M¶ng a ®îc gäi lµ hîp lÖ nÕu nã chøa ®óng 3 phÇn tö d¬ng vµ 3 phÇn tö ©m. H·y cho biÕt a cã hîp lÖ kh«ng? nÕu a kh«ng hîp lÖ h·y s¾p a theo chiÒu t¨ng dÇn b»ng ph¬ng ph¸p chÌn. §Ò 11. NhËp mét ma trËn a gåm n dßng, m cét. H·y tÝnh tæng c¸c phÇn tö d¬ng trªn ma trËn vµ in kÕt qu¶ ra mµn h×nh. H·y tÝnh tæng cña c¸c phÇn tö xung quanh ma trËn ®ång thêi in ma trËn võa nhËp ra mµn h×nh. §Ò 12. NhËp mét ma trËn vu«ng n x n phÇn tö nguyªn. Ma trËn ®îc gäi lµ hîp lÖ nÕu tæng c¸c phÇn tö trªn mçi dßng cña tÊt c¶ c¸c dßng ®Òu b»ng nhau. H·y kiÓm tra xem ma trËn võa nhËp cã hîp lÖ kh«ng? In m¶ng võa nhËp ra mµn h×nh. §Ò 13. NhËp mét m¶ng a gåm n phÇn tö nguyªn. H·y t¸ch c¸c phÇn tö ch½n trong a ra mét m¶ng b, t¸ch c¸c phÇn tö lÎ trong a ra mét m¶ng c. In c¶ 3 m¶ng ra mµn h×nh. §Ò 14. NhËp mét m¶ng a gåm n phÇn tö nguyªn. H·y s¾p xÕp m¶ng a sao cho c¸c phÇn tö lín nhÊt vÒ cuèi d·y, c¸c phÇn tö cßn l¹i ®îc s¾p gi¶m dÇn. In kÕt qu¶ ra mµn h×nh. Cho biÕt m¶ng võa s¾p cã bao nhiªu phÇn tö nhá nhÊt? §Ò 15. NhËp mét ma trËn vu«ng a gåm n x n phÇn tö nguyªn. Ma trËn ®îc gäi lµ hîp lÖ nÕu tÊt c¶ c¸c dßng cña nã, mçi dßng chØ chøa ®øng 1 phÇn tö ©m. H·y kiÓm tra xem ma trËn võa nhËp cã hîp lÖ kh«ng? in m¶ng võa nhËp ra mµn h×nh.

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

9 9

§Ò c¬ng chi tiÕt thuËt lËp tr×nh

Kü

Môc lôc Ch¬ng I. tæng quan vÒ C++...............................................................2 I. Quy tr×nh lµm viÖc trong C++.............................................................2 I.1. C¸c bíc ®Ó lËp mét tr¬ng tr×nh b»ng C++...............................2 I.2. CÊu tróc mét ch¬ng tr×nh ®¬n gi¶n trong C++.......................3 II. BiÕn, biÓu thøc, c¸c lÖnh nhËp xuÊt....................................................5 II.1. BiÕn............................................................................................5 II.2. BiÓu thøc....................................................................................5 II.3. C¸c lÖnh nhËp-xuÊt....................................................................8 a. C¸c lÖnh nhËp xuÊt trong IOStream.h....................................8 b. C¸c lÖnh nhËp xuÊt trong Stdio.h..........................................10 c. C¸c lÖnh nhËp xuÊt trong Conio.h..........................................11 Ch¬ng II. C¸c cÊu tróc ®iÒu khiÓn trong C++.................................13 I. CÊu tróc rÏ nh¸nh vµ cÊu tróc chän.......................................................13 I.1. CÊu tróc rÏ nh¸nh..........................................................................13 I.2. CÊu tróc chän...............................................................................16 II. CÊu tróc lÆp.........................................................................................18 II.1. Vßng lÆp víi sè lÇn lÆp x¸c ®Þnh...............................................18 II.2. Vßng lÆp víi sè lÇn lÆp kh«ng x¸c ®Þnh....................................22 a. LÆp kiÓm tra ®iÒu kiÖn tríc: ...............................................22 b. LÆp kiÓm tra ®iÒu kiÖn sau: ...............................................24 II.3. C¸c vÝ dô minh ho¹ sö dông vßng lÆp.........................................26 Ch¬ng III. Kü thuËt lËp tr×nh ®¬n thÓ...........................................28 I. §¬n thÓ vµ lËp tr×nh ®¬n thÓ...................................................28 I.1. Kh¸i niÖm vµ ph©n lo¹i ®¬n thÓ.................................................28 I.2. §Þnh nghÜa vµ sö dông hµm..............................................................29 I.3. Tæ chøc c¸c hµm..........................................................................32 I. 4. Ph¹m vi ho¹t ®éng cña biÕn..............................................................36 II. Kü thuËt ®Ö quy..................................................................................37 II.1. Kh¸i niÖm vÒ ®Ö quy..................................................................37 II.2. ThiÕt kÕ hµm ®Ö quy.................................................................39 Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 0 0

§Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh II.3. §Ö quy vµ c¸c d·y truy håi...........................................................41 II.4. Mét sè vÝ dô vÒ ®Ö quy.............................................................42 III. Kü thuËt truyÒn tham sè.....................................................................43 III.1. Kh¸i niÖm vµ ph©n lo¹i tham sè.................................................43 III.2. TruyÒn tham sè..........................................................................44 Ch¬ng IV. Kü thuËt lËp tr×nh dïng m¶ng.........................................47 I. M¶ng mét chiÒu...........................................................................47 I.1. Khai niÖm vµ c¸ch khai b¸o..........................................................47 I.2. C¸c thao t¸c c¬ b¶n trªn m¶ng mét chiÒu...................................48 I.3. C¸c bµi to¸n c¬ b¶n......................................................................48 a. Bµi to¸n s¾p xÕp m¶ng........................................................48 b. Bµi to¸n t×m kiÕm................................................................54 II. M¶ng hai chiÒu...........................................................................58 II.1. C¸c thao t¸c c¬ b¶n trªn m¶ng hai chiÒu....................................58 II.2. C¸c bµi to¸n c¬ b¶n trªn m¶ng 2 chiÒu.......................................60 III. X©u ký tù – m¶ng c¸c ký tù.......................................................62 III.1. Mét sè lu ý khi sö dông x©u ký tù..............................................62 III.2. Mét sè bµi to¸n ®Æc thï trªn x©u..............................................65 Ch¬ng V. Kü thuËt lËp tr×nh dïng con trá........................................68 I. Tæng quan vÒ con trá...........................................................................68 I.1. Kh¸i niÖm vµ c¸ch khai b¸o..........................................................68 I.2. Mét sè thao t¸c c¬ b¶n trªn con trá..............................................68 II. Con trá - m¶ng vµ hµm.......................................................................69 II.1. Con trá vµ m¶ng..........................................................................69 II.2. Con trá vµ hµm............................................................................70 III. CÊp ph¸t vµ gi¶i phãng bé nhí cho con trá..........................................73 III.1. CÊp ph¸t bé nhí ®éng cho con trá..............................................73 III.2. CÊp ph¸t l¹i hoÆc gi¶i phãng bé nhí cho con trá........................75 Mét sè Bµi tËp thùc hµnh....................................................................78

Tµi liÖu gi¶ng d¹y- Lu hµnh néi bé Trang

1 0 1