Đề cương môn học: Kỹ thuật lập trì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: BT§K ®óng? Thùc hiÖn lÖnh lÆp Y N + Có ph¸p: do while () ý nghÜa: B1: Thùc hiÖn lÖnh lÆp. B2: KiÓm tra . NÕu <BiÓu thøc ®iÒu kiÖn ®óng, quay l¹i B1. Ng­îc l¹i, tho¸t khái vßng lÆp. Chó ý: cã thÓ lµ mét khèi lÖnh. ph¶i ®­îc ®Æt trong dÊu “(“ “)”; CÇn tr¸nh c¸c tr­êng hîp lÆp v« h¹n. VD1: 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 #include #include #include main() { clrscr(); int x=0; do x +=1; while (x <=5 | | sin(x) !=1) cout<<”Sè cÇn t×m lµ ”<<x; getch(); } VD2: 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 ch­a. NÕu ch­a, 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. #include #include #include main() { clrscr(); int So; cout<<”NhËp mét sè nguyªn “; do { cin>>So; if (So <=10) cout<<”Sè kh«ng tháa m·n. NhËp l¹i : “; } while (So <=10) 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(); } cout<<”Sè cÇn t×m lµ ”<<So; getch(); } §Ó tho¸t khái vßng lÆp kh«ng x¸c ®Þnh, ta còng cã thÓ sö dông break ho¨ck 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õ 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. §Ó 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 ®ã b¾t buéc ph¶i sö dông lÖnh break vµ goto trong th©n vßng for ®Ó tho¸t c­ìng bøc. C¸c vÝ dô minh häa VD1: 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? #include #include #include main() { clrscr(); int So, Tong, Dem; cout<<”NhËp sè nguyªn”; cin>>So; Tong =Dem=0; for (int i=1; i<=n; i++) { int Check = 0; for (int j=2; j<n; j++) if (i%j==0) Check = 1; If (Check ==0) { Tong +=i; Dem++; } } cout<<”Tæng c¸c sè nguyªn tè “<<Tong; cout<<” Cã “<<Dem<<sè nguyªn tè trong ®o¹n 1..n”; getch(); } VD2: 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: F = #include #include #include main() { clrscr(); int n; float x, F; float ts, ms; cout<<”NhËp x”; cin>>x; cout<<”NhËp n”; cin>>n; F=0; ts=x; ms=1; if (n%2==0) { for(int i=1; i<=n; i++) { ts*=x; ms*=3; F+=ts/ms; } } cout<<”Gi¸ trÞ cña biÓu thøc “<<F; getch(); } Ch­¬ng III. Kü thuËt lËp tr×nh ®¬n thÓ Giíi thiÖu Kh¸i niÖm vÒ ®¬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 t¹o thµnh tõ nhiÒu ®¬n thÓ kh¸c nhau. C¸c ®¬n thÓ thùc hiÖn nh÷ng nhiÖm vô t­¬ng ®èi ®éc lËp vµ ®­îc “l¾p ghÐp” l¹i thµnh 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é thuËt to¸n ®­îc thÓ hiÖn trong mét ®o¹n m· tõ trªn xuèng d­íi. 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, ch­¬ng tr×nh dµi kh«ng cÇn thiÕt. 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. Trong C++, ta cã hai lo¹i ®¬n thÓ sau: [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. 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 tr­ng cña hµm Mét hµm trong C++ cã c¸c ®Æc tr­ng sau: 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 kh«ng ®­îc chøa dÊu c¸ch vµ c¸c ký tù ®Æc biÖt (trõ dÊu g¹ch d­íi). KiÓu gi¸ trÞ tr¶ vÒ cña hµm: NÕu hµm tr¶ vÒ mét gi¸ trÞ nµo ®ã th× gi¸ trÞ ®ã 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. KiÓu vµ tªn c¸c ®èi cña hµm: NÕu hµm sö dông c¸c ®èi 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. Kh¸c víi trong Pascal, tÊt c¶ c¸c hµm ®Òu tr¶ vÒ mét gi¸ trÞ nµo ®ã, c¸c hµm trong C++ ®­î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. 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++, ®· ®­î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. §Þnh nghÜa vµ sö dông hµm §Þnh nghÜa hµm CÊu tróc mét hµm: Mét hµm th­êng cã cÊu tróc nh­ sau: { C¸c lÖnh trong th©n hµm; } Trong ®ã: : lµ kiÓu gi¸ trÞ tr¶ vÒ cña hµm. NÕu hµm kh«ng cã gi¸ trÞ tr¶ vÒ, ta dïng tõ kiÓu 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. : 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ã). VD1: hµm tÝnh n! ®­îc viÕt nh­ sau: long GT(int n) { long kq=1; if (n==0 | | n==1) kq=1; else for (int i=1; i<=n; i++) kq *=i; return kq; } Chó ý: Mçi ®èi cÇn ®i kÌm víi kiÓu ®èi, mçi cÆp [kiÓu ®èi] [tªn ®èi] c¸ch nhau bëi dÊu ph¶y. Th©n hµm ®­îc ®Æt gi÷a hai dÊu “{“ “}”. NÕu hµm cã gi¸ trÞ tr¶ vÒ th× cÇn cã c©u lÖnh ®Ó g¸n gi¸ trÞ cña BiÓu_Thøc cho tªn hµm. TuyÖt ®èi kh«ng ®­îc g¸n = . VD2: 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; } 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 viÕt theo cÊu tróc sau: #include… …. { th©n hµm 1; } { th©n hµm 2; } … void main() { Th©n hµm main; } HoÆc: #include… …. ; …. void main() { Th©n hµm main; } { Th©n hµm 1; } { Th©n hµm 2; } …. VD1: 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!. #include #include #include int NT(int n) { if (n ==1 | | n ==2) return =1; else {Check =0; for (int i=2; i<n; i++) if (n%i==0) Check =1; if (Check = 0) return 1; else return 0; } } //================= long GT(int n) { long kq=1; if (n==0 | | n==1) kq=1; else for (int i=1; i<=n; i++) kq *=i; return kq; } void main() { int a; cout<<”NhËp a”; cin>>a; if (NT(a) == 0) cout<<”Sè “<<a<<” Kh«ng ph¶i nguyªn tè”; else { cout<<”Sè “<<a<<” lµ sè nguyªn tè”; cout<<” Giai thõa cña “<<a<<” lµ “<<GT(a); } getch(); } C¸ch 2: Tæ chøc trong tÖp th­ viÖn: B1: ViÕt c¸c hµm (trõ hµm main() )trong mét file sau ®ã l­u d­íi ®Þnh d¹ng .h. File nµy th­êng ®­îc gäi lµ file th­ viÖn. (®Ó 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 ®ã di chuyÓn toµn bé c¸c hµm (trõ hµm main() sang mét file .h vµ l­u l¹i) 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 Chó ý: 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. VD: T¹o file .h víi néi dông sau, VD file “TV.h”: int NT(int n) { if (n ==1 | | n ==2) return =1; else {Check =0; for (int i=2; i<n; i++) if (n%i==0) Check =1; if (Check = 0) return 1; else return 0; } } //================= long GT(int n) { long kq=1; if (n==0 | | n==1) kq=1; else for (int i=1; i<=n; i++) kq *=i; return kq; } Më mét file míi vµ viÕt hµm main(): #include #include #include #include <C:\TC\BIN\ TV.h” void main() { int a; cout<<”NhËp a”; cin>>a; if (NT(a) == 0) cout<<”Sè “<<a<<” Kh«ng ph¶i nguyªn tè”; else { cout<<”Sè “<<a<<” lµ sè nguyªn tè”; cout<<” Giai thõa cña “<<a<<” lµ “<<GT(a); } getch(); } Chó ý: - C¸c file th­ viÖn .h kh«ng nhÊt thiÕt 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. Sö dông hµm Hµm ®­îc sö dông th«ng qua lêi gäi cña nã. C¸ch viÕt mét lêi gäi hµm nh­ sau: Chó ý: NÕu hµm ®­îc ®Þnh nghÜa cã ®èi sè th× khi gäi hµm ta ph¶i truyÒn ®Çy ®ñ c¸c tham sè cho hµm. 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: . NÕu hµm cã gi¸ trÞ tr¶ vÒ th× tªn hµm ®­îc sö dông nh­ mét biÕn. 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. Ph¹m vi cña biÕn Theo ph¹m vi ho¹t ®éng cña biÕn, ta chia ra: BiÕn toµn côc: Ph¹m vi ho¹t ®éng trong toµn bé ch­¬ng tr×nh, kÓ tõ vÞ trÝ khai b¸o biÕn. VÞ trÝ khai b¸o n»m ngoµi c¸c hµm (kÓ c¶ hµm main). 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. BiÕn côc bé: 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Ó 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. VD1: XÐt vÝ dô sau: 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(); } NhËn xÐt: 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 viÕ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. Sö dông c¸c tham sè trong lËp tr×nh ®¬n thÓ Ph©n lo¹i tham sè 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è t­¬ng øng cho hµm. C¸c tham sè cã thÓ lµ c¸c biÕn hoÆc c¸c h»ng gi¸ trÞ. Cã hai lo¹i tham sè: [1]. Tham chiÕu: 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ã. [2]. Tham trÞ: Khi truyÒn tham sè d­íi d¹ng tham trÞ, tham sè sÏ kh«ng ®­î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Þ tham ®æi gi¸ trÞ cña nã khi ra khái hµm. Thùc thi hµm Vïng nhí cña biÕn BiÕn Gäi hµm Thùc thi hµm Vïng nhí cña biÕn BiÕn Gäi hµm Vïng nhí míi a) truyÒn tham chiÕu b) TruyÒn tham trÞ TruyÒn tham sè NÕu ch­¬ng tr×nh viÕt trong c¸c file cã phÇn më réng .h, ta cã duy nhÊt mét c¸ch truyÒn tham sè: TruyÒn theo tham trÞ. Tõ C++3.0 trë lªn, cho phÐp sö dông c¶ hai c¸ch truyÒn tham sè trong c¸c ch­¬ng tr×nh viÕt d­íi d¹ng c¸c file .CPP. Khi biÕn truyÒn vµo hµm, nã ®­îc 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. VD1: 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 “<<n; tang(n); cout<<”Gi¸ trÞ sau khi gäi hµm “<<n; getch(); } VD2: xÐt hµm sau int Ham(int a, int b) { if (a%2==0){ a+=1; b+=a; } cout<<”Gi¸ trÞ a trong th©n hµm “<<a; cout<<Gi¸ trÞ b trong th©n hµm “<<b; } void main() { int a, b; a=1; b=2; cout<<”Gi¸ trÞ a tr­íc khi gäi hµm “<<a; cout<<”Gi¸ trÞ b tr­íc khi gäi hµm “<<b; Ham(a, b); cout<<”Gi¸ trÞ a sau khi gäi hµm “<<a; cout<<”Gi¸ trÞ b sau khi gäi hµm “<<b; getch(); } Kü thuËt ®Ö quy Kh¸i niÖm vÒ ®Ö quy Trong C++, mét hµm cã thÓ gäi ®Õn chÝnh nã, kh¶ n¨ng nµy cña hµm gäi lµ ®Ö quy. Khi mét hµm gäi ®Õn chÝnh nã, hµm ®­îc viÕt theo kiÓu ®Ö quy. VD: XÐt hµm tÝnh n!. Ta cã ®Þnh nghÜa sau: n! = (n-1)! * n. Nh­ vËy, gi¶ sö n=5 th× n! ®­îc tÝnh nh­ sau: 5! = 4! * 5 = 3! * 4 * 5. = 2! * 3 * 4 * 5. = 1! * 2 * 3 * 4 * 5. Víi 1! = 1, ta hoµn toµn cã thÓ tÝnh ®­îc 5!. Khi ®ã, ®Ó tÝnh ®­îc 5!, ta ph¶i tÝnh 2!, 3!, 4!. Hµm lÆp: long GT(int n) { long kq=1; if (n==0 | | n==1) kq=1; else for (int i=1; i<=n; i++) kq *=i; return kq; } Hµm ®Ö quy: long GT(int n) { if (n==1) return 1; else return GT(n-1) * n; } Thùc hiÖn: Gi¶ sö n kh¸c 1. Khi ®ã, quy tr×nh thùc hiÖn nh­ sau: n! (n-1)! (n-2)! (1)! 1 * 2 *…* (n-2) 1 * 2 *…* (n-1) 1 * 2 *…* (n) (2)! 1 * 2 (n-1)! *n (n-2)! * (n-1) (n-3)! * (n-2) 1 (1)! * 2 … … …. = = = = Mçi lÇn gäi ®Ö quy, ch­¬ng tr×nh thùc hiÖn nh­ sau: L­u ®Þa chØ cña dßng lÖnh gäi ®Ö quy. T¹o mét t¹o mét b¶n sao cña hµm, cÊp ph¸t c¸c vïng nhí míi cho c¸c biÕn côc bé, thùc hiÖn b¶n sao nµy. LÊy ®Þa chØ cña dßng lÖnh gäi ®Ö quy vµ quay vÒ. §Ó râ h¬n ta xem s¬ ®å sau: B¾t ®Çu Gäi ®Ö quy Gäi ®Ö quy Gäi ®Ö quy KÕt thóc B¶n sao 1 B¶n sao n Bá qua lÖnh gäi ®Ö quy … Nh­ vËy cã bao nhiªu lêi gäi hµm th× cã bÊy nhiªu lÇn kÕt thóc hµm. Trong tr­êng hîp kh«ng tån t¹i mét b¶n sao cña hµm mµ t¹i ®ã kh«ng thùc hiÖn hiÖn lêi gäi ®Ö quy th× qu¸ tr×nh ®Ö quy sÏ kh«ng dõng ®­îc (ta gäi lµ ®Ö quy v« h¹n). Trong vÝ dô vÒ tÝnh n!, víi n=3 vµ c«ng thøc ®Ö quy n! = n * (n-1)!, s¬ ®å ®Ö quy cã thÓ nh­ sau: B¾t ®Çu : tÝnh 3! Gäi ®Ö quy GT(2) Gäi ®Ö quy GT(1) Gäi ®Ö quy GT(0) KÕt thóc Return 1*2*3 Hµm GT(2) Hµm GT(1) Bá qua lÖnh gäi ®Ö quy Return 1 Return 1*2 ­u nh­îc ®iÓm cña ph­¬ng ph¸p ®Ö quy: Ch­¬ng tr×nh ng¾n gäi, dÔ hiÓu. Qu¸ tr×nh dÞch phøc t¹p. Nãi chung, tèn nhiÒu kh«ng gian nhí h¬n lÆp. Chó ý: L­u ý tíi ®iÒu kiÖn dõng cña hµm viÕt theo kiÓu ®Ö quy. Ph­¬ng ph¸p ®Ö quy ®Æc biÖt thÝch hîp víi mét sè bµi to¸n nh­ duyÖt c©y, ®å thÞ… Tuy nhiªn, nãi chung ta nªn Ýt sö dông ®Ö quy khi viÕt ch­¬ng tr×nh do c¸c nh­îc ®iÓm trªn, trõ nh÷ng tr­êng hîp ®Æc thï. ThiÕt kÕ ch­¬ng tr×nh theo kiÓu ®Ö 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 nh­ng 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 say biÕn. 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!. 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 lµ: 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 kh¸c 1 vµ n kh¸c 0) khi ®ã: n! = n* (n-1)!. Ch­¬ng tr×nh ®Ö quy ®­îc thiÕt kÕ 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: Khung ch­¬ng tr×nh cã d¹ng: if (suy biÕn) C«ng thøc trong tr­êng hîp suy biÕn. else C«ng thøc trong tr­êng hîp tæng qu¸t. VD1: 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); Sau khi thiÕt kÕ song, viÖc lËp hµm ®Ö quy trë lªn rÊt ®¬n gi¶n. VD2. D·y sè Catalan ®­îc ph¸t biÓu ®Ö quy nh­ sau: C1 = 1; Cn = 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 = B­íc 2: if (n = = 1) return 1; else { int C =0; for (int i=1; i<n; i++) C+= CataLan(i) * CataLan(n-i); Return C; } Víi phÇn thiÕt kÕ trªn, hµm ®Ö quy tÝnh sè CataLan thø n ®­îc viÕt nh­ sau: int CataLan(int n) { if (n==1) return 1; else { int C=0; for (int i=1; i<n; i++) C+=CataLan(i)*CataLan(n-i); return C; } } §Ö 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 sè h¹ng ®øng tr­íc cña d·y. VD: 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!… HoÆc d·y c¸c sè Fibonacci: A[1] = 1; A[2] = 1; A[n] = A[n-1] + A[n-2] (víi n>2). Víi c¸c d·y truy håi, ta hoµn toµn cã thÓ dïng c¸c thuËt to¸n lÆp ®Ó tÝnh. Tuy nhiªn c¸c gi¶i thuËt ®Ö quy th­êng ®­îc ¸p dông trªn c¸c d·y truy håi . Mét sè vÝ dô vÒ ®Ö quy VD1: 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: ThiÕt kÕ: 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) LËp tr×nh: Int USCLN_DQ(int a, int b) { if (b==0) return a; else return USCLN_DQ(b, a%b); } VD2: 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. ThiÕt kÕ: 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); LËp tr×nh: int Fibo(int n) { if(n<=1) return 1; else return Fibo(n-1) + Fibo(n-2); } Ch­¬ng IV. Kü thuËt lËp tr×nh dïng m¶ng Khai b¸o vµ sö dông m¶ng Kh¸i niÖm vµ ph©n lo¹i m¶ng Kh¸i niÖm vÒ m¶ng §Ó biÓu diÔn mét d·y sè hay mét b¶ng sè ta cã thÓ dïng nhiÒu biÕn, c¸ch nµy kh«ng tiÖn lîi do c¸c nh­îc ®iÓm sau: Ch­¬ng tr×nh viÕt dµi kh«ng cÇn thiÕt. DÔ g©y nhÇm lÉn. Kh«ng kh¶ thi trong tr­êng hîp sè phÇn tö cña d·y, b¶ng sè qu¸ lín. §Ó kh¾c phôc nh÷ng nh­îc ®iÓm trªn, ng­êi ta ®­a ra mét kiÓu d÷ liÖu m¶ng. M¶ng lµ kiÓu d÷ liÖu ®Ó khai b¸o mét tËp hîp nhiÒu phÇn tö cã cïng kiÓu vµ chung mét tªn. Mçi phÇn tö nh­ vËy gäi lµ mét phÇn tö cña m¶ng. Nãi chung, m¶ng cã c¸c ®Æc ®iÓm sau: Mçi phÇn tö cña m¶ng biÓu diÔn mét gi¸ trÞ. Mçi phÇn tö cña m¶ng ®­îc ®¸nh chØ sè cho phÐp truy cËp tíi phÇn tö ®ã. §Ó dïng kiÓu m¶ng ta cÇn x¸c ®Þnh râ: + Lo¹i m¶ng: kiÓu cña mçi phÇn tö cña m¶ng (float, int, double…) + Tªn m¶ng(hay tªn biÕn cã kiÓu m¶ng): Tïy ý ®Æt theo quy ­íc ®Æt tªn biÕn. + Sè chiÒu vµ kÝch th­íc mçi chiÒu. Ph©n lo¹i m¶ng Dùa vao sè chiÒu cña m¶ng ng­êi ta chia ra: M¶ng mét chiÒu: dïng ®Ó l­u d·y c¸c gi¸ trÞ cïng kiÓu. ChØ sè cña m¶ng ®­îc ®¸nh tõ 0. Nh­ vËy ph©n tö thø i trong m¶ng ®­îc ®¸nh chØ sè lµ i-1. VD: Mét m¶ng cã tªn lµ a. Khi ®ã: PhÇn tö thø nhÊt cña m¶ng lµ a[0]. PhÇn tö thø 2 cña m¶ng lµ a[1]…. M¶ng hai chiÒu: Dïng ®Ó l­u tr÷ mét b¶ng c¸c gi¸ trÞ cïng kiÓu. C¸c cét vµ dßng ®­îc ®¸nh chØ sè tõ 0. Nh­ vËy, phÇn tö t¹i dßng i, cét j ®¸nh chØ sè lµ [i-1][j-1]. VD: Víi m¶ng hai chiÒu a ta cã: PhÇn tö t¹i dßng 1 cét 1: a[0][0]. PhÇn tö t¹i cét 1 dßng 2: a[0][1]. … Khai b¸o m¶ng M¶ng mét chiÒu Có ph¸p: ; Trong ®ã: + : cã thÓ lµ c¸c kiÓu chuÈn nh­ float, int, double, long…hoÆc kiÓu tù ®Þnh nghÜa. + : hay tªn biÕn m¶ng, tïy ý ®Æt theo quy ­íc ®Æt tªn biÕn. + : dïng ®Ó xc¸ ®Þnh sè phÇn tö tèi ®a cña m¶ng. VD: float a[10]; SÏ khai b¸o mét biÕn m¶ng c¸c gi¸ trÞ kiÓu thùc, sè phÇn tö tèi ®a lµ 10. C¸c phÇn tö ®­îc ®¸nh chØ sè a[0], a[1], …, a[9]. M¶ng hai chiÒu: T­¬ng tù nh­ m¶ng mét chiÒu ta cã: ; Víi : chØ ra kÝch th­íc mçi chiÒu cña m¶ng. VD: double b[3][2]; SÏ khai b¸o mét m¶ng 2 chiÒu cã 3 dßng, 2 cét víi c¸c ph©n tö kiÓu double. C¸c phÇn tö ®­îc ®¸nh chØ sè nh­ sau: b[0][0] b[0][1] b[1][0] b[1][1] b[2][0] b[2][1] Sö dông m¶ng LÊy ®Þa chØ c¸c phÇn tö Víi m¶ng mét chiÒu, ta vÉn sö dông phÐp lÊy ®Þa chØ th«ng th­êng VD: ®Ó lÊy ®Þa chØ phÇn tö a[i] ta viÕt: &a[i]. Víi m¶ng hai chiÒu: nãi chung kh«ng cho phÐp lÊy ®Þa chØ cña c¸c phÇn tö m¶ng. Nh­ vËy, kh«ng chÊp nhËn c¸ch viÕt: & a[i][j]. Víi C++3.0 trë lªn, ta vÉn cã thÓ sö dông phÐp lÊy ®Þa chØ c¸c phÇn tö m¶ng thùc hai chiÒu víi c¸c file ch­¬ng tr×nh cã phÇn më réng .CPP. DuyÖt m¶ng Víi m¶ng mét chiÒu cã n phÇn tö, ®Ó duyÖt qua c¸c phÇn tö cña m¶ng ta cã thÓ sö dông 1 vßng lÆp for sau: for(int i=0; i<n; i++) { Truy cËp tíi hÇn tö cã chØ sè i; } VD: NhËp d÷ liÖu cho mét m¶ng gåm 10 phÇn tö nguyªn. int a[10]; for(int i=0; i<10; i++) { printf(“NhËp A[%d] : “,i); scanf(“%d”, &a[i]); } Víi m¶ng 2 chiÒu cã n dßng, m cét, ta cã thÓ sö dông 2 vßng for lång nhau: for(int i=0; j<n; i++) for(int j=0; j<m; j++) { Truy cËp tíi phÇn tö cã chØ sè [i][j]; } VD: NhËp d÷ liÖu cho m¶ng thùc 2 chiÒu 5 dßng, 3 cét: float a[5][3]; float tg; for(int i=0; i<5; i++) for(int j=0; j<3; j++) { printf(“NhËp a[%d][%d]: “,i, j); scanf(“%f”, &tg); a[i][j] = tg; } Chó ý: V× c¸c file .h trong C kh«ng chÊp nhËn phÐp lÊy ®Þa chØ c¸c phÇn tö m¶ng hai chiÒu nªn ta kh«ng thÓ viÕt trùc tiÕp: scanf(“%f”, &a[i][j]); Mµ cÇn sö dông mét biÕn trung gian tg cã cïng kiÓu ®Ó lµm trung gian trong qu¸ tr×nh nhËp d÷ liÖu. Sau ®ã, ta g¸n a[i][j] b»ng gi¸ trÞ tg võa nhËp nµy. Tuy nhiªn, tõ C 3.0 trë lªn, vÉn cho phÐp lÊy ®Þa chØ cña phÇn tö m¶ng 2 chiÒu nh­ th­êng. VÊn ®Ò t¹o d¸ng ma trËn §Ó t¹o gi¸ng ma trËn, ta sö dông c©u lÖnh gotoxy(). C©u lÖnh nµy cã t¸c dông ®­a con trá mµn h×nh tíi c¸c täa ®é mµn h×nh ®· chØ ra trong c¸c tham sè ®Ó 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. X Y 1 80 25 Nh­ vËy, ta cã thÓ sö dông c©u lÖnh gotoxy trong vßng lÆp nh­ sau for (i=0; i<n; i++) for(j = 0; j <m; j++) { gotoxy(X + j *n, Y + i*m); cout<<a[i][j]; } Trong ®ã : X, Y lµ to¹ ®é ®Ønh tr¸i, trªn cña ma trËn; n, m lµ c¸c b­íc nh¶y theo trôc x vµ trôc y. Th«ng th­êng, ta chän n = 3 vµ m = 1. C¸c vÝ dô minh häa 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 vµ in kÕt qu¶ ra mµn h×nh. #include #include #include void main() { int a[100]; int tg, n, j; printf(“NhËp n “); scanf(“%d”, &n); for(int i=0; i<n; i++) { printf(“NhËp a[%d]: “,i); scanf(“%d”, &a[i]); } for(i=0; i<n-1; i++) for(j=i+1; j<n; j++) if (a[i]>a[j]) { tg=a[i]; a[i] = a[j]; a[j] = tg; } printf(“m¶ng sau khi s¾p”); for (i=0; i<n; i++) printf(“%d “, a[i]); getch(); } VD2: NhËp mét ma trËn sè nguyªn gåm n dßng, m cét. In ma trËn võa nhËp vµ phÇn tö lín nhÊt ra mµn h×nh. #include #include #include void main() { int a[100][100]; int n, m, Max, tg; printf(“NhËp sè dßng “); scanf(“%d”, &n); printf(“NhËp sè cét “); scanf(“%d”, &m); for(int i=0; i<n; i++) for(int j=0; j<m; j++) { printf(“NhËp a[%d][%d]: “, i, j); scanf(“%d”, &tg); a[i][j] = tg; } Max = a[0][0]; for(i=0; i<n; i++) for(j=0; j<m; j++) { if(a[i][j]>Max) Max = a[i][j]; printf(“%d\n”, a[i][j]); } printf(“PhÇn tö lín nhÊt %d“, Max); getch(); } TruyÒn tham sè m¶ng cho hµm Trong C++, cho phÐp viÕt c¸c hµm cã ®èi sè lµ m¶ng nh­ s¸c ®èi sè th«ng th­êng. Tuy nhiªn, khi truyÒn tham sè lµ m¶ng, ta th­êng truyÒn thªm c¶ c¸c biÕn lµ kÝch th­íc cña m¶ng. VD1: ViÕt ch­¬ng tr×nh thùc hiÖn viÖc nhËp mét d·y sè nguyªn, tÝnh tæng c¸c phÇn tö lÎ vµ in kÕt qu¶ ®ã lªn mµn h×nh. #include “stdio.h” … long Tong(int a[100], int n) { long T=0; for (int i=0; i<n; i++) if(a[i]%2==0) T+=a[i]; return T; } void main() { int b[100]; int n; cout<<”NhËp n”; cin>>n; for(int i=0; i<n; i++) { cout<<”NhËp b[“<<i<<”]”; cin>>b[i]; cout<<”Tæng c¸c phÇn tö lÎ “<<Tong(b, n); getch(); } VD2: ViÕt ch­¬ng tr×nh nhËp mét ma trËn n hµng, m cét. T×m phÇn tö lín nhÊt cña ma trËn vµ in ma trËn võa nhËp cïng phÇn tö lín nhÊt ra mµn h×nh. #include… … double Max(double a[100][100], n, m) { Max = a[0][0]; for(int i=0; i<n; i++) for(int j=0; j<m; j++) if (a[i][j]>Max) Max=a[i][j]; return Max; } void main() { double b[100][100]; int m, n; cout>n; cout>m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) { cout<<”b[“<<i<<”]= “; cin>>b[i][j]; } cout<<”Ma trËn võa nhËp lµ “; for(int i=0; i<n; i++) for(int j=0; j<m; j++) cout<<”b[“<<i<<”]= “<<b[i][j]; cout<<”PhÇn tö lín nhÊt : “<<Max(b, n, m); getch(); } C¸c bµi to¸n c¬ b¶n vÒ m¶ng Bµi to¸n trªn m¶ng mét chiÒu. Bµi 1: ViÕt ch­¬ng tr×nh nhËp vµo m¶ng n sè nguyªn vµ mét sè nguyªn c. Cho biÕt cã bao nhiªu sè nguyªn c trong m¶ng vµ vÞ trÝ cña nã. Bµi 2: ViÕt ch­¬ng tr×nh nhËp vµo mét m¶ng n phÇn tö nguyªn. tÝnh tæng c¸c phÇn tö lÎ, ch½n, chia hÕt cho 3 trong m¶ng. Bµi to¸n trªn m¶ng hai chiÒu. Bµi 1: ViÕt ch­¬ng tr×nh nhËp vµo 2 ma trËn A, B cïng kÝch th­íc m x n c¸c sè nguyªn. TÝnh vµ in ma trËn C = A+B. Bµi 2: Ma trËn B gäi lµ ma trËn chuyÓn vÞ cña A nÕu B[i][j] = A[j][i]. ViÕt ch­¬ng tr×nh nhËp vµo mét ma trËn A cã n dßng, m cét c¸c phÇn tö thùc. TÝnh vµ in ra ma trËn chuyÓn vÞ cña A. C¸c gi¶i thuËt t×m kiÕm, s¾p xÕp trªn m¶ng Bµi to¸n t×m kiÕm c¬ b¶n ®­îc ph¸t biÓu nh­ sau: Cho mét m¶ng a gåm n phÇn tö vµ mét kho¸ c. H·y cho biÕt kho¸ c cã xuÊt hiÖn trong a kh«ng? NÕu cã, h·y chØ ra mét vÞ trÝ cña c trong a. Bµi to¸n s¾p xÕp ®­îc ph¸t biÓu rÊt ®¬n gi¶n: Cho mét m¶ng a gåm n phÇn tö. H·y s¾p xÕp m¶ng a theo thø tù t¨ng dÇn (hoÆc gi¶m dÇn). Víi hai bµi to¸n ®Æc thï trªn m¶ng nh­ trªn, viÖc t×m ra c¸c ph­¬ng ph¸p kh¸c nhau ®Ó gi¶i quyÕt lµ rÊt quan träng. Sau ®©y sÏ lÇn l­ît tr×nh bµy mét sè gi¶i thuËt c¬ b¶n ®Ó gi¶i quyÕt hai bµi to¸n trªn. T×m kiÕm tuÇn tù Mét ph­¬ng ph¸p ®¬n gi¶n nhÊt ®Ó gi¶i quyÕt bµi to¸n t×m kiÕm lµ t×m kiÕm tuÇn tù. Theo ph­¬ng ph¸p nµy, ta chØ cÇn duyÖt tõ ®Çu ®Õn cuèi m¶ng. NÕu gÆp kho¸ c, sÏ in ra vÞ trÝ cña c (tøc lµ chØ sè cña phÇn tö c trong m¶ng). Ng­îc l¹i, khi duyÖt hÕt m¶ng mµ kh«ng t×m thÊy c, tøc lµ c kh«ng xuÊt hiÖn trong m¶ng. Nh­ vËy, ®é phøc t¹p cña thuËt gi¶i lµ O(n). int d=0; ×or (i =0; i< n; i++) if (a[i]==c) { cout<<” VÞ trÝ t×m ®­îc c “<<i+1; d++; } if (d==0) cout<<”kho¸ c kh«ng xuÊt hiÖn trong m¶ng”; §«i khi, cÇn ph¶i n¾m ®­îc tÊt c¶ c¸c vÞ trÝ xuÊt hiÖn c, ta sö dông mét m¶ng VT[] ®ång hµnh ®Ó l­u c¸c vÞ trÝ ®· t×m ®­îc c. Nh­ vËy, thay b»ng viÖc in vÞ trÝ t×m ®­îc ra mµn h×nh, ta l­u vÞ trÝ ®ã trong m¶ng VT: VT[d] = i+1; T×m kiÕm nhÞ ph©n trªn m¶ng ®­îc s¾p Ph­¬ng ph¸p nµy chØ ¸p dông trªn m¶ng ®· ®­îc s¾p. ý t­ëng cã thÓ h×nh dung nh­ sau: L m¶ng a R Gi¶ sö ta cÇn t×m kiÕm c trong mét ®o¹n tõ vÞ trÝ L tíi vÞ trÝ R trªn mét m¶ng a ®­îc s¾p: Khi ®ã, ta chia m¶ng a lµm hai phÇn bëi ®iÓm chia M: M = (L+R)/ 2 L M R Ta ¸p dông t×m kiÕm trªn 2 nöa cña a. Tuy nhiªn, do a ®· ®­îc s¾p nªn chØ cã thÓ s¶y ra 3 tr­êng hîp sau: [1]. NÕu a[M] = c th× ta ®· t×m ®­îc c trong m¶ng. VÞ trÝ cña c lµ M. [2]. NÕu a[M] > c th× c thuéc vÒ nöa tr¸i cña m¶ng a. Khi ®ã ta ¸p dông t×m kiÕm trªn nöa tr¸i, tøc lµ tõ vÞ trÝ L tíi M-1. [3]. NÕu a[M] < c th× c thuéc vÒ nöa ph¶i cña m¶ng a. Khi ®ã ta ¸p dông t×m kiÕm trªn nöa ph¶i, tøc lµ tõ vÞ trÝ M+1 tíi R. ViÖc t×m kiÕm trªn c¸c nöa cña a còng ¸p dông ph­¬ng ph¸p chia ®«i t­¬ng tù nh­ trªn. Nh­ vËy, ngay tõ ®Çu ta ¸p dông t×m kiÕm nhÞ ph©n trªn toµn m¶ng a (L=0; R=n-1). Hµm t×m kiÕm nhÞ ph©n lÆp sau ®©y tr¶ vÒ gi¸ trÞ -1 nÕu kh«ng t×m thÊy c trong a; ng­îc l¹i, nã tr¶ vÒ vÞ trÝ cña c trong a. int TKNP_Lap(int a[100], int n, int c) { int L, R, M; L =0; R = n-1; do { M = (L+R)/2; if (a[M] > c) L = M+1; if (a[M] < c) R = M-1; } while (L<R && a[M]!=c); if (a[M] ==c) return M; else return -1; } Râ rµng lµ trong tr­êng hîp nµy, viÖc ¸p dông ®Ö quy lµ rÊt phï hîp. Sau ®©y ta xem xÐt kh¶ n¨ng ¸p dông ®Ö quy víi thiÕt kÕ sau: B1: Suy biÕn trong tr­êng hîp L > R hoÆc a[M] = c. Khi ®ã NÕu L > R th× kh«ng t×m ®­îc c trong a. NÕu a[M] = c th× tr¶ vÒ M lµ vÞ trÝ cña c trong a. Ng­îc l¹i, trong tr­êng hîp L <= R vµ a[M] ! = c. Khi ®ã: NÕu a[M] > c th× gäi ®Ò quy trªn ®o¹n [L, M-1] NÕu a[M] < c th× gäi ®Ò quy trªn ®o¹n [M+1, R]. B2: if (L > R) return -1; else if (a[M] ==c) return M; else if (a[M] > c) return TKQD(a, n, c, L, M-1); else return TKDQ(a, n, c, M+1, R); Sau ®©y lµ code: int TKNP_DQ(int a[100], int n, int c, int L, int R) { int M=(L+R)/2; if (L>R) return -1; else if (a[M]==c) return M; else if (a[M] > c) return TKNP_DQ(a, n, c, M+1, R); else return TKNP_DQ(a, n, c, L, M-1); } ThuËt to¸n t×m kiÕm ®Ö quy trªn m¶ng ®­îc s¾p ®­îc ®¸nh gi¸ t­¬ng ®èi tèt. §é phøc t¹p trong tr­êng hîp tåi nhÊt lµ O(lg (n)). Ph­¬ng ph¸p nµy kh«ng bao giê dïng nhiÒu h¬n lg(n) + 1 phÐp so s¸nh. Mét ph­¬ng ph¸p t×m kiÕm hiÖu qu¶ h¬n lµ t×m kiÕm néi suy trªn c©y (Ýt h¬n lg(lg(n)) +1 phÐp so s¸nh) kh«ng ®­îc ®Ò cËp trong bµi gi¶ng nµy. S¾p xÕp næi bät Ph­¬ng ph¸p s¾p xÕp c¬ b¶n nhÊt lµ ph­¬ng ph¸p næi bät quen thuéc. Gi¶i thuËt ®ùoc tr×nh bµy nh­ sau: for (i=0; i < n-1; i++) for (j=i+1; j<n; j++) If (a[i] > a[j]) //®æi chç a[i] cho a[j]; KÕt thóc hai vßng lÆp trªn, m¶ng ®· ®­îc s¾p (t¨ng). ta cã thÓ h×nh dung qu¸ tr×nh s¾p xÕp qua vÝ dô sau B¾t ®Çu s¾p i = 0 3 5 2 7 4 8 HÕt 1 vßng lÆp j; i = 1; 2 5 3 7 4 8 HÕt mét vßng j; i=2; 2 3 5 7 4 8 HÕt mét vßng j; i=3; 2 3 4 7 5 8 HÕt mét vßng j; i=4; 2 3 4 5 7 8 Trong tr­êng hîp trung b×nh vµ tr­êng hîp tåi nhÊt, ph­¬ng ph¸p nµy cÇn n2/2 lÇn so s¸nh vµ n2/ 2 lÇn ®æi chç. S¾p xÕp chän Ph­¬ng ph¸p s¾p xÕp c¬ b¶n thø 2 lµ ph­¬ng ph¸p chän. ý t­ëng cña ph­¬ng ph¸p nh­ sau: NÕu a ®­îc s¾p t¨ng th× c¸c phÇn tö ®øng sau lu«n lín h¬n c¸c phÇn tö ®øng tr­íc. X©y dùng mét m¶ng a míi b»ng c¸ch: Chän ra c¸c phÇn tö nhá nhÊt trong a vµ ®Æt chóng theo thø tù tõ tr¸i qua ph¶i. C¸c phÇn tö ®· ®­îc chän sÏ kh«ng ®­îc xÐt trong c¸c lÇn chän tiÕp theo. B¶ng sau cho thÊy qu¸ tr×nh s¾p xÕp m¶ng a gåm 6 phÇn tö. Víi mçi b­íc s¾p, ta tÝnh Min cña c¸c phÇn tö cßn l¹i (phÇn tö ®­îc b«i ®en). 3 5 2 7 4 8 Min = 2 2 5 3 7 4 8 Min = 3 2 3 5 7 4 8 Min = 4 2 3 4 7 5 8 Min = 5 2 3 4 5 7 8 Min = 7 2 3 4 5 7 8 Min = 8 Sau ®©y lµ hµm s¾p xÕp chän void SapChon(int a[100], int n) { for (int i=0; i<n-1; i++) { int min = i; for (int j = i+1; j<n; j++) if (a[j] < a[min]) min = j; int tg = a[i]; a[i] = a[min]; a[min]=tg; } } S¾p xÕp b»ng ph­¬ng ph¸p chän cÇn n2/ 2 lÇn so s¸nh vµ n lÇn ho¸n vÞ. S¾p xÕp chÌn Ph­¬ng ph¸p nµy xuÊt ph¸t tõ ý t­ëng: NÕu m¶ng a cã duy nhÊt 1 phÇn tö th× nã ®· ®­îc s¾p. NÕu bæ sung mét phÇn tö n÷a vµo a th× phÇn tö bæ sung cÇn ®­îc ®Æt ë vÞ trÝ sao cho kh«ng thay ®æi tÝnh ®­îc s¾p cña c¸c phÇn tö ®· cã. Nh­ vËy, cã thÓ h×nh dung ph­¬ng ph¸p nµy b»ng lµ viÖc x©y dùng mét m¶ng míi b»ng c¸ch lÊy lÇn l­ît c¸c phÇn tö cña a vµ chÌn vµo mét m¶ng a míi sao cho kh«ng ph¸ vì tÝnh ®­îc s¾p cña c¸c phÇn tö ®· s¾p. 3 5 2 7 4 8 3 PhÇn tö ®Çu tiªn 3 5 ChÌn 5 vµo 2 3 5 ChÌn 2 vµo 2 3 5 7 ChÌn 7 vµo 2 3 4 5 7 ChÌn 4 vµo 2 3 4 5 7 8 ChÌn 8 vµo Ta xem xÐt qu¸ tr×nh chÌn mét phÇn tö vµo m¶ng míi (gi¶ sö chÌn 2 vµo). Khi ®ã, c¸c phÇn tö 3 vµ 5 ®· ®­îc chÌn vµ qu¸ tr×nh diÔn ra nh­ sau: B1 3 5 2 7 4 8 B2 3 5 7 4 8 B3 3 5 7 4 8 B4 2 3 5 7 4 8 2 Tg B1: LÊy phÇn tö 2 (a[i] ; i = 2) ®Ó ra mét biÕn trung gian Tg. B2: j = i-1 = 1; a[j] > Tg; dÞch chuyÓn a[j] sang ph¶i 1 vÞ trÝ. B3: j = j -1 = 0; a[j] > Tg; dÞch chuyÓn a[j] sang ph¶i 1 vÞ trÝ. B4: j = j -1 = -1; Lóc nµy j < 0 nªn chÌn Tg vµo a[j+1]. Nh­ vËy qu¸ tr×nh dÞch chuyÓn sang ph¶i sÏ kÕt thóc nÕu a[j] < = Tg hoÆc J < 0. Khi ®ã chØ cÇn chÌn Tg vµo vÞ trÝ a[j+1]. void SapChen(int a[100], int n) { for (int i=1; i< n; i++) { int Tg = a[i]; int j = i-1; while (a[j] > Tg && j >=0) { a[j+1] = a[j]; j--; } a[j+1]=Tg; } } 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 XuÊt ph¸t tõ bµi to¸n trén hai m¶ng ®­îc s¾p thµnh mét m¶ng còng ®­îc s¾p, h×nh thµnh lªn ph­¬ng ph¸p s¾p xÕp trÖn. XÐt bµi to¸n trén: gi¶ sö cã hai m¶ng a (n phÇn tö) vµ b (m phÇn tö) ®· ®­îc s¾p, ta cÇn trén l¹i ®Ó ®­îc mét m¶ng c còng ®­îc s¾p: void Tron(int a[100], int b[100], int c[100],int n, int m) { int max; if (a[n-1]>b[m-1]) max = a[n-1]+1; else max = b[m-1]+1; a[n]=b[m]=max; int i,j; i=j=0; for (int k=0; k<m+n-1; k++) if (a[i]<b[j]) { c[k]=a[i]; i++; } else { c[k]=b[j]; j++; } } B©y giê trë l¹i bµi to¸n s¾p xÕp trén. Gi¶ sö cã m¶ng c ch­a ®­îc s¾p nh­ h×nh sau: NÕu ta chia m¶ng c lµm hai phÇn vµ s¾p xÕp trªn hai phÇn ®ã th× ta thu ®­îc m¶ng c cã 2 nöa c1 vµ c2 ®· ®­îc s¾p d¹ng: Cuèi cïng, dïng gi¶i thuËt trén ë trªn ®Ó trén c1 vµ c2 ®Ó thu ®­îc mét m¶ng c ®· ®­îc s¾p: ý t­ëng trªn cho ta mét thuËt to¸n s¾p xÕp rÊt tèt nÕu nh­ trªn 2 m¶ng c1 vµ c2 ta l¹i ¸p dông chia thµnh c¸c m¶ng con ®Ó s¾p xÕp vµ trén chóng vµ cø nh­ vËy m·i cho tíi khi c¸c m¶ng con chØ cßn 1 phÇn tö. ¸p dông ®Ö quy vµo c¸ch chia, s¾p xÕp, trén nµy ta thu ®­îc ph­¬ng ph¸p s¾p xÕp trén æn ®Þnh . kh«ng ¶nh h­ëng bëi thø tù ban ®Çu cña d÷ liÖu. Ph­¬ng ph¸p nµy nãi chung cÇn n.lg(n) lÇn so s¸nh ®Ó s¾p xÕp mét tËp d÷ liÖu n phÇn tö. Ph­¬ng ¸n s¾p xÕp QuickSort ý t­ëng cña QuickSort còng lµ chia m¶ng a cÇn s¾p thµnh 2 phÇn nh­ ph­¬ng ph¸p trén, tuy nhiªn ®iÓm chia ®­îc tÝnh to¸n sao cho phï hîp. ®Ó x¸c ®Þnh ®­îc ®iÓm chia, ta sö dông hµm Partition(L, R). Hµm nµy sÏ sö dông ®Ó tr¶ vÒ ®iÓm chia lµm c¬ së ®Ó chia m¶ng a. NÕu ®iÓm chia lµ i th×: i = Partition(L, R); Khi cã ®iÓm chia råi, ta sÏ chia a thµnh 2 nöa theo ®iÓm chia vµ ¸p dông viÖc s¾p trªn 2 nöa, trén l¹i ®Ó thu ®­îc mét m¶ng ®· ®­îc s¾p. Tuy nhiªn ®Ó s¾p trªn 2 nöa cña a, ta còng ¸p dông ph­¬ng ph¸p t­¬ng tù. Nh­ vËy, gi¶i thuËt cã thÓ nh­ sau: void QuickSort(int L, int R) { int i= Partition(L, R); QuickSort(L, i-1); QuickSort(i+1, R); } VÊn ®Ò cßn l¹i lµ hµm Partition x¸c ®Þnh ®iÓm chia nh­ thÕ nµo. Ta cã thÓ h×nh dung ®iÒu nµy nh­ sau: B1: LÊy phÇn tö cuèi cïng cña m¶ng lµm phÇn tö cÇm canh (tøc lµ a[R]). B2: Cho i ch¹y tõ tr¸i sang cho tíi khi gÆp phÇn tö lín h¬n phÇn tö cÇm canh. Cho j ch¹y tõ bªn ph¶i vÒ cho tíi khi gÆp phÇn tö nhë h¬n phÇn tö cÇm canh. B3: §¶o chç hai phÇn tö a[i] cho a[j]. Cho i, j tiÕp tôc ch¹y nh­ trong B2. TiÕp tôc ®æi chç nh­ vËy cho tíi khi i vµ j giao nhau (tøc lµ i>=j). B4: §æi chç a[i] cho a[j] lÇn cuèi. Khi ®ã, dÔ thÊy c¸c phÇn tö bªn tr¸i cña a[i] ®Òu nhë h¬n a[i] vµ c¸c phÇn tö bªn ph¶i th× lín h¬n nã. §iÓm i chÝnh lµ ®iÓm chia t×m ®­îc. return i; ThuËt to¸n nµy, thªm mét chót c¶i tiÕn sÏ lµ thuËt to¸n s¾p xÕp rÊt tèt (trong tr­êng hîp d÷ liÖu bÊt kú) víi trung b×nh 2n.lg(n) phÐp so s¸nh. ThËt vËy, gi¶i thuËt Partition cÇn duyÖt qua n phÇn tö ®Ó x¸c ®Þnh ®iÓm chia. Khi cã ®iÓm chia råi ta cÇn s¾p xÕp c¸c phÇn tö trªn 2 nöa cña m¶ng. (mçi nöa tÝnh trung b×nh cã n/2 phÇn tö. Nh­ vËy tæng phÝ tæn lµ: Cn = 2 Cn/2 + n. Gi¶i c«ng thøc truy håi nµy cho ta ®­îc ®é phøc t¹p: Cn = 2n.ln(n) Ch­¬ng V: Kü thuËt lËp tr×nh víi con trá Khai b¸o vµ sö dông con trá §Þa chØ cña biÕn: Khi khai b¸o mét biÕn, m¸y tÝnh sÏ cÊp ph¸t mét vïng nhí ®Ó chøa gi¸ trÞ cña biÕn. KÝch th­íc cña vïng nhí ®­îc x¸c ®Þnh tïy theo kiÓu biÕn. Vïng nhí ph¶i ®­îc ®Æt tªn, ta gäi lµ tªn biÕn. §Ó qu¶n lý biÕn nµy, vïng nhí ®­îc ®¸nh ®Þa chØ, gäi lµ ®Þa chØ cña biÕn. §Þa chØ cña biÕn lµ ®Þa chØ cña byte ®Çu tiªn trong vïng nhí cña biÕn. §Ó lÊy ®Þa chØ cña biÕn, ta sö dông phÐp to¸n & theo có ph¸p: ; Con trá: §«i khi, ta muèn lÊy ®Þa chØ cña c¸c biÕn. V× vËy cÇn cã c¸c biÕn ®Ó chøa c¸c ®Þa chØ nµy gäi lµ c¸c biÕn con trá. Nh­ vËy, con trá lµ biÕn dïng ®Ó chøa ®Þa chØ. C¸c biÕn cã nhiÒu kiÓu kh¸c nhau, v× vËy, ®Ó chøa ®Þa chØ cña chóng, con trá còng cã nhiÒu kiÓu. KiÓu cña con trá trïng víi kiÓu biÕn mµ nã sÏ chøa ®Þa chØ. VD: con trá kiÓu float dïng ®Ó chøa ®Þa chØ c¸c biÕn kiÓu float, con trá kiÓu int dïng ®Ó chøa ®Þa chØ c¸c biÕn kiÓu int… Mét con trá còng cÇn ph¶i ®­îc khai b¸o tr­íc khi sö dông. Có ph¸p khai b¸o nh­ sau: ;. VD: c©u lÖnh int a, b, *p, *q; sÏ khai b¸o hai biÕn a, b kiÓu nguyªn vµ hai con trá p, q kiÓu nguyªn. Hai con trá p, q cã cïng kiÓu víi hai biÕn a, b nªn cã thÓ dïng ®Ó chøa ®Þa chØ cña hai biÕn a, b. Khi cã con trá, ta cã thÓ sö dông c¸c phÐp lÊy ®Þa chØ th«ng th­êng ®Ó g¸n ®Þa chØ vµo con trá. VD: c¸c c©u lÖnh p = & a; q = &b; sÏ lÊy ®Þa chØ cña hai biÕn a, b ®Ó g¸n vµo con trá p vµ q. Khi ®ã, p vµ q chøa ®Þa chØ cña hai biÕn a, b vµ ta nãi p trá tíi a, q trá tíi b. Sö dông con trá Ta sö dông biÕn con trá nh­ mét biÕn th«ng th­êng th«ng qua tªn biÕn. Khi sö dông tªn con trá trong biÓu thøc th× ®Þa chØ cña vïng nhí mµ nã trá tíi sÏ ®­îc sö dông trong biÓu thøc chø kh«ng ph¶i lµ gi¸ trÞ cña vïng nhí. Khi con trá p trá tíi biÕn a th× ®Ó sö dông gi¸ trÞ cña biÕn a nµy th«ng qua con trá p ta viÕt *p. Nh­ vËy 3 c¸ch viÕt sau lµ t­¬ng ®­¬ng: b = 2*a + 3; b = 2*(*p) + 3; *q = 2*(*p) + 3;// víi q lµ con trá trá tíi biÕn b. VD: void main() { int a, b, x, *p, *q; cout<<”NhËp a”; cin>>a; p = &a; q = &b; b = 2*a+3; cout<<b; *q = 2*a +3; cout<<b; *q = 2*(*p) +3. cout<<b; getch(); } NhËn xÐt: Khi lÊy ®­îc ®Þa chØ cña biÕn chøa vµo con trá, ta cã thÓ sö dông con trá ®Ó thay ®æi gi¸ trÞ cña biÕn mµ nã trá tíi. §Æc biÖt, ta cã thÓ g¸n con trá p cho mét con trá q kh¸c cïng kiÓu. Khi ®ã, hai con trá p, q sÏ trá tíi cïng mét vïng nhí cña cïng mét biÕn. VD: void main() { int a, *p, *q; a = 2; p=&a; cout<<*p; q = p; cout<<*q; getch(); } Con trá vµ hµm C¸c hµm ®Þnh nghÜa theo c¸c c¸ch ®· häc chØ tr¶ vÒ mét gi¸ trÞ duy nhÊt th«ng qua tªn hµm. VËy khi muèn hµm tr¶ vÒ nhiÒu gi¸ trÞ cung lóc th× lµm thÕ nµo? §Ó tr¶ lêi c©u hái nµy, trong c¸c hµm cã ®èi sè, ta chia ®èi sè lµm hai lo¹i: ®èi vµo vµ ®èi ra. §èi vµo: Lµ c¸c ®èi sè sÏ truyÒn c¸c gi¸ trÞ vµo trong hµm ®Ó sö dông trong th©n hµm. §èi ra: lµ c¸c ®èi nhËn gi¸ trÞ mµ hµm sÏ tr¶ vÒ. Nh­ vËy, ngoµi kh¶ n¨ng tr¶ vÒ gi¸ trÞ th«ng qua tªn hµm, hµm cßn cã thÓ tr¶ vÒ c¸c gi¸ trÞ kh¸c th«ng qua c¸c ®èi ra. VD: Hµm gi¶i ph­¬ng tr×nh bËc hai: a, b, c lµ c¸c ®èi vµo. Hai nghiÖm x1, x2 (nÕu cã) cã thÓ lµ c¸c ®èi ra. C¸c ®èi ra b¾t buéc ph¶i lµ con trá. V× c¸c ®èi ra lµ c¸c con trá nªn khi truyÒn tham sè cho c¸c ®èi ra, c¸c tham sè ®ã ph¶i lµ c¸c ®Þa chØ. VD: ViÕt ch­¬ng tr×nh gi¶i ph­¬ng tr×nh bËc hai. NÕu ph­¬ng tr×nh cã nghiÖm x1, x2 h·y tÝnh gi¸ trÞ biÓu thøc P = 2*x1 + x2. int PTBH(int a, int b, int c, int *x1, int *x2) { float dt; if (a==0) return 0; dt = b*b-4*a*c; if(dt<0) return –1; *x1 = (-b+sqrt(dt))/(2*a); *x2 = (-b-sqrt(dt))/(2*a); return 1; } void main() { float a, b, c, x1, x2; printf(“NhËp a b c”); scanf(“%f%f%f”, &a, &b, &c); float s = PTBH(a, b, c, &x1, &x2); if (s==0) cout<<”Ph­¬ng tr×nh kh«ng ph¶i bËc hai”; else if (s==-1) cout<<”Ph­¬ng tr×nh v« nghiÖm”; else { cout<<” Ph­¬ng tr×nh cã hai nghiÖm”<<x1<<” vµ “<<x2; float P = 2* x1+x2; cout<<”Gi¸ trÞ cña P “<<P; } getch(); } NhËn xÐt: C¸c gi¸ trÞ tr¶ vÒ cña hµm t¹i x1 vµ x2 cã thÓ ®­îc sö dông tiÕp trong ch­¬ng tr×nh. Ch­¬ng tr×nh sö dông c¶ c¸c gi¸ trÞ tr¶ vÒ cña c¸c ®èi ra vµ cña tªn hµm. Con trá vµ m¶ng Con trá vµ m¶ng mét chiÒu Nh­ ®· biÕt, c¸c phÇn tö cña m¶ng cã thÓ ®­îc x¸c ®Þnh th«ng qua chØ sè. VÝ dô phÇn tö thø nhÊt lµ a[0], phÇn tö thø 2 lµ a[1]… Ta cßn cã c¸ch thø 2 ®Ó x¸c ®Þnh c¸c phÇn tö cña m¶ng, kh«ng ph¶i th«ng qua c¸c chØ sè mµ th«ng qua con trá. Khi khai b¸o mét m¶ng a gåm 10 phÇn tö, m¸y tÝnh sÏ cÊp ph¸t 10 « nhí liªn tiÕp nhau. §iÒu ®Æc biÖt lµ: ®Þa chØ cña phÇn tö ®Çu tiªn cña m¶ng ®­îc chøa trong tªn m¶ng. Nh­ vËy a t­¬ng ®­¬ng víi &a[0] vµ tªn m¶ng t­¬ng ®­¬ng víi mét con trá chøa ®Þa chØ cña phÇn tö ®Çu tiªn cña m¶ng. Ta cã: a chøa ®Þa chØ &a[0]. a+i chøa ®Þa chØ &a[i]. Nh­ vËy, nÕu p lµ con trá cïng kiÓu ta cã thÓ g¸n: p = a; vµ khi ®ã: a[i] = p[i] = *(a+i) = *(p+i); Thay b»ng truy cËp tíi phÇn tö thø i+1 cña m¶ng qua a[i] ta cã thÓ viÕt p[i] hoÆc *(a+i) hoÆc *(p+i). VD1: float a[4]; a[0] = 0; a[1] = 1; a[2] = 2; a[3] = 3; cout<<a[3]; cout<<*(a+3); float *p; p = a; cout<<p[3]; cout<<*(p+3); getch(); } VD2: NhËp vµo mét m¶ng 4 sè nguyªn vµ tÝnh tæng cña c¸c sè ®ã. C¸ch 1: void main() { float a[4]; for (int i=0; i<4; i++) { cout<<”NhËp a[“<<i<<”]”; cin>>a[i]; } float T=0; for(i=0; i<4; i++) T+=*(a+i); cout<<”Tæng b»ng”<<T; getch(); } C¸ch 2: void main() { float a[4], *p; for (int i=0; i<4; i++) { cout<<”NhËp a[“<<i<<”]”; cin>>a[i]; } p=a; float T=0; for(i=0; i<4; i++) T+=p[i]; cout<<”Tæng b»ng”<<T; getch(); } C¸ch 3: void main() { float a[4], *p; for (int i=0; i<4; i++) { cout<<”NhËp a[“<<i<<”]”; cin>>a[i]; } p=a; float T=0; for(i=0; i<4; i++) T+=*(p+i); cout<<”Tæng b»ng”<<T; getch(); } Do tªn m¶ng còng t­¬ng ®­¬ng víi mét con trá nªn khi p lµ mét con trá kiÓu nguyªn, ta cã thÓ khai b¸o int *p; nh­ng còng cã thÓ khai b¸o nh­ mét m¶ng h×nh thøc: int p[]. MÆt kh¸c, thËm chÝ ta cã thÓ sö dông con trá p nh­ mét m¶ng. Hµm Sum2() sau sÏ sö dông con trá a nh­ mét m¶ng. VD: ViÕt hµm tÝnh tæng c¸c phÇn tö cña m¶ng 4 phÇn tö. double Sum1(double a[]) { double T=0; for(int i=0; i<4; i++) T+=a[i]; return T; } double Sum2(double *a) {double T=0; for(int i=0; i<4; i++) T+=a[i]; return T; } void main() { double *b; b[0] = 1; b[1] = 3; b[2] = 2; b[3] = 5; cout<<”Tæng thø nhÊt”<<Sum1(b); cout<<”Tæng thø hai”<<Sum2(b); getch(); } Con trá vµ m¶ng hai chiÒu Khi khai b¸o m¶ng hai chiÒu A[2][3], m¸y tÝnh sÏ cÊp ph¸t vïng nhí nh­ sau: A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2] Nh­ vËy, vÒ c¸ch tæ chøc bé nhí, m¶ng hai chiÒu thùc chÊt lµ m¶ng mét chiÒu. Ta gäi lµ m¶ng cña m¶ng. Tuy nhiªn, ta kh«ng thÓ g¸n trùc tiÕp tªn m¶ng hai chiÒu A cho mét con trá p cïng kiÓu mµ ph¶i sö dông to¸n tö Ðp kiÓu. Víi c¸ch hiÓu trªn, nÕu ta g¸n con trá thùc p = (float*)A th×: p trá tíi A[0][0]. p+1 trá tíi A[0][1]. p+2 trá tíi A[0][2]. p+3 trá tíi A[1][0]. p+4 trá tíi A[1][1]. p+5 trá tíi A[1][2]. Nh­ vËy ta cã thÓ sö dông con trá trong qu¸ tr×nh truy cËp m¶ng hai chiÒu. Víi m¶ng hai chiÒu, ®Ó nhËp c¸c phÇn tö m¶ng, ta chØ cÇn mét vßng lÆp. VD: NhËp d÷ liÖu cho m¶ng hai chiÒu th«ng qua con trá: void main() { float a[2][3], *p; p=(float*) a; for(int i=0; i<6; i++) scanf(“%f”, p+i); } HoÆc cã thÓ dïng ngay a nh­ lµ mét con trá víi to¸n tö Ðp kiÓu: void main() { float a[2][3]; for(int i=0; i<6; i++) scanf(“%f”, (float*)(a + i)); } M¶ng con trá M¶ng con trá còng t­¬ng tù nh­ m¶ng th«ng th­êng, chØ kh¸c ë chç, mçi phÇn tö m¶ng lµ mét con trá. Nh­ vËy ta chØ sö dông m¶ng con trá ®Ó chøa c¸c dÞa chØ chø kh«ng chøa c¸c gi¸ trÞ nh­ m¶ng th«ng th­êng. Khai b¸o: int a[100]: lµ khai b¸o biÕn m¶ng th«ng th­êng a cã tèi ®a 100 phÇn tö. M¶ng a cã thÓ dïng ®Ó chøa mét d·y sè cã tèi ®a 100 phÇn tö. Khai b¸o: int * a[100]: lµ khai b¸o biÕn m¶ng con trá a. M¶ng a cã tèi ®a 100 phÇn tö, mçi phÇn tö lµ mét con trá. M¶ng a cã thÓ dïng ®Ó chøa 100 ®Þa chØ kh¸c nhau. Có ph¸p khai b¸o: ; M¶ng con trá kh«ng dïng ®éc lËp mµ nã th­êng ®­îc dïng kÌm víi c¸c biÕn kh¸c (th­êng lµ m¶ng). §Æc biÖt, m¶ng con trá thÝch hîp trong bµi to¸n vÒ xö lý ma trËn th­a. XÐt bµi to¸n cã ma trËn th­a: Cã n xe t¶i chuyªn chë vËt liÖu. Sè liÖu tõng chuyÕn cña tõng xe trong ngµy ®­îc cho trong b¶ng sau (VD n=4, ®¬n vÞ TÊn) Xe 1 Xe 2 Xe 3 Xe 4 2 3 4 3 4 4 3 5 2 3 4 3 4 3 5 Theo b¶ng sè liÖu, xe 1 chë ®­îc 3 chuyÕn/ ngµy víi tæng céng 9 tÊn, xe 2 chë ®­îc 2 chuyÕn víi tæng céng 7 tÊn… VÊn ®Ò ®Æt ra lµ sö dông kiÓu d÷ liÖu nµo ®Ó l­u tr÷ b¶ng sè liÖu nµy. Ta nghÜ ngay ®Õn kiÓu m¶ng. Nh­ vËy m¶ng sè liÖu sÏ nh­ sau: 2 3 4 2 3 4 3 3 4 5 4 3 4 3 5 Ma trËn nµy l·ng phÝ rÊt nhiÒu « nhí (v× kh«ng dïng ®Õn) cã thÓ xem nh­ lµ mét ma trËn th­a. §Ó kh¾c phôc ®­îc tÝnh tr¹ng l·ng phÝ bé nhí, ta chuyÓn sang sö dông m¶ng 1 chiÒu, nh­ vËy, m¶ng sè liÖu sÏ lµ: 2 3 4 3 4 4 3 5 2 3 4 3 4 3 5 Nh­ vËy sÏ tr¸nh ®­îc t×nh tr¹ng l·ng phÝ bé nhí. Tuy nhiªn, mét vÊn ®Ò kh¸c n¶y sinh lµ lµm thÕ nµo ®Ó cã ®­îc sè liÖu cña xe i (i=1..4) bÊt kú. Râ rµng ta cÇn dïng ®Õn mét m¶ng con trá ®Ó l­u ®Þa chØ cña phÇn tö ®Çu tiªn trong d·y c¸c sè liÖu cña tõng xe, nh­ vËy th×: 2 3 4 3 4 4 3 5 2 3 4 3 4 3 5 M¶ng con trá p[] Dùa vµo m¶ng con trá nµy ta cã thÓ lÊy ®­îc th«ng tin cña tõng xe. Sau ®©y lµ code cña ch­¬ng tr×nh. #include "conio.h" #include "iostream.h" #include "stdio.h" void main() { clrscr(); int a[100], n; int *p[50], *q; cout>n; //nhap thong tin cho n xe, ket thuc bang so 0. p[0] =q = a;// cho con tro q vaf p[0] tro toi a[0] for (int i=0; i<n; i++) { cout<<"Nhap so lieu cho xe "<<i+1<<endl; cin>>*q; while(*q!=0) { q++; cin>>*q; } p[i+1]=q; } //xuat so lieu cua xe bay ky ra man hinh int stt; cout>stt;//nhap stt thuoc [0..n-1] for (q=p[stt-1]; q<p[stt]; q++) cout<<*(q)<<" "; getch(); } Con trá hµm Con trá hµm dïng ®Ó trá tíi c¸c hµm (hay chøa ®Þa chØ cña c¸c hµm). Tuú theo d¹ng thøc cña c¸c hµm mµ ta khai b¸o con trá hµm t­¬ng øng. Hµm: (); Con trá hµm t­¬ng øng: )> ; Trong ®ã: : Ph¶i trïng víi kiÓu tr¶ vÒ cña hµm mµ nã sÏ trá tíi. : lµ tuú ý ®Æt. : ph¶i t­¬ng øng cíi c¸c kiÓu ®èi cña hµm mµ nã sÏ trá tíi. VD: Hµm Con trá hµm t­¬ng øng int GT(int n); int (*p) (int) void Check(double x, double y); void (*q) (double, double) Khi khai b¸o con trá hµm song, ta cã thÓ cho nã trá vµo hµm t­¬ng øng b»ng c¸ch g¸n: = ; VD: p = GT; hoÆc q = Check; Tõ ®©y ta cã thÓ sö dông tªn con trá thay cho tªn hµm. Trong tr­êng hîp khi gäi hµm, tham sè cña hµm l¹i lµ mét hµm kh¸c th× ®èi sè t­¬ng øng ph¶i lµ con trá hµm. VD: ViÕt hµm tÝnh gi¸ trÞ cña biÓu thøc F(x) = , sau ®ã viÕt hµm tÝnh P(x, y) = F(x) + F(y) include "conio.h" #include "iostream.h" #include "stdio.h" float ham(float x) { return (x*x-1)/ (x*x+1); } float F(float (*p)(float),float x, float y) { return p(x)+p(y); } void main() { clrscr(); int x=5; int y=3; cout<<"F la "<<F(ham, x, y); getch(); } VD2: ViÕt hµm tÝnh gi¸ trÞ biÓu thøc F(x) = #include "conio.h" #include "iostream.h" #include "stdio.h" float TS(float x) { return (x*x-1); } float MS(float x) { return (x*x+1); } float F(float (*p)(float), float (*q) (float), float x) { return p(x)/q(y); } void main() { clrscr(); int x=5; cout<<"F la "<<F(TS,MS, x); getch(); }