Kĩ thuật lập trình - Chương I: Đại cương về lập trình

Kü thuËt lËp tr×nh 1 CH¦¥NG i §¹I C¦¥NG VÒ LËP TR×NH I. Kh¸i niÖm thuËt to¸n: I.1. Kh¸i niÖm: ThuËt to¸n lµ tËp hîp c¸c quy t¾c cã logic nh»m gi¶i mét líp bµi to¸n nµo ®ã ®Ó ®­îc mét kÕt qu¶ x¸c ®Þnh. I.2. C¸c tÝnh chÊt ®Æc tr­ng cña thuËt to¸n : I.2.1. TÝnh tæng qu¸t : ThuËt to¸n ®­îc lËp kh«ng ph¶i chØ ®Ó gi¶i mét bµi to¸n cô thÓ mµ th«i mµ cßn ph¶i gi¶i ®­îc mét líp c¸c bµi to¸n cã d¹ng t­¬ng tù. I.2.2. TÝnh giíi h¹n : ThuËt to¸n gi¶i mét bµi to¸n ph¶i ®­îc thùc hiÖn qua mét sè giíi h¹n c¸c thao t¸c ®Ó ®¹t ®Õn kÕt qu¶. I.2.3. TÝnh duy nhÊt : Toµn bé qu¸ tr×nh biÕn ®æi, còng nh­ trËt tù thùc hiÖn ph¶i ®­îc x¸c ®Þnh vµ lµ duy nhÊt. Nh­ vËy khi dïng thuËt to¸n cïng mét d÷ liÖu ban ®Çu ph¶i cho cïng mét kÕt qu¶. I.3. Ph©n lo¹i: Theo cÊu tróc, ta cã thÓ ph©n thµnh ba lo¹i thuËt to¸n c¬ b¶n sau : - ThuËt to¸n kh«ng ph©n nh¸nh. - ThuËt to¸n cã ph©n nh¸nh. - ThuËt to¸n theo chu tr×nh cã b­íc lÆp x¸c ®Þnh vµ cã b­íc lÆp kh«ng x¸c ®Þnh. II. M« t¶ thuËt to¸n b»ng l­u ®å : II.1. L­u ®å : L­u ®å lµ mét d¹ng ®å thÞ dïng ®Ó m« t¶ qu¸ tr×nh tÝnh to¸n mét c¸ch cã hÖ thèng. Ng­êi ta th­êng thÓ hiÖn thuËt to¸n b»ng l­u ®å. II.2. C¸c ký hiÖu trªn l­u ®å : Tªn khèi Ký hiÖu ý nghÜa Khèi më ®Çu hoÆc kÕt thóc Dïng më ®Çu hoÆc kÕt thóc ch­¬ng tr×nh Khèi vµo ra §­a sè liÖu vµo hoÆc in kÕt qu¶ Kü thuËt lËp tr×nh 2 Khèi tÝnh to¸n BiÓu diÔn c¸c c«ng thøc tÝnh to¸n vµ thay ®æi gi¸ trÞ cña c¸c biÕn Khèi ®iÒu kiÖn Dïng ®Ó ph©n nh¸nh ch­¬ng tr×nh Ch­¬ng tr×nh con Dïng ®Ó gäi ch­¬ng tr×nh con Mòi tªn ChØ h­íng truyÒn th«ng tin, liªn hÖ c¸c khèi II.3. Mét sè vÝ dô biÓu diÔn thuËt to¸n b»ng l­u ®å II.3.1. ThuËt to¸n kh«ng ph©n nh¸nh: VÝ dô 1: TÝnh A = x2 + y2 Beáin Nâaäê (ò,y) A = ò2 + y2 Xïaát (A) End VÝ dô 2 : TÝnh yò CByAò S 22    ; biÕt A,B,C,x,y pow(x,n) Beáin Nâaäê (A, B, C, ò,y) S = (Aò + By + C) / SQRT (ò*ò + y*y) Xïaát S End Kü thuËt lËp tr×nh 3 II.3.2. ThuËt to¸n cã ph©n nh¸nh: VÝ dô 1: T×m gi¸ trÞ max cña ba sè thùc a,b,c Beáin Nâaäê (a, b, c) Maò = a Xïaát (Maò) End a > b Maò < c Maò = c S S Maò = b Ñ Ñ VÝ dô 2: Gi¶i ph­¬ng tr×nh bËc nhÊt Ax+B =0 víi c¸c nghiÖm thùc. Beáin Nâaäê (a, b) Xïaát (‘PTVÑ’) End a = 0 S S Xïaát (-b/a) b = 0 Xïaát (‘PTVN’) Ñ Ñ Kü thuËt lËp tr×nh 4 VÝ dô 3 : Gi¶i ph­¬ng tr×nh bËc hai Ax2+Bx+C =0 víi c¸c nghiÖm thùc. Beáin Nâaäê (a, b, c) Xïaát (‘X1= ’,(-b + SQRT(Delta)) / (2*a)) Xïaát (‘X2= ’,(-b - SQRT(Delta)) / (2*a)) End a = 0 Ñ Ñ PTB1 (b, c) Delta < 0 Xïaát (‘PTVN’) S S Delta = b*b - 4*a*c Ñ Delta = 0 Xïaát (-b / (2*a)) S II.3.3. ThuËt to¸n cã chu tr×nh: ThuËt to¸n cã chu tr×nh víi c¸c b­íc lÆp x¸c ®Þnh th­êng ®­îc thÓ hiÖn b»ng l­u ®å sau : i = áiaù tìò ban ñaàï Leänâ S; Taêná i i <= n S Ñ víi n lµ gi¸ trÞ kÕt thóc. Kü thuËt lËp tr×nh 5 VÝ dô 4: TÝnh S= i i n x   1 , víi c¸c xi do ta nhËp vµo. Beáin Nâaäê (n) i = 1 S = 0 Nâaäê (òi) End i = i+1 S = S+òi i <= n Xïaát (S) S Ñ III. C¸C NG«N NG÷ LËP TR×NH & CH­¬NG TR×NH DÞCH: III.1. Ng«n ng÷ lËp tr×nh: III.1.1. Giíi thiÖu: Con ng­êi muèn giao tiÕp víi m¸y tÝnh ph¶i th«ng qua ng«n ng÷. Con ng­êi muèn m¸y tÝnh thùc hiÖn c«ng viÖc, ph¶i viÕt c¸c yªu cÇu ®­a cho m¸y b»ng ng«n ng÷ m¸y hiÓu ®­îc. ViÖc viÕt c¸c yªu cÇu ta gäi lµ lËp tr×nh (programming). Ng«n ng÷ dïng ®Ó lËp tr×nh ®­îc gäi lµ ng«n ng÷ lËp tr×nh. NÕu ng«n ng÷ lËp tr×nh gÇn víi vÊn ®Ò cÇn gi¶i quyÕt, gÇn víi ng«n ng÷ tù nhiªn th× viÖc lËp tr×nh sÏ ®¬n gi¶n h¬n nhiÒu. Nh÷ng ng«n ng÷ lËp tr×nh cã tÝnh chÊt nh­ trªn ®­îc gäi lµ ng«n ng÷ cÊp cao. Nh­ng m¸y tÝnh chØ hiÓu ®­îc ng«n ng÷ riªng cña m×nh, ®ã lµ c¸c chuçi sè 0 víi 1 vµ nh­ vËy râ rµng lµ khã kh¨n cho lËp tr×nh viªn, v× nã kh«ng gÇn gòi víi con ng­êi. HiÖn t¹i, ng«n ng÷ lËp tr×nh ®­îc chia ra lµm c¸c lo¹i sau: III.1.2. Ph©n lo¹i ng«n ng÷ lËp tr×nh: - Ng«n ng÷ m¸y (machine language) Kü thuËt lËp tr×nh 6 - Hîp ng÷ (assembly language) - Ng«n ng÷ cÊp cao (higher-level language) Do m¸y tÝnh chØ hiÓu ®­îc ng«n ng÷ m¸y, cho nªn mét ch­¬ng tr×nh viÕt trong ng«n ng÷ cÊp cao ph¶i ®­îc biªn dÞch sang ng«n ng÷ m¸y. C«ng cô thùc hiÖn viÖc biªn dÞch ®ã ®­îc gäi lµ ch­¬ng tr×nh dÞch. III.2. Ch­¬ng tr×nh dÞch: Ch­¬ng tr×nh dÞch ®­îc chia ra lµm 2 lo¹i : tr×nh biªn dÞch (compiler) vµ tr×nh th«ng dÞch (interpreter) III.2.1. Tr×nh biªn dÞch: lµ viÖc chuyÓn mét ch­¬ng tr×nh trong ng«n ng÷ cÊp cao nµo ®ã (ch­¬ng tr×nh nguån) sang ng«n ng÷ m¸y (ch­¬ng tr×nh ®Ých). - Thêi gian chuyÓn mét ch­¬ng tr×nh nguån sang ch­¬ng tr×nh ®Ých ®­îc gäi lµ thêi gian dÞch. - Thêi gian mµ ch­¬ng tr×nh ®Ých thùc thi ®­îc gäi lµ thêi gian thùc thi. Nh­ vËy, ch­¬ng tr×nh nguån vµ d÷ liÖu ®Ó ch­¬ng tr×nh thùc thi ®­îc xö lý trong c¸c thêi ®iÓm kh¸c nhau, ®­îc gäi lµ thêi gian dÞch (compile time) vµ thêi gian thùc thi (run-time) Câö ôná tììnâ náïoàn Tììnâ bieân dòcâ Câö ôná tììnâ ñscâ Maùy tsnâ tâö ïc âieän Keát qïaû Dö õ lieäï H×nh I.1. Ch­¬ng tr×nh thùc thi theo c¬ chÕ dÞch cña tr×nh biªn dÞch III.2.2. Tr×nh th«ng dÞch: qu¸ tr×nh dÞch vµ thùc thi x¶y ra cïng 1 thêi gian, dÞch ®Õn ®©u thi hµnh lÖnh ®Õn ®ã. Câö ôná tììnâ náïoàn Câö ôná tììnâ tâoâná dòcâ Keát qïaû Dö õ lieäï H×nh I.2. Ch­¬ng tr×nh thùc thi theo c¬ chÕ dÞch cña tr×nh th«ng dÞch Kü thuËt lËp tr×nh 7 CH­¬NG 2 LµM QUEN VíI NG«N NG÷ C * Giíi thiÖu ng«n ng÷ C Ng«n ng÷ C do Dennis Ritchie lµ ng­êi ®Çu tiªn ®Ò xuÊt, ®· thiÕt kÕ vµ cµi ®Æt C trong m«i tr­êng UNIX. Nã cã nguån gèc tõ ng«n ng÷ BCPL do Martin Richards ®­a ra vµo n¨m 1967 vµ ng«n ng÷ B do Ken Thompson ph¸t triÓn tõ ng«n ng÷ BCPL n¨m 1970 khi viÕt hÖ ®iÒu hµnh Unix. C lµ ng«n ng÷ lËp tr×nh ®a dông, cÊp cao nh­ng l¹i cã kh¶ n¨ng thùc hiÖn c¸c thao t¸c nh­ cña ng«n ng÷ Assembly. V× thÕ ng«n ng÷ C nhanh chãng ®­îc cµi ®Æt, sö dông trªn m¸y vi tÝnh vµ ®· trë thµnh mét c«ng cô lËp tr×nh kh¸ m¹nh, hiÖn nay ®ang cã khuynh h­íng trë thµnh mét ng«n ng÷ lËp tr×nh chÝnh cho m¸y vi tÝnh trªn thÕ giíi. * §Æc ®iÓm ng«n ng÷ C Ng«n ng÷ C cã nh÷ng ®Æc ®iÓm c¬ b¶n sau : - TÝnh c« ®äng (compact) : Ng«n ng÷ C chØ cã 32 tõ kho¸ chuÈn, 40 to¸n tö chuÈn mµ hÇu hÕt ®­îc biÓu diÓn bëi c¸c d·y ký tù ng¾n gän. - TÝnh cÊu tróc (structured) : Ng«n ng÷ C cã mét tËp hîp c¸c ph¸t biÓu lËp tr×nh cÊu tróc nh­ ph¸t biÓu quyÕt ®Þnh hoÆc lÆp. Do ®ã, nã cho phÐp chóng ta viÕt ch­¬ng tr×nh cã tæ chøc vµ dÓ hiÓu. - TÝnh t­¬ng thÝch (compactable) : Ng«n ng÷ C cã bé lÖnh tiÒn xö lý vµ c¸c th­ viÖn chuÈn lµm cho c¸c ch­¬ng tr×nh viÕt b»ng ng«n ng÷ C cã thÓ t­¬ng thÝch khi chuyÓn tõ m¸y tÝnh nµy sang m¸y tÝnh kiÓu hoµn toµn kh¸c. - TÝnh linh ®éng (flexible) : Ng«n ng÷ C lµ mét ng«n ng÷ rÊt linh ®éng vÒ ng÷ ph¸p, nã cã thÓ chÊp nhËn rÊt nhiÒu c¸ch thÓ hiÖn mµ kh«ng cã ë ng«n ng÷ kh¸c nh­ Pascal, nã gióp cho kÝch th­íc m· lÖnh cã thÓ thu gän l¹i ®Ó ch­¬ng tr×nh thùc thi nhanh chãng h¬n. - Biªn dÞch : Ng«n ng÷ C ®­îc biªn dÞch b»ng nhiÒu b­íc vµ cho phÐp biªn dÞch nhiÒu tËp tin ch­¬ng tr×nh riªng rÏ thµnh c¸c tËp tin ®èi t­îng (object) vµ nèi c¸c ®èi t­îng ®ã l¹i víi nhau (link) thµnh mét ch­¬ng tr×nh thùc thi thèng nhÊt. I. C¸C KH¸I NIÖM C¬ B¶N I.1. CÊu tróc c¬ b¶n cña mét ch­¬ng tr×nh C [tiÒn xö lý] [C¸c hµm] void main() Kü thuËt lËp tr×nh 8 { [khai b¸o biÕn;] [nhËp d÷ liÖu ;] [xö lý ;] [xuÊt ;] } VÝ dô : Ch­¬ng tr×nh hiÖn trªn mµn h×nh c©u “Chao cac ban” void main() { printf(“Chao cac ban\n”); } Mét vµi nhËn xÐt quan träng : - Ch­¬ng tr×nh C bao giê còng cã mét hay nhiÒu hµm, trong ®ã cã mét hµm chÝnh b¾t buéc ph¶i cã lµ hµm main(). §©y chÝnh lµ hµm ®­îc thùc hiÖn ®Çu tiªn trong ch­¬ng tr×nh. - CÆp dÊu “{ } “ ®Ó x¸c ®Þnh mét khèi lÖnh. - Hµm printf(“ Chao cac ban \n”) lµ hµm chuÈn cña C dïng ®Ó xuÊt c©u th«ng b¸o “Chao cac ban” ra mµn h×nh. Ký tù “\n“ lµ ký tù ®Æc biÖt dïng ®Ó xuèng dßng. - DÊu “;” ®Ó chÊm døt mét lÖnh. - Ch­¬ng tr×nh C cã ph©n biÖt ch÷ th­êng víi ch÷ hoa. §a sè c¸c tõ kho¸ cña C ®­îc viÕt b»ng ch÷ th­êng, cßn mét sè Ýt ®­îc viÕt b»ng ch÷ hoa mµ ta ph¶i tu©n thñ chÆt chÏ, nÕu kh«ng th× ch­¬ng tr×nh dÞch sÏ kh«ng hiÓu. * Mét vµi vÝ dô VÝ dô 1: In b¶ng lòy thõa 2 cña c¸c sè nguyªn tõ 10 ®Õn 50 /* Ch­¬ng tr×nh in b×nh ph­¬ng c¸c sè tõ 10 ®Õn 50*/ #include void main() {int n; /*Khai b¸o biÕn n kiÓu nguyªn */ n=10; /*G¸n n=10 */ while (n<=50) /*LÆp tõ 10 ®Õn 50 b»ng while */ { printf(“%3d \t %5d\n”,n,n*n); /*in d¹ng 5d lµ dµnh 5 vÞ trÝ ®Ó in n vµ n2 */ n++; /* T¨ng n lªn 1 */ } /*HÕt while*/ } /*HÕt main*/ Kü thuËt lËp tr×nh 9 VÝ dô 2 : T­¬ng tù nh­ vÝ dô 1 nh­ng viÕt c¸ch kh¸c : #include #define max 50 /*TiÒn xö lý, ®Þnh nghÜa max =50*/ void main() { int n; /*Khai b¸o biÕn n kiÓu nguyªn*/ for (n=10; n<=max; n++) /*LÆp tõ 10 ®Õn 50 b»ng for*/ printf(“%3d \t %5d\n”,n,n*n); /*in n vµ n2 d¹ng 5d lµ n¨m ch÷ sè*/ } /*HÕt main*/ VÝ dô 3 : Ch­¬ng tr×nh in lòy thõa 2, 3, 4, 5; cã dïng hµm ®Ó tÝnh lòy thõa : #include #define max 50 /*TiÒn xö lý, ®Þnh nghÜa max =50*/ float luythua(int n, int m) /*Hµm luythua víi 2 th«ng sè*/ { float s=1; /*Khai b¸o vµ khëi t¹o biÕn s*/ for ( ;m>0;m--) /*LÆp gi¶m dÇn tõ m tíi 1*/ s=s*n; return s; /*Tr¶ kÕt qu¶ vÒ*/ } void main() { int n,n2,n3,n4,n5; /*Khai b¸o biÕn kiÓu nguyªn*/ for (n=10;n<=50;n++) /*LÆp tõ 10 ®Õn 50 b»ng for*/ { n2= luythua(n,2); /*Gäi hµm luythua*/ n3= luythua(n,3); n4= luythua(n,4); n5= luythua(n,5); printf(“%3d \t %5.2f \t %5.2f\t %5.2f\t %5.2f\t %5.2f\n”, n,n2,n3,n4,n5); /*in n vµ nm d¹ng 5 ch÷ sè víi 2 sè lÎ */ } } /*HÕt main*/ * Hµm xuÊt chuÈn printf() Có ph¸p : printf(“chuçi-®Þnhd¹ng”,thamso1,thamso2,...) ý nghÜa : Hµm printf() sÏ xem xÐt chuçi-®Þnhd¹ng, lÊy gi¸ trÞ c¸c tham sè (nÕu cÇn) ®Ó ®Æt vµo theo yªu cÇu cña chuçi-®Þnhd¹ng vµ gëi ra thiÕt bÞ chuÈn. Chuçi-®Þnhd¹ng lµ mét chuçi ký tù, trong ®ã cã nh÷ng ký tù xuÊt ra nguyªn vÑn hoÆc xuÊt ë d¹ng ®Æc biÖt, vµ cã thÓ cã nh÷ng chuçi ®iÒu khiÓn cÇn lÊy gi¸ trÞ cña c¸c tham sè ®Ó thay vµo ®ã khi in ra. Kü thuËt lËp tr×nh 10 - Nh÷ng ký tù ®Æc biÖt : Ký tù T¸c dông M· ASCII \n Xuèng hµng míi 10 \t Tab 9 \b Xãa ký tù bªn tr¸i 8 \r Con trá trë vÒ ®Çu hµng 13 \f Sang trang 12 \a Ph¸t tiÕng cßi 7 \\ XuÊt dÊu chÐo ng­îc 92 \’ XuÊt dÊu nh¸y ®¬n ‘ 39 \’’ XuÊt dÊu nh¸y kÐp “ 34 \xdd XuÊt ký tù cã m· ASCII d¹ng Hex lµ dd \ddd XuÊt ký tù cã m· ASCII d¹ng Dec lµ ddd \0 Ký tù NULL 0 - Chuçi ®Þnh d¹ng : % [ flag][width][.prec][FNhl] type Type : ®Þnh kiÓu cña tham sè theo sau chuçi-®Þnhd¹ng ®Ó lÊy gi¸ trÞ ra Type ý nghÜa d,i Sè nguyªn c¬ sè 10 U Sè nguyªn c¬ sè 10 kh«ng dÊu O Sè nguyªn c¬ sè 8 X Sè nguyªn c¬ sè 16, ch÷ th­êng(a,b,...,f) X Sè nguyªn c¬ sè 16, ch÷ in (A,B,...,F) F Sè thùc d¹ng [-]dddd.ddd... E Sè thùc d¹ng [-]d.ddd e[+/-]ddd E Sè thùc d¹ng [-]d.ddd E[+/-]ddd g,G Sè thùc d¹ng e(E) hay f tïy theo ®é chÝnh x¸c C Ký tù S Chuçi ký tù tËn cïng b»ng ‘\0’ % DÊu % cÇn in Kü thuËt lËp tr×nh 11 Flag : D¹ng ®iÒu chØnh Flag ý nghÜa nÕu kh«ng cã in d÷ liÖu ra víi canh ph¶i - in d÷ liÖu ra víi canh tr¸i + Lu«n b¾t ®Çu sè b»ng + hay - # in ra tïy theo type, nÕu: 0 : ChÌn thªm 0 ®øng tr­íc gi¸ trÞ >0 x,X : ChÌn thªm 0x hay 0X ®øng tr­íc sè nµy e,E,f : Lu«n lu«n cã dÊu chÊm thËp ph©n G,g : Nh­ trªn nh­ng kh«ng cã sè 0 ®i sau Width : ®Þnh kÝch th­íc in ra Width ý nghÜa n Dµnh Ýt nhÊt n ký tù , ®iÒn kho¶ng tr¾ng c¸c ký tù cßn trèng 0n Dµnh Ýt nhÊt n ký tù , ®iÒn sè 0 c¸c ký tù cßn trèng * Sè ký tù Ýt nhÊt cÇn in n»m ë tham sè t­¬ng øng Prec : ®Þnh kÝch th­íc phÇn lÏ in ra Prec ý nghÜa kh«ng cã ®é chÝnh x¸c nh­ b×nh th­êng 0 d,i,o,u,x ®é chÝnh x¸c nh­ cò e,E,f Kh«ng cã dÊu chÊm thËp ph©n n nhiÒu nhÊt lµ n ký tù (sè) * Sè ký tù Ýt nhÊt cÇn in n»m ë tham sè t­¬ng øng C¸c ch÷ bæ sung : F Tham sè lµ con trá xa XXXX:YYYY N Tham sè lµ con trá gÇn YYYY h Tham sè lµ short int l Tham sè lµ long int (d,i,o,u,x,X) double (e,E,f,g,G) VÝ dô 1: char c=‘A’; char s[]=“Blue moon!” ; Kü thuËt lËp tr×nh 12 D¹ng Th«ng sè t­¬ng øng XuÊt NhËn xÐt %c c “A” ®é réng 1 %2c c “ A” ®é réng 2, canh ph¶i %-3c c “A “ ®é réng 3, canh tr¸i %d c “65” M· ASCII cña ‘A’ %s s “Blue moon!” ®é réng 10 %3s s “Blue moon!” NhiÒu ký tù h¬n cÇn thiÕt %.6s s “Blue m” ChÝnh x¸c 6 ký tù %-11.8s s “Blue moo “ ChÝnh x¸c 8, canh tr¸i VÝ dô 2: int i = 123; float x = 0.123456789; D¹ng Th«ng sè t­¬ng øng XuÊt NhËn xÐt %d i “123” ®é réng 3 %05d i “00123” Thªm 2 sè 0 %7o” i “ 123” HÖ 8, canh ph¶i %-9x i “7b “ HÖ 16, canh tr¸i %c i “{“ Ký tù cã m· ASCII 123 %-#9x i “0x7b “ HÖ 16, canh tr¸i %10.5f x “ 0.12346” ®é réng 10, cã 5 ch÷ sè thËp ph©n %-12.5e x “1.23457e-01 “ Canh tr¸i, in ra d­íi d¹ng khoa häc VÝ dô 3: ViÕt ch­¬ng tr×nh in h×nh ch÷ nhËt kÐp b»ng c¸c ký tù ASCII C9 CD BB C8 CD BC void main() { printf(“\n\xC9\xCD\xBB”); printf(“\n\xC8\xCD\xBC\n); } Kü thuËt lËp tr×nh 13 I.2. KiÓu d÷ liÖu c¬ b¶n I.2.1. ®Þnh nghÜa: KiÓu d÷ liÖu c¬ b¶n lµ kiÓu d÷ liÖu cã gi¸ trÞ ®¬n, kh«ng ph©n chia ®­îc n÷a nh­ sè, ký tù I.2.2. Ph©n lo¹i: Tªn kiÓu ý nghÜa KÝch th­íc Ph¹m vi char Ký tù 1 byte -128 127 unsigned char Ký tù kh«ng dÊu 1 byte 0255 unsigned short Sè nguyªn ng¾n kh«ng dÊu 2 bytes 065535 Enum Sè nguyªn cã dÊu 2 bytes -3276832767 short int Sè nguyªn cã dÊu 2 bytes -3276832767 Int Sè nguyªn cã dÊu 2 bytes -3276832767 unsigned int Sè nguyªn kh«ng dÊu 2 bytes 0  65535 long Sè nguyªn dµi cã dÊu 4 bytes -2147483648  2147483647 unsigned long Sè nguyªn dµi kh«ng dÊu 4 bytes 04294967295 float Sè thùc ®é chÝnh x¸c ®¬n 4 bytes 3.4 E-383.4 E+38 Double Sè thùc ®é chÝnh x¸c kÐp 8 bytes 1.7 E-308  1.7 E+308 long double Sè thùc ®é chÝnh x¸c h¬n double 10 bytes 3.4 E-4932  1.1 E+4932 Chó ý : 1. Ng«n ng÷ C kh«ng cã kiÓu logic (boolean nh­ Pascal) mµ quan niÖm 0 lµ false ; Kh¸c 0 lµ true 2. Ng«n ng÷ C kh«ng cã kiÓu chuçi nh­ kiÓu string trong Pascal 3. C¸c kiÓu ®ång nhÊt: int = short int = short = signed int = signed short int long int = long signed long int = long unsigned int = unsigned = unsigned short = unsigned short int unsigned long int = unsigned long Kü thuËt lËp tr×nh 14 I.3. BiÕn I.3.1. Tªn biÕn : Tªn biÕn lµ mét chuçi ký tù b¾t ®Çu b»ng ký tù ch÷, ký tù kÕ tiÕp lµ ký tù ch÷ (dÊu g¹ch d­íi “_” ®­îc xem lµ ký tù ch÷) hoÆc sè vµ kh«ng ®­îc trïng víi c¸c tõ khãa cña C. Chó ý : - Ng«n ng÷ C ph©n biÖt ch÷ th­êng víi ch÷ hoa nªn biÕn ch÷ th­êng víi ch÷ hoa lµ kh¸c nhau. VÝ dô : Bien_1 _bien2 lµ hîp lÖ bi&en 2a a b lµ kh«ng hîp lÖ - Ng«n ng÷ C chØ ph©n biÖt hai tªn hîp lÖ víi nhau b»ng n ký tù ®Çu tiªn cña chóng. Th«ng th­êng n=8, nh­ng hiÖn nay nhiÒu ch­¬ng tr×nh dÞch cho phÐp n=32, nh­ Turbo C cho phÐp thay ®æi sè ký tù ph©n biÖt tõ 8-32) VÝ dô : Hai biÕn sau bÞ xem lµ cïng tªn bien_ten_dai_hon_32_ky_tu_dau_tien_1 bien_ten_dai_hon_32_ky_tu_dau_tien_2 I.3.2. Khai b¸o biÕn C¸c biÕn ph¶i ®­îc khai b¸o tr­íc khi sö dông nh»m gióp cho ch­¬ng tr×nh dÞch cã thÓ xö lý chóng. Khai b¸o biÕn cã d¹ng : KiÓud÷liÖu tªnbiÕn1 [,tenbiÕn2 ...] ; VÝ dô: int a=0,b=1,c; float x,y,delta; char c; * Khai b¸o vµ khëi t¹o biÕn: KiÓu d÷ liÖu tªnbiÕn = gi¸trÞ ; I.3.3. Hµm nhËp d÷ liÖu chuÈn a) Hµm scanf() Có ph¸p: scanf(“chuçi-®Þnhd¹ng“,®i¹chØthamsè1, ®i¹chØthamsè2,...) - Chuçi-®Þnhd¹ng cña scanf() gåm cã ba lo¹i ký tù : + Chuçi ®iÒu khiÓn + Ký tù tr¾ng + Ký tù kh¸c tr¾ng  Chuçi ®iÒu khiÓn cã d¹ng : %[width][h/l] type Kü thuËt lËp tr×nh 15 Víi type: x¸c ®Þnh kiÓu cña biÕn ®Þa chØ tham sè sÏ nhËn gi¸ trÞ nhËp vµo Type ý nghÜa d,i Sè nguyªn c¬ sè 10 (int) o Sè nguyªn c¬ sè 8 (int) u Sè nguyªn c¬ sè 10 kh«ng dÊu (unsigned) x Sè nguyªn c¬ sè 16 (int) f,e Sè thùc (float) c Ký tù (char) s Chuçi ký tù p Con trá (pointer) lf Sè thùc (double) Lf Sè thùc (long double) Width : x¸c ®Þnh sè ký tù tèi ®a sÏ nhËn vµo cho vïng ®ã. Hµm scanf() chØ nhËn cho ®ñ width ký tù hoÆc cho ®Õn khi gÆp ký tù tr¾ng ®Çu tiªn. NÕu chuçi nhËp vµo nhiÒu h¬n th× phÇn cßn l¹i sÏ dµnh l¹i cho lÇn gäi scanf() kÕ tiÕp. VÝ dô 1: scanf(“%3s”,str); NÕu nhËp chuçi ABCDEFG  th× scanf() sÏ nhËn tèi ®a 3 ký tù cÊt vµo m¶ng str, cßn DEFG sÏ ®­îc lÊy nÕu sau ®ã cã lÇn gäi sanf(“%s”,str) kh¸c. VÝ dô 2: unsigned long money; scanf(“%lu”,&money); L­u ý: NÕu scanf(“%ul”, &money) th× gi¸ trÞ nhËp vµo sÏ kh«ng ®­îc l­u tr÷ trong biÕn money, nh­ng ch­¬ng tr×nh dÞch kh«ng b¸o lçi. VÝ dô 3: NhËp vµo tªn vµ bÞ giíi h¹n trong kho¶ng [A-Z,a-z] char name[20]; printf(“Name : ”) ; scanf(“%[A-Za-z]”,&name); Trong tr­êng hîp nµy, nÕu ta gâ sai d¹ng th× name =””  Ký tù tr¾ng: nÕu cã trong chuçi-d¹ng sÏ yªu cÇu scanf() bá qua mét hay nhiÒu ký tù tr¾ng trong chuçi nhËp vµo. Ký tù tr¾ng lµ ký tù kho¶ng tr¾ng (‘ ‘), tab (‘\t’), xuèng hµng (‘\n’). Mét ký tù tr¾ng trong chuçi-®Þnhd¹ng sÏ ®­îc hiÓu lµ chê nhËp ®Õn ký tù kh¸c tr¾ng tiÕp theo. Kü thuËt lËp tr×nh 16 VÝ dô 4: scanf(“%d “,&num); Hµm scanf() cho ta nhËp mét ký tù kh¸c tr¾ng n÷a th× míi tho¸t ra. Ký tù ®ã sÏ n»m trong vïng ®Öm vµ sÏ ®­îc lÊy bëi hµm scanf() hoÆc gets() tiÕp theo.  Ký tù kh¸c tr¾ng: nÕu cã trong chuçi-®Þnhd¹ng sÏ khiÕn cho scanf() nhËn vµo ®óng ký tù nh­ thÕ. VÝ dô 5: scanf(%d/%d/%d”,&d,&m,&y); Hµm scanf() chê nhËn mét sè nguyªn, cÊt vµo d, kÕ ®Õn lµ dÊu ‘/’, bá dÊu nµy ®i vµ chê nhËn sè nguyªn kÕ tiÕp ®Ó cÊt vµo m. NÕu kh«ng gÆp dÊu ‘/’ kÕ tiÕp sè nguyªn th× scanf() chÊm døt. Chó ý : Hµm scanf() ®ßi hái c¸c tham sè ph¶i lµ c¸c ®Þa chØ cña c¸c biÕn hoÆc lµ mét con trá. * To¸n tö ®Þa chØ & : LÊy ®Þa chØ cña mét biÕn VÝ dô 6: int n;  biÕn n &n;  ®Þa chØ cña n printf(“trÞ = %d, ®Þa chØ = %d”,n,&n); b) Hµm getch(): Hµm getch() dïng ®Ó nhËn mét ký tù do ta nhËp trªn bµn phÝm mµ kh«ng cÇn gâ Enter víi có ph¸p : ch = getch(); Kh«ng hiÖn ký tù nhËp trªn mµn h×nh ch = getche(); HiÖn ký tù nhËp trªn mµn h×nh Víi ch lµ biÕn kiÓu char. VÝ dô 7: void main() { char ch; printf(“Go vao ky tu bat ky : ‘); ch = getche(); printf(“\n Ban vua go %c”,ch); getch(); } VÝ dô 8: B¹n nhËp vµo 1 ch÷ c¸i. NÕu ch÷ c¸i nhËp vµo lµ 'd' th× ch­¬ng tr×nh sÏ kÕt thóc, ng­îc l¹i ch­¬ng tr×nh sÏ b¸o lçi vµ b¾t nhËp l¹i. #include #include void main() { char ch; Kü thuËt lËp tr×nh 17 printf("\nBan nhap vao 1 chu cai tu a den e: "); while ((ch=getche()) != 'd') { printf("\nXin loi, %c la sai roi",ch); printf("\n Thu lai lan nua. \n"); } } L­u ý: Hµm getch() cßn cho phÐp ta nhËp vµo 1 ký tù më réng nh­ c¸c phÝm F1, F2,.., c¸c phÝm di chuyÓn cursor. C¸c phÝm nµy lu«n cã 2 bytes: byte thø nhÊt b»ng 0, cßn byte 2 lµ m· scancode cña phÝm ®ã. §Ó nhËn biÕt ta ®· gâ phÝm ký tù hay phÝm më réng, ta cã ch­¬ng tr×nh sau: void main() { int c; int extended = 0; c = getch(); if (!c) extended = getch(); if (extended) printf("The character is extended\n"); else printf("The character isn't extended\n"); } PhÝm M· scancode F1 59 F2 60 F3 61 F4 62 F5 63 F6 64 F7 65 F8 66 F9 67 F10 68 Home 71  72  80  75 Kü thuËt lËp tr×nh 18  77 PgUp 73 PgDn 81 End 79 Ins 82 Del 83 B¶ng m· scancode cña c¸c phÝm më réng c. Hµm kbhit(): Hµm int kbhit() sÏ kiÓm tra xem cã phÝm nµo ®­îc gâ vµo hay kh«ng. NÕu cã, hµm kbhit sÏ tr¶ vÒ mét sè nguyªn kh¸c 0, vµ ng­îc l¹i. Ký tù mµ ta nhËp vµo qua hµm kbhit() cã thÓ lÊy ®­îc qua hµm getch() hoÆc getche(). VÝ dô: void main() { printf("Press any key to continue:"); while (!kbhit()) /* do nothing */ ; char kytu=getch(); printf("\nKy tu vua an : %c",kytu); } I.4 H»ng: H»ng lµ c¸c ®¹i l­îng mµ gi¸ trÞ cña nã kh«ng thay ®æi trong qu¸ tr×nh ch­¬ng tr×nh thùc hiÖn. I.4.1. Ph©n lo¹i : a. H»ng sè : lµ c¸c gi¸ trÞ sè ®· x¸c ®Þnh vµ kh«ng ®æi. int unsigned long hÖ 8 hÖ 16 float/double D¹ng nnnn -nnnn nnnnU/u nnnnL/l -nnnnl/L 0nnnn 0xnnnn nnnn.nnnn nnnn.nnnE/ennn VÝ dô 4567 -12 123U 12uL 456789L -1234L 0345 0x1AB 123.654 123.234E-4 Chó ý : - C¸c h»ng sè viÕt kh«ng dÊu hoÆc kh«ng sè mò ®­îc hiÓu lµ sè nguyªn, ng­îc l¹i lµ double. - C¸c h»ng sè nguyªn lín h¬n int sÏ ®­îc l­u tr÷ theo kiÓu long, cßn lín h¬n long th× ®­îc l­u tr÷ theo kiÓu double. - C¸c h»ng sè nguyªn d­¬ng lín h¬n long sÏ ®­îc l­u tr÷ theo kiÓu double - Mét h»ng sè ®­îc l­u tr÷ theo d¹ng long nÕu theo sè ®ã cã ký tù l (L), Kü thuËt lËp tr×nh 19 d¹ng unsigned nÕu sau ®ã cã ch÷ u (U), d¹ng thËp lôc ph©n nÕu tr­íc sè ®ã cã 0x vµ d¹ng b¸t ph©n nÕu tr­íc sè ®ã cã 0 VÝ dô: 50000; 10 L;  Long 5U, 100u  unsigned 0x10  hÖ 16 = 1610 010  hÖ 8 = 810 b. H»ng ký tù : lµ ký tù riªng biÖt ®­îc viÕt trong hai dÊu nh¸y ®¬n : ‘A’ Gi¸ trÞ cña h»ng ký tù lµ m· ASCII cña nã. VÝ dô : printf(“%c cã gi¸ trÞ lµ %d”,’A’,’A’);  ‘A’ cã gi¸ trÞ lµ 65  H»ng ký tù cã thÓ tham gia vµo c¸c phÐp to¸n nh­ mäi sè nguyªn kh¸c. VÝ dô : ‘9’-’0’=57-48=9  H»ng ký tù cã thÓ lµ c¸c ký tù ®Æc biÖt d¹ng ‘\c1’ mµ ta ®· xÐt ë hµm printf() nh­ ‘\n’,’\a’,’\t’ ... c. H»ng chuçi : Lµ mét chuçi ký tù n»m trong hai dÊu nh¸y kÐp “ “. VÝ dô : “Day la mot chuoi” “Hang chuoi co ky tu ®¹c biÖt nh­ \ \n \248” “”  chuçi rçng. Chó ý : - Ph©n biÖt “A”  ‘A’ H»ng: Chuçi Ký tù D¹ng l­u tr÷ : A \0 A - NhËn xÐt: ë d¹ng l­u tr÷, ta thÊy tËn cïng cña chuçi cã ký tù NULL ‘\0’ mµ kh«ng cã ë d¹ng ký tù. ChÝnh v× vËy mµ kh«ng cã ký tù rçng ‘’. - Mét chuçi cã thÓ ®­îc viÕt trªn nhiÒu hµng víi ®iÒu kiÖn hµng trªn ph¶i cã dÊu ‘\’. VÝ dô : “Day la mot chuoi duoc viet tren \ nhieu hang \n” d. H»ng biÓu thøc : Lµ mét biÓu thøc mµ trong ®ã c¸c to¸n h¹ng ®Òu lµ c¸c h»ng. Khi ®ã ch­¬ng tr×nh dÞch sÏ tÝnh to¸n biÓu thøc tr­íc, vµ kÕt qu¶ ®­îc l­u tr÷ th¼ng b»ng mét h»ng sè t­¬ng ®­¬ng. VÝ dô : 8*20-13  kÕt qu¶ l­u tr÷ lµ 173 Kü thuËt lËp tr×nh 20 ‘a -’A’  “ lµ 97-65 = 32 1<8  “ lµ 0 (sai) I.4.2. Khai b¸o h»ng: Có ph¸p: const tªnh»ng = biÓuthøc; VÝ dô : const MAX = 50; const PI = 3.141593; Chó ý : - Ta cã thÓ khai b¸o h»ng b»ng c¸ch ®Þnh nghÜa 1 macro nh­ sau: #define tªnh»ng gi¸trÞ - LÖnh #define ph¶i ®­îc khai b¸o ngoµi hµm vµ sau nã kh«ng cã dÊu ; I.5. PhÐp to¸n I.5.1. PhÐp g¸n: Có ph¸p: biÕn = biÓu thøc; Chó ý : PhÐp g¸n trong ng«n ng÷ C tr¶ vÒ mét kÕt qu¶ lµ trÞ cña biÓu thøc VÝ dô 1 : c = 10; a = b = c; printf(“a=%d , b=%d”,a,b);  a=10,b=10 VÝ dô 2 : x = b + 2*c;  y= a + (ò= b + 2*c) y = a + x; VÝ dô 3 : (n+3) = 4+z; (kh«ng hîp lÖ v× bªn tr¸i lµ biÓu thøc) ‘ ‘= c +’o’; (kh«ng hîp lÖ v× bªn tr¸i lµ h»ng) I.5.2. C¸c phÐp to¸n sè häc : a. PhÐp to¸n hai to¸n h¹ng : +, -, *, /, % PhÐp to¸n KiÓu to¸n h¹ng KiÓu kÕt qu¶ +, -, * char, int, long, float, double KiÓu cña to¸n h¹ng cã kiÓu cao nhÊt / nguyªn/nguyªn KiÓu nguyªn vµ lµ phÐp chia nguyªn thùc(nguyªn)/thùc (nguyªn) KiÓu thùc vµ lµ phÐp chia thùc % nguyªn/nguyªn KiÓu nguyªn vµ lµ phÐp chia lÊy phÇn d­ VÝ dô : #include void main() Kü thuËt lËp tr×nh 21 { char cv; int iv = 121; float fv1,fv2; printf(“ ChuyÓn kiÓu :\n\n”); cv = iv; printf(“int ®­îc g¸n cho char : %d  %d (%c)\n\n”,iv,cv,cv); fv1 = iv/50; printf(“ int : %d / 50 = %f \n\n”,iv,fv1); fv1 = iv/50.0; printf(“ float : %d / 50.0 = %f \n\n”,iv,fv1); fv1 = 1028.75; fv2 = fv1 +iv ; printf(“ %f + %d = %f \n\n”,fv1,iv,fv2); getch(); } b. PhÐp to¸n mét to¸n h¹ng : phÐp t¨ng ++, phÐp gi¶m -- a++ hoÆc ++a  a = a+1 a-- hoÆc --a  a = a-1 Chó ý : Tuy nhiªn a++ sÏ kh¸c ++a khi chóng ®øng trong biÓu thøc (cã phÐp g¸n). a++ : T¨ng a sau khi gi¸ trÞ cña nã ®­îc sö dông. ++a : T¨ng a tr­íc khi gi¸ trÞ cña nã ®­îc sö dông. VÝ dô : main() a b n { int a=4 , b=6, n; n = a + b; n = a++ + b; n = ++a + b; n = --a + b; n = a-- + b; n = a+ b; } 4 4 5 6 5 4 4 6 6 6 6 6 6 6 10 10 12 11 11 10 I.5.3. PhÐp g¸n phøc hîp: Có ph¸p: biÕn op=  biÕn = biÕn op Víi op lµ phÐp to¸n. Kü thuËt lËp tr×nh 22 C¸c phÐp g¸n phøc hîp : += , -= , *= , /= , %= , >= VÝ dô : n = n*(10+x)  n *= (10 +x) n = n % 10  n %= 10 I = I +3  I += 3 << : lµ phÐp dÞch chuyÓn bit qua tr¸i . >> : lµ phÐp dÞch chuyÓn bit qua ph¶i . I.5.4. PhÐp to¸n quan hÖ: < : nhá h¬n > : lín h¬n >= : lín h¬n hoÆc b»ng <= : nhá h¬n hoÆc b»ng != : kh¸c == : b»ng Chó ý: - Ph©n biÖt to¸n tö so s¸nh == víi phÐp g¸n = - C kh«ng cã kiÓu d÷ liÖu boolean mµ qui ­íc : Gi¸ trÞ 0 lµ sai Gi¸ trÞ !=0 lµ ®óng VÝ dô: a=10; b= (a>6)*(a-6)  b = 4 c= (a< 5)*(a-5)  c = 0 VÝ dô: T×m sè lín nhÊt trong 3 sè nguyªn a, b, c #include #include void main () { int a, b, c, max; printf(“Ch­¬ng tr×nh t×m sè lín nhÊt trong 3 sè”); printf(“NhËp a, b, c”); scanf(“%d %d %d ”, &a, &b, &c); max = a; if (max<b) max = b; if (max<c) max = c; printf(“Sè lín nhÊt = %d”, max); getch(); } Kü thuËt lËp tr×nh 23 I.5.5.To¸n tö logic: To¸n tö ý nghÜa NOT ! Phñ ®Þnh AND && Giao, vµ OR || Héi Thø tù tÝnh to¸n tõ trªn xuèng. B¶ng ch©n trÞ: x ! x x y x && y true false true true true false true true false false false true false false false false x y x || y true true true false true true false true true false false false VÝ dô 1: XÐt ký tù c cã ph¶i lµ ký sè hay kh«ng? char c; if (c >= ‘0’ && c <= ‘9’) printf (“% c lµ kÝ tù sè “, c); VÝ dô 2: XÐt ký tù ch lµ ch÷ c¸i hay kh«ng? if ((ch> =‘a’) and (ch =‘A’) and (ch< =‘Z’)) printf(“%c lµ chu cai \n”,ch); VÝ dô 3: int a=10, b=5, c=0; a && b  1 a && c  0 a | | c  1 VÝ dô 4: int a=10, b=5; Kü thuËt lËp tr×nh 24 int i=2, j=0; (a>b) && (i<j)  0 (aj)  1 VÝ dô 5: n=5; while (n) { printf("\nSè n = %d",n); n--; } I.5.6. To¸n tö phÈy: Có ph¸p: T = (exp1, exp2, exp3 ); // T = kÕt qu¶ cña exp3 VÝ dô: m= (t=2, t*t+3)  m=7; t=2 c= (a=10,b=5,a+b);  a=10, b=5, c=15 I.5.7. To¸n tö ®iÒu kiÖn: Có ph¸p : T = ? : ; NÕu lµ ®óng th× T = , ng­îc l¹i T = VÝ dô: A = i>= MAX ? 1: 0; printf (“ max (a,b) = %d “, (a>b) ? a:b); lower = (c > = ‘A’ && c< = ‘Z’) ? c - ‘A’ + ‘a’ :c; I.5.8. To¸n tö trªn bit (bit wise) : D¹ng Ký hiÖu ý nghÜa NOT bit ~ lÊy bï 1 AND bit & giao OR bit | héi XOR bit ^ héi lo¹i trõ dÞch tr¸i << nh©n 2 dÞch ph¶i >> chia 2 Kü thuËt lËp tr×nh 25 B¶ng ch©n trÞ: Bit Bit Bit kÕt qu¶ A B ~ A A & B A | B A ^ B 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 VÝ dô: a= 4564 0001 0001 1101 0100 b= 13667 0011 0101 0110 0011 a & b 0001 0001 0100 0000 a | b 0011 0101 1111 0111 a ^ b 0010 0100 1011 0111 ý nghÜa: 1. PhÐp AND bit th­êng ®­îc dïng ®Ó kiÓm tra mét bit cô thÓ nµo ®ã trong thµnh phÇn d÷ liÖu x cã trÞ 0 hay 1. ViÖc nµy thùc hiÖn b»ng c¸ch sö dông mét mÆt n¹ (mask) víi bit cÇn quan t©m b»ng 1 cßn c¸c bit kh¸c b»ng 0. Ta lÊy mask AND víi gi¸ trÞ x. NÕu kÕt qu¶ thu ®­îc b»ng mask th× lµ bit cÇn quan t©m lµ 1, ng­îc l¹i lµ 0. VÝ dô 1: void main() { unsigned x1; x2; printf (“\n cho 2 sè hex(2 sè) “); scanf (“%x %x “, &x1, &x2); printf (“% 02x & % 02x = % 02x\n”, x1, x2, x1& x2); } VÝ dô 2: Ta muèn biÕt bit thø 3 cña sè hexa ch lµ 1 hay 0 : void main() { unsigned char ch, kq; printf (“ \n cho 1 sè hex 2 sè :”); scanf ( “%x“, &ch); kq= ch & 0x08; if (kq== 0x08) printf (“bit 3 = 1”); else printf (“bit 3 = 0”); } Kü thuËt lËp tr×nh 26 2. PhÐp OR dïng ®Ó bËt c¸c bit cÇn thiÕt lªn còng nhê vµo mét mÆt n¹. Ch¼ng h¹n nh­ ta muèn bËt bit thø 7 cña biÕn ch (unsigned char ch) lªn 1: ch = ch | 0x80; VÝ dô 3: void main() { unsigned char x1,x2; printf (“\n cho 2 sè hex (ff hay nhá h¬n) :”); scanf (“%x %x”, &x1, &x2); printf (“ %02x | %02x %02x \n”, x1, x2, x1| x2); } 3. PhÐp XOR dïng ®Ó “lËt” bit nghÜa lµ ho¸n chuyÓn 01 VÝ dô 4: §Ó lËt bit 3 ta cã ch­¬ng tr×nh: void main() { unsigned char ch; printf (“ nhËp 1 sè hex < = ff :”); scanf (“%x”, &ch); printf (“%02x ^ 0x08 = %02x \n “, ch, ch ^ 0x08); } 4. To¸n tö > << dÞch sang tr¸i (nh©n 2) >> dÞch sang ph¶i (chia 2) VÝ dô 5: num = 201 (0x00c9) nïm : 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 nïm << 2 : 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 KÕt qu¶ = 0x0324  804 nghÜa lµ 201* 4 VÝ dô 6: void main() { unsigned char x1, x2 ; printf (“ nhËp 1 sè hex < = ff vµ sè bit : “); scanf ( %x %d “, &x1, &x2); printf (“ %02x >> %d = %02x \n”, x1, x2, x1>> x2); } Chó ý: Trong phÐp dÞch ph¶i C lµm theo 2 c¸ch kh¸c nhau tïy thuéc vµo Kü thuËt lËp tr×nh 27 kiÓu d÷ liÖu cña to¸n h¹ng bªn tr¸i. - NÕu to¸n h¹ng bªn tr¸i kiÓu unsigned th× phÐp dÞch sÏ ®iÒn 0 vµo c¸c bit bªn tr¸i. - NÕu to¸n h¹ng bªn tr¸i kiÓu signed th× phÐp dÞch sÏ ®iÒn bit dÊu vµo c¸c bit bªn tr¸i VÝ dô 7: unsigned int num; num = 39470; // 9A2E hexa num = num >> 2 = 0  1 0 0 1 9867 = 0x268B 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 1 1 VÝ dô 8 : int num; // 9A2E hexa num = -26066 num = num >> 2 = 1  1 0 0 1 -6517 = 0xE68B 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 1 1 VÝ dô 8: Ch­¬ng tr×nh ®æi sè hex ra sè nhÞ ph©n : #include #include void main() { int num; unsigned int mask; clrscr(); printf ("Chuong trinh doi so hexa sang nhi phan\n"); printf ("Nhap vao so hexa :"); scanf("%x",&num); mask = 0x8000; printf("\n Dang nhi phan cua so %x la ",num); for (int j=1; j<=16; j++) { printf("%d",mask & num?1:0); if (j==4 || j==8 || j==12) printf("-"); mask >>=1; } getch(); } Kü thuËt lËp tr×nh 28 VÝ dô 9: Ch­¬ng tr×nh m¸y tÝnh bitwise §©y lµ ch­¬ng tr×nh gi¶ lËp mét m¸y tÝnh thùc hiÖn c¸c to¸n tö bitwise. #define TRUE 1 main() { char op[10]; int x1, x2; while (TRUE) { printf (“\n \n Cho biÓu thøc ( vd ‘ ffoo & f11’) : “); printf (“\n”); switch ( op[0]) { case ‘&’: pbin (x1); printf (“& (and) \n “); pbin (x2); pline (); pbin (x1 & x2); break; case ‘|’: pbin (x1); printf (“| \n “); pbin (x2); pline (); pbin (x1 | x2); break; case ‘^’: pbin (x1); printf (“^ \n); pbin (x2); pline (); pbin (x1 ^ x2); break; case ’>‘: pbin (x1); printf (“ >>“); printf (“%d \n “,x2); pline (); pbin (x1 >> x2); break; case ‘<‘: pbin (x1); printf (“<<“); printf (“%d \n”, x2); pline (); pbin (x1 << x2); break; case ‘~’: pbin (x1); printf (“~ \n”); pline (); pbin (~ x1); break; default : printf (“To¸n tö kh«ng hîp lÖ /n “); } } Kü thuËt lËp tr×nh 29 } pbin (num) int num; { unsigned int mask; int j, bit; mask = 0x8000; printf (“%04x”, num); for(j=0; j<16; j++) { bit = ( mask & num ) ? 1:0; printf (“%d”, bit); if (j= = 7) printf (“- -”); mask >> = 1; } printf (“- -”); mask >> 1; } pline () { printf (“- - - - - - - - \n”); } * Sù chuyÓn kiÓu b¾t buéc: Trong C cã 2 tr­êng hîp chuyÓn kiÓu: chuyÓn kiÓu tù ®éng vµ chuyÓn kiÓu b¾t buéc. ChuyÓn kiÓu b¾t buéc: ®­îc ¸p dông khi chuyÓn kiÓu tù ®éng kh«ng ®­îc. Có ph¸p: (Type) biÓu thøc VÝ dô: d = (float) (f - 32) int a= 100, b=6; double f; f =a/b // kÕt qu¶ f=16 f= a/ (double)b // kÕt qu¶ f= 100.0 / 6.0= 16.666. * Møc ®é ­u tiªn cña c¸c phÐp to¸n: §é ­u tiªn PhÐp to¸n Thø tù kÕt hîp 1 () [ ]   2 ! ~ ++ - - (type) * & size of  3 * / %  4 + -  5 >  Kü thuËt lËp tr×nh 30 6 >=  7 = = !=  8 &  9 ^  10 |  11 &&  12 | |  13 ?  14 = + = - = ..  VÝ dô 1: 3/4 * 6 # 3*6 /4 0 * 6 18 /4 0 4 VÝ dô 2: (float) 2 /4 # (float) (2/4) 2.0 /4 (float) 0 0.5 0.0 I.6. Chuçi I.6.1. §Þnh nghÜa :Chuçi lµ mét m¶ng mµ c¸c phÇn tö cña nã cã kiÓu ký tù. Khai b¸o mét chuçi ký tù chøa tèi ®a 49 ký tù char chuçi[50]; * L­u ý: TÊt c¶ c¸c chuçi ®Òu ®­îc kÕt thóc b»ng ký tù NULL (‘\0’). Do ®ã, nÕu chuçi dµi 50 th× ta chØ cã thÓ chøa tèi ®a 49 ký tù. I.6.2. Khëi ®éng trÞ: char chuçi[ ] = {‘A’, ‘N’, ‘H’, ‘ \0’}; char chuçi[ ] = "ANH"; I.6.3. NhËp / xuÊt chuçi: a. NhËp chuçi: gets (chuçi) b. XuÊt chuçi: puts (chuçi) Chó ý: - Khi nhËp chuçi th× kh«ng ®­îc dïng hµm scanf v× hµm scanf kh«ng chÊp nhËn kho¶ng tr¾ng. VÝ dô: scanf(“%s”, chuçi); // ta nhËp vµo NguyÔn V¨n ¸i th× Kü thuËt lËp tr×nh 31 // chuçi = “NguyÔn” v× hµm scanf c¾t kho¶ng tr¾ng - Khi dïng hµm gets trong ch­¬ng tr×nh th× kh«ng nªn dïng hµm scanf ë bÊt k× ®©u dï r»ng dïng hµm scanf ®Ó nhËp sè mµ ta nªn dïng hµm gets vµ hµm atoi, atof ®Ó nhËp sè. V× : scanf(“%d”, &n); // ta nhËp sè 5  gets (chuçi); // lóc nµy chuçi = ““ (chuçi rçng) I.6.4. Hµm chuyÓn ®æi sè sang chuçi vµ ng­îc l¹i sèint = atoi (chuçisè) // chuyÓn chuçi sè sang sè nguyªn sèf = atof (chuçisè) // chuyÓn chuçi sè sang sè thùc * Hai hµm nµy n»m trong I.6.5. C¸c hµm vÒ chuçi: (# include ) - int strlen(S) : tr¶ vÒ chiÒu dµi chuçi S. - int strcmp(S1, S2): so s¸nh chuçi S1 víi S2. NÕu chuçi S1 gièng S2 kÕt qu¶ b»ng 0. NÕu chuçi S1 S2 kÕt qu¶ > 0. - int stricmp(S1, S2): so s¸nh chuçi S1, S2 kh«ng ph©n biÖt ch÷ th­êng hay ch÷ hoa - int strncmp(S1, S2, n): chØ so s¸nh n ký tù ®Çu cña 2 chuçi S1, S2 víi nhau. - int strnicmp(S1, S2, n): chØ so s¸nh n ký tù ®Çu cña 2 chuçi S1, S2 víi nhau, kh«ng ph©n biÖt ch÷ th­êng, ch÷ hoa - strcpy(dest, source): chÐp chuçi tõ nguån source sang ®Ých dest VÝ dô: char string[10]; char *str1 = "abcdefghi"; strcpy(string, str1); printf("%s\n", string); // "abcdefghi" - strncpy(dest, source, n): chÐp chuçi tõ nguån sang ®Ých víi nhiÒu nhÊt lµ n ký tù. VÝ dô: char string[10]; char *str1 = "abcdefghi"; strncpy(string, str1, 3); // string = "abcx1zwe12" string[3] = '\0'; // §Æt ký tù kÕt thóc chuçi vµo cuèi chuçi. printf("%s\n", string); // "abc" - strcat(dest, src): nèi chuçi src vµo sau chuçi dest. ChiÒu dµi cña chuçi kÕt qu¶ b»ng strlen(dest) + strlen(src) Kü thuËt lËp tr×nh 32 VÝ dô: char destination[25]; char *blank = " ", *c = "C++", *turbo = "Turbo"; strcpy(destination, turbo); // destination = "Turbo" strcat(destination, blank); // destination = "Turbo " strcat(destination, c); // destination = "Turbo C++" - strncat(dest, src, n): nèi nhiÒu nhÊt lµ n ký tù cña src vµo cuèi chuçi dest, sau ®ã thªm ký tù null vµo cuèi chuçi kÕt qu¶. VÝ dô: char destination[25]; char *source = " States"; strcpy(destination, "United"); strncat(destination, source, 6); printf("%s\n", destination); // destination = "United State" - char * strchr(s, ch): tr¶ vÒ ®Þa chØ cña ký tù ch ®Çu tiªn cã trong chuçi S; nÕu kh«ng cã th× tr¶ vÒ NULL (th­êng dïng ®Ó lÊy hä) VÝ dô: char string[15]; char *ptr, c = 'r'; strcpy(string, "This is a string"); ptr = strchr(string, c); if (ptr) printf("Ký tù %c ë vÞ trÝ: %d\n", c, ptr-string); else printf("Kh«ng t×m thÊy ký tù %c\n",c); - char * strstr(S1, S2): tr¶ vÒ vÞ trÝ cña chuçi S2 trong chuçi S1; nÕu S2 kh«ng cã trong S1 th× hµm strstr tr¶ vÒ trÞ NULL. I.6.6. M¶ng c¸c chuçi *Khai b¸o: Khai b¸o biÕn ds chøa tèi ®a 50 chuçi ký tù, mçi chuçi ký tù cã tèi ®a 30 ký tù. char ds[50 ] [30]; Chó ý: - Kh«ng nªn g¸n chuçi víi chuçi (s1= s2) mµ ph¶i dïng hµm strcpy(S1,S2) - Kh«ng ®­îc so s¸nh 2 chuçi b»ng c¸c to¸n tö quan hÖ (S1== S2, S1>S2, S1>= S2), mµ ph¶i dïng hµm strcmp(S1,S2). Kü thuËt lËp tr×nh 33 VÝ dô: ViÕt ch­¬ng tr×nh t×m kiÕm 1 tõ trong 1 c©u # include # include void main () { char cau[80], tõ[7], *ptr; printf(“NhËp c©u :”); gets(c©u); printf(“NhËp tõ :”); gets(tõ); ptr = strstr(c©u, tõ); if (ptr == NULL) printf(“Kh«ng cã tõ”); else printf(“cã tõ”); } II. C¸c cÊu tróc ®iÒu khiÓn trong C: Ng«n ng÷ C lµ ng«n ng÷ lËp tr×nh cÊp cao cã cÊu tróc, gåm: cÊu tróc tuÇn tù, chän, vµ lÆp. II.1 CÊu tróc tuÇn tù (Sequence) : C¸c lÖnh trong ch­¬ng tr×nh ®­îc thùc hiÖn tuÇn tù tõ lÖnh nµy ®Õn lÖnh kh¸c cho ®Õn khi hÕt ch­¬ng tr×nh. VÝ du : ViÕt ch­¬ng tr×nh tÝnh vµ in ra diÖn tÝch cña hai ®­êng trßn b¸n kÝnh lÇn l­ît lµ 3m vµ 4.5m cïng víi hiÖu sè cña 2 diÖn tÝch. #define PI 3.14159 #include #include void main() { float r1, r2, hieuso; clrscr(); printf("\nCHUONG TRINH TINH DIEN TICH 2 HINH TRON VA HIEU SO\n"); printf("Ban kinh hinh tron thu nhat : "); scanf("%f",&r1); printf("Ban kinh hinh tron thu hai : "); scanf("%f",&r2); printf ("Dien tich hinh tron 1 = %.2f\n",PI*r1*r1); Kü thuËt lËp tr×nh 34 printf ("Dien tich hinh tron 2 = %.2f\n",PI*r2*r2); hieuso = PI*r1*r1 - PI*r2*r2; printf ("Hieu so dien tich 2 hinh tron = %.2f\n",hieuso); getch(); } II.2. CÊu tróc chän Ký hiÖu : ®k lµ biÓu thøc Logic S1, S2 lµ c¸c ph¸t biÓu hay 1 nhãm c¸c ph¸t biÓu (lÖnh) II.2.1. LÖnh if else: Có ph¸p: if (®k) S1; ÑK NO YES S1 if (®k) S1; else S2; ÑK S1 S2 NO YES Chó ý: C¸c lÖnh if else lång nhau if (®k1) S1; else if (®k2) S2; else if (®k3) S3; S4; VÝ dô 1: T×m max(a,b,c) Kü thuËt lËp tr×nh 35 if (a>b) if (a>c) max=a; else max=c; else if (b>c) max =b; else max= c; VÝ dô 2: TÝnh hµm f(x) : f(x) = x2 , nÕu -2 < = x< 2 4 , x > = 2 if (x>=-2 && x<2) fx= x*x; else if (x>=2) fx= 4; else { printf("\n Khong xac dinh") ; exit(0) ;} II.2.2. LÖnh chän lùa: switch_case Có ph¸p: switch (biÓu thøc) { case h»ng 1: S1; case h»ng 2: S2; break; . . . case h»ng 3: Sn; break; default: S0; } C¸ch ho¹t ®éng: - (biÓuthøc) cã kÕt qu¶ nguyªn - H»ng: ký tù, sè nguyªn, biÓu thøc cã sè nguyªn - NÕu kÕt qu¶ b»ng h»ng I nµo ®ã th× nã sÏ lµm lÖnh Si vµ tuÇn tù thùc hiÖn hÕt c¸c lÖnh ë d­íi cho ®Õn khi hÕt lÖnh switch. - Muèn ng¾t sù tuÇn tù trªn th× ph¶i dïng lÖnh break. VÝ dô: NhËp 1 ký tù sè d¹ng hex ®æi ra sè thËp ph©n #include #include void main() Kü thuËt lËp tr×nh 36 { unsignedchar ch; int k; clrscr(); printf("Nhap 1 ky tu so hex : "); ch=getche(); switch (ch) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': k=ch-'0'; break; case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':k=ch-'A'+10; break; case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': k= ch-'a'+10; break; default: k=0; } printf ("\nSo thap phan cua ky tu hexa %c la %d ",ch,k); getch(); } VÝ dô: ViÕt ch­¬ng tr×nh t¹o 1 m¸y tÝnh cã 4 phÐp to¸n + , - , * , / #include #include void main() { Kü thuËt lËp tr×nh 37 float num1, num2; char op; clrscr(); printf ("Go vao so, toan tu, so \n"); scanf("%f %c %f", &num1, &op, &num2); switch (op) { case '+': printf("= %f",num1+num2); break; case '-': printf("= %f",num1-num2); break; case '*': printf("= %f",num1*num2); break; case '/': printf("= %f",num1/num2); break; default : printf("To¸n tö l¹, kh«ng biÕt"); } } II.3. CÊu tróc lÆp II.3.1. LÖnh while: Có ph¸p: while (bt) S; ÑK NO YES S Chó ý: Trong phÇn th©n lÖnh ph¶i cã biÕn ®iÒu khiÓn vßng lÆp. VÝ dô 1: ViÕt ch­¬ng tr×nh in ra b¶ng m· ASCII void main () { int n=0; while (n <= 255) Kü thuËt lËp tr×nh 38 { printf(“%c cã m· ASCII lµ %d”, n, n); n ++ } } VÝ dô 2: NhËp mét chuçi ký tù, vµ kÕt thóc nhËp b»ng ESC #define ESC ‘\ 0x1b’ #include #include void main() { char c; while (1) if ((c = getche() ) == ESC ) break; } VÝ dô 3: ViÕt ch­¬ng tr×nh in b¶ng cöu ch­¬ng void main () { int a, b; b = 1; while (b < = 9) { a = 2; while (a < = 9) { printf(“%d * %d = %d \t”, a, b, a*b); a++; } b ++; printf(“\n”); } } II.3.2. LÖnh do while: Có ph¸p: do S while (bt); S ñk No Yes VÝ dô 1: ViÕt ch­¬ng tr×nh in b¶ng m· ASCII #include Kü thuËt lËp tr×nh 39 main () { int n=0; do { printf(“%c cã m· ASCII %d\n”, n, n); n ++; } while (n <= 255); } II.3.3. LÖnh for: Có ph¸p: for ([bt_khëi ®éng] ; [bt_®k] ; [btlÆp]) S ; VÝ dô 1: LÆp lÖnh S tõ 1 ®Õn 10 for (int I=1; I== 10; I++)  sai S; for (int I=10; I>= 1; I--)  ®óng S ; VÝ dô 2: for ( ; 1 ; ) { c = getch() if (c == ESC) break; } So s¸nh vßng lÆp while - for: bt_khëi ®éng; while (BiÓuThøc_®K) { S; BT_lÆp; } for ( bt_khëi ®éng; bt_®k; bt_lÆp) S; VÝ dô 3: ViÕt ch­¬ng tr×nh in ra b¶ng cöu ch­¬ng b»ng vßng for void main () { int a; for (a=2; a<= 9; a++) { for (b =1; b <= 9; b++) printf(“%d* %d = %d \t”, a, b, a*b); printf(“\n); } } VÝ dô 4: ViÕt ch­¬ng tr×nh tÝnh n giai thõa Kü thuËt lËp tr×nh 40 void main () { long gt = 1; for (int i =1; i<= n; i++) gt = gt * i; printf(“%d! = %u \n”, n, gt); } VÝ dô 5: ViÕt ch­¬ng tr×nh tÝnh biÓu thøc: (1 + 1/12 ) * (1 + 1/22 ) *......... (1 + 1/ n2 ) void main () { int i, n; float S; printf(“NhËp sè :”); scanf(“%d”, &n); S = 1; for (i= 1;i<= n; i++) S = S*(1+1.0 / (i*i)); printf(“\nKet qua = %f”, S) } * Ph¸t biÓu break, continue, goto: 1. Break: LÖnh break cho phÐp tho¸t ra sím khái vßng lÆp ( whiledo , for, dowhile), lÖnh switch. 2. LÖnh continue: LÖnh continue chØ dïng trong vßng lÆp lµm cho ch­¬ng tr×nh nh¶y t¾t vÒ ®iÒu kiÖn kiÓm tra cña vßng lÆp ®Ó b¾t ®Çu mét vßng lÆp míi. VÝ dô: ViÕt ch­¬ng tr×nh nhËp mét c©u ch÷ th­êng kÕt thóc b»ng dÊu chÊm, xuÊt ra b»ng ch÷ hoa void main () { char ch; while (1) { ch = getch (); if ((ch> = ‘a’) && (ch< = ‘z’)) printf(“%c”, ch - ‘a’ + ‘A’); if (ch == ‘ ‘ ) continue; if (ch == ‘.’) break; } Kü thuËt lËp tr×nh 41 } 3. LÖnh goto: dïng ®Ó chuyÓn ®iÒu khiÓn ch­¬ng tr×nh vÒ mét vÞ trÝ nµo ®ã. Có ph¸p: Goto nh·n; LÖnh goto sÏ chuyÓn ®iÒu khiÓn ch­¬ng tr×nh ngay lËp tøc vÒ vÞ trÝ ®Æt nh·n. VÝ dô: Again: ; . . goto Again; Bµi tËp: 1. ViÕt ch­¬ng tr×nh tÝnh diÖn tÝch - H×nh vu«ng - H×nh thang - Tam gi¸c th­êng - Tam gi¸c vu«ng - H×nh trßn 2. TÝnh kho¶ng c¸ch mét ®iÓm (X0, Y0) tíi mét ®­êng th¼ng Ax + By + C = 0 BA CByAò S 22 00    , nhËp A, B, C, X0, Y0 3. Cho 3 sè thùc x, y, z. T×m a. Max(x+y+z, x*y*z) b. Min2 ((x+y+z) / 2, x*y*z) +1 4. ViÕt ch­¬ng tr×nh t×m sè lín nhÊt trong 3 sè nguyªn a,b, c 5. Gi¶i ph­¬ng tr×nh bËc 2 Ax2+Bx+C = 0 trªn tr­êng sè thùc. 6. ViÕt ch­¬ng tr×nh tÝnh diÖn tÝch h×nh trßn, biÕt b¸n kÝnh r d­¬ng; Ch­¬ng tr×nh cã kiÓm tra sè liÖu nhËp vµo, nÕu r <=0 th× ch­¬ng tr×nh b¸o lçi vµ b¾t nhËp l¹i. 7. ViÕt ch­¬ng tr×nh nhËp sè thËp lôc ph©n in ra sè nhÞ ph©n, cø 4 sè th× c¸ch mét kho¶ng tr¾ng. 8. ViÕt ch­¬ng tr×nh t¹o 1 m¸y tÝnh gåm c¸c phÐp to¸n sau : + , - , * , / , ^ (ax víi x nguyªn d­¬ng), @ (ex ) Kü thuËt lËp tr×nh 42 9. ViÕt ch­¬ng tr×nh kiÓm tra 1 bit bÊt k× cña sè b»ng 0 hay 1 10. ViÕt ch­¬ng tr×nh tÝnh kÕt qu¶ cña mét sè sau khi dÞch ph¶i hoÆc dÞch tr¸i n lÇn. 11. §Õm sè lÇn xuÊt hiÖn cña tõ mét trong 1 c©u 12. Thay thÕ 1 tõ trong 1 c©u b»ng 1 tõ kh¸c. 13. NhËp hä tªn, t¸ch hoten ra lµm 2 phÇn hä vµ tªn riªng. 14. ViÕt ch­¬ng tr×nh ®æi c¸c ký tù ®Çu cña c¸c tõ ra ch÷ in, c¸c ký tù cßn l¹i ra ch÷ th­êng. 15. ViÕt ch­¬ng tr×nh cho phÐp ta kiÓm tra mét password lµ ®óng hay sai (nhËp tèi ®a password 3 lÇn). 16. Cho chuçi s, viÕt ch­¬ng tr×nh di chuyÓn ch÷ tõ bªn tr¸i qua bªn ph¶i cña mµn h×nh t¹i dßng 5. Qu¸ tr×nh di chuyÓn dõng l¹i khi ta Ên phÝm ESC. 17. B¹n h·y viÕt ch­¬ng tr×nh tÝnh gi¸ trÞ tæng céng cña mét s¶n phÈm cã kÓ c¶ thuÕ, biÕt r»ng tû suÊt thuÕ lµ 13.6% tÝnh trªn gi¸ gèc. Gi¸ gèc cña s¶n phÈm va so luong cua san pham ®­îc ®äc vµo, vµ cÇn in ra: - TiÒn thuÕ - Gi¸ ®· cã thuÕ 18. Trong mét kú thi cuèi khãa, c¸c häc viªn ph¶i thi 4 m«n : m«n I hÖ sè 2, m«n II hÖ sè 4, m«n III hÖ sè 1, m«n IV hÖ sè 2, ®iÓm c¸c m«n cho tèi ®a lµ 10 ®iÓm. ViÕt ch­¬ng tr×nh nhËp ®iÓm cña 4 m«n vµ tÝnh ®iÓm trung b×nh. 19. Mét ng­êi b¸n r­îu b¸n N chai r­îu cã ®¬n gi¸ lµ P. NÕu tæng sè tiÒn v­ît qu¸ 5000000 th× viÖc chuyªn chë lµ miÓn phÝ, nÕu kh«ng phÝ chuyªn chë th­êng ®­îc tÝnh b»ng 1% tæng trÞ gi¸ hµng. ViÕt ch­¬ng tr×nh nhËp vµo N, P. In ra c¸c chi tiÕt Tæng trÞ gi¸ hµng, tiÒn chuyªn chë, vµ tæng sè tiÒn ph¶i tr¶. 20. Mét sinh viªn dù tuyÓn cã c¸c chi tiÕt sau : hä tªn, ®iÓm L1 cña lÇn 1, ®iÓm L2 cña lÇn 2, ®iÓm thi cuèi kú CK. ViÕt ch­¬ng tr×nh x¸c ®Þnh xem mét sinh viªn cã ®­îc tuyÓn hay bÞ lo¹i, biÕt r»ng sÏ ®­îc tuyÓn nÕu ®iÓm ®­îc tÝnh theo c«ng thøc sau lín h¬n hay b»ng 7 : Max( (L1+L2+CK)/3, CK). 21. ViÕt ch­¬ng tr×nh cho biÕt tiÒn l­¬ng hµng ngµy cña mét ng­êi gi÷ trÎ. C¸ch tÝnh lµ 15000®/giê cho mçi giê tr­íc 14 giê vµ 25000 ®/giê cho mçi giê sau 14 giê. Giê b¾t ®Çu vµ giê kÕt thóc c«ng viÖc ®­îc nhËp tõ bµn phÝm. 22. Cho 3 sè thùc x, y z a. Tån t¹i hay kh«ng mét tam gi¸c cã 3 c¹nh cã ®é dµi x, y, z ? b. NÕu lµ tam gi¸c th× nã vu«ng, c©n, ®Òu hay th­êng 23. Gi¶i hÖ ph­¬ng tr×nh bËc nhÊt: Kü thuËt lËp tr×nh 43  ax+by = c a’x+b’y = c’ H­íng dÉn: D = a b a’ b’ = ab’ - a’b Dx= c b c’ b’ = cb’ - c’b Dy= a c a’ c’ = ac’ - a’c if D!= 0 x= Dx/D; y= Dy/ D else if (( Dx != 0) | | ( Dy != 0)) pt v« nghiÖm else pt v« ®Þnh 24. Gi¶i hÖ ph­¬ng tr×nh 3 Èn sè bËc nhÊt  a1 x + b1 y + c1 z = d1 a2 x + b2 y + c2 z = d2 a3 x + b3 y + c3 z = d3 25. ViÕt ch­¬ng tr×nh gi¶i ph­¬ng tr×nh trïng ph­¬ng ax4 + bx2 + c = 0 26. Ng­êi ta muèn lËp hãa ®¬n cho kh¸ch hµng cña C«ng ty ®iÖn lùc. ChØ sè ®Çu vµ chØ sè cuèi kú sÏ ®­îc cho biÕt. BiÕt r»ng biÓu gi¸ ®­îc tÝnh tïy theo ®iÖn n¨ng tiªu thô. - NÕu ®iÖn n¨ng tiªu thô nhá h¬n 100Kwh, gi¸ mçi Kwh lµ 500®. - NÕu ®iÖn n¨ng tiªu thô tõ 100Kwh trë lªn, th× mçi Kwh d«i ra sÏ ®­îc tÝnh gi¸ lµ 800® - PhÝ khu vùc lµ 5000® cho mçi kh¸ch hµng. ViÕt ch­¬ng tr×nh tÝnh tiÒn ph¶i tr¶ tæng céng gåm tiÒn ®iÖn, vµ phÝ khu vùc 27. BiÕt 2 sè X, Y biÓu diÓn thêi gian tÝnh theo gi©y. Ng­êi ta muèn viÕt ch­¬ng tr×nh : - §äc 2 sè nµy vµ in ra tæng cña chóng - ChuyÓn c¸c sè nµy vµ tæng ra d¹ng giê, phÜt, gi©y cña chóng råi in ra. KiÓm xem kÕt qu¶ cña 2 c¸ch tÝnh cã nh­ nhau kh«ng? 28. ViÕt ch­¬ng tr×nh in b¶ng cöu ch­¬ng tõ 2  9 theo hµng ngang 29. In tam gi¸c *, h×nh ch÷ nhËt *, rçng - ®Æc 30. VÏ l­u ®å vµ viÕt ch­¬ng tr×nh tÝnh : a. 1+2+...+n Kü thuËt lËp tr×nh 44 b. 1+3+5+...+2n-1 c. 2+4+6+...+2n d. 12+ 22+ 32+...+n2 e. 1/1+ 1/2+ 1/3+...+ 1/n f. 2+4+8+...+2n g. 1+ 1/22 + 1/32 +....+ 1/n2 31. Cho epsilon = 0.000001, x¸c ®Þnh c¸c tæng sau ®©y sao cho sè h¹ng cuèi cïng cña tæng lµ kh«ng ®¸ng kÓ (sè h¹ng cuèi cïng < epsilon ) a. 1/1+ 1/2+ 1/3+1/4+..... b. 1+ 1/22 + 1/32 +....+... 32. ViÕt ch­¬ng tr×nh in ra b¶ng m· ASCII, 16 ký tù trªn 1 dßng. 33. VÏ l­u ®å vµ viÕt ch­¬ng tr×nh : a. XÐt mét sè cã ph¶i lµ sè nguyªn tè hay kh«ng ? b. In trªn mµn h×nh 100 sè nguyªn tè ®Çu tiªn 34. ViÕt ch­¬ng tr×nh cho phÐp mét ký tù ngÉu nhiªn r¬i trªn mµn h×nh. NÕu ng­êi sö dông kh«ng kÞp Ên phÝm t­¬ng øng vµ ®Ó ch¹m ®¸y mµn h×nh th× thua cuéc. 35. Cho hµm Fibonacci: Fn =  1 ; n=0,1 Fn-1 + Fn-2 ; n>=2 a. T×m Fn, víi n do ta nhËp b. In ra N phÇn tö ®Çu tiªn cña d·y Fibonacci 36. ViÕt ch­¬ng tr×nh ®äc vµo sè nguyªn N vµ in ra 1*2*3*..*N cho ®Õn khi N <=0. 37. Cho 1 d·y gåm mét triÖu tõ 32 bit, h·y ®Õm sè bit 1 trong mçi tõ. 38. ViÕt ch­¬ng tr×nh ®o¸n sè : ng­êi ch¬i sÏ ®o¸n 1 sè trong ph¹m vi tõ 0 ®Õn 100, tèi ®a 5 lÇn. Ch­¬ng tr×nh kiÓm tra kÕt qu¶ vµ xuÊt th«ng b¸o h­íng dÉn: - Sè b¹n ®o¸n lín h¬n - Sè b¹n ®o¸n nhá h¬n - B¹n ®o¸n ®óng - M¸y th¾ng cuéc Kü thuËt lËp tr×nh 45 III. Hµm - §Ö quy: III.1. Hµm: III.1.1. Môc ®Ých: Hµm lµ mét ch­¬ng tr×nh con cña ch­¬ng tr×nh chÝnh, víi c¸c môc ®Ých sau: * Tr¸nh viÖc lÆp ®i lÆp l¹i c¸c ®o¹n ch­¬ng tr×nh gièng nhau, nhê ®ã, ta sÏ tiÕt kiÖm lóc lËp tr×nh. * Tæ chøc ch­¬ng tr×nh: Dïng hµm ta sÏ ph©n m¶nh ch­¬ng tr×nh thµnh nh÷ng khèi nhá ®éc lËp, mçi khèi lµ mét hµm thùc hiÖn mét c«ng viÖc nµo ®ã. Tõng hµm sÏ ®­îc lËp tr×nh, kiÓm tra hoµn chØnh; Sau ®ã, ta kÕt l¹i ®Ó t¹o ch­¬ng tr×nh hoµn chØnh. Nhê vËy, ch­¬ng tr×nh vÒ sau dÓ hiÓu vµ dÓ s÷a. * TÝnh ®éc lËp: cho phÐp hµm ®éc lËp víi ch­¬ng tr×nh chÝnh. VÝ dô hµm cã nh÷ng biÕn côc bé mµ ch­¬ng tr×nh chÝnh vµ c¸c hµm kh¸c kh«ng thÓ ®ông tíi. Do ®ã, nÕu ta cã khai b¸o c¸c biÕn trïng tªn víi c¸c hµm kh¸c th× còng kh«ng sî ¶nh h­ëng tíi c¸c biÕn trïng tªn ®ã. Chó ý: - C kh«ng cho phÐp c¸c hµm lång nhau nghÜa lµ c¸c hµm ®Òu ngang cÊp nhau (cã thÓ gäi lÉn nhau). - C kh«ng ph©n biÖt thñ tôc hay hµm, mµ chØ quan t©m ®Õn kÕt qu¶ tr¶ vÒ cña hµm. NÕu hµm kh«ng tr¶ vÒ kÕt qu¶ g× c¶ th× cã thÓ xem lµ thñ tôc. VÝ dô: VÏ h×nh ch÷ nhËt ®Æc b»ng dÊu ‘*’: #include #include void ve_hcn(int d,int r) // khai b¸o void cho biÕt hµm kh«ng tr¶ vÒ trÞ nµo c¶ { int i,j ; // i, j lµ 2 biÕn côc bé trong hµm ve_hcn for (i=1;i<=r;i++) { for (j=1;j<=d; ++j) printf("*"); printf("\n"); } } void main() { int d=20, r=5; clrscr(); ve_hcn(d,r); // lêi gäi hµm getch(); } Kü thuËt lËp tr×nh 46 III.1.2. Có ph¸p ®Þnh nghÜa hµm Có ph¸p: KiÓu tªnhµm (ds ®èi sè) { Khai b¸o biÕn côc bé; lÖnh; [ return (expr);] } - KiÓu: Lµ kÕt qu¶ tr¶ vÒ cña hµm. NÕu kh«ng ghi kiÓu, C sÏ tù hiÓu lµ kiÓu int. NÕu kh«ng muèn cã kÕt qu¶ tr¶ vÒ th× ghi kiÓu void. - Danh s¸ch ®èi sè: LiÖt kª c¸c ®èi sè vµ kiÓu cña ®èi sè gëi ®Õn hµm, c¸ch nhau bëi dÊu ','. NÕu kh«ng cã ®èi sè ta chØ cÇn ghi() - LÖnh return: cã c¸c d¹ng sau: return; return (expr); return expr; VÝ dô: Hµm chuyÓn ch÷ th­êng sang ch÷ hoa #include #include Get_upper(char ch) { return (ch >='a' && ch <='z')? ch-'a'+'A':ch; } void main() { char ch; printf("\nNhap vao ky tu bat ky "); ch=getche(); printf("\nKy tu %c qua ham Get_upper tro thanh %c",ch,Get_upper(ch)); getch(); } L­u ý: - H¹n chÕ cña lÖnh return lµ chØ tr¶ vÒ mét kÕt qu¶. - LÖnh return kh«ng nhÊt thiÕt ph¶i ë cuèi hµm. Nã cã thÓ xuÊt hiÖn ë bÊt kú n¬i nµo trong hµm. Khi gÆp lÖnh return, quyÒn ®iÒu khiÓn sÏ chuyÓn ngay vÒ ch­¬ng tr×nh gäi. III.1.3. C¸c lo¹i truyÒn ®èi sè a. TruyÒn theo trÞ Kü thuËt lËp tr×nh 47 #include #include int max (int a,int b) { int m= a>b?a:b; a=a*100; b=b*100; return m; } void main() { int a,b,c; clrscr(); printf("\nChuong trinh tim Max(a,b)\n"); printf("Nhap a b : "); scanf("%d %d",&a,&b); c=max(a,b); printf("\nGia tri lon nhat =%d",c); printf("\nGia tri a =%d",a); printf("\nGia tri b =%d",b); getch(); } Gi¶ sö ta ch¹y ch­¬ng tr×nh trªn: Nhap a b : 12 24 Gia tri lon nhat =24 Gia tri a =12 Gia tri b=24 NhËn xÐt: - Ta nhËn thÊy r»ng gi¸ trÞ hai biÕn a, b tr­íc vµ sau khi vµo hµm max lµ kh«ng thay ®æi (mÆc dï trong hµm max, c¶ hai biÕn a vµ b ®Òu thay ®æi); ®ã lµ c¬ chÕ cña sù truyÒn ®èi sè theo trÞ. Lêi gäi hµm: tªnhµm (ds ®èisèthùc); - NÕu truyÒn ®èi sè theo trÞ th× ®èi sè thùc cã thÓ lµ biÕn, hoÆc cã thÓ lµ biÓu thøc. VÝ dô: c = max(1000,b); b. TruyÒn theo ®Þa chØ: ®èi sè thùc lµ ®Þa chØ cña biÕn #include #include Kü thuËt lËp tr×nh 48 max (int &a,int b) { int m= a>b? a : b; a=a *100; b=b*100; return m; } void main() { int a,b,c; clrscr(); printf("\nChuong trinh tim Max(a,b)\n"); printf("Nhap a b : "); scanf("%d %d",&a,&b); c=max(a,b); // a lµ tham sè thùc biÕn printf("\nGia tri lon nhat =%d",c); printf("\nGia tri a =%d",a); printf("\nGia tri b =%d",b); getch(); } Gi¶ sö ta ch¹y ch­¬ng tr×nh trªn: Nhap a b : 12 24 Gia tri lon nhat =24 Gia tri a =1200 Gia tri b=24 NhËn xÐt: - Ta nhËn thÊy r»ng gi¸ trÞ biÕn a tr­íc vµ sau khi vµo hµm max ®· thay ®æi; ®ã lµ c¬ chÕ cña sù truyÒn ®èi sè theo ®Þa chØ. Lêi gäi hµm: tªnhµm (tªnbiÕn); - NÕu truyÒn ®èi sè theo ®Þa chØ th× tham sè thùc b¾t buéc ph¶i lµ mét tªn biÕn. VÝ dô: c = max(1000,b); lµ sai VÝ dô: ViÕt hµm giaoho¸n ®Ó ho¸n ®æi gi¸ trÞ cña 2 biÕn nguyªn a,b. void giaohoan (int &a, int &b) { int tam; tam = a; a = b; b = tam; } Kü thuËt lËp tr×nh 49 void main() { int a,b; printf ("a, b = "); scanf ("%d %d", &a, &b); // a=10 , b=20 giaohoan(a, b); } * TruyÒn ®èi sè lµ m¶ng gäihµm (mang) hµm (kiÓu mang[]) hoÆc hµm(kiÓu *mang) VÝ dô: Céng thªm mét h»ng sè vµo m¶ng tªn lµ dayso. #define SIZE 5 // d·y sè cã 5 sè #include #include void add_const(int *a, int n, int con) // int *a  int a[] { for (int i=0; i<n; i++) *a = *(a++) + con; } void main() { int dayso [SIZE] = {3,5,7,9,11}; int konst = 10; add_const(dayso, SIZE, konst); printf("\nDay so sau khi cong them hang so :"); for (int i=0; i<SIZE; i++) printf("%d ", *(dayso+i)); // *(dayso+i)  dayso[i] getch(); } III.1.4. Khai b¸o nguyªn mÉu cña hµm - Khai b¸o hµm theo nguyªn mÉu ®ßi hái ph¶i khai b¸o kiÓu d÷ liÖu cña ®èi sè n»m trong ®Þnh nghÜa hµm chø kh«ng ®Æt chóng trªn c¸c dßng riªng. - C kh«ng nhÊt thiÕt ph¶i khai b¸o hµm theo nguyªn mÉu. Tuy nhiªn, nªn cã v× nã cho phÐp ch­¬ng tr×nh dÞch ph¸t hiÖn cã lçi do kh«ng ®óng kiÓu d÷ liÖu gi÷a trÞ truyÒn ®Õn hµm vµ trÞ mµ hµm mong muèn. VÝ dô: float dinhthuc (float a, float b, float c, float d) { return (a*d- b*c); } void main() Kü thuËt lËp tr×nh 50 { float a ,b, a1, b1; printf(“Nhap a,b,a1,b1:”); scanf(“%f %f %f %f,&a,&b,&a1,&b1); printf(“Dinh thuc = %f”,dinhthuc(a,b,a1,b1); getch(); } III.1.5. Ph¹m vi tån t¹i cña biÕn: a. BiÕn toµn côc: lµ biÕn ®­îc khai b¸o ngoµi c¸c hµm ( kÓ c¶ hµm main). Nã ®­îc phÐp truy nhËp ®Õn tõ tÊt c¶ c¸c hµm trong suèt thêi gian ch­¬ng tr×nh ho¹t ®éng. VÝ dô: Khai b¸o ngoµi hµm main KiÓu tªn biÕn; // biÕn toµn côc void main() { } b. BiÕn côc bé: lµ biÕn ®­îc khai b¸o trong c¸c hµm, kÓ c¶ trong hµm main. Nã kh«ng cho phÐp c¸c hµm kh¸c truy nhËp ®Õn nã. Nã tån t¹i trong thêi gian sèng cña hµm chøa nã. void main() { kiÓu tªn biÕn;  biÕn côc bé trong hµm main() } c. BiÕn ngoµi : lµ biÕn mµ c¸c hµm cã thÓ truy xuÊt tíi mµ kh«ng ph¶i ph©n phèi bé nhí. Nã ®­îc dïng ë c¸c hµm trªn c¸c tËp tin kh¸c nhau liªn kÕt l¹i. External KiÓu tªn biÕn; void main() { } d. BiÕn tÜnh : lµ mét biÕn côc bé cña mét hµm nh­ng vÉn gi÷ gi¸ trÞ cña lÇn gäi hµm ®ã cuèi cïng void main() { static KiÓu tªnbiÕn; } e. BiÕn thanh ghi : lµ mét biÕn sö dông c¸c thanh ghi cña CPU ®Ó t¨ng tèc ®é truy xuÊt register KiÓu tªnbiÕn ; Kü thuËt lËp tr×nh 51 III.1.6. C¸c dÉn h­íng tiÒn xö lý III.1.6.1. #define a. ®Þnh nghÜa h»ng: #define tªn h»ng gi¸ trÞ VÝ dô: #define PI 3.14 #define MAX 100 #define THONGBAO “HÕt Gi¸" #define khoangtrang ‘ ‘ b. ®Þnh nghÜa Macro: #define tªnmacro (®èi sè ) thao t¸c VÝ dô: #define sqr (x) x*x #define sum (x,y) x+y a = b * sum (x,y); //  a = b * x+y; #define sum (x,y) (x+y) a = b * sum (x,y); //  a = b * (x+y); *Chó ý: Trong c¸c thao t¸c Macro nªn sö dông c¸c dÊu ngoÆc ®Ó tr¸nh dÉn ra mét kÕt qu¶ sai VÝ dô: #define max (a,b) ((a) > (b) ? (a) : (b)) #define ho¸nvÞ (a,b) { int t¹m =a; a= b; b= t¹m;} #define error (n) printf (“ error %d”, n) D­íi ®©y mét sè Macro ph©n tÝch ký tù, tÊt c¶ ®Òu trong . C¸c macro nµy tr¶ vÒ trÞ kh¸c 0 nÕu thµnh c«ng. §èi víi mçi macro, thµnh c«ng ®­îc ®Þnh nghÜa nh­ sau: Macro Ký tù isalpha (c) c lµ ký tù a z, A Z isupper (c) c lµ ký tù A  Z islower (c) c lµ ký tù a  z isdigit (c) c lµ ký sè 0  9 isxdigit (c) 0  9, A  F, a  z iscntrl(c) c lµ ký tù xãa hoÆc ký tù ®iÒu khiÓn (0x7F hoÆc 0x00 ®Õn 0x1F) ispace (c) c lµ ký tù space, tab, carriage return, new line (0x09 ®Õn 0x0D, 0x20) Khai b¸o: char c; Kü thuËt lËp tr×nh 52 * Ph©n biÖt Macro víi hµm: - Dïng Macro: truy xuÊt nhanh, tèn bé nhí. - Dïng hµm: ng­îc l¹i III.1.6.2. #include Lµ tiÒn xö lý dïng ®Ó kÕt nèi tËp trung khai b¸o trong include víi tËp tin ®ang lµm viÖc. # include # include “ tªn tËp tin.h” D¹ng : ®i t×m tËp tin.h trong th­ môc ®· ®­îc chØ ®Þnh trong Include Directories. D¹ng “ ”: t×m tËp tin.h trong th­ môc Source Directories, nÕu kh«ng cã, nã ®i t×m trong th­ môc ®· ®­îc chØ ®Þnh trong Include Directories. III.2. §Ö qui (Recursion): III.2.1. Kh¸i niÖm: §Ö qui lµ 1 c«ng cô rÊt th­êng dïng trong khoa häc m¸y tÝnh vµ trong to¸n häc ®Ó gi¶i quyÕt c¸c vÊn ®Ò. Tr­íc hÕt, chóng ta h·y kh¶o s¸t thÕ nµo lµ mét vÊn ®Ò cã ®Ö qui qua vÝ dô sau: TÝnh S(n) = 1 +2 +3 +4+ ...+n Ta nhËn thÊy r»ng, c«ng thøc trªn cã thÓ diÔn ®¹t l¹i nh­ sau: S(n) = S(n-1) + n, vµ S(n-1) = S(n-2) + (n-1) ..... S(2) = S(1) + 2 S(1) = 1 Nh­ vËy, mét vÊn ®Ò cã ®Ö qui lµ vÊn ®Ò ®­îc ®Þnh nghÜa l¹i b»ng chÝnh nã. §Ó tÝnh S(n): ta cã kÕt qu¶ cña S(1), thay nã vµo S(2), cã S(2) ta thay nã vµo S(3) ...., cø nh­ vËy cã S(n-1) ta sÏ tÝnh ®­îc S(n) *Mét sè vÝ dô 1. Hµm giai thõa: n! = { 1*2*3*......*(n-1)*n , n>0 1 , n=0 = { n*(n-1)! , n>0 1 , n=0 Kü thuËt lËp tr×nh 53 NhËn xÐt: - Theo c«ng thøc trªn, ta nhËn thÊy trong ®Þnh nghÜa cña n giai thõa (n!) cã ®Þnh nghÜa l¹i chÝnh nã nªn hµm giai thõa cã ®Ö qui. - Víi n >=0 , ®iÒu kiÖn dõng tÝnh hµm giai thõa lµ n=1 2. Hµm FIBONACCI: Fn =  1 ; n =0,1 Fn-1 + Fn-2 ; n>1 - Theo ®Þnh nghÜa trªn, hµm Fibonacci cã lêi gäi ®Ö qui. - Qu¸ tr×nh tÝnh dõng l¹i khi n= 1 III.2.2. Hµm ®Ö qui trong ng«n ng÷ C: Ng«n ng÷ C cã trang bÞ c¬ chÕ gäi hµm ®Ö qui. Hµm ®Ö qui lµ hµm gäi ®Õn chÝnh hµm ®ã mét c¸ch trùc tiÕp hay gi¸n tiÕp. VÝ dô 1: ViÕt hµm ®Ö qui tÝnh S(n) = 1 + 2 + 3 +...+n #include #include int S(int n) { if (n==1) // ®iÒu kiÖn dõng return 1; else // b­íc ®Ö qui return (S(n-1) + n); } void main() { int n; printf("\n Nhap n = "); scanf("%d",&n); printf("Tong S = 1 + 2 + ...+ %d = %d",n, S(n)); getch(); } VÝ dô 2 : ViÕt hµm ®Ö qui tÝnh hµm giai thõa n. long giaithua(int n) { return ((n==0) ? 1 : n*giaithua(n-1)); } III.2.3. Hµm ®Ö qui vµ Stack: Mét ch­¬ng tr×nh C th­êng gåm cã hµm main() vµ c¸c hµm kh¸c. Khi ch¹y ch­¬ng tr×nh C th× hµm main() sÏ ®­îc gäi ch¹y tr­íc, sau ®ã hµm main() gäi c¸c hµm kh¸c, c¸c hµm nµy trong khi ch¹y cã thÓ gäi c¸c hµm kh¸c n÷a. Khi Kü thuËt lËp tr×nh 54 mét hµm ®­îc gäi, th× mét khung kÝch ho¹t cña nã ®­îc t¹o ra trong bé nhí stack. Khung kÝch ho¹t nµy chøa c¸c biÕn côc bé cña hµm vµ mÉu tin ho¹t ®éng cña hµm. MÉu tin ho¹t ®éng chøa ®Þa chØ trë vÒ cña hµm gäi nã vµ c¸c tham sè kh¸c. BiÕn côc bé MÉu tin ho¹t ®éng  §Þa chØ trë vÒ Th«ng sè kh¸c Khung kÝch ho¹t Sau khi hµm ®­îc gäi ®· thi hµnh xong th× ch­¬ng tr×nh sÏ thùc hiÖn tiÕp dßng lÖnh ë ®Þa chØ trë vÒ cña hµm gäi nã, ®ång thêi xãa khung kÝch ho¹t cña hµm ®ã khái bé nhí. Gi¶ sö ta cã c¬ chÕ gäi hµm trong mét ch­¬ng tr×nh C nh­ sau: main() { ...... A(); .....; B(); ....; } A() {.....; C(); ....; D(); } B() {.....; D(); } C() {......; D(); .....; } D() {........; ........; } H×nh sau ®©y cho ta thÊy sù chiÕm dông bé nhí stack khi ch¹y ch­¬ng tr×nh C nh­ m« t¶ ë trªn. bé nhí Stack D C C C D D A A A A A A A B B B M M M M M M M M M M M M M thêi gian T­¬ng tù víi tr­êng hîp hµm ®Ö qui, khi gäi ®Ö qui lÉn nhau th× mét lo¹t c¸c khung kÝch ho¹t sÏ ®­îc t¹o ra vµ n¹p vµo bé nhí Stack. CÊp ®Ö qui cµng cao th× sè khung kÝch ho¹t trong Stack cµng nhiÒu, do ®ã, cã kh¶ n¨ng dÉn ®Õn trµn Stack (Stack overflow). Trong nhiÒu tr­êng hîp khi lËp tr×nh, nÕu cã thÓ ®­îc ta nªn gì ®Ö qui cho c¸c bµi to¸n. Kü thuËt lËp tr×nh 55 IV. Structure: C¸c kiÓu ®¬n gi¶n t¹i mét thêi ®iÓm chØ l­u gi÷ ®­îc mét gi¸ trÞ duy nhÊt. Cßn mét biÕn kiÓu m¶ng dïng ®Ó l­u tr÷ c¸c gi¸ trÞ cïng kiÓu d÷ liÖu víi nhau, ch½ng h¹n nh­ mét d·y sè, mét d·y c¸c ký tù,...Nh­ng trong thùc tÕ, ®iÒu nµy vÉn ch­a ®ñ v× c¸c thµnh phÇn mµ ta l­u gi÷ th­êng lµ kh¸c kiÓu d÷ liÖu víi nhau. VÝ dô : Ta muèn l­u gi÷ c¸c th«ng tin vÒ mét sinh viªn nh­ sau : MASO, HO, TEN, NGAYSINH, NOISINH, PHAI, DIACHI, LOP . Víi c¸c thµnh phÇn nh­ vËy, th× râ rµng c¸c thµnh phÇn cña 1 sinh viªn kh«ng thÓ cïng kiÓu mµ ph¶i thuéc c¸c kiÓu kh¸c nhau, cô thÓ lµ: - MASO, HO, TEN : m¶ng ch÷ - NGAYSINH : int ngµy , th¸ng , n¨m ; - NOISINH : m¶ng ch÷ - PHAI : unsigned int; - LOP : m¶ng ch÷; Do ®ã, ®Ó l­u tr÷ ®­îc c¸c thµnh phÇn kh¸c nhau cña mét ®èi t­îng ta ph¶i sö dông mét kiÓu d÷ liÖu trong C lµ Structure. (t­¬ng tù nh­ record trong Pascal) IV.1. §Þnh nghÜa: Mét biÕn cã kiÓu structure ®­îc dïng ®Ó l­u tr÷ mét ®èi t­îng cã nhiÒu thµnh phÇn. C¸c thµnh phÇn cã thÓ thuéc c¸c kiÓu d÷ liÖu kh¸c nhau. IV.2. Khai b¸o: Muèn khai b¸o kiÓu hocvien dïng ®Ó l­u tr÷ hä, tªn, ®iÓm m«n TOAN,LY,HOA, §TB, XÕp lo¹i cña mét häc viªn, ta cã : typedef struct hocvien { char ho[30]; char ten[7]; float toan, ly, hoa , dtb; char xeploai[10]; } ; - §Ó khai b¸o biÕn hv cã kiÓu hocvien : hocvien hv; - §Ó truy xuÊt tíi mét thµnh phÇn, ta dïng dÊu chÊm, vÝ dô nh­: hv->ho ®Ó truy xuÊt tíi hä cña häc viªn. * Khai b¸o kÕt hîp: võa khai b¸o kiÓu structure võa khai b¸o biÕn cã kiÓu ®ã. struct hocvien Kü thuËt lËp tr×nh 56 { char ho[30]; char ten[7]; float toan, ly, hoa , dtb; char xeploai[10]; } hv1, hv2; // khai b¸o 2 biÕn hv1, hv2 cïng kiÓu hocvien - Khai b¸o structure lång nhau: VÝ dô: void main() { struct ngaysinh { unsigned int ngay, thang, nam; }; struct hocvien { char ho[30]; char ten[7]; struct ngaysinh ngsinh; float toan, ly, hoa, dtb; char xeploai[10]; } ; struct hocvien hv; } Trong tr­êng hîp nµy, ®Ó truy xuÊt tíi th¸ng sinh cña häc viªn hv, ta viÕt nh­ sau: hv.ngsinh.thang. V. FILE: V.1. File v¨n b¶n: - File v¨n b¶n lµ file ®­îc l­u tr÷ d­íi d¹ng kiÓu ký tù Cã 2 c¸ch truy xuÊt theo kiÓu ký tù. - Truy xuÊt theo tõng ký tù - Truy xuÊt theo tõng dßng V.1.1. Khai b¸o tËp tin: Khai b¸o biÕn kiÓu file: FILE *fptr; V.1.2. Më tËp tin: fptr = fopen (“tªn file”, “kiÓu”); - Trong "tªnfile" , ta cã thÓ chØ ®Þnh mét ®­êng dÉn ®Çy ®ñ nh­ sau Kü thuËt lËp tr×nh 57 "C:\THU\KTLT\VIDU.TXT". Hµm fopen nÕu më file thµnh c«ng sÏ tr¶ vÒ mét con trá file cho tËp tin "tªn file", vµ con trá nµy ®­îc cÊt gi÷ trong biÕn fptr (biÕn kiÓu FILE). NÕu kh«ng cã file "tªn file" trªn dÜa th× hµm fopen sÏ tr¶ vÒ trÞ NULL ( nÕu fptr == NULL nghÜa lµ kh«ng cã file ®ã ) - KiÓu: gåm cã: “r“ : ®äc ( file ph¶i cã s½n, nÕu kh«ng cã file, hµm fopen tr¶ vÒ trÞ NULL) “w“ : ghi ( nÕu cã file sÏ xãa file cò ) “a” : nèi vµo cuèi tËp tin “r +”: ®äc / ghi, tËp tin ph¶i cã s½n trªn dÜa “a+”: ®äc, ghi vµo cuèi tËp tin, nÕu trªn dÜa ch­a cã tËp tin th× nã sÏ ®­îc t¹o ra. VÝ dô: §Õm sè ký tù trong file VB.TXT. #include #include #include void main() { FILE *fptr; int dem=0; char ch; if ((fptr = fopen("VB.txt", "r")) == NULL) // më file ®Ó ®äc { printf("File nay khong the mo\n"); return ; // kÕt thóc ch­¬ng tr×nh, hµm exit thuéc vÒ stdlib.h } while (!feof(fptr)) { ch=fgetc(fptr); // ®äc 1 ký tù trong file fptr ra dem++; } fclose(fptr); printf("\nSo ky tu trong file VB.TXT =%d",dem); getch(); } V.1.3. §ãng file: fclose (fptr) Kü thuËt lËp tr×nh 58 V.1.4. §äc / ghi ký tù: Cho biÕn ký tù char ch; - §äc ký tù tõ tËp tin ch = getc (fptr) - Ghi ký tù lªn tËp tin putc (ch, fptr) VÝ dô 1: T¹o 1 file trùc tiÕp tõ bµn phÝm. Qu¸ tr×nh t¹o sÏ dõng l¹i khi ta Ên phÝm Enter. #include #include #include void main() { FILE *fptr; char tenfile[67]; char ch; clrscr(); printf("Cho biet ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"w"))==NULL) // më file míi ®Ó ghi { printf("Viec tao file co loi\n"); exit(0); } while ((ch=getche()) !='\r') putc(ch,fptr); fclose(fptr); } VÝ dô 2: In néi dung tËp tin ra mµn h×nh #include #include #include void main() { FILE *fptr; char tenfile[67]; char ch; clrscr(); printf("Cho biet ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"r"))==NULL) Kü thuËt lËp tr×nh 59 { printf("Viec mo file co loi\n"); exit(0); } while ((ch=getc(fptr)) !=EOF) printf("%c",ch); fclose(fptr); } Kü thuËt lËp tr×nh 60 VÝ dô 3: Ch­¬ng tr×nh ®Õm sè tõ trong file #inclïde #include #include void main() { FILE *fptr; char tenfile[67]; int ch; int dem=0, tu=0; clrscr(); printf("Cho biet ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"r"))==NULL) // më file ®Ó ®äc { printf("Viec mo file co loi\n"); exit(0); } while ((ch=getc(fptr)) !=EOF) { if ((ch>='a' && ch ='A' && ch<='Z')) tu=1; if ((ch==' ' || ch=='\n' || ch=='\t') && tu) { dem++; tu=0; } } printf("So tu trong file =%d",dem); fclose(fptr); } V.1.5. §äc / ghi chuçi ký tù: * Hµm fgets (chuçi, chiÒudµi, fptr); Hµm fgets ®äc 1 chuçi ký tù tõ trong file fptr vµo biÕn víi chiÒu dµi tèi ®a lµ . Hµm nµy tr¶ vÒ NULL khi ®· ®äc hÕt file * Hµm fputs (chuçi, fptr): ghi 1 chuçi ký tù trong vµo file fptr. Hµm nµy kh«ng tù ®éng thªm vµo m· kÕt thóc ®Ó chuyÓn dßng míi, do ®ã ta ph¶i ghi thªm m· nµy vµo tËp tin b»ng lÖnh fputs ("\n", fptr); VÝ dô 1: Ch­¬ng tr×nh ghi chuçi lªn file, cho ®Õn khi chuçi nhËp vµo lµ rçng th× kÕt thóc. Kü thuËt lËp tr×nh 61 #include #include #include #include void main() { FILE *fptr; char tenfile[67]; char chuoi[80]; clrscr(); printf("Cho biet ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"w"))==NULL) // t¹o file míi { printf("Viec tao file co loi\n"); exit(0); } while (strlen(gets(chuoi)) > 0) // hµm strlen() trong { fputs(chuoi,fptr); fputs("\n",fptr); } fclose(fptr); } VÝ dô 2: §äc c¸c chuçi ký tù tõ tËp tin, vµ in nã trªn mµn h×nh. #include #include #include void main() { FILE *fptr; char tenfile[67]; char chuoi[81]; clrscr(); printf("Cho biet ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"r"))==NULL) { printf("Viec tao file co loi\n"); exit(0); } while (fgets(chuoi,80,fptr)!= NULL) printf("%s",chuoi); fclose(fptr); getch(); } Kü thuËt lËp tr×nh 62 V.1.6. Xãa file: LÖnh remove xo¸ file ®­îc chØ ®Þnh qua Có ph¸p: remove (tªn file) Hµm remove tr¶ vÒ 0 : xãa thµnh c«ng tr¶ vÒ -1 : cã lçi khi xãa file, vµ lóc nµy biÕn errno cã 1 trong 2 gi¸ trÞ sau: ENOENT : kh«ng t×m thÊy file muèn xãa EACCES : kh«ng cho phÐp xãa file mµ b¹n chØ ®Þnh L­u ý: File nªn ®ãng tr­íc khi xãa. VÝ dô: Xãa file do ta chØ ®Þnh. #include void main() { char filename[80]; /* prompt for file name to delete */ printf("File muon xoa: "); gets(filename); /* delete the file */ if (remove(filename) == 0) printf("Removed %s.\n",filename); else perror("remove"); // in th«ng b¸o lçi mµ hµm remove g©y ra } V.2. File nhÞ ph©n (file cã cÊu tróc) File nhÞ ph©n lµ file dïng ®Ó l­u tr÷ c¸c cÊu tróc d­íi d¹ng struct hoÆc union V.2.1. Khai b¸o: FILE * fptr; V.2.2. Më file: fptr = fopen (tªnfile, “kiÓu”); . rb ( b: binary): më chØ ®Ó ®äc . wb : ®Ó ghi. NÕu file ®· cã th× xãa tr­íc khi më. . ab : nèi thªm; më ®Ó ghi thªm vµo cuèi file, nÕu file ch­a cã th× t¹o míi . rb+ : më file ®· cã ®Ó cËp nhËt (®äc/ghi) . wb+ : t¹o file míi cho phÐp ®äc/ghi . ab+ : më ®Ó nèi thªm vÒ cuèi file, cho phÐp ®äc/ghi Kü thuËt lËp tr×nh 63 V.2.3. §ãng file: fclose (fptr) V.2.4. §äc/ghi file: Hµm fread : ®äc sè mÉu tin(cÊu tróc) trong file fptr vµo . fread (& biÕn cÊu tróc, sizeof (biÕn cÊu tróc) , sè cÊu tróc, fptr); Hµm fread tr¶ vÒ sè cÊu tróc ®äc ®­îc Hµm fwrite ghi d÷ liÖu trong vµo file fptr. int fwrite (&biÕn cÊu tróc, sizeof (biÕn cÊu tróc) , sè cÊu tróc, fptr); Hµm fwrite tr¶ vÒ sè cÊu tróc ghi ®­îc lªn file Chó ý: - §Ó kiÓm tra viÖc ®äc file ta kiÓm tra sè cÊu tróc ®­îc ®äc. NÕu sè cÊu tróc tr¶ vÒ b»ng 0 mµ ta cÇn ®äc lµ 1 cÊu tróc th× ®iÒu ®ã chøng tá ®· hÕt file. * Ghi mét m¶ng cÊu tróc lªn file fwrite(tªnm¶ng, sizeof (tªnm¶ng), 1, fptr);  for (i= 0; i< n; i++) fwrite (&tªnm¶ng[i], sizeof (tªnm¶ng[i]) , 1, fptr); VÝ dô 1: Ch­¬ng tr×nh ghi lªn file nhÞ ph©n #include #include #include void main() { struct hocvien { char hoten[30]; int tuoi; } hv; FILE *fptr; char tenfile[67]; char tuoi[3]; printf("Nhap ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"wb")) == NULL) // më file nhÞ ph©n ®Ó ghi { printf ("Khong the tao file\n"); exit(0); } Kü thuËt lËp tr×nh 64 do { printf("Nhap ho ten hoc vien :"); gets(hv.hoten); if (strlen(hv.hoten) !=0) { printf("Nhap tuoi :"); gets(tuoi); hv.tuoi = atoi(tuoi); // macro doi chuoi qua so nguyen fwrite(&hv, sizeof(hv), 1, fptr) ; // ghi noi dung 1 mau tin trong bien hv // vao file fptr } } while (strlen(hv.hoten)!=0); fclose (fptr); } VÝ dô 2: Ghi d÷ liÖu m¶ng vµo file nhÞ ph©n #include #include #include void main() { struct hocvien { char hoten[30]; int tuoi; } hv; struct hocvien table[3]; FILE *fptr; char tenfile[67]; char tuoi[3]; int i=0; printf("Nhap ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"wb")) == NULL) { printf ("Khong the tao file\n"); exit(0); } do { printf("Nhap ho ten hoc vien :"); gets(hv.hoten); printf("Nhap tuoi :"); gets(tuoi); Kü thuËt lËp tr×nh 65 hv.tuoi = atoi(tuoi); // macro doi chuoi qua so nguyen table[i++]=hv; } while (i<3); fwrite(table, sizeof(table), 1, fptr) ; // ghi noi dung toan bo hoc vien trong // table vao file fptr // hoÆc for (i=0; i<3; i++) // fwrite(&table[i], sizeof(table[i]), 1, fptr) fclose (fptr); } VÝ dô 3: Ch­¬ng tr×nh ®äc file nhÞ ph©n, vµ in danh s¸ch häc viªn ra mµn h×nh. // In danh s¸ch häc viªn ra mµn h×nh #include #include #include void main() { struct hocvien { char hoten[30]; int tuoi; } hv; FILE *fptr; char tenfile[67]; char tuoi[3]; printf("Nhap ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"rb")) == NULL) // Më file ®Ó ®äc { printf ("Khong the mo file\n"); exit(0); } clrscr(); printf(" Ho va ten Tuoi"); while (fread(&hv,sizeof(hv),1,fptr) ==1) { printf("\n%-20s",hv.hoten); printf("%3d",hv.tuoi); } fclose (fptr); } Kü thuËt lËp tr×nh 66 V.2.5. Truy xuÊt tËp tin ngÉu nhiªn: (®iÒu khiÓn con trá tËp tin trªn file nhÞ ph©n) * Con trá file: Mçi tËp tin ®Òu cã con trá file sau khi ®­îc më. Con trá file lµ con trá chØ ®Õn tõng byte trªn file. Khi ®äc hay ghi d÷ liÖu trªn tËp tin, ta ®· lµm dÞch chuyÓn con trá file mét sè byte, ®©y chÝnh lµ sè byte mµ kiÓu d÷ liÖu ®· chiÕm. Khi ®ãng råi më tËp tin, con trá file lu«n ë ®Çu tËp tin ; ngo¹i trõ tr­êng hîp ta më b»ng tïy chän 'a' th× con trá file sÏ ë cuèi tËp tin ®Ó ghi thªm d÷ liÖu vµo cuèi tËp tin. Hµm fseek cho phÐp ta di chuyÓn con trá file ®Õn vÞ trÝ mong muèn. Có ph¸p: int fseek (FILE * fptr, long nbytes, kiÓu) + nbytes : sè bytes tÝnh tõ vÞ trÝ kiÓu cho ®Õn vÞ trÝ cÇn tíi + kiÓu lµ sè nguyªn : kiÓu = 0 (tÝnh tõ ®Çu tËp tin) kiÓu = 1 (tÝnh tõ vÞ trÝ hiÖn t¹i) kiÓu = 2 (tÝnh tõ cuèi tËp tin) NÕu fseek tr¶ vÒ 0 nghÜa lµ nã ®· di chuyÓn tíi vÞ trÝ ®ã. L­u ý: sè thø tù trªn tËp tin tÝnh tõ 0. VÝ dô: ViÕt ch­¬ng tr×nh truy xuÊt ngÉu nhiªn mét mÉu tin theo sè thø tù cña nã trong file nhÞ ph©n #include #include #include void main() { struct hocvien { char hoten[30]; int tuoi; } hv; FILE *fptr; char tenfile[67]; int stt, sobytes; printf("Nhap ten file :"); gets(tenfile); if ((fptr=fopen(tenfile,"rb")) == NULL) { printf ("Khong the mo file\n"); exit(0); Kü thuËt lËp tr×nh 67 } clrscr(); printf("Cho biet so thu tu mau tin can di chuyen den :"); scanf("%d",&stt); sobytes = stt * sizeof(hv); if (fseek(fptr,sobytes,0)!=0) { printf ("Khong the di chuyen con tro file toi vi tri ban chi dinh duoc"); exit(0); } fread(&hv,sizeof(hv),1,fptr) ; printf("\n%-20s",hv.hoten); printf("%3d",hv.tuoi); fclose (fptr); getch(); } V.3. Ph¸t hiÖn lçi khi truy xuÊt tËp tin PhÇn lín nh÷ng hµm xuÊt, nhËp tËp tin chuÈn kh«ng th«ng b¸o râ néi dung cña lçi. Ch¼ng h¹n nh­: - putc () sÏ tr¶ vÒ EOF khi cã lçi hoÆc cuèi tËp tin - fgets () sÏ tr¶ vÒ lµ NULL khi ®äc hÕt file hoÆc khi cã lçi Do ®ã, ®Ó ph¸t hiÖn lçi khi truy xuÊt tËp tin, ta dïng macro ferror (FILE *fptr) int ferror (file * ptr) Macro ferror tr¶ vÒ mét trÞ kh¸c 0 nÕu ph¸t hiÖn ra lçi trªn file fptr. * §Ó xuÊt c©u th«ng b¸o lçi ta dïng hµm perror () void perror (const char * str) víi str : chuçi ký tù chøa c©u th«ng b¸o * Hai hµm nµy th­êng ®­îc sö dông ngay sau khi sö dông c¸c hµm ®äc / ghi file VÝ dô: fwrite (&table, sizeof (table), 1, fptr); if (ferror (fptr) != 0) { perror (“Loi ghi du lieu”); exit (0); } VÝ dô : #include void main() Kü thuËt lËp tr×nh 68 { FILE *fp; fp = fopen("perror.dat", "r"); if (!fp) perror("Kh«ng thÓ më file ®Ó ®äc"); } Khi ch¹y ch­¬ng tr×nh nµy, nÕu trªn dÜa ch­a cã tËp tin perror.dat th× sÏ hiÖn th«ng b¸o lçi: Kh«ng thÓ më file ®Ó ®äc: No such file or directory. Bµi tËp 1. T¹o tËp tin diÖn tÝch.h #define Pi 3.14 #define dthv (x) x*x #define dtht (x) (Pi*x*x) 2. ViÕt ch­¬ng tr×nh tÝnh diÖn tÝch dùa vµo file dientich.h ë trªn 3. ViÕt hµm ®Ö qui tÝnh tÝch P(n) = 1 * 2 * 3* ....* n , n>0 4. ViÕt hµm ®Ö qui tÝnh hµm mò xn, víi n nguyªn. 5. ViÕt hµm ®Ö qui tÝnh phÇn tö thø n cña hµm Fibonacci. 6. ViÕt hµm ®Ö qui gi¶i quyÕt bµi to¸n Th¸p Hµ néi. Cã 3 cét A, B, C. Cét A hiÖn ®ang cã n dÜa kÝch th­íc kh¸c nhau, dÜa nhá ë trªn dÜa lín ë d­íi. H·y dêi n dÜa tõ cét A sang cét C (xem cét B lµ cét trung gian) víi ®iÒu kiÖn mçi lÇn chØ ®­îc dêi 1 dÜa vµ dÜa ®Æt trªn bao giê còng nhá h¬n dÜa ®Æt d­íi. 7. ViÕt ch­¬ng tr×nh m· hãa vµ gi¶i m· mét file v¨n b¶n sao cho nÕu ta ®· m· hãa råi th× ch­¬ng tr×nh kh«ng m· hãa n÷a, vµ nÕu file ®ã ch­a m· hãa th× kh«ng ®­îc gi¶i m·. 8. Cho biÕt trong mét file v¨n b¶n do ta nhËp vµo cã bao nhiªu ký tù, bao nhiªu tõ, vµ bao nhiªu dßng; biÕt r»ng c¸c tõ c¸ch nhau kho¶ng tr¾ng, dÊu tab, dÊu chÊm. 9. ViÕt ch­¬ng tr×nh t¹o mét menu thùc hiÖn c¸c chøc n¨ng sau trªn file v¨n b¶n: - T¹o file míi - §äc file - Xãa file - Ghi nèi ®u«i file - Copy file Kü thuËt lËp tr×nh 69 - Di chuyÓn file tõ th­ môc nµy sang th­ môc kh¸c - T×m mét tõ xuÊt hiÖn bao nhiªu lÇn trong file (kh«ng ph©n biÖt ch÷ in, ch÷ th­êng) - Thay thÕ tõ nµy b»ng tõ kh¸c 10. T¹o menu thùc hiÖn c¸c c«ng viÖc sau: - NhËp danh s¸ch cã kiÓu häc viªn vµo mét file tªn 'HOSO.TXT', mçi häc viªn cã c¸c th«ng tin sau: maso (int), hoten (chuçi tèi ®a 30 ký tù), ph¸i (NAM/NU), tuæi (int). - LiÖt kª danh s¸ch häc viªn ra mµn h×nh theo d¹ng sau: M· sè Hä vµ tªn Ph¸i Tuæi - Truy xuÊt ngÉu nhiªn theo thø tù mÉu tin - T×m kiÕm mét ng­êi trong file theo m· sè - CËp nhËt söa ®æi c¸c mÉu tin theo m· sè (NhËp m· sè, sau ®ã hiÖu chØnh l¹i hoten, phai, vµ tuæi). - Xãa mét ng­êi trong file theo m· sè. Kü thuËt lËp tr×nh 70 CH­¬NG 3 C¸C THUËT TO¸N TR£N CÊU TRóC D÷ LIÖU M¶NG I. M¶ng kh«ng s¾p xÕp vµ thuËt to¸n t×m kiÕm trªn m¶ng ch­a cã thø tù I.1. Mét sè kh¸i niÖm vÒ m¶ng: I.1.1. §Þnh nghÜa: M¶ng lµ 1 d·y c¸c phÇn tö cã cïng kiÓu d÷ liÖu ®­îc s¾p xÕp liªn tiÕp nhau trong bé nhí 0100 0102 1 int 0104 2 M¶ng n phÇn tö n-1 Bé nhí Khai b¸o: Có ph¸p: Khai b¸o m¶ng 1 chiÒu KiÓu_DL Tªnm¶ng [kÝch th­íc];  KiÓu_DL : lµ 1 trong c¸c kiÓu d÷ liÖu c¬ b¶n, ®ã lµ kiÓu cña phÇn tö cña m¶ng  Tªnm¶ng: lµ tªn cña m¶ng ®­îc ®Æt 1 c¸ch hîp lÖ  KÝch th­íc: lµ 1 h»ng nguyªn cho biÕt sè phÇn tö tèi ®a cña m¶ng VÝ dô 1: Khai b¸o 1 m¶ng sè nguyªn  int n ; int M[n] ; SAI  int M[10] ; ®óng v× kÝch th­íc m¶ng ph¶i lµ h»ng kh«ng ph¶i lµ biÕn  #define max 100 int M[max] ; VÝ dô 2: Khai b¸o 1 danh s¸ch hä tªn häc viªn cña 1 líp häc char dshv[50][30]; // dshv cã thÓ chøa tèi ®a hä tªn 50 häc viªn, // chiÒu dµi hä tªn mçi häc viªn tèi ®a lµ 30 ký tù Có ph¸p: Khai b¸o m¶ng 2 chiÒu Kü thuËt lËp tr×nh 71 KiÓu_DL Tªnm¶ng [kÝch th­íc 1][kÝch th­íc 2] Chó ý: Mét m¶ng trong C, c¸c phÇn tö ®­îc ®¸nh sè tõ 0 tíi n-1 VÝ dô: Víi M[10] th× thµnh phÇn thø 1 lµ M[0] thµnh phÇn cuèi cïng M[9] * C kh«ng b¾t bÎ, kh«ng kiÓm tra xem biÕn ®Õm cã v­ît ra khái giíi h¹n cho phÐp cña m¶ng ch­a. Do ®ã, chóng ta ph¶i kiÓm tra biÕn ®Õm trong ch­¬ng tr×nh (ph¶i nhá h¬n n) I.1.2. Khëi ®éng trÞ cho m¶ng: Ta khëi ®éng ®­îc trÞ cho m¶ng trong 2 tr­êng hîp sau:  M¶ng ®­îc khai b¸o lµ biÕn ngoµi (main) nghÜa lµ biÕn toµn côc  M¶ng ®­îc khai b¸o côc bé VÝ dô 1 : int M[3] = {10,11,12} main() { } VÝ dô 2: main() { static int M[ ]={10,22,30}; ............ }  Ta cã thÓ g¸n 1 h»ng cho c¶ m¶ng nh­ sau: memset (M,0,sizeof(int) *3) ; // g¸n 0 cho m¶ng M víi M cã 3 phÇn tö  Tõ khãa static dïng ®Ó khai b¸o 1 biÕn côc bé th­êng trùc cho phÐp duy tr× gi¸ trÞ riªng cña nã ë nh÷ng lÇn gäi hµm sau nµy.  Khëi t¹o m¶ng 2 chiÒu: int M[2][3]= {{1,2,3}, {0,1,0}}; I.1.3.Truy xuÊt thµnh phÇn cña m¶ng: M[chØ sè]  Truy xuÊt thµnh phÇn thø 2 cña m¶ng 1 chiÒu: M[1]  Truy xuÊt thµnh phÇn thø i cña m¶ng 1 chiÒu: M[i-1]  Truy xuÊt thµnh phÇn dßng 2, cét 3 cña m¶ng 2 chiÒu M[1][2] I.1.4. §äc (nhËp) d÷ liÖu cho m¶ng: - §Ó nhËp d÷ liÖu cho m¶ng ta ph¶i nhËp d÷ liÖu cho tõng thµnh phÇn cña m¶ng. VÝ dô 1: Kü thuËt lËp tr×nh 72 int n,i; float M[10]; printf("\nCho biet so phan tu cua mang:") scanf (“%d”,&n); for ( i=0; i< n; i++) { printf(“a[%d]= “,i+1); scanf (“%f”,&M[i]); } VÝ dô 2: NhËp vµo m¶ng 2 chiÒu. int m, n, i, j; float M[10] [10]; printf("So dong ="); scanf("%d",&n); printf("So cot ="); scanf("%d",&m); for(i= 0; i< n; i++) for(j= 0; j<m; j++) { printf(“M[%d] [%d] = “,i,j); scanf(“%f”, &M[i][j]); } I.1.5. XuÊt d÷ liÖu kiÓu m¶ng: §Ó xuÊt d÷ liÖu m¶ng ta còng ph¶i xuÊt d÷ liÖu cña tõng thµnh phÇn m¶ng VÝ dô: int i, n; float M[10]; for(i = 0; i< n; i++) printf(“a[%d] = %f”,i+1, M[i]); I.2. ThuËt to¸n t×m kiÕm trªn m¶ng ch­a cã thø tù: Do m¶ng ch­a cã thø tù nªn ta ¸p dông ph­¬ng ph¸p t×m kiÕm tuyÕn tÝnh t×m tõ ®Çu m¶ng cho ®Õn cuèi m¶ng. Trong ch­¬ng tr×nh sau ®©y, hµm TimkiÕm sÏ tr¶ vÒ trÞ -1 nÕu kh«ng cã m· sinh viªn trong danh s¸ch ds, ng­îc l¹i hµm sÏ tr¶ vÒ vÞ trÝ cña m· sè ®ã trong danh s¸ch ds. #include #include #include #include #define MAX_SOSV 100 // sè sinh viªn tèi ®a trong danh s¸ch typedef struct sinhvien // ®Þnh nghÜa kiÓu sinhvien Kü thuËt lËp tr×nh 73 { char maso[6]; char hoten[30]; }; typedef struct danhsach_sv // ®Þnh nghÜa kiÓu danhsach_sv { int tssv; sinhvien sv[MAX_SOSV]; } ; void Nhap_ds (struct danhsach_sv *psv) { char sosv[4]; printf("So sinh vien muon nhap :"); gets(sosv); psv->tssv=atoi(sosv); for (int i=0; itssv; i++) { printf("Ma so :"); gets(psv->sv[i].maso); printf("Ho ten :"); gets(psv->sv[i].hoten); } } void Lietke_ds (struct danhsach_sv *psv) { int i=0; clrscr(); printf (" Ma so Ho & ten \n"); while (i tssv) { printf ("%8s %-s\n", psv->sv[i].maso,psv->sv[i].hoten); i++; } getch(); } /* Hµm Timkiem t×m maso trong danhsach *psv */ int Timkiem(danhsach_sv *psv, char maso[]) { int i=0; while ((itssv) && (strcmp(psv->sv[i].maso, maso)!=0)) i++; return (i==psv->tssv ? -1 : i) ; Kü thuËt lËp tr×nh 74 } void main() { struct danhsach_sv ds; char maso[6]; int vitri; Nhap_ds(&ds); // Gäi hµm Nhap_ds víi tham sè lµ ds Lietke_ds(&ds); printf("Ma so sinh vien ban can tim :"); gets(maso); vitri = Timkiem(&ds, maso); if (vitri !=-1) printf("Ho ten cua sinh vien la %s",ds.sv[vitri].hoten); else printf(" Khong co sinh vien voi ma ban nhap vao"); getch(); } II. C¸c thuËt to¸n s¾p xÕp: Trong thùc tÕ cuéc sèng còng nh­ trong lÜnh vùc lËp tr×nh, viÖc qu¶n lü d÷ liÖu th­êng ®ßi hái sù t×m kiÕm c¸c d÷ liÖu cÇn thiÕt; §Ó thuËn tiÖn cho viÖc t×m kiÕm, d÷ liÖu th­êng ®­îc s½p xÕp theo mét thø tù nµo ®ã. Cã rÊt nhiÒu ph­¬ng ph¸p s¾p thø tù, trong bµi gi¶ng nµy ta chØ kh¶o s¸t hai ph­¬ng ph¸p s¾p xÕp lµ Bubble_Sort vµ Quick_Sort. §Ó thuËn tiÖn ta gi¶ sö m¶ng lµ d·y sè cã tèi ®a 100 sè, vµ c¸c thuËt to¸n d­íi ®©y dïng ®Ó s¾p xÕp d·y sè theo thø tù t¨ng dÇn. II.1. S¾p xÕp theo ph­¬ng ph¸p Bubble_Sort (ph­¬ng ph¸p næi bät) - Néi dung : Ta cho i duyÖt d·y a[0], .. ,a[n-1]; nÕu a[i-1] lín h¬n a[i] th× ta ho¸n ®æi (a[i-1],a[i]). LÆp l¹i qu¸ tr×nh duyÖt d·y nµy cho ®Õn khi kh«ng cã x¶y ra viÖc ®æi chç cña hai phÇn tö. VÝ dô: Ta s¾p thø tù d·y sè sau : 26 33 35 29 19 12 32 B­íc 0 1 2 3 4 5 6 26 12 12 12 12 12 12 33 26 19 19 19 19 19 35 33 26 26 26 26 26 29 35 33 29 29 29 29 19 29 35 33 32 32 32 Kü thuËt lËp tr×nh 75 12 19 29 35 33 33 33 32 32 32 32 35 35 35 - Ch­¬ng tr×nh: #include #include int mang[100]; // biÕn toµn côc int size ; void Bubble_Sort(int A[100], int n) { int i,j,temp; for (i=1; i<n; i++) for (j=n-1;j>=i; j--) if (A[j-1] > A[j]) { temp = A[j-1]; A[j-1] = A[j]; A[j] = temp; } } int Nhap_day_so (int A[]) { int i,n; printf("\nSo phan tu cua mang :"); scanf("%d",&n); for (i=0; i<n; i++) { printf ("A[%d] = ",i+1); scanf("%d",&A[i]); } return n; } void Liet_ke (int A[], int n) { int i; printf("\n Gia tri mang da duoc sap : \n"); for (i=0; i<n; i++) printf ("%5d",A[i]); getch(); } void main() { size= Nhap_day_so(mang); Kü thuËt lËp tr×nh 76 Bubble_Sort(mang,size); Liet_ke(mang,size); } Ta nhËn thÊy ph­¬ng ph¸p nµy cã thÓ ®­îc c¶i tiÕn dÔ dµng. NÕu ë lÇn duyÖt d·y nµo ®ã mµ kh«ng cã cã sù ®æi chç gi÷a hai phÇn tö th× d·y ®· cã thø tù vµ gi¶i thuËt kÕt thóc. Trong tr­êng hîp nµy, ta dïng mét cê hiÖu flag ®Ó ghi nhËn ®iÒu nµy, vµ gi¶i thuËt Bubble Sort ®­îc c¶i tiÕn nh­ sau: #define FALSE 0 #define TRUE 1 void Bubble_Sort_Ad(int A[], int n) { int i,temp; unsigned char flag=TRUE; while (flag) { flag = FALSE ; for (i=0; i<n-1; i++) if (A[i] > A[i+1]) { temp = A[i]; A[i] = A[i+1]; A[i+1] = temp; flag=TRUE; } } } II.2. S¾p xÕp theo ph­¬ng ph¸p Quick_Sort II.2.1. Néi dung: Chän mét phÇn tö bÊt kú trong danh s¸ch lµm ®iÓm chèt x, so s¸nh vµ ®æi chç nh÷ng phÇn tö trong danh s¸ch nµy ®Ó t¹o ra 3 phÇn: phÇn cã gi¸ trÞ nhá h¬n x, phÇn cã gi¸ trÞ b»ng x, vµ phÇn cã gi¸ trÞ lín h¬n x. L¹i tiÕp tôc chia 2 phÇn cã gi¸ trÞ nhá h¬n vµ lín h¬n x theo nguyªn t½c nh­ trªn; qu¸ tr×nh chia phÇn sÏ kÕt thóc khi mçi phÇn chØ cßn l¹i mét phÇn tö, lóc nµy ta ®· cã mét danh s¸ch cã thø tù. VÝ dô: XÐt d·y 26 33 35 29 19 12 32  LÇn chia phÇn thø nhÊt : Chän phÇn tö chèt cã khãa lµ 29, ®Æt lµ x 26 33 35 29 19 12 32 i   j Dïng hai biÕn chØ sè i vµ j ®Ó duyÖt tõ hai ®Çu danh s¸ch ®Õn x. NÕu i gÆp Kü thuËt lËp tr×nh 77 phÇn tö lín h¬n hay b»ng x sÏ dõng l¹i, j gÆp phÇn tö nhá h¬n hay b»ng x sÏ dõng l¹i, råi ®æi chç hai phÇn tö nµy; sau ®ã tiÕp tôc duyÖt cho ®Õn khi i>j th× ngõng l¹i. Lóc nµy d·y sÏ cã 3 phÇn kh¸c nhau nh­ h×nh vÏ sau : 26 33 35 29 19 12 32 i j 26 12 35 29 19 33 32 i j 26 12 19 29 35 33 32 ij 26 12 19 29 35 33 32 j i  LÇn chia phÇn thø hai cho d·y con 26 12 19, chän chèt x=12 26 12 19  12 26 19 i j j i KÕt thóc ta sÏ cã hai phÇn : 12 ; 26 19  LÇn chia phÇn thø 3 cho d·y con 26 19, chän chèt x=26 26 19  19 26 KÕt thóc qu¸ tr×nh chia nhá d·y con 26 12 19 i j j i - LÇn chia phÇn thø 4 cho d·y con 35 33 32, chän chèt x= 33 35 33 32  32 33 35  32 33 35 i j ij j i KÕt thóc ta sÏ cã ba phÇn : 32 ; 33 ; 35 §Õn ®©y qu¸ tr×nh chia phÇn kÕt thóc v× tÊt c¶ c¸c phÇn chØ cã mét phÇn tö, lóc nµy ta sÏ cã mét danh s¸ch cã thø tù lµ : 12 19 26 29 32 33 35 II.2.2. Gi¶i thuËt: a. Gi¶i thuËt kh«ng ®Ö quy: - Ta t¹o mét Stack , mçi phÇn tö cña Stack cã 2 thµnh phÇn lµ q, r chøa chØ sè ®Çu vµ chØ sè cuèi cña d·y cÇn s¾p. Ban ®Çu, Stack[0].q = 0 vµ Stack[0].r =n-1 - TiÕn hµnh ph©n ho¹ch d·y sè gåm c¸c sè b¾t ®Çu tõ chØ sè q ®Õn chØ sè r - Sau mçi lÇn chia phÇn, ta kiÓm tra xem phÇn cã gi¸ trÞ nhá h¬n chèt vµ phÇn cã gi¸ trÞ lín h¬n chèt nÕu cã tõ 2 phÇn tö trë lªn th× ®­a vµo Stack. Sau mçi lÇn ph©n ho¹ch, ta l¹i lÊy d·y sè míi tõ Stack ra ph©n ho¹ch tiÕp. Kü thuËt lËp tr×nh 78 - Qu¸ tr×nh cø nh­ thÕ cho tíi khi Stack rçng th× kÕt thóc. * Ch­¬ng tr×nh: #include #include #include #include int mang[100]; int size ; void Quick_Sort(int A[100], int n) { struct Element_Stack // kiÓu phÇn tö trong Stack { int q, r; } ; Element_Stack Stack[50]; // Stack cã tèi ®a 50 phÇn tö int sp=0; // con trá Stack, khëi t¹o sp=0 int i,j,x,q,r,temp; Stack[0].q =0 ; // chØ sè ®Çu cña m¶ng cÇn s¾p Stack[0].r =n-1; // chØ sè cuèi cña m¶ng cÇn s¾p do { // LÊy mét ph©n ho¹ch ra tõ Stack q = Stack[sp].q ; r =Stack[sp].r ; sp--; // Xãa 1 phÇn tö khái Stack do { // Ph©n ®o¹n d·y con a[q] ,..., a[r] i = q; j =r; x = A[(q+r) / 2] ; // LÊy phÇn tö gi÷a cña d·y cÇn s¾p thø tù lµm chèt do { while (A[i] < x) i++; //T×m phÇn tö ®Çu tiªn cã trÞ lín h¬n hay b»ng x while (A[j] > x) j--; //T×m phÇn tö ®Çu tiªn cã trÞ nhá h¬n hay b»ng x if (i<=j) // §æi chç A[i] víi A[j] { temp = A[i]; A[i] =A[j]; A[j] = temp; i++ ; j--; } } while (i<=j); Kü thuËt lËp tr×nh 79 if (i<r) // phÇn thø ba cã tõ 2 phÇn tö trë lªn { // §­a vµo Stack chØ sè ®Çu vµ chØ sè cuèi cña phÇn thø ba sp++; Stack[sp].q=i; Stack[sp].r=r; } r = j ; // ChuÈn bÞ vÞ trÝ ®Ó ph©n ho¹ch phÇn cã gi¸ trÞ nhá h¬n chèt } while (q< r); } while (sp!=-1); // Ket thuc khi Stack rong } int Nhap_day_so (int A[]) /* T¹o d·y n sè ngÉu nhiªn tõ 0 ®Õn 9999 ®­a vµo m¶ng A */ { int i,n; printf("\nSo phan tu cua mang :"); scanf("%d",&n); randomize(); // dïng vµ for (i=0; i<n; i++) A[i]= rand() % 10000; // Ph¸t sinh c¸c sè ngÉu nhiªn tõ 0 ®Õn 9999 return n; } void Liet_ke (char str[],int A[], int n) { int i; printf("\n%s\n",str); for (i=0; i<n; i++) printf ("%5d",A[i]); getch(); } void main() { size= Nhap_day_so(mang); Liet_ke("Day so ngau nhien :",mang,size); Quick_Sort(mang,size); Liet_ke("Gia tri mang da duoc sap :",mang,size); } b. Gi¶i thuËt Quick Sort ®Ö qui: vÒ c¬ chÕ thùc hiÖn th× còng gièng nh­ Kü thuËt lËp tr×nh 80 gi¶i thuËt kh«ng ®Ö qui, nh­ng ta kh«ng kiÓm so¸t Stack mµ ®Ó cho qu¸ tr×nh gäi ®Ö qui tù t¹o ra Stack. * Ch­¬ng tr×nh: void Sort(int A[], int q,int r) { int temp; int i=q; int j=r; int x = A[(q+r) / 2] ; // LÊy phÇn tö gi÷a cña d·y cÇn s¾p thø tù lµm chèt do { // Ph©n ®o¹n d·y con a[q] ,..., a[r] while (A[i] < x) i++; //T×m phÇn tö ®Çu tiªn cã trÞ lín h¬n hay b»ng x while (A[j] > x) j--; //T×m phÇn tö ®Çu tiªn cã trÞ nhá h¬n hay b»ng x if (i<=j) // Doi cho A[i] voi A[j] { temp = A[i]; A[i] =A[j]; A[j] = temp; i++ ; j--; } } while (i<=j); if (q<j) // phÇn thø nhÊt cã tõ 2 phÇn tö trë lªn Sort(A,q,j); if (i<r) // phÇn thø ba cã tõ 2 phÇn tö trë lªn Sort (A,i,r); } void Quick_Sort(int A[], int n) { Sort( A,0,n-1); // Gäi hµm Sort víi phÇn tö ®Çu cã chØ sè 0 ®Õn // phÇn tö cuèi cïng cã chØ sè n-1 } III. T×m kiÕm trªn m¶ng ®· cã thø tù: Gi¶ sö d·y sè cña ta lµ d·y sè ®· cã thø tù t¨ng dÇn, vµ x lµ gi¸ trÞ cÇn t×m. C¸c hµm t×m kiÕm sÏ tr¶ vÒ trÞ -1 nÕu kh«ng cã x trong d·y, ng­îc l¹i c¸c hµm t×m kiÕm sÏ tr¶ vÒ chØ sè cña x trong d·y. III.1. T×m kiÕm nhanh b»ng ph­¬ng ph¸p lÆp: - Néi dung: Do d·y sè ®· cã thø tù t¨ng dÇn, nªn nÕu ta t×m ®­îc phÇn tö ®Çu tiªn cã trÞ võa lín h¬n x th× ta cã thÓ kÕt luËn d·y sè kh«ng chøa trÞ x. V× vËy, ta sÏ rót ng¾n thêi gian t×m kiÕm. Kü thuËt lËp tr×nh 81 - Gi¶i thuËt: int Search(int A[], int n, int x) { int i=0; while (i<n && A[i] < x) i++; return (i<n && A[i]==x ? i : -1) ; } void main() { int so,vitri; size= Nhap_day_so(mang); Quick_Sort(mang,size); Liet_ke("Gia tri mang da duoc sap :",mang,size); printf("\nGia tri muon tim :"); scanf("%d",&so); vitri = Search(mang,size, so); if (vitri !=-1) printf("Vi tri cua so %d trong day = %d",so,vitri); else printf(" Khong co so %d trong day",so); getch(); } III.2. PhÐp t×m kiÕm nhÞ ph©n: - Néi dung:  B­íc 1: Ph¹m vi t×m kiÕm ban ®Çu lµ toµn bé danh s¸ch.  B­íc 2: LÊy phÇn tö chÝnh gi÷a cña ph¹m vi t×m kiÕm (gäi lµ y) so s¸nh víi x. NÕu x=y th× ta ®· t×m thÊy, tr¶ vÒ chØ sè. Gi¶i thuËt kÕt thóc NÕu x < y th× ph¹m vi t×m kiÕm míi lµ c¸c phÇn tö n»m phÝa tr­íc cña y. NÕu x > y th× ph¹m vi t×m kiÕm míi lµ c¸c phÇn tö n»m phÝa sau cña y.  B­íc 3: NÕu cßn tån t¹i ph¹m vi t×m kiÕm th× lÆp l¹i b­íc 2, ng­îc l¹i gi¶i thuËt kÕt thóc víi kÕt qu¶ lµ kh«ng cã x trong d·y sè. - Gi¶i thuËt: int Binary_Search(int A[], int n, int x) { unsigned char found=FALSE; // Gi¶ sö ban ®Çu ta ch­a t×m thÊy x trong d·y // Ph¹m vi ban ®Çu t×m kiÕm lµ tõ k=0  m = n-1 Kü thuËt lËp tr×nh 82 int k=0; int m=n-1; int j; while (k<=m && !found) { j=(k+m) /2; //chØ sè phÇn tö gi÷a if (A[j]==x) found=TRUE; else if (x>A[j]) k=j+1; // Ph¹m vi t×m míi lµ (j+1, m) else m=j-1; // Ph¹m vi t×m míi lµ (k, j-1) } return (found ? j : -1) ; } III.3. PhÐp t×m kiÕm nhÞ ph©n ®Ö qui: - Néi dung: t­¬ng tù nh­ trªn  B­íc 1: Ph¹m vi t×m kiÕm ban ®Çu lµ toµn bé danh s¸ch (k=0m=n-1).  B­íc 2: LÊy phÇn tö chÝnh gi÷a cña ph¹m vi t×m kiÕm (gäi lµ y) so s¸nh víi x. NÕu x=y th× ta ®· t×m thÊy, tr¶ vÒ chØ sè. Gi¶i thuËt kÕt thóc NÕu x < y th× ph¹m vi t×m kiÕm míi lµ c¸c phÇn tö n»m phÝa tr­íc cña y, nªn ta gäi ®Ö qui víi ph¹m vi míi lµ (k,j-1) NÕu x > y th× ph¹m vi t×m kiÕm míi lµ c¸c phÇn tö n»m phÝa sau cña y, nªn ta gäi ®Ö qui víi ph¹m vi míi lµ (j+1,m )  §iÒu kiÖn dõng: x=y hoÆc k > m. - Gi¶i thuËt: int Binary_Search2(int A[], int k,int m, int x) { int j=(k+m) /2; if (k>m) return -1 ; else if (A[j]==x) return j ; else Binary_Search2(A, (A[j] x ?j-1:m),x); } Kü thuËt lËp tr×nh 83 Bµi tËp: 1. Cho mét d·y n sè thùc A : a) T×m phÇn tö nhá nhÊt cña d·y sè A b) T×m phÇn tö lín nhÊt cña d·y sè A c) TÝnh gi¸ trÞ trung b×nh cña d·y sè A. 2. HiÖn ®ang l­u hµnh c¸c tê giÊy b¹c 50000®, 20000®, 10000®, 5000®, 2000®, 1000®, 500®, 200®, 100®. NÕu cã x ®ång, hái r»ng nªn chän c¸c tê giÊy b¹c nµo ®Ó sè l­îng c¸c tê giÊy b¹c lµ Ýt nhÊt. 3. ViÕt ch­¬ng tr×nh nhËp mét ma trËn sè nguyªn cã kÝch th­íc M x N. In ra: - Tæng c¸c phÇn tö cña ma trËn - Sã c¸c phÇn tö d­¬ng, phÇn tö ©m, phÇn tö 0 cña ma trËn - PhÇn tö lín nhÊt, nhá nhÊt cña ma trËn - C¸c phÇn tö trªn ®­êng chÐo chÝnh cña ma trËn (víi M = N ) - Tæng c¸c phÇn tö trªn ®­êng chÐo chÝnh cña ma trËn (víi M = N ) 4. Cho 2 ma trËn vu«ng A(n,n) vµ B (n,n) : - TÝnh ma trËn tæng C = A+ B, biÕt C[i,j] = A[i,j] + B[i,j] , i,j [1,m] - TÝnh ma trËn tÝch D = A * B, biÕt D [i,j] = A i k B k j k n [ , ]* [ , ]   1 ; i, j = 1..n 5. T¹o mét menu thùc hiÖn c¸c c«ng viÖc sau: a. NhËp danh s¸ch cã kiÓu häc viªn vµo mét m¶ng, mçi häc viªn cã c¸c th«ng tin sau: maso (int), hoten (chuçi tèi ®a 30 ký tù), ph¸i(NAM/NU), ®iÓm (float), h¹ng (unsigned char). Qu¸ tr×nh nhËp sÏ dõng l¹i khi m· sè nhËp vµo lµ 0. b. LiÖt kª danh s¸ch häc viªn ra mµn h×nh theo d¹ng sau: M· sè Hä vµ tªn Ph¸i §iÓm H¹ng c. T×m kiÕm mét häc viªn trong danh s¸ch theo m· sè, vµ in ra c¸c th«ng tin cßn l¹i cña häc viªn ®ã. d. S¾p xÕp danh s¸ch häc viªn theo ®iÓm t¨ng dÇn. e. XÕp h¹ng danh s¸ch häc viªn theo qui t¾c cïng ®iÓm th× cïng h¹ng, h¹ng cña häc viªn sau b»ng h¹ng cña nhãm häc viªn tr­íc céng sè ng­êi cña nhãm häc viªn tr­íc cïng ®iÓm. f. Gi¶ sö danh s¸ch häc viªn ®· cã thø tù t¨ng dÇn theo ®iÓm; NhËp thªm 1 häc viªn sao cho sau khi nhËp th× danh s¸ch vÉn cßn cã thø tù. g. CËp nhËt söa ®æi c¸c mÉu tin theo m· sè (NhËp m· sè, sau ®ã hiÖu chØnh Kü thuËt lËp tr×nh 84 l¹i hoten, phai, ®iÓm). h. Lo¹i bá 1 häc viªn ra khái danh s¸ch dùa vµo m· sè. 6. a) ViÕt ch­¬ng tr×nh t¹o ngÉu nhiªn mét d·y sè 20000 sè nguyªn cã gi¸ trÞ tõ 0 ®Õn 9999. b) §Õm sè lÇn so s¸nh cña 2 gi¶i thuËt t×m kiÕm tuÇn tù (trªn d·y sè ch­a cã thø tù) vµ t×m kiÕm nhÞ ph©n (trªn d·y sè ®· ®­îc s¾p thø tù). c) Trong tr­êng hîp d·y sè trªn lµ 200000 sè nguyªn ph©n biÖt kh¸c nhau trong miÒn gi¸ trÞ [1..300000] th× ta tèi ­u gi¶i thuËt s¾p xÕp vÒ mÆt kh«ng gian vµ thêi gian nh­ thÕ nµo? Cho biÕt thêi gian thùc thi cña gi¶i thuËt Quick Sort vµ gi¶i thuËt b¹n cµi ®Æt. 7. Cho biÕt thêi gian thùc thi cña 2 gi¶i thuËt Bubble Sort vµ Quick Sort trªn d·y sè cã sè phÇn tö kh¸ lín. 8. Gi¶ sö ta ®· cã 1 d·y sè thùc A t¨ng dÇn. ViÕt gi¶i thuËt thªm 1 sè thùc x vµo d·y A sao cho sau khi thªm x th× d·y vÉn t¨ng dÇn ? 9. ViÕt hµm xãa tÊt c¶ c¸c phÇn tö cã trÞ b»ng x trong d·y sè A. 10. ViÕt ch­¬ng tr×nh tÝnh ®iÓm cña mét líp: - NhËp c¸c th«ng tin sau cho mçi häc viªn : hoten, namsinh, trung b×nh HK1, trung b×nh HK2 - In ra danh s¸ch c¸c häc viªn cña líp theo thø tù gi¶m dÇn cña §TB toµn n¨m TB toµn n¨m = (TB HK1 + TB HK2)/2 theo mÉu sau: DANH S¸CH §iÓM LíP ...... STT Hä & Tªn TB HK1 TB HK2 TB toµn n¨m H¹ng 1 2 3 L­u ý:- C¸c häc viªn cïng §TB th× cïng h¹ng - In 17 häc viªn trªn mét trang mµn h×nh 11. Cho 2 d·y sè A cã n phÇn tö vµ B cã m phÇn tö víi thø tù t¨ng dÇn. H·y trén 2 d·y sè trªn thµnh 1 d·y míi C sao cho sau khi trén th× C còng t¨ng dÇn. Kü thuËt lËp tr×nh 85 CH¦¥NG 4 CON TRá (POINTER) I. §ÞNH NGHÜA Con trá lµ mét kiÓu d÷ liÖu dïng ®Ó chøa ®Þa chØ. BiÕn con trá lµ mét biÕn chøa ®Þa chØ cña mét thùc thÓ nµo ®ã, thùc thÓ ®ã lµ biÕn hoÆc lµ hµm. Con trá th­êng ®­îc dïng ®Ó: - Tr¶ vÒ nhiÒu trÞ tõ hµm qua c¬ chÕ truyÒn theo tham sè theo ®Þa chØ trong hµm (tham sè h×nh thøc biÕn). - T¹o c¸c cÊu tróc d÷ liÖu phøc t¹p nh­ danh s¸ch liªn kÕt vµ c©y nhÞ ph©n. - TruyÒn m¶ng vµ chuçi gi÷a c¸c hµm kh¸ thuËn lîi. I.1. Khai b¸o: Khai b¸o biÕn pi lµ con trá trá ®Õn mét sè nguyªn. int *pi; Lóc nµy, pi chiÕm 2 bytes chøa ®Þa chØ cña sè nguyªn mµ nã ®ang chØ ®Õn, ®ång thêi tr×nh biªn dÞch cña C còng biÕt pi ®ang chØ ®Õn mét sè nguyªn (do khai b¸o). §Ó ®­a mét gi¸ trÞ nguyªn vµo vïng nhí mµ pi ®ang trá ®Õn, ta dïng lÖnh: *pi = 1; VÝ dô: void main() { int x=4, y=10; int *px, *py ; // px, py lµ c¸c biÕn con trá px = &x ; // ®­a ®Þa chØ cña x,y vµo px vµ py py = &y; *px = *px + *py; // t¨ng gi¸ trÞ cña vïng nhí mµ px ®ang trá tíi // thªm y , t­¬ng ®­¬ng víi x = x+y } Minh häa ch­¬ng tr×nh trªn trong bé nhí: BiÕn int x=4, y=10; int *px, *py; px=&x; py=&y; *px = *px + *py; x 950 4 4 14 951 y 952 10 10 10 953 px 950 950 py 952 952 Kü thuËt lËp tr×nh 86 H×nh 7.1. C¬ chÕ truy xuÊt gi¸ trÞ qua biÕn con trá. Tæng qu¸t: KiÓu *biÕn; I.2. TruyÒn ®Þa chØ cho hµm: Trong 1 sè tr­êng hîp ta muèn gëi ®Þa chØ cña 1 biÕn x cho hµm. Nhê vµo c¬ chÕ truyÒn theo ®Þa chØ nµy mµ hµm cã thÓ tr¶ vÒ nhiÒu gi¸ trÞ cho ch­¬ng tr×nh gäi. VÝ dô: Hµm ho¸n ®æi gi¸ trÞ cña 2 biÕn x, y void hoandoi (int *a, int *b) { int tam; tam = *a; *a = *b; *b = tam; } void main() { int x,y; printf ("x, y = "); scanf ("%d %d", &x, &y); giaohoan(&x, &y); // TruyÒn ®Þa chØ cña 2 biÕn x,y cho hµm hoandoi } II C¸c phÐp to¸n trªn biÕn con trá: II.1. To¸n tö ®Þa chØ &: NÕu x lµ biÕn th«ng th­êng, &x sÏ lµ ®Þa chØ cña biÕn x VÝ dô: float x, *pf; x = 50; pf = x; // sai v× pf lµ biÕn con trá nªn ta viÕt pf = & x; x = pf; // sai ; ta viÕt x = *pf; { lÊy néi dung cña pf } II.2. To¸n tö néi dung * : NÕu p lµ pointer th× *p lµ néi dung cña nã. VÝ dô: int x,y, *p; x = 50; p = &x; // p chøa ®Þa chØ cña vïng nhí x y = *p; // y= *p = 50 v× p chøa ®Þa chØ cña vïng nhí x VÝ dô: a =2; p = & a; b = (*p) + + + 3; // b =5, *p = 3, a= 3. ( v× p trá tíi ®Þa chØ a nªn *p t¨ng th× a t¨ng) Tãm l¹i: *x lµ biÕn mµ x gi÷ ®Þa chØ &x lµ ®Þa chØ cña x nÕu x lµ biÕn th«ng th­êng Kü thuËt lËp tr×nh 87 II.3. PhÐp céng trõ biÕn con trá víi mét sè nguyªn: NÕu p lµ biÕn pointer th× p+n lµ ®Þa chØ cña mét biÕn míi c¸ch nã n biÕn theo chiÒu t¨ng, cßn p-n th× ng­îc l¹i. Chó ý: - PhÐp céng con trá víi mét sè nguyªn chØ ®­îc ¸p dông trªn mét d·y biÕn cïng kiÓu - Kh«ng ®­îc céng 2 pointer víi nhau - Kh«ng ®­îc nh©n, chia, lÊy d­ biÕn con trá víi bÊt kú sè nµo VÝ dô: Gi¶ sö ta cã m¶ng nums[]= {10,20,30,40,50}. ViÖc tham kh¶o tíi nums[i] thùc chÊt lµ dïng d¹ng ký hiÖu con trá, v× khi biªn dÞch, tr×nh biªn dÞch sÏ chuyÓn ®æi ký hiÖu m¶ng thµnh ký hiÖu con trá. void main() { static int nums [] = {10,20,30,40,50}; for (int i =0; i<5; i++) printf (“%d\n”, *(nums + i)); } L­u ý: *(nums+i) t­¬ng ®­¬ng víi nums[i] II.4. PhÐp g¸n vµ phÐp so s¸nh: - PhÐp g¸n: c¸c biÕn con trá cã thÓ g¸n cho nhau víi ®iÒu kiÖn ph¶i cïng kiÓu VÝ dô: int *p1, *p2; *p1 = 10; p2 = p1; // lóc nµy *p2 = 10; - PhÐp so s¸nh: ta cã thÓ so s¸nh 2 biÕn con trá xem cã cïng ®Þa chØ hay kh«ng, ®­¬ng nhiªn 2 biÕn con trá ®ã ph¶i cïng kiÓu víi nhau. II.5. Sù chuyÓn kiÓu: Có ph¸p: ( KiÓu) *tªnbiÕn VÝ dô: int *p1, num ; float *p2; num =5; p1 = # *p2 = (float ) *p1; // * p2 = 5.0 VÝ dô: int num, *p, n; char c; p = # Kü thuËt lËp tr×nh 88 *p = 97; // num =97 n = *p; // n=97 c = (char) *p; // c = ‘a’ Chó ý: §Þa chØ cña mét biÕn ®­îc xem nh­ mét con trá h»ng, do ®ã nã kh«ng ®­îc phÐp g¸n, t¨ng hoÆc gi¶m. VÝ dô: int num, *p, n; p = & num; p ++; // ®óng ( & num) ++; // sai con trá h»ng II.6. Khai b¸o mét con trá h»ng vµ con trá chØ ®Õn ®èi t­îng h»ng: a. Con trá h»ng: KiÓu * const p = gi¸ trÞ; b. Con trá chØ ®Õn ®èi t­îng h»ng: KiÓu const *p = gi¸ trÞ h»ng; hoÆc Const kiÓu *p = gi¸ trÞ h»ng; VÝ dô: char *const p2 = “ABCD” const char *p1= “ABCD” p2 + + ; // sai p1 + + ; // ®óng; *p1= ‘B’ ; p1 = "BCD" III. Sù t­¬ng quan gi÷a con trá vµ m¶ng VÝ dô: Ta cã m¶ng A nh­ sau: int A[10] , *p; th× A = &A[0] NÕu p = A th× ®Ó truy xuÊt tíi phÇn tö thø i cña m¶ng A, ta cã c¸c c¸ch sau: A[i]  *(A + i)  *( p + i) & A[i]  (A + i)  (p +i ) VÝ dô: NhËp m¶ng A: int A[10] , *p, i; p = A; for (i = 0; i< 9; i++) scanf (“%d”, p+i ); XuÊt m¶ng A: for (i = 0; i< 9;i++) printf (“%d”, *(p+i)); Kü thuËt lËp tr×nh 89 VÝ dô: S¾p xÕp m¶ng b»ng c¸ch tham kh¶o con trá. const n =10 ; int a[n], *p; void main() { int j,temp; clrscr(); p=a; printf("\Nhap day so A :\n"); for (int i=0; i<n; i++) { printf("A[%d] = ",i+1); scanf("%d",p+i); } // Sap xep mang A theo giai thuat Bubble Sort for ( i=1; i&l