Nội dung

1 Kü thuË t lË p tr× nh 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 Khèi më ®Ç u hoÆ c kÕ t thóc Khèi vµ o ra Ký hiÖ u ý nghÜ a Dïng më ®Ç u hoÆ c kÕ t thóc ch­¬ng tr× nh §­a sè liÖ u vµ o hoÆ c in kÕ t qu¶ 2 Kü thuË t lË p tr× nh 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 Dïng ®Ó ph© n nh¸ nh ch­¬ng tr× nh Khèi tÝ nh to¸ n Khèi ®iÒ u kiÖ n Dïng ®Ó gäi ch­¬ng tr× nh con ChØ h­íng truyÒ n th«ng tin, liª n hÖ c¸ c khèi Ch­¬ng tr× nh con Mòi tª n 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 Begin Nhaäp (x,y) A = x2 + y2 Xuaát (A) End VÝ dô 2 : TÝ nh S = Ax + By + C x +y 2 2 ; biÕ t A,B,C,x,y Begin Nhaä p (A, B, C, x,y) S = (Ax + By + C) / SQRT (x*x + y*y) Xuaát S End 3 Kü thuË t lË p tr× nh 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 Begin Nhaäp (a, b, c) S a>b Max = b Ñ Max = a S Max < c Ñ Max = c Xuaát (Max) End VÝ dô 2: Gi¶ i ph­¬ng tr× nh bË c nhÊ t Ax+B =0 víi c¸ c nghiÖ m thùc. Begin Nhaäp (a, b) a=0 S Xuaát (-b/a) Ñ b=0 S Ñ Xuaát (‘PTVÑ’) End Xuaát (‘PTVN’) 4 Kü thuË t lË p tr× nh VÝ dô 3 : Gi¶ i ph­¬ng tr× nh bË c hai Ax2+Bx+C =0 víi c¸ c nghiÖ m thùc. Begin Nhaäp (a, b, c) Ñ a=0 PTB1 (b, c) S Delta = b*b - 4*a*c Ñ Delta < 0 Xuaát (‘PTVN’) S Ñ Delta = 0 Xuaát (-b / (2*a)) S Xuaát (‘X1= ’,(-b + SQRT(Delta)) / (2*a)) Xuaát (‘X2= ’,(-b - SQRT(Delta)) / (2*a)) End 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 = giaù trò ban ñaàu Leä nh S; Taê ng i Ñ i <= n S víi n lµ gi¸ trÞ kÕ t thóc. 5 Kü thuË t lË p tr× nh n VÝ dô 4: TÝ nhS= ∑ xi , víi c¸ c xi do ta nhË p vµ o. i =1 Begin Nhaäp (n) i=1 S=0 Nhaäp (xi) i = i+1 S = S+xi Ñ i <= n S Xuaát (S) End 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) 6 Kü thuË t lË p tr× nh - 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) Döõ lieäu Chöông trình nguoàn Trình bieâ n dòch Chöông trình ñích Maùy tính thöïc hieän Keát quaû 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 ®ã. Chöông trình nguoàn Chöông trình thoâ ng dòch Keát quaû Döõ lieäu H× nh I.2. Ch­¬ng tr× nh thùc thi theo c¬ chÕ dÞch cña tr× nh th«ng dÞch 7 Kü thuË t lË p tr× nh 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] 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. 10 Kü thuË t lË p tr× nh - Nh÷ng ký tù ®Æc biÖ t : Ký tù T¸c dông \n \t \b \r \f \a \\ \’ \’’ \xdd \ddd M· ASCII Xuèng hµ ng míi Tab Xãa ký tù bª n tr¸ i Con trá trë vÒ ®Ç u hµ ng Sang trang Ph¸ t tiÕ ng cßi XuÊ t dÊ u chÐo ng­îc XuÊ t dÊ u nh¸ y ®¬n ‘ XuÊ t dÊ u nh¸ y kÐp “ XuÊ t ký tù cã m∙ ASCII d¹ ng Hex lµ dd XuÊ t ký tù cã m∙ ASCII d¹ ng Dec lµ ddd Ký tù NULL \0 - Chuçi ®Þnh d¹ng : % [ flag][width][.prec][FNhl] type 10 9 8 13 12 7 92 39 34 0 Type : ®Þnh kiÓ u cña tham sè theo sau chuçi-®Þnhd¹ ng ®Ó lÊ y gi¸ trÞ ra Type d,i u o x X f e E g,G c s % ý nghÜ a Sè nguyª n c¬ sè 10 Sè nguyª n c¬ sè 10 kh«ng dÊ u Sè nguyª n c¬ sè 8 Sè nguyª n c¬ sè 16, ch÷ th­êng(a,b,...,f) Sè nguyª n c¬ sè 16, ch÷ in (A,B,...,F) Sè thùc d¹ ng [-]dddd.ddd... Sè thùc d¹ ng [-]d.ddd e[+/-]ddd Sè thùc d¹ ng [-]d.ddd E[+/-]ddd Sè thùc d¹ ng e(E) hay f tïy theo ®é chÝ nh x¸ c Ký tù Chuçi ký tù tË n cïng b» ng ‘\0’ DÊ u % cÇ n in