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

Một ngôn ngữ lập trình (NNLT) bậc cao cho phép người sử dụng (NSD) biểu hiện ý tưởng của mình để giải quyết một vấn đề, bài toán bằng cách diễn đạt gần với ngôn ngữ thông thường thay vì phải diễn đạt theo ngôn ngữ máy (dãy các kí hiệu 0,1). Hiển nhiên, các ý tưởng NSD muốn trình bày phải được viết theo một cấu trúc chặt chẽ thường được gọi là thuật toán hoặc giải thuật và theo đúng các qui tắc của ngôn ngữ gọi là cú pháp hoặc văn phạm. Trong giáo trình này chúng ta bàn đến một ngôn ngữ lập trình như vậy, đó là ngôn ngữ lập trình C++ và làm thế nào để

doc88 trang | Chia sẻ: tlsuongmuoi | Ngày: 25/06/2013 | Lượt xem: 1041 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Đề cương chi tiết kỹ thuật lập trình, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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

Các file đính kèm theo tài liệu này:

  • docĐề cương chi tiết kỹ thuật lập trình.DOC
Tài liệu liên quan