Đề cương chi tiết kỹ thuật lập trình

7 9 10 §Ó 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 ch­a ®­î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<n&&j<m) if(a[i]<b[j]) {c[k]=a[i]; i++; k++;} else {c[k]=b[j]; j++; k++;} // G¾n ®u«i------------------------------ if(i<n) for(int t=i; t<n; t++) {c[k]=a[t]; k++;} else for(int t=j; t<m; t++) {c[k]=b[t]; 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Ó ch­a ®­î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: b 1 4 6 7 9 10 11 a 2 3 5 11 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<b[m-1]) Max=b[m-1]; a[n]=b[m]=Max+1; //------------------------ int i=0, j=0; for(int k=0; k<n+m; k++) if(a[i]<b[j]) {c[k]=a[i]; i++;} else {c[k]=b[j]; j++;} } ý t­ëng cña gi¶i thuËt s¾p xÕp trén nh­ sau: - Gi¶ sö cã m¶ng a ch­a s¾p: 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 nh­ng 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]<b[j]) {a[k]=b[i];i++;} else {a[k]=b[j];j--;} } } S¾p xÕp b»ng trén sö dông kho¶ng n lg(n) lÇn so s¸nh ®Ó s¾p bÊt kú mét m¶ng nµo gåm n phÇn tö. 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µ æ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. 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]<c) L=M+1; } while(a[M]!=c && L<R); if(a[M]==c) cout<<c<<" xuat hien tai "<<M; else cout<<c<<" khong xuat hien"; } 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) { 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 10 11 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 10 1 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)) M¶ng hai chiÒu II.1. C¸c thao t¸c c¬ b¶n trªn m¶ng hai chiÒu 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 nh­ng kh¸c nhau vÒ chØ sè dïng ®Ó l­u 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: a 0 1 2 3 0 1 2 a[1][2] Khai b¸o m¶ng 2 chiÒu: [] []; 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. X Y 1 x 80 y 25 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(35 + 3 *j, 5 + i); gotoxy(5 + 3 *j, 15 + 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<n; i++) for(j=0; j<m; j++) { gotoxy(5 + 3 * j, 5 + i); cin>>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<n; i++) for(j=0; j<m; j++) { gotoxy(35 + 3 * j, 5 + i); cout<<a[i][j]; } 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<n; i++) for(j=0; j<m; j++) { //Th¨m phÇn tö cã chØ sè [i][j] } 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: c[i][j] = void main() { int a[50][50], b[50][50], c[50][50]; int n, m, k; clrscr(); cout>n; cout>m; cout>k; for(int i=0; i<n; i++) for(int j=0; j<k; j++) { gotoxy(5+3*j, 5+i); cin>>a[i][j]; } for(i=0; i<k; i++) for(j=0; j<m; j++) { gotoxy(35+3*j, 5+i); cin>>b[i][j]; } for(i=0; i<n; i++) for(j=0; j<m; j++) { c[i][j]=0; for(int t=0; t<k; t++)c[i][j]+=a[i][t]*b[t][j]; gotoxy(5+3*j, 15+i); cout<<c[i][j]; } getch(); } 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 ch­a 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: (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: (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Ö. void main() { int a[50][50];int n; clrscr(); cout>n; for(int i=0; i<n; i++) for(int j=0; j<n; j++) { gotoxy(5+3*j, 5+i); cin>>a[i][j]; } int d=0; for(i=0; i<n; i++) for(j=0; j<n; j++) { if(i==j && a[i][j]!=0) d++; if(i<j && a[i][j]<=0) d++; if(i>j && a[i][j]>=0) d++; } if(d==0) cout<<"Ma tran la hop le !"; else cout<<"Ma tran la khong hop le !"; getch(); } 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 l­u 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>n; cout>m; cout<<"Nhap dt cua tung cua hang-tung thang:"; for(int i=0; i<n; i++) for(int j=0; j<m; j++) { gotoxy(5+3*j, 5+i); cin>>a[i][j]; } for(i=0; i<n; i++) { int d=0; for(j=0; ja[i][j+1]) d++; if (d==m-1) cout<<"Cua hang "<<i+1<<" se bi dong cua !"; } getch(); } X©u ký tù – m¶ng c¸c ký tù III.1. Mét sè l­u ý 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 []; (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 ch­a 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 ch­a 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). 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); 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ù ®ã. 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 ch­a 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++) if(S[i]==' ' && S[i+1] !=' ') d++; if(S[0]!=' ') d++; cout<<"Xau co: "<<d<<" tu !"; getch(); } 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) BiÕn ®Õm t­¬ng øng A (65) d[0] = d[65-65] B (66) d[1] = d[66-65] C (67) d[2] = d[67-65] … … S[i] ((int) S[i]) d[(int) S[i]-65] Ch÷ c¸i th­êng (m· ASCII) BiÕn ®Õm t­¬ng øng a (97) d[0] = d[97- 97] b (98) d[1] = d[98-97] c (99) d[2] = d[99-97] … … S[i] ((int) S[i]) 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]. 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 "<<d[i]<<" lan !"<<endl; getch(); } 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 ®Ó l­u 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í) nh­ng ®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: 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 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 lµ ®Þa chØ cña a[0] a+1 lµ ®Þa chØ cña a[1] a+2 lµ ®Þa chØ cña a[2] … a+i lµ ®Þa chØ cña a[i] Nh­ vËy th× *a lµ a[0] *(a+1) lµ a[1] *(a+2) lµ a[2] … *(a+i) 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 lµ ®Þa chØ cña a p+1 lµ ®Þa chØ cña « nhí ngay sau a … p+i lµ ®Þa chØ cña « nhí thø i kÓ tõ a. p a p+1 p+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. GPTB2 a b c 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. 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; cout>b; cout>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(); } 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<n; i++) { if(a[i]%2==0) *T1+=*(a+i); else *T2+=*(a+i); if(a[i]%3==0) *T3+=*(a+i); } } void main() { int *a;int n; cout>n; for(int i=0; i<n; i++) cin>>a[i]; int T1, T2, T3; TinhTong(a,n,&T1,&T2,&T3); cout<<"Tong chan="<<T1<<endl; cout<<"Tong le="<<T2<<endl; cout<<"Tong chia het 3="<<T3; getch(); } Hµm TinhTong() ë trªn kh«ng tr¶ vÒ gi¸ trÞ nµo th«ng qua tªn hµm (hµm void) nh­ng l¹i tr¶ vÒ ®ång thêi 3 gi¸ trÞ th«ng qua 3 ®èi ra. C¸c tham sè T1, T2, T3 ®­îc truyÒn vµo hµm chØ lµm nhiÖm vô duy nhÊt lµ chøa c¸c tæng tÝnh ®­îc vµ “mang” ra khái hµm. III. CÊp ph¸t vµ gi¶i phãng bé nhí cho con trá III.1. CÊp ph¸t bé nhí ®éng cho con trá ViÖc sö dông con trá thay cho m¶ng sÏ gióp tiÕt kiÖm bé nhí nÕu nh­ ta cÊp ph¸t bé nhí ®éng cho con trá (tøc sö dông tíi ®©u, cÊp ph¸t tíi ®ã). ViÖc cÊp ph¸t bé nhí cho con trá sö dông c¸c hµm ®Þnh vÞ bé nhí (allocation memory) cña C++. Cã rÊt nhiÒu hµm lµm c«ng viÖc nµy, tuy nhiªn ta hay sö dông hai hµm calloc vµ malloc Hµm calloc: Có ph¸p: = (*) calloc(, ); Trong ®ã, lµ sè « nhí cÇn cÊp ph¸t (sè phÇn tö cña m¶ng); lµ kÝch th­íc cña mét « nhí. Hµm calloc nÕu thùc hiÖn thµnh c«ng sÏ cÊp ph¸t mét vïng nhí cã kÝch th­íc * Byte vµ sÏ trá tíi « nhí ®Çu tiªn cña vïng nhí nµy. Ng­îc l¹i, nÕu thùc hiÖn kh«ng thµnh c«ng (do kh«ng ®ñ bé nhí hoÆc hoÆc kh«ng hîp lÖ) hµm sÏ tr¶ vÒ gi¸ trÞ NULL (tøc con trá trá tíi NULL). Gi¶ sö p lµ mét m¶ng nguyªn, khi ®ã kÝch th­íc mçi « nhí lµ 2 Byte (tøc = 2). NÕu p lµ m¶ng thùc th× =4 .v.v…To¸n tö sizeof sÏ cho ta biÕt kÝch th­íc cña mçi « nhí thuéc mét kiÓu bÊt kú. Muèn vËy ta chØ cÇn viÕt: sizeof(). VÝ dô sizeof(int) = 2; sizeof(float) = 4; .v.v… Hµm calloc thuéc th­ viÖn alloc.h. VÝ dô 1: NhËp mét m¶ng p gåm n phÇn tö nguyªn, sö dông hµm calloc cÊp ph¸t bé nhí ®éng. int *p, n; cout>n; p = (int *) calloc(n, sizeof(int)); if(p==NULL) cout<< “Cap phat bo nho khong thanh cong”; else //Nhap mang for(int i=0; i<n; i++) { cout<< “p[”<<i<< “]=”; cin>>p[i]; } Hµm malloc: T­¬ng tù nh­ hµm calloc, hµm malloc sÏ cÊp ph¸t mét vïng nhí cho con trá. Có ph¸p nh­ sau: = (*) malloc(); Trong ®ã lµ kÝch th­íc cña « nhí cÇn cÊp ph¸t tÝnh b»ng Byte. Ch¼ng h¹n ta cÇn cÊp ph¸t bé nhí cho mét m¶ng a gåm 10 phÇn tö nguyªn. Khi ®ã kÝch th­íc vïng nhí cÇn cÊp ph¸t = 10 * sizeof(int) = 10*2=20 Byte, ta viÕt: a = (int*) malloc(20); hoÆc a = (int*) malloc(10 * sizeof(int)); VÝ dô 2: NhËp mét m¶ng p gåm n phÇn tö nguyªn, sö dông hµm malloc cÊp ph¸t bé nhí ®éng. int *p, n; cout>n; p = (int *) malloc(n*sizeof(int)); if(p==NULL) cout<< “Cap phat bo nho khong thanh cong”; else //Nhap mang for(int i=0; i<n; i++) { cout<< “p[”<<i<< “]=”; cin>>p[i]; } VÝ dô 3. NhËp mét m¶ng a gåm n phÇn tö thùc b»ng c¸ch sö dông con trá vµ cÊp ph¸t bé nhí ®éng. T×m phÇn tö lín nhÊt vµ lín thø nh× trong m¶ng. void main() { float *a;int n; cout>n; a = (float*) calloc(n, sizeof(float)); if(a==NULL) cout<<"cap phat bo nho that bai!"; else { for(int i=0; i<n; i++) { cout<<"a["<<i<<"]="; cin>>*(a+i); } int Max1, Max2; //Tim phan tu lon nhat chua vao Max1 Max1=a[0]; for(i=0; i<n; i++) if(Max1<*(a+i)) Max1=*(a+i); //Tim phan tu lon thu nhi chua vao Max2 i=0; while(a[i]==Max1) i++; Max2=a[i]; for(i=0; i<n; i++) if(Max2<*(a+i) && *(a+i) !=Max1) Max2=*(a+i); //In ket qua ra man hinh cout<<"Phan tu lon nhat = "<<Max1<<endl; cout<<"Phan tu lon thu nhi = "<<Max2<<endl; } getch(); } Gi¶i thuËt trªn sÏ kh«ng cho kÕt qu¶ ®óng khi tÊt c¶ c¸c phÇn tö cña m¶ng b»ng nhau (kh«ng tån t¹i sè lín thø nh×). Ta cã thÓ kh¾c phôc ®iÒu ®ã b»ng c¸ch kiÓm tra tr­íc tr­êng hîp nµy. III.2. CÊp ph¸t l¹i hoÆc gi¶i phãng bé nhí cho con trá §«i khi, trong qu¸ tr×nh ho¹t ®éng, kÝch th­íc cña m¶ng l¹i thay ®æi. NÕu ta sö dông cÊp ph¸t bé nhí ®éng th× kÝch th­íc cña m¶ng “võa ®ñ dïng” nªn nÕu kÝch th­íc nµy t¨ng hoÆc gi¶m (khi ch­¬ng tr×nh thùc thi míi ph¸t sinh ®iÒu nµy) th× cÇn thiÕt ph¶i cÊp ph¸t l¹i bé nhí cho con trá. §Ó lµm ®iÒu ®ã, ta sö dông hµm realloc. Hµm nµy cã nhiÖm vô cÊp ph¸t mét vïng nhí víi kÝch th­íc míi cho m¶ng (con trá) nh­ng vÉn gi÷ nguyªn c¸c gi¸ trÞ vèn cã cña m¶ng. Có ph¸p: = (*) realloc(, ); Trong ®ã, ®­îc tÝnh b»ng Byte. VÝ dô: NhËp vµo mét m¶ng a gåm n phÇn tö nguyªn. H·y sao chÐp c¸c gi¸ trÞ ch½n cña m¶ng ®Æt vµo cuèi m¶ng. Gi¶ sö ta cã m¶ng a ban ®Çu gåm c¸c phÇn tö nh­ sau: 1 4 3 2 6 5 Sau khi sao chÐp c¸c phÇn tö ch½n ®Æt vµo cuèi m¶ng, m¶ng a cã d¹ng: 1 4 3 2 6 5 4 2 6 Râ rµng kÝch th­íc cña m¶ng a bÞ thay ®æi (t¨ng lªn). Mçi khi cã mét phÇn tö ch½n ®­îc ®Æt vµo cuèi m¶ng th× kÝch th­íc cña m¶ng ®­îc t¨ng lªn 1. Do ®ã cÇn cÊp ph¸t l¹i bé nhí cho a víi kÝch th­íc t¨ng thªm 1 « nhí (2 Byte). void main() { int *a;int n; cout>n; a = (int*) calloc(n, sizeof(int)); if(a==NULL) cout<<"cap phat bo nho that bai!"; else { for(int i=0; i<n; i++) { cout<<"a["<<i<<"]="; cin>>*(a+i); } int m=n; for(i=0; i<m; i++) if(a[i]%2==0) { a = (int*) realloc(a,(n+1)*sizeof(int)); a[n]=a[i];n++; } } for(int i=0; i<n; i++) cout<<a[i]<<" "; getch(); } 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­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 l­u 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); 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 NhËp hai sè nguyªn, tÝnh tæng, hiÖu, tÝch, th­¬ng, ®ång d­. 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­?) ViÕt ch­¬ng tr×nh tÝnh gi¸ trÞ biÓu thøc: F(x) = (x2+e|x|+sin2(x))/ Ch­¬ng II: c¸c cÊu tróc ®iÒu khiÓn 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Î. 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. 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. 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? 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. 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. 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. ------------------- 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. ------------------- 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. 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? 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 = 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 F = 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 = 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. 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]. 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. 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 ®ã. 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. 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? 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. §Ó 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)) < e. 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 e = 0.00001. LËp tr×nh ®Ó tÝnh sin(x) víi ®é chÝnh x¸c e = 0.00001 theo c«ng thøc : sin(x) = x – x3/3! + x5/ 5! + …+ (-1)nx(2n+1)/ (2n+1)!. 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Ó 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]? 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 = 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 = 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. ViÕt ch­¬ng tr×nh gi¶i ph­¬ng tr×nh trïng ph­¬ng : ax4 + bx2 + c = 0. 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. ViÕt hµm t×m kiÕm ®Ö quy trªn mét d·y sè nguyªn ®· ®­îc s¾p. 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 ®Î). ViÕt hµm ®Ö quy tÝnh n!. ViÕt hµm ®Ö quy tÝnh f(x, n) = xn. ViÕt hµm ®Ö quy tÝnh gi¸ trÞ cña biÓu thøc: F(x, n) = 2xn/ n! ViÕt hµm ®Ö quy tÝnh sè ch÷ sè trong 1 sè nguyªn? (vÝ dô sè 1423 cã 4 ch÷ sè) 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. 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. 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. 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. 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. 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. 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. 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 ch­a. 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 ch­a 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. 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. 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? 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<n; i++) h·y s¾p m¶ng a theo chiÒu t¨ng dÇn (hoÆc gi¶m dÇn). Cã nhËn xÐt g× vÒ bµi tËp nµy? NhËp mét x©u ký tù vµo biÕn S. Mét ®­êng ®i trong x©u lµ d·y liªn tiÕp c¸c ký tù gièng nhau trong S (kh«ng ph©n biÖt ch÷ hoa vµ ch÷ th­êng), ®é dµi cña ®­êng ®i lµ sè ký tù cã trong ®­êng ®i. H·y cho biÕt ®é dµi cña ®­êng ®i dµi nhÊt trong S? Cho mét biÓu thøc gåm toµn c¸c dÊu më/ ®ãng ngoÆc ‘(‘ vµ ‘)’. Mét biÓu thøc ®­îc gäi lµ hîp lÖ nÕu c¸c dÊu më/ ®ãng ngoÆc ®­îc ®Æt phï hîp nh­ khi nã ®Æt trong biÓu thøc to¸n häc. VÝ dô biÓu thøc: (( )( )) hoÆc ((( )))( ) lµ hîp 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? 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? 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). 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). 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. 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. 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 ®ã. 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). 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. 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á 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 (l­u ý sö dông tªn m¶ng nh­ con trá vµ sö dông con trá). 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. 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. 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. 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. ViÕt hµm céng hai ma trËn vu«ng a vµ b cÊp n (sö dông con trá). 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. 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. 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). 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. NhËp mét m¶ng a gåm n phÇn tö nguyªn, h·y ®¶o ng­îc m¶ng a vµ in m¶ng ®· ®¶o ng­îc ra mµn h×nh. S¾p sÕp l¹i m¶ng a theo chiÒu t¨ng dÇn vµ in ra phÇn tö lín nhÊt trong m¶ng 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. §Ò 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. 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 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è l­u ý 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