intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Kỹ thuật lập trình đơn thể

Chia sẻ: Diemanh Diemanh | Ngày: | Loại File: DOC | Số trang:21

Thêm vào BST
Báo xấu
260
lượt xem 54
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đơn thể (hay Module) là một đoạn chương trình được viết theo một cấu trúc nào đó, giải quyết một vấn đề tương đối độc lập của bài toán.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Kỹ thuật lập trình đơn thể

  1. Ch ¬ng II I. Kü thuËt lËp tr×nh ®¬n thÓ I. §Þnh nghÜa vµ sö dông ®¬n thÓ 1. Kh¸i niÖm – ph©n lo¹i Kh¸i niÖm: §¬n thÓ (hay Module) lµ mét ®o¹n ch¬ng tr×nh ®îc viÕt theo mét cÊu tróc nµo ®ã, gi¶i quyÕt mét vÊn ®Ò t ¬ng ®èi ®éc lËp cña bµi to¸n. Khi viÕt mét ch¬ng tr×nh, chóng ta cã thÓ triÓn khai theo hai c¸ch: C¸ch 1: Toµn bé c¸c lÖnh cña ch¬ng tr×nh ®îc viÕt trong hµm main(). C¸c lÖnh ®îc viÕt theo tr×nh tù ®Ó gi¶i quyÕt bµi to¸n ®Æt ra. C¸ch 2: Ch¬ng tr×nh ®îc t¹o thµnh tõ nhiÒu ®¬n thÓ kh¸c nhau. C¸c ®¬n thÓ thùc hiÖn nh÷ng nhiÖm vô t ¬ng ®èi ®éc lËp vµ ®îc “l¾p ghÐp” l¹i thµnh ch¬ng tr×nh th«ng qua nh÷ng lêi gäi ®¬n thÓ trong hµm main(). u nh îc ®iÓm: - Víi c¸ch 1: sÏ thÝch hîp khi viÕt nh÷ng ch¬ng tr×nh cã kÝch th íc nhá. Toµn bé thuËt to¸n ®îc thÓ hiÖn trong mét ®o¹n m· tõ trªn xuèng díi. Tuy nhiªn, c¸ch nµy kh«ng phï hîp víi c¸c ch¬ng tr×nh lín do: + KÝch th íc ch¬ng tr×nh cång kÒnh, khã kiÓm so¸t, chØnh söa. + C¸c ®o¹n m· cã thÓ lÆp ®i lÆp l¹i, ch¬ng tr×nh dµi kh«ng cÇn thiÕt. - Víi c¸ch 2: Ch¬ng tr×nh ®îc chia nhá thµnh c¸c ®¬n thÓ kh¾c phôc ®îc hai nhîc ®iÓm c¬ b¶n trªn. §Æc biÖt phï hîp víi c¸c ch¬ng tr×nh cã kÝch th íc lín.
  2. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh Trong C++, ta cã hai lo¹i ®¬n thÓ sau: [1]. C¸c líp ®èi tîng: Ch¬ng tr×nh bao gåm mét sè ®o¹n m· m« t¶ c¸c líp c¸c ®èi t îng nµo ®ã sÏ sö dông trong ch¬ng tr×nh chÝnh. Lo¹i ®¬n thÓ nµy ®îc nghiªn cøu trong néi dung m«n häc “LËp tr×nh híng ®èi t îng”. [2]. C¸c hµm: Ch¬ng tr×nh ®îc cÊu t¹o tõ c¸c hµm. Mçi hµm thùc thi mét nhiÖm vô t ¬ng ®èi ®éc lËp, trong ®ã cã mét hµm main ®ãng vai trß nh ch¬ng tr×nh chÝnh ®Ó sö dông c¸c hµm kh¸c. Trong ph¹m vi m«n häc, ta chØ xem xÐt c¸c ®¬n thÓ díi d¹ng c¸c hµm. 2. C¸c ®Æc tr ng cña hµm Mét hµm trong C++ cã c¸c ®Æc tr ng sau: [1]. Tªn hµm: do ngêi lËp tr×nh tù ®Æt vµ cã nh÷ng ®Æc ®iÓm sau: + Tªn hµm th êng mang tÝnh ®¹i diÖn cho c«ng viÖc mµ hµm sÏ ®¶m nhiÖm. + Tªn hµm ®îc ®Æt tuú ý nhng tu©n theo quy íc ®Æt tªn trong C++. [2]. KiÓu gi¸ trÞ tr¶ vÒ cña hµm: NÕu hµm tr¶ vÒ mét gi¸ trÞ th× gi¸ trÞ ®ã ph¶i thuéc mét kiÓu d÷ liÖu nµo ®ã; ta gäi lµ kiÓu gi¸ trÞ tr¶ vÒ cña hµm. KiÓu gi¸ trÞ tr¶ vÒ cña hµm cã thÓ lµ c¸c kiÓu d÷ liÖu chuÈn. [3]. C¸c ®èi cña hµm: NÕu hµm sö dông c¸c ®èi th× c¸c ®èi ph¶i thuéc mét kiÓu d÷ liÖu nµo ®ã. Khi thiÕt lËp mét hµm, ta cÇn chØ ra danh s¸ch c¸c ®èi cña hµm vµ kiÓu d÷ liÖu cña mçi ®èi. Biªn so¹n: NguyÔn M ¹nh Cêng Trang 2
  3. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh [4]. Th©n hµm: lµ néi dung chÝnh cña hµm, chøa toµn bé c¸c lÖnh cña hµm. 3. Ph©n lo¹i hµm Tïy theo nguån gèc cña hµm ta ph©n ra: - C¸c hµm cã s½n: Lµ c¸c hµm chøa trong c¸c th viÖn cña C++, ®· ®îc ®Þnh nghÜa tõ tr íc. C¸c hµm nµy ®îc ®Æt trong c¸c th viÖn .h. Ngêi lËp tr×nh chØ viÖc sö dông chóng th«ng qua c¸c chØ thÞ: #include mµ kh«ng cÇn ®Þnh nghÜa hµm. VD: C¸c hµm sqrt(); sin(); cos(); gets(); puts() .v.v… - C¸c hµm tù ®Þnh nghÜa: Lµ c¸c hµm mµ tr íc khi dïng chóng ta ph¶i ®Þnh nghÜa chóng. C¸c hµm nµy còng cã thÓ ®îc tËp hîp l¹i trong mét file .h ®Ó dïng nh mét th viÖn cã s½n. Tuú theo kiÓu cña gi¸ trÞ tr¶ vÒ cña hµm ta ph©n ra: - Hµm kh«ng cã gi¸ trÞ tr¶ vÒ: Lµ hµm chØ cã chøc n¨ng thùc hiÖn mét c«ng viÖc nµo ®ã mµ ta kh«ng quan t©m tíi gi¸ trÞ tr¶ vÒ cña hµm. C¸c gi¸ trÞ tÝnh to¸n ®îc trong th©n hµm th êng ®îc kÕt xuÊt lªn mµn h×nh. - Hµm cã gi¸ trÞ tr¶ vÒ: Ngoµi viÖc thùc hiÖn mét c«ng viÖc nµo ®ã, hµm nµy cßn tr¶ vÒ mét gi¸ trÞ th«ng qua tªn hµm. Gi¸ trÞ nµy cã thÓ ®îc dïng trong nh÷ng ®o¹n tr×nh tiÕp theo sau lêi gäi hµm. NhËn xÐt: - Trong pascal, ta cã hai lo¹i ch¬ng tr×nh con: thñ tôc (procedure) vµ hµm (function). Trong C++, chóng ta cã duy nhÊt mét lo¹i “ch¬ng tr×nh con” (mµ ta gäi lµ ®¬n thÓ), ®ã lµ hµm. Biªn so¹n: NguyÔn M ¹nh Cêng Trang 3
  4. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh - Mét ch¬ng tr×nh trong C++ ®îc cÊu t¹o tõ c¸c hµm, trong ®ã hµm main lµ hµm b¾t buéc ph¶i cã, ®ãng vai trß nh ch¬ng tr×nh chÝnh. 4. §Þnh nghÜa vµ sö dông hµm a. CÊu tróc mét hµm: Mét hµm th êng cã cÊu tróc nh sau: - Hµm kh«ng cã gi¸ trÞ tr¶ vÒ (hµm void): { //C¸c lÖnh trong th©n hµm; } - Hµm cã gi¸ trÞ tr¶ vÒ: void { //C¸c lÖnh trong th©n hµm; } Trong ®ã: - : lµ kiÓu gi¸ trÞ tr¶ vÒ cña hµm. NÕu hµm kh«ng cã gi¸ trÞ tr¶ vÒ, ta dïng kiÓu void. Ngîc l¹i, ta th êng sö dông c¸c kiÓu chuÈn nh int, float, double, char… - : do ngêi dïng tù ®Þnh nghÜa. - [ ] : liÖt kª danh s¸ch c¸c ®èi cña hµm vµ kiÓu d÷ liÖu cña ®èi (nÕu hµm cã ®èi). Biªn so¹n: NguyÔn M ¹nh Cêng Trang 4
  5. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh VD1: hµm tÝnh n! ®îc viÕt theo 2 d¹ng: cã vµ kh«ng cã gi¸ trÞ C¸ch 1: Hµm cã gi¸ trÞ tr¶ C¸ch 2: Hµm kh«ng cã gi¸ trÞ long GT(int n) void GT(int n) { { long kq=1; long kq=1; for (int i=1; i
  6. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh Mét vÊn ®Ò ®Æt ra lµ: khi nµo th× viÕt hµm díi d¹ng cã gi¸ trÞ tr¶ vÒ, khi nµo th× viÕt hµm kh«ng cã gi¸ trÞ tr¶ vÒ? Nãi chung, tuú thuéc vµo bµi to¸n cô thÓ ta cã thÓ quyÕt ®Þnh ®iÒu nµy, tuy nhiªn: - NÕu ta chØ dïng hµm ®Ó thùc thi mét c«ng viÖc nµo ®ã mµ kÕt qu¶ cña nã chØ cÇn ®îc kÕt xuÊt ra mµn h×nh lµ ®ñ th× hµm th êng ®îc viÕt díi d¹ng kh«ng cã gi¸ trÞ tr¶ vÒ. - NÕu kÕt qu¶ tr¶ vÒ cña hµm cã thÓ ®îc dïng trong nh÷ng c«ng viÖc tiÕp theo (tøc ta cßn sö dông chóng sau nµy) th× hµm th êng ®îc viÕt díi d¹ng cã gi¸ trÞ tr¶ vÒ. b. C¸ch tæ chøc c¸c hµm C¸ch 1: C¸c hµm ®Æt trong cïng mét tÖp víi hµm main(). Ch¬ng tr×nh ngoµi hµm main() cßn cã c¸c hµm kh¸c th× ®îc viÕt theo cÊu tróc sau: D¹ng 1: Hµm ®Æt tr íc hµm main() D¹ng 2: Hµm ®Æt sau hµm #include… #include… …. …. //C¸c hµm ®Æt ë ®©y //Nguyªn mÉu cña hµm ®Æt ë ®©y … … void main() void main() { { Th©n hµm main; Th©n hµm main; } //C¸c hµm ®Æt ë ®©y main() Biªn so¹n: NguyÔn M ¹nh Cêng Trang 6
  7. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh C¸ch 2: C¸c hµm ®Æt trong th viªn: B1: ViÕt c¸c hµm (trõ hµm main()) trong mét file sau ®ã l u díi ®Þnh d¹ng .h. File nµy th êng ®îc gäi lµ file th viÖn. (®Ó thuËn tiÖn cho viÖc so¸t lçi, tèt nhÊt tr íc tiªn nªn tæ chøc c¸c hµm nh c¸ch 1, sau ®ã di chuyÓn toµn bé c¸c hµm (trõ hµm main() sang mét file .h vµ l u l¹i) B2: Më mét tÖp míi vµ viÕt hµm main() trong mét tÖp nµy. §Ó hµm main() cã thÓ sö dông c¸c hµm viÕt trong file th viÖn ®· t¹o trong B1, cÇn thªm chØ thÞ: #include
  8. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh #include #include
  9. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh - C¸c lÖnh cã thÓ ®îc dïng ®éc lËp mµ kh«ng thÓ dïng lÖnh nµy bªn trong lÖnh kia. Ghi nhí: - C¸c hµm cã gi¸ trÞ tr¶ vÒ dïng nh mét biÕn. - C¸c hµm kh«ng cã gi¸ trÞ tr¶ vª dïng nh mét lÖnh. Mét sè nguyªn t¾c khi dïng hµm: - NÕu hµm ®îc ®Þnh nghÜa cã ®èi sè th× khi gäi hµm ta ph¶i truyÒn ®Çy ®ñ c¸c tham sè (hay ®èi sè thùc sù) cho hµm. - C¸c tham sè ph¶i cã kiÓu trïng víi kiÓu cña ®èi sè t ¬ng øng. - NÕu hµm kh«ng cã ®èi sè th× lêi gäi hµm vÉn ph¶i sö dông dÊu () kÌm tªn hµm: . 5. Ph¹m vi cña biÕn Theo ph¹m vi ho¹t ®éng cña biÕn, ta chia ra: - BiÕn toµn côc: lµ c¸c biÕn cã ph¹m vi ho¹t ®éng trong toµn bé ch¬ng tr×nh, kÓ tõ vÞ trÝ khai b¸o biÕn. VÞ trÝ khai b¸o biÕn toµn côc n»m ngoµi c¸c hµm (kÓ c¶ hµm main). NÕu ch¬ng tr×nh ®îc viÕt trªn nhiÒu tÖp, ®Ó ph¹m vi ho¹t ®éng cña biÕn bao gåm c¶ c¸c tÖp kh¸c, ta cÇn thªm chØ danh extern vµo tr íc khai b¸o biÕn. - BiÕn côc bé: lµ c¸c biÕn cã ph¹m vi ho¹t ®éng bÞ h¹n chÕ: NÕu biÕn ®îc khai b¸o trong th©n mét khèi nµo ®ã sÏ cã ph¹m vi ho¹t ®éng chØ trong khèi, kÓ c¶ c¸c khèi con n»m bªn trong khèi ®ã. + KÕt thóc khèi, biÕn côc bé sÏ ®îc gi¶i phãng. Biªn so¹n: NguyÔn M ¹nh Cêng Trang 9
  10. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh + Muèn biÕn nµy tån t¹i trong suèt thêi gian ch¬ng tr×nh lµm viÖc, ta cÇn thªm tõ khãa static tr íc khai b¸o biÕn ®Ó khai b¸o biÕn d- íi d¹ng biÕn tÜnh. VD1: XÐt vÝ dô sau: int x; void Ham(int a) { cout
  11. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh NÕu hµm cã ®èi sè (tham sè h×nh thøc), khi gäi hµm ta ph¶i truyÒn c¸c tham sè t ¬ng øng cho hµm. C¸c tham sè cã thÓ lµ c¸c biÕn hoÆc c¸c h»ng gi¸ trÞ. Cã hai c¸ch truyÒn tham sè: [1]. TruyÒn d¹ng tham chiÕu: Khi truyÒn tham sè díi d¹ng tham chiÕu, tham sè lµ c¸c biÕn vµ tham sè sÏ ®îc truy cËp trùc tiÕp. Nh vËy, c¸c tham sè ®îc truyÒn vµo mét hµm th× sau khi ra khái hµm, gi¸ tÞ cña chóng cã thÓ bÞ thay ®æi. [2]. TruyÒn d¹ng tham trÞ: Khi truyÒn tham sè díi d¹ng tham trÞ, tham sè sÏ kh«ng ®îc truy cËp trùc tiÕp. Hµm sÏ cÊp ph¸t mét vïng nhí míi vµ sao chÐp gi¸ trÞ cña tham sè vµo ®ã. C¸c lÖnh trong th©n hµm sÏ thao t¸c trªn vïng nhí míi nµy. Nh vËy, mét tham sè khi truyÒn vµo mét hµm díi d¹ng tham trÞ sÏ kh«ng bÞ tham ®æi gi¸ trÞ cña nã khi ra khái hµm. BiÕn Vïng BiÕn Vïng nhí cña nhí cña Vïng nhí míi Gäi hµm Thùc t hi Gäi hµm Thùc t hi hµm hµm a) truyÒn tham chiÕu b) TruyÒn tham trÞ 2. TruyÒn tham sè NÕu ch¬ng tr×nh viÕt trong c¸c file cã phÇn më réng .h, ta cã duy nhÊt mét c¸ch truyÒn tham sè: TruyÒn theo tham trÞ. Tõ C++3.0 Biªn so¹n: NguyÔn M ¹nh Cêng Trang 1 1
  12. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh trë lªn, cho phÐp sö dông c¶ hai c¸ch truyÒn tham sè trong c¸c ch¬ng tr×nh viÕt díi d¹ng c¸c file .CPP. XÐt tr êng hîp ta cã c¸c biÕn th«ng th êng (kh«ng ph¶i lµ biÕn con trá) - NÕu biÕn ®îc truyÒn díi d¹ng th«ng th êng th× c¸ch truyÒn ®ã lµ truyÒn theo tham trÞ. - NÕu ta kh«ng truyÒn biÕn vµo hµm mµ thay vµo ®ã, ta truyÒn ®Þa chØ cña biÕn vµo th× ®ã lµ c¸ch truyÒn tham chiÕu. VD: int a=3, b=5; Ham (&a, b); Khi ®ã biÕn a ®îc truyÒn vµo hµm díi d¹ng tham chiÕu; biÕn b ®îc truyÒn vµo hµm díi d¹ng tham trÞ. XÐt tr êng hîp ta cã c¸c biÕn con trá. V× b¶n th©n con trá th êng chøa ®Þa chØ cña biÕn nµo ®ã (mµ nã trá tíi) nªn khi truyÒn con trá vµo hµm th× mÆc nhiªn ®· lµ truyÒn theo d¹ng tham chiÕu. VD: int a, *p; a = 5; p = & a; Ham(p); Khi ®ã biÕn p ®îc truyÒn vµo hµm nhng thùc chÊt lµ ta ®· chuyÒn ®Þa chØ cña a vµo hµm. VËy cã thÓ coi ®©y lµ tr êng hîp truyÒn biÕn a vµo hµm díi d¹ng tham chiÕu (tøc sau khi ra khái hµm, biÕn a cã thÓ bÞ thay ®æi gi¸ trÞ). VD1: XÐt hµm sau: int tang(int a) Biªn so¹n: NguyÔn M ¹nh Cêng Trang 1 2
  13. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh { a++; } void main() { int n=1; cout
  14. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh Trong C++, mét hµm cã thÓ gäi ®Õn chÝnh nã. TÝnh chÊt nµy cña hµm gäi lµ tÝnh ®Ö quy. Khi mét hµm gäi ®Õn chÝnh nã, hµm ®îc viÕt theo kiÓu ®Ö quy. VD: XÐt hµm tÝnh n!. Ta cã ®Þnh nghÜa sau: n! = n * (n-1)! . Hµm lÆp: long GT(int n) { long kq=1; if (n==0 || n==1) kq=1; else for (int i=1; i
  15. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh NÕu biÕt 1!=1 th× ta cã thÓ tõ ®ã tÝnh ®îc 2! vµ 3!. VËy thø tù thùc hiÖn c«ng viÖc tÝnh to¸n sÏ lµ: 1!, 2!, 3! (tøc ph¶i gäi hµm tÝnh n! tíi 3 lÇn víi 3 ®èi vµo 1, 2, 3). Mçi lÇn gäi ®Ö quy, ch¬ng tr×nh thùc hiÖn nh sau: - Lu ®Þa chØ cña dßng lÖnh gäi ®Ö quy. - T¹o mét t¹o mét b¶n sao cña hµm, cÊp ph¸t c¸c vïng nhí míi cho c¸c biÕn côc bé, thùc hiÖn b¶n sao nµy. - LÊy ®Þa chØ cña dßng lÖnh gäi ®Ö quy vµ quay vÒ. §Ó râ h¬n ta xem s¬ ®å sau: B¾t ®Çu B¶n sao 1 B¶n sao n Gäi ®Ö Gäi ®Ö … Gäi ®Ö Bá qua lÖnh gäi K Õt t hóc Nh vËy cã bao nhiªu lêi gäi hµm th× cã bÊy nhiªu lÇn kÕt thóc hµm. Trong tr êng hîp kh«ng tån t¹i mét b¶n sao cña hµm mµ t¹i ®ã kh«ng thùc hiÖn hiÖn lêi gäi ®Ö quy th× qu¸ tr×nh ®Ö quy sÏ kh«ng B¾t dõng ®îc (ta gäi lµ ®Ö quyH µm GT(2) v« h¹n). H µm GT(1) ®Çu : Trong vÝ dô vÒ tÝnh n!, víi n=3 vµ c«ng thøc ®Ò quy n! = n * (n- 1)!, s¬ ®å ®Ö quy cã thÓ nh sau: Gäi ®Ö Gäi ®Ö Gäi ®Ö Bá qua lÖnh gäi Biªn so¹n: NguyÔn M ¹nh Cêng Trang 1 K Õt t hóc Ret ur n 1* 2 Ret ur n 1 5 Ret ur n 1* 2* 3
  16. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh u nh îc ®iÓm cña ph¬ng ph¸p ®Ö quy: - Ch¬ng tr×nh ng¾n gäi, dÔ hiÓu. - Qu¸ tr×nh dÞch phøc t¹p. - Nãi chung, tèn nhiÒu kh«ng gian nhí h¬n lÆp. Ph¬ng ph¸p ®Ö quy ®Æc biÖt thÝch hîp víi mét sè bµi to¸n nh duyÖt c©y, ®å thÞ… Tuy nhiªn, nãi chung ta nªn Ýt sö dông ®Ö quy khi viÕt ch¬ng tr×nh do c¸c nhîc ®iÓm trªn. 2. ThiÕt kÕ ch¬ng tr×nh theo kiÓu ®Ö quy. C¸c bµi to¸n ¸p dông gi¶i thuËt ®Ö quy th êng cã ®Æc ®iÓm sau: - Bµi to¸n dÔ dµng gi¶i quyÕt trong mét sè tr êng hîp riªng øng víi c¸c gi¸ trÞ ®Æc biÖt cña tham sè. Trong tr êng hîp nµy, ta cã thÓ gi¶i quyÕt bµi to¸n mµ kh«ng cÇn gäi ®Ö quy. Ta gäi tr êng hîp nµy lµ tr - êng hîp suy biÕn. - Trong tr êng hîp tæng qu¸t, bµi to¸n cã thÓ quy vÒ bµi to¸n cïng d¹ng nhng gi¸ trÞ cña tham sè thay ®æi. Vµ sau mét sè h÷u h¹n bíc biÕn ®æi ®Ö quy, sÏ dÉn tíi tr êng hîp suy biÕn. Gi¶ sö bµi to¸n tÝnh n!, dÔ dµng thÊy: - Víi n=0 hoÆc n = 1 th× n! = 1. Khi ®ã ta kh«ng cÇn gäi ®Ö quy vÉn cã thÓ tÝnh ®îc n!. ta gäi tr êng hîp nµy lµ tr êng hîp suy biÕn. Biªn so¹n: NguyÔn M ¹nh Cêng Trang 1 6
  17. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh - Tr êng hîp n > 1: n! = n* (n-1)!. Tøc lµ ®Ó tÝnh n!, ta cã thÓ quy vÒ bµi to¸n tÝnh (n-1)!. Sau mét sè h÷u h¹n bíc biÕn ®æi, ta cã thÓ quy vÒ bµi to¸n tÝnh 1!. VËy ®©y lµ tr êng hîp tæng qu¸t Nh vËy: - Tr êng hîp suy biÕn: n=0 hoÆc n=1. Khi ®ã: n! = 1; - Tr êng hîp tæng qu¸t: n > 1. Khi ®ã: n! = n* (n-1)!. Ch ¬ng tr×nh ®Ö quy ®îc thiÕt kÕ nh sau: Bíc 1: X¸c ®Þnh c¸c tr êng hîp suy biÕn – tæng qu¸t - X¸c ®Þnh tr êng hîp suy biÕn: gi¸ trÞ cña tham sè, c«ng thøc ®Ó tÝnh to¸n trong tr êng hîp nµy. - X¸c ®Þnh tr êng hîp tæng qu¸t: gi¸ trÞ cña tham sè, c«ng thøc ®Ó tÝnh to¸n trong tr êng hîp nµy. Bíc 2: ViÕt khung ch¬ng tr×nh: if (suy biÕn) C«ng thøc trong tr êng hîp suy biÕn. else C«ng thøc trong tr êng hîp tæng qu¸t. VD1: ThiÕt kÕ hµm ®Ö quy tÝnh n!. Bíc 1: - Suy biÕn : n=0 hoÆc n = 1; C«ng thøc n! = 1; - Tæng qu¸t: n kh¸c 0 vµ n kh¸c 1; C«ng thøc n! = n* (n-1)!. Bíc 2: Biªn so¹n: NguyÔn M ¹nh Cêng Trang 1 7
  18. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh if (n= = 0 | | n= = 1) return 1; else return n * GT(n- 1); Sau khi thiÕt kÕ, viÖc lËp hµm ®Ö quy trë lªn rÊt ®¬n gi¶n. VD2 . D·y sè Catalan ®îc ph¸t biÓu ®Ö quy nh sau: C 1 = 1; n −1 Cn = ∑C C i =1 i n −i H·y x©y dùng hµm ®Ö quy t×m sè CataLan thø n. Hµm ®Ö quy ®îc thiÕt kÕ nh sau: Bíc 1: - Suy biÕn: n = 1; C«ng thøc suy biÕn: Cn = 1; n −1 - Kh«ng suy biÕn: n kh¸c 1; c«ng thøc tæng qu¸t: Cn = ∑C C i =1 i n −i Bíc 2: if (n = = 1) return 1; else { int C =0; for (int i=1; i
  19. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh { if (n==1) return 1; else { int C=0; for (int i=1; i2). Víi c¸c d·y truy håi, ta hoµn toµn cã thÓ dïng c¸c thuËt to¸n lÆp ®Ó tÝnh. Tuy nhiªn c¸c gi¶i thuËt ®Ö quy th êng ®îc ¸p dông rÊt hiÖu qu¶ trªn c¸c d·y truy håi . 4. Mét sè vÝ dô vÒ ®Ö quy VD1: USCLN cña hai sè nguyªn a, b ®îc ®Þnh nghÜa nh sau: Biªn so¹n: NguyÔn M ¹nh Cêng Trang 1 9
  20. §Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh USCLN(a, b) = a nÕu b =0 = USCLN(b, a%b) nÕu b kh¸c 0. ViÕt hµm lÆp vµ ®Ö quy ®Ó tÝnh USCLN cña hai sè nguyªn a, b. Hµm lÆp: int USCLN_Lap(int a, int b) { int Sodu; while (y !=0) { Sodu = a%b; a = b; b = Sodu; } return a; } Hµm ®Ö quy: Bíc 1: - Suy biÕn : b=0; c«ng thøc suy biÕn: USCLN(a, b) = b; - Kh«ng suy biÕn: b kh¸c 0; c«ng thøc tæng qu¸t: USCLN (a, b) = USCLN(b, a%b); Bíc 2: if (b==0) return a; else return USCLN(b, a%b) LËp tr×nh: Int USCLN_DQ(int a, int b) { if (b==0) Biªn so¹n: NguyÔn M ¹nh Cêng Trang 2 0
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2